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. */
56 #include "langhooks.h"
58 static void encode PARAMS ((HOST_WIDE_INT *,
59 unsigned HOST_WIDE_INT,
61 static void decode PARAMS ((HOST_WIDE_INT *,
62 unsigned HOST_WIDE_INT *,
64 static tree negate_expr PARAMS ((tree));
65 static tree split_tree PARAMS ((tree, enum tree_code, tree *, tree *,
67 static tree associate_trees PARAMS ((tree, tree, enum tree_code, tree));
68 static tree int_const_binop PARAMS ((enum tree_code, tree, tree, int));
69 static tree const_binop PARAMS ((enum tree_code, tree, tree, int));
70 static hashval_t size_htab_hash PARAMS ((const void *));
71 static int size_htab_eq PARAMS ((const void *, const void *));
72 static tree fold_convert PARAMS ((tree, tree));
73 static enum tree_code invert_tree_comparison PARAMS ((enum tree_code));
74 static enum tree_code swap_tree_comparison PARAMS ((enum tree_code));
75 static int comparison_to_compcode PARAMS ((enum tree_code));
76 static enum tree_code compcode_to_comparison PARAMS ((int));
77 static int truth_value_p PARAMS ((enum tree_code));
78 static int operand_equal_for_comparison_p PARAMS ((tree, tree, tree));
79 static int twoval_comparison_p PARAMS ((tree, tree *, tree *, int *));
80 static tree eval_subst PARAMS ((tree, tree, tree, tree, tree));
81 static tree omit_one_operand PARAMS ((tree, tree, tree));
82 static tree pedantic_omit_one_operand PARAMS ((tree, tree, tree));
83 static tree distribute_bit_expr PARAMS ((enum tree_code, tree, tree, tree));
84 static tree make_bit_field_ref PARAMS ((tree, tree, int, int, int));
85 static tree optimize_bit_field_compare PARAMS ((enum tree_code, tree,
87 static tree decode_field_reference PARAMS ((tree, HOST_WIDE_INT *,
89 enum machine_mode *, int *,
90 int *, tree *, tree *));
91 static int all_ones_mask_p PARAMS ((tree, int));
92 static tree sign_bit_p PARAMS ((tree, tree));
93 static int simple_operand_p PARAMS ((tree));
94 static tree range_binop PARAMS ((enum tree_code, tree, tree, int,
96 static tree make_range PARAMS ((tree, int *, tree *, tree *));
97 static tree build_range_check PARAMS ((tree, tree, int, tree, tree));
98 static int merge_ranges PARAMS ((int *, tree *, tree *, int, tree, tree,
100 static tree fold_range_test PARAMS ((tree));
101 static tree unextend PARAMS ((tree, int, int, tree));
102 static tree fold_truthop PARAMS ((enum tree_code, tree, tree, tree));
103 static tree optimize_minmax_comparison PARAMS ((tree));
104 static tree extract_muldiv PARAMS ((tree, tree, enum tree_code, tree));
105 static tree strip_compound_expr PARAMS ((tree, tree));
106 static int multiple_of_p PARAMS ((tree, tree, tree));
107 static tree constant_boolean_node PARAMS ((int, tree));
108 static int count_cond PARAMS ((tree, int));
109 static tree fold_binary_op_with_conditional_arg
110 PARAMS ((enum tree_code, tree, tree, tree, int));
111 static bool fold_real_zero_addition_p PARAMS ((tree, tree, int));
113 /* The following constants represent a bit based encoding of GCC's
114 comparison operators. This encoding simplifies transformations
115 on relational comparison operators, such as AND and OR. */
116 #define COMPCODE_FALSE 0
117 #define COMPCODE_LT 1
118 #define COMPCODE_EQ 2
119 #define COMPCODE_LE 3
120 #define COMPCODE_GT 4
121 #define COMPCODE_NE 5
122 #define COMPCODE_GE 6
123 #define COMPCODE_TRUE 7
125 /* We know that A1 + B1 = SUM1, using 2's complement arithmetic and ignoring
126 overflow. Suppose A, B and SUM have the same respective signs as A1, B1,
127 and SUM1. Then this yields nonzero if overflow occurred during the
130 Overflow occurs if A and B have the same sign, but A and SUM differ in
131 sign. Use `^' to test whether signs differ, and `< 0' to isolate the
133 #define OVERFLOW_SUM_SIGN(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)
135 /* To do constant folding on INTEGER_CST nodes requires two-word arithmetic.
136 We do that by representing the two-word integer in 4 words, with only
137 HOST_BITS_PER_WIDE_INT / 2 bits stored in each word, as a positive
138 number. The value of the word is LOWPART + HIGHPART * BASE. */
141 ((x) & (((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)) - 1))
142 #define HIGHPART(x) \
143 ((unsigned HOST_WIDE_INT) (x) >> HOST_BITS_PER_WIDE_INT / 2)
144 #define BASE ((unsigned HOST_WIDE_INT) 1 << HOST_BITS_PER_WIDE_INT / 2)
146 /* Unpack a two-word integer into 4 words.
147 LOW and HI are the integer, as two `HOST_WIDE_INT' pieces.
148 WORDS points to the array of HOST_WIDE_INTs. */
151 encode (words, low, hi)
152 HOST_WIDE_INT *words;
153 unsigned HOST_WIDE_INT low;
156 words[0] = LOWPART (low);
157 words[1] = HIGHPART (low);
158 words[2] = LOWPART (hi);
159 words[3] = HIGHPART (hi);
162 /* Pack an array of 4 words into a two-word integer.
163 WORDS points to the array of words.
164 The integer is stored into *LOW and *HI as two `HOST_WIDE_INT' pieces. */
167 decode (words, low, hi)
168 HOST_WIDE_INT *words;
169 unsigned HOST_WIDE_INT *low;
172 *low = words[0] + words[1] * BASE;
173 *hi = words[2] + words[3] * BASE;
176 /* Make the integer constant T valid for its type by setting to 0 or 1 all
177 the bits in the constant that don't belong in the type.
179 Return 1 if a signed overflow occurs, 0 otherwise. If OVERFLOW is
180 nonzero, a signed overflow has already occurred in calculating T, so
183 Make the real constant T valid for its type by calling CHECK_FLOAT_VALUE,
187 force_fit_type (t, overflow)
191 unsigned HOST_WIDE_INT low;
195 if (TREE_CODE (t) == REAL_CST)
197 #ifdef CHECK_FLOAT_VALUE
198 CHECK_FLOAT_VALUE (TYPE_MODE (TREE_TYPE (t)), TREE_REAL_CST (t),
204 else if (TREE_CODE (t) != INTEGER_CST)
207 low = TREE_INT_CST_LOW (t);
208 high = TREE_INT_CST_HIGH (t);
210 if (POINTER_TYPE_P (TREE_TYPE (t)))
213 prec = TYPE_PRECISION (TREE_TYPE (t));
215 /* First clear all bits that are beyond the type's precision. */
217 if (prec == 2 * HOST_BITS_PER_WIDE_INT)
219 else if (prec > HOST_BITS_PER_WIDE_INT)
220 TREE_INT_CST_HIGH (t)
221 &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
224 TREE_INT_CST_HIGH (t) = 0;
225 if (prec < HOST_BITS_PER_WIDE_INT)
226 TREE_INT_CST_LOW (t) &= ~((unsigned HOST_WIDE_INT) (-1) << prec);
229 /* Unsigned types do not suffer sign extension or overflow unless they
231 if (TREE_UNSIGNED (TREE_TYPE (t))
232 && ! (TREE_CODE (TREE_TYPE (t)) == INTEGER_TYPE
233 && TYPE_IS_SIZETYPE (TREE_TYPE (t))))
236 /* If the value's sign bit is set, extend the sign. */
237 if (prec != 2 * HOST_BITS_PER_WIDE_INT
238 && (prec > HOST_BITS_PER_WIDE_INT
239 ? 0 != (TREE_INT_CST_HIGH (t)
241 << (prec - HOST_BITS_PER_WIDE_INT - 1)))
242 : 0 != (TREE_INT_CST_LOW (t)
243 & ((unsigned HOST_WIDE_INT) 1 << (prec - 1)))))
245 /* Value is negative:
246 set to 1 all the bits that are outside this type's precision. */
247 if (prec > HOST_BITS_PER_WIDE_INT)
248 TREE_INT_CST_HIGH (t)
249 |= ((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
252 TREE_INT_CST_HIGH (t) = -1;
253 if (prec < HOST_BITS_PER_WIDE_INT)
254 TREE_INT_CST_LOW (t) |= ((unsigned HOST_WIDE_INT) (-1) << prec);
258 /* Return nonzero if signed overflow occurred. */
260 ((overflow | (low ^ TREE_INT_CST_LOW (t)) | (high ^ TREE_INT_CST_HIGH (t)))
264 /* Add two doubleword integers with doubleword result.
265 Each argument is given as two `HOST_WIDE_INT' pieces.
266 One argument is L1 and H1; the other, L2 and H2.
267 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
270 add_double (l1, h1, l2, h2, lv, hv)
271 unsigned HOST_WIDE_INT l1, l2;
272 HOST_WIDE_INT h1, h2;
273 unsigned HOST_WIDE_INT *lv;
276 unsigned HOST_WIDE_INT l;
280 h = h1 + h2 + (l < l1);
284 return OVERFLOW_SUM_SIGN (h1, h2, h);
287 /* Negate a doubleword integer with doubleword result.
288 Return nonzero if the operation overflows, assuming it's signed.
289 The argument is given as two `HOST_WIDE_INT' pieces in L1 and H1.
290 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
293 neg_double (l1, h1, lv, hv)
294 unsigned HOST_WIDE_INT l1;
296 unsigned HOST_WIDE_INT *lv;
303 return (*hv & h1) < 0;
313 /* Multiply two doubleword integers with doubleword result.
314 Return nonzero if the operation overflows, assuming it's signed.
315 Each argument is given as two `HOST_WIDE_INT' pieces.
316 One argument is L1 and H1; the other, L2 and H2.
317 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
320 mul_double (l1, h1, l2, h2, lv, hv)
321 unsigned HOST_WIDE_INT l1, l2;
322 HOST_WIDE_INT h1, h2;
323 unsigned HOST_WIDE_INT *lv;
326 HOST_WIDE_INT arg1[4];
327 HOST_WIDE_INT arg2[4];
328 HOST_WIDE_INT prod[4 * 2];
329 unsigned HOST_WIDE_INT carry;
331 unsigned HOST_WIDE_INT toplow, neglow;
332 HOST_WIDE_INT tophigh, neghigh;
334 encode (arg1, l1, h1);
335 encode (arg2, l2, h2);
337 memset ((char *) prod, 0, sizeof prod);
339 for (i = 0; i < 4; i++)
342 for (j = 0; j < 4; j++)
345 /* This product is <= 0xFFFE0001, the sum <= 0xFFFF0000. */
346 carry += arg1[i] * arg2[j];
347 /* Since prod[p] < 0xFFFF, this sum <= 0xFFFFFFFF. */
349 prod[k] = LOWPART (carry);
350 carry = HIGHPART (carry);
355 decode (prod, lv, hv); /* This ignores prod[4] through prod[4*2-1] */
357 /* Check for overflow by calculating the top half of the answer in full;
358 it should agree with the low half's sign bit. */
359 decode (prod + 4, &toplow, &tophigh);
362 neg_double (l2, h2, &neglow, &neghigh);
363 add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
367 neg_double (l1, h1, &neglow, &neghigh);
368 add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
370 return (*hv < 0 ? ~(toplow & tophigh) : toplow | tophigh) != 0;
373 /* Shift the doubleword integer in L1, H1 left by COUNT places
374 keeping only PREC bits of result.
375 Shift right if COUNT is negative.
376 ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
377 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
380 lshift_double (l1, h1, count, prec, lv, hv, arith)
381 unsigned HOST_WIDE_INT l1;
382 HOST_WIDE_INT h1, count;
384 unsigned HOST_WIDE_INT *lv;
388 unsigned HOST_WIDE_INT signmask;
392 rshift_double (l1, h1, -count, prec, lv, hv, arith);
396 #ifdef SHIFT_COUNT_TRUNCATED
397 if (SHIFT_COUNT_TRUNCATED)
401 if (count >= 2 * HOST_BITS_PER_WIDE_INT)
403 /* Shifting by the host word size is undefined according to the
404 ANSI standard, so we must handle this as a special case. */
408 else if (count >= HOST_BITS_PER_WIDE_INT)
410 *hv = l1 << (count - HOST_BITS_PER_WIDE_INT);
415 *hv = (((unsigned HOST_WIDE_INT) h1 << count)
416 | (l1 >> (HOST_BITS_PER_WIDE_INT - count - 1) >> 1));
420 /* Sign extend all bits that are beyond the precision. */
422 signmask = -((prec > HOST_BITS_PER_WIDE_INT
423 ? ((unsigned HOST_WIDE_INT) *hv
424 >> (prec - HOST_BITS_PER_WIDE_INT - 1))
425 : (*lv >> (prec - 1))) & 1);
427 if (prec >= 2 * HOST_BITS_PER_WIDE_INT)
429 else if (prec >= HOST_BITS_PER_WIDE_INT)
431 *hv &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
432 *hv |= signmask << (prec - HOST_BITS_PER_WIDE_INT);
437 *lv &= ~((unsigned HOST_WIDE_INT) (-1) << prec);
438 *lv |= signmask << prec;
442 /* Shift the doubleword integer in L1, H1 right by COUNT places
443 keeping only PREC bits of result. COUNT must be positive.
444 ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
445 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
448 rshift_double (l1, h1, count, prec, lv, hv, arith)
449 unsigned HOST_WIDE_INT l1;
450 HOST_WIDE_INT h1, count;
452 unsigned HOST_WIDE_INT *lv;
456 unsigned HOST_WIDE_INT signmask;
459 ? -((unsigned HOST_WIDE_INT) h1 >> (HOST_BITS_PER_WIDE_INT - 1))
462 #ifdef SHIFT_COUNT_TRUNCATED
463 if (SHIFT_COUNT_TRUNCATED)
467 if (count >= 2 * HOST_BITS_PER_WIDE_INT)
469 /* Shifting by the host word size is undefined according to the
470 ANSI standard, so we must handle this as a special case. */
474 else if (count >= HOST_BITS_PER_WIDE_INT)
477 *lv = (unsigned HOST_WIDE_INT) h1 >> (count - HOST_BITS_PER_WIDE_INT);
481 *hv = (unsigned HOST_WIDE_INT) h1 >> count;
483 | ((unsigned HOST_WIDE_INT) h1 << (HOST_BITS_PER_WIDE_INT - count - 1) << 1));
486 /* Zero / sign extend all bits that are beyond the precision. */
488 if (count >= (HOST_WIDE_INT)prec)
493 else if ((prec - count) >= 2 * HOST_BITS_PER_WIDE_INT)
495 else if ((prec - count) >= HOST_BITS_PER_WIDE_INT)
497 *hv &= ~((HOST_WIDE_INT) (-1) << (prec - count - HOST_BITS_PER_WIDE_INT));
498 *hv |= signmask << (prec - count - HOST_BITS_PER_WIDE_INT);
503 *lv &= ~((unsigned HOST_WIDE_INT) (-1) << (prec - count));
504 *lv |= signmask << (prec - count);
508 /* Rotate the doubleword integer in L1, H1 left by COUNT places
509 keeping only PREC bits of result.
510 Rotate right if COUNT is negative.
511 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
514 lrotate_double (l1, h1, count, prec, lv, hv)
515 unsigned HOST_WIDE_INT l1;
516 HOST_WIDE_INT h1, count;
518 unsigned HOST_WIDE_INT *lv;
521 unsigned HOST_WIDE_INT s1l, s2l;
522 HOST_WIDE_INT s1h, s2h;
528 lshift_double (l1, h1, count, prec, &s1l, &s1h, 0);
529 rshift_double (l1, h1, prec - count, prec, &s2l, &s2h, 0);
534 /* Rotate the doubleword integer in L1, H1 left by COUNT places
535 keeping only PREC bits of result. COUNT must be positive.
536 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
539 rrotate_double (l1, h1, count, prec, lv, hv)
540 unsigned HOST_WIDE_INT l1;
541 HOST_WIDE_INT h1, count;
543 unsigned HOST_WIDE_INT *lv;
546 unsigned HOST_WIDE_INT s1l, s2l;
547 HOST_WIDE_INT s1h, s2h;
553 rshift_double (l1, h1, count, prec, &s1l, &s1h, 0);
554 lshift_double (l1, h1, prec - count, prec, &s2l, &s2h, 0);
559 /* Divide doubleword integer LNUM, HNUM by doubleword integer LDEN, HDEN
560 for a quotient (stored in *LQUO, *HQUO) and remainder (in *LREM, *HREM).
561 CODE is a tree code for a kind of division, one of
562 TRUNC_DIV_EXPR, FLOOR_DIV_EXPR, CEIL_DIV_EXPR, ROUND_DIV_EXPR
564 It controls how the quotient is rounded to an integer.
565 Return nonzero if the operation overflows.
566 UNS nonzero says do unsigned division. */
569 div_and_round_double (code, uns,
570 lnum_orig, hnum_orig, lden_orig, hden_orig,
571 lquo, hquo, lrem, hrem)
574 unsigned HOST_WIDE_INT lnum_orig; /* num == numerator == dividend */
575 HOST_WIDE_INT hnum_orig;
576 unsigned HOST_WIDE_INT lden_orig; /* den == denominator == divisor */
577 HOST_WIDE_INT hden_orig;
578 unsigned HOST_WIDE_INT *lquo, *lrem;
579 HOST_WIDE_INT *hquo, *hrem;
582 HOST_WIDE_INT num[4 + 1]; /* extra element for scaling. */
583 HOST_WIDE_INT den[4], quo[4];
585 unsigned HOST_WIDE_INT work;
586 unsigned HOST_WIDE_INT carry = 0;
587 unsigned HOST_WIDE_INT lnum = lnum_orig;
588 HOST_WIDE_INT hnum = hnum_orig;
589 unsigned HOST_WIDE_INT lden = lden_orig;
590 HOST_WIDE_INT hden = hden_orig;
593 if (hden == 0 && lden == 0)
594 overflow = 1, lden = 1;
596 /* calculate quotient sign and convert operands to unsigned. */
602 /* (minimum integer) / (-1) is the only overflow case. */
603 if (neg_double (lnum, hnum, &lnum, &hnum)
604 && ((HOST_WIDE_INT) lden & hden) == -1)
610 neg_double (lden, hden, &lden, &hden);
614 if (hnum == 0 && hden == 0)
615 { /* single precision */
617 /* This unsigned division rounds toward zero. */
623 { /* trivial case: dividend < divisor */
624 /* hden != 0 already checked. */
631 memset ((char *) quo, 0, sizeof quo);
633 memset ((char *) num, 0, sizeof num); /* to zero 9th element */
634 memset ((char *) den, 0, sizeof den);
636 encode (num, lnum, hnum);
637 encode (den, lden, hden);
639 /* Special code for when the divisor < BASE. */
640 if (hden == 0 && lden < (unsigned HOST_WIDE_INT) BASE)
642 /* hnum != 0 already checked. */
643 for (i = 4 - 1; i >= 0; i--)
645 work = num[i] + carry * BASE;
646 quo[i] = work / lden;
652 /* Full double precision division,
653 with thanks to Don Knuth's "Seminumerical Algorithms". */
654 int num_hi_sig, den_hi_sig;
655 unsigned HOST_WIDE_INT quo_est, scale;
657 /* Find the highest non-zero divisor digit. */
658 for (i = 4 - 1;; i--)
665 /* Insure that the first digit of the divisor is at least BASE/2.
666 This is required by the quotient digit estimation algorithm. */
668 scale = BASE / (den[den_hi_sig] + 1);
670 { /* scale divisor and dividend */
672 for (i = 0; i <= 4 - 1; i++)
674 work = (num[i] * scale) + carry;
675 num[i] = LOWPART (work);
676 carry = HIGHPART (work);
681 for (i = 0; i <= 4 - 1; i++)
683 work = (den[i] * scale) + carry;
684 den[i] = LOWPART (work);
685 carry = HIGHPART (work);
686 if (den[i] != 0) den_hi_sig = i;
693 for (i = num_hi_sig - den_hi_sig - 1; i >= 0; i--)
695 /* Guess the next quotient digit, quo_est, by dividing the first
696 two remaining dividend digits by the high order quotient digit.
697 quo_est is never low and is at most 2 high. */
698 unsigned HOST_WIDE_INT tmp;
700 num_hi_sig = i + den_hi_sig + 1;
701 work = num[num_hi_sig] * BASE + num[num_hi_sig - 1];
702 if (num[num_hi_sig] != den[den_hi_sig])
703 quo_est = work / den[den_hi_sig];
707 /* Refine quo_est so it's usually correct, and at most one high. */
708 tmp = work - quo_est * den[den_hi_sig];
710 && (den[den_hi_sig - 1] * quo_est
711 > (tmp * BASE + num[num_hi_sig - 2])))
714 /* Try QUO_EST as the quotient digit, by multiplying the
715 divisor by QUO_EST and subtracting from the remaining dividend.
716 Keep in mind that QUO_EST is the I - 1st digit. */
719 for (j = 0; j <= den_hi_sig; j++)
721 work = quo_est * den[j] + carry;
722 carry = HIGHPART (work);
723 work = num[i + j] - LOWPART (work);
724 num[i + j] = LOWPART (work);
725 carry += HIGHPART (work) != 0;
728 /* If quo_est was high by one, then num[i] went negative and
729 we need to correct things. */
730 if (num[num_hi_sig] < (HOST_WIDE_INT) carry)
733 carry = 0; /* add divisor back in */
734 for (j = 0; j <= den_hi_sig; j++)
736 work = num[i + j] + den[j] + carry;
737 carry = HIGHPART (work);
738 num[i + j] = LOWPART (work);
741 num [num_hi_sig] += carry;
744 /* Store the quotient digit. */
749 decode (quo, lquo, hquo);
752 /* if result is negative, make it so. */
754 neg_double (*lquo, *hquo, lquo, hquo);
756 /* compute trial remainder: rem = num - (quo * den) */
757 mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
758 neg_double (*lrem, *hrem, lrem, hrem);
759 add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
764 case TRUNC_MOD_EXPR: /* round toward zero */
765 case EXACT_DIV_EXPR: /* for this one, it shouldn't matter */
769 case FLOOR_MOD_EXPR: /* round toward negative infinity */
770 if (quo_neg && (*lrem != 0 || *hrem != 0)) /* ratio < 0 && rem != 0 */
773 add_double (*lquo, *hquo, (HOST_WIDE_INT) -1, (HOST_WIDE_INT) -1,
781 case CEIL_MOD_EXPR: /* round toward positive infinity */
782 if (!quo_neg && (*lrem != 0 || *hrem != 0)) /* ratio > 0 && rem != 0 */
784 add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
792 case ROUND_MOD_EXPR: /* round to closest integer */
794 unsigned HOST_WIDE_INT labs_rem = *lrem;
795 HOST_WIDE_INT habs_rem = *hrem;
796 unsigned HOST_WIDE_INT labs_den = lden, ltwice;
797 HOST_WIDE_INT habs_den = hden, htwice;
799 /* Get absolute values */
801 neg_double (*lrem, *hrem, &labs_rem, &habs_rem);
803 neg_double (lden, hden, &labs_den, &habs_den);
805 /* If (2 * abs (lrem) >= abs (lden)) */
806 mul_double ((HOST_WIDE_INT) 2, (HOST_WIDE_INT) 0,
807 labs_rem, habs_rem, <wice, &htwice);
809 if (((unsigned HOST_WIDE_INT) habs_den
810 < (unsigned HOST_WIDE_INT) htwice)
811 || (((unsigned HOST_WIDE_INT) habs_den
812 == (unsigned HOST_WIDE_INT) htwice)
813 && (labs_den < ltwice)))
817 add_double (*lquo, *hquo,
818 (HOST_WIDE_INT) -1, (HOST_WIDE_INT) -1, lquo, hquo);
821 add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
833 /* compute true remainder: rem = num - (quo * den) */
834 mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
835 neg_double (*lrem, *hrem, lrem, hrem);
836 add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
840 /* Given T, an expression, return the negation of T. Allow for T to be
841 null, in which case return null. */
853 type = TREE_TYPE (t);
856 switch (TREE_CODE (t))
860 if (! TREE_UNSIGNED (type)
861 && 0 != (tem = fold (build1 (NEGATE_EXPR, type, t)))
862 && ! TREE_OVERFLOW (tem))
867 return convert (type, TREE_OPERAND (t, 0));
870 /* - (A - B) -> B - A */
871 if (! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations)
872 return convert (type,
873 fold (build (MINUS_EXPR, TREE_TYPE (t),
875 TREE_OPERAND (t, 0))));
882 return convert (type, fold (build1 (NEGATE_EXPR, TREE_TYPE (t), t)));
885 /* Split a tree IN into a constant, literal and variable parts that could be
886 combined with CODE to make IN. "constant" means an expression with
887 TREE_CONSTANT but that isn't an actual constant. CODE must be a
888 commutative arithmetic operation. Store the constant part into *CONP,
889 the literal in *LITP and return the variable part. If a part isn't
890 present, set it to null. If the tree does not decompose in this way,
891 return the entire tree as the variable part and the other parts as null.
893 If CODE is PLUS_EXPR we also split trees that use MINUS_EXPR. In that
894 case, we negate an operand that was subtracted. Except if it is a
895 literal for which we use *MINUS_LITP instead.
897 If NEGATE_P is true, we are negating all of IN, again except a literal
898 for which we use *MINUS_LITP instead.
900 If IN is itself a literal or constant, return it as appropriate.
902 Note that we do not guarantee that any of the three values will be the
903 same type as IN, but they will have the same signedness and mode. */
906 split_tree (in, code, conp, litp, minus_litp, negate_p)
909 tree *conp, *litp, *minus_litp;
918 /* Strip any conversions that don't change the machine mode or signedness. */
919 STRIP_SIGN_NOPS (in);
921 if (TREE_CODE (in) == INTEGER_CST || TREE_CODE (in) == REAL_CST)
923 else if (TREE_CODE (in) == code
924 || (! FLOAT_TYPE_P (TREE_TYPE (in))
925 /* We can associate addition and subtraction together (even
926 though the C standard doesn't say so) for integers because
927 the value is not affected. For reals, the value might be
928 affected, so we can't. */
929 && ((code == PLUS_EXPR && TREE_CODE (in) == MINUS_EXPR)
930 || (code == MINUS_EXPR && TREE_CODE (in) == PLUS_EXPR))))
932 tree op0 = TREE_OPERAND (in, 0);
933 tree op1 = TREE_OPERAND (in, 1);
934 int neg1_p = TREE_CODE (in) == MINUS_EXPR;
935 int neg_litp_p = 0, neg_conp_p = 0, neg_var_p = 0;
937 /* First see if either of the operands is a literal, then a constant. */
938 if (TREE_CODE (op0) == INTEGER_CST || TREE_CODE (op0) == REAL_CST)
939 *litp = op0, op0 = 0;
940 else if (TREE_CODE (op1) == INTEGER_CST || TREE_CODE (op1) == REAL_CST)
941 *litp = op1, neg_litp_p = neg1_p, op1 = 0;
943 if (op0 != 0 && TREE_CONSTANT (op0))
944 *conp = op0, op0 = 0;
945 else if (op1 != 0 && TREE_CONSTANT (op1))
946 *conp = op1, neg_conp_p = neg1_p, op1 = 0;
948 /* If we haven't dealt with either operand, this is not a case we can
949 decompose. Otherwise, VAR is either of the ones remaining, if any. */
950 if (op0 != 0 && op1 != 0)
955 var = op1, neg_var_p = neg1_p;
957 /* Now do any needed negations. */
959 *minus_litp = *litp, *litp = 0;
961 *conp = negate_expr (*conp);
963 var = negate_expr (var);
965 else if (TREE_CONSTANT (in))
973 *minus_litp = *litp, *litp = 0;
974 else if (*minus_litp)
975 *litp = *minus_litp, *minus_litp = 0;
976 *conp = negate_expr (*conp);
977 var = negate_expr (var);
983 /* Re-associate trees split by the above function. T1 and T2 are either
984 expressions to associate or null. Return the new expression, if any. If
985 we build an operation, do it in TYPE and with CODE. */
988 associate_trees (t1, t2, code, type)
998 /* If either input is CODE, a PLUS_EXPR, or a MINUS_EXPR, don't
999 try to fold this since we will have infinite recursion. But do
1000 deal with any NEGATE_EXPRs. */
1001 if (TREE_CODE (t1) == code || TREE_CODE (t2) == code
1002 || TREE_CODE (t1) == MINUS_EXPR || TREE_CODE (t2) == MINUS_EXPR)
1004 if (TREE_CODE (t1) == NEGATE_EXPR)
1005 return build (MINUS_EXPR, type, convert (type, t2),
1006 convert (type, TREE_OPERAND (t1, 0)));
1007 else if (TREE_CODE (t2) == NEGATE_EXPR)
1008 return build (MINUS_EXPR, type, convert (type, t1),
1009 convert (type, TREE_OPERAND (t2, 0)));
1011 return build (code, type, convert (type, t1), convert (type, t2));
1014 return fold (build (code, type, convert (type, t1), convert (type, t2)));
1017 /* Combine two integer constants ARG1 and ARG2 under operation CODE
1018 to produce a new constant.
1020 If NOTRUNC is nonzero, do not truncate the result to fit the data type. */
1023 int_const_binop (code, arg1, arg2, notrunc)
1024 enum tree_code code;
1028 unsigned HOST_WIDE_INT int1l, int2l;
1029 HOST_WIDE_INT int1h, int2h;
1030 unsigned HOST_WIDE_INT low;
1032 unsigned HOST_WIDE_INT garbagel;
1033 HOST_WIDE_INT garbageh;
1035 tree type = TREE_TYPE (arg1);
1036 int uns = TREE_UNSIGNED (type);
1038 = (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type));
1040 int no_overflow = 0;
1042 int1l = TREE_INT_CST_LOW (arg1);
1043 int1h = TREE_INT_CST_HIGH (arg1);
1044 int2l = TREE_INT_CST_LOW (arg2);
1045 int2h = TREE_INT_CST_HIGH (arg2);
1050 low = int1l | int2l, hi = int1h | int2h;
1054 low = int1l ^ int2l, hi = int1h ^ int2h;
1058 low = int1l & int2l, hi = int1h & int2h;
1061 case BIT_ANDTC_EXPR:
1062 low = int1l & ~int2l, hi = int1h & ~int2h;
1068 /* It's unclear from the C standard whether shifts can overflow.
1069 The following code ignores overflow; perhaps a C standard
1070 interpretation ruling is needed. */
1071 lshift_double (int1l, int1h, int2l, TYPE_PRECISION (type),
1079 lrotate_double (int1l, int1h, int2l, TYPE_PRECISION (type),
1084 overflow = add_double (int1l, int1h, int2l, int2h, &low, &hi);
1088 neg_double (int2l, int2h, &low, &hi);
1089 add_double (int1l, int1h, low, hi, &low, &hi);
1090 overflow = OVERFLOW_SUM_SIGN (hi, int2h, int1h);
1094 overflow = mul_double (int1l, int1h, int2l, int2h, &low, &hi);
1097 case TRUNC_DIV_EXPR:
1098 case FLOOR_DIV_EXPR: case CEIL_DIV_EXPR:
1099 case EXACT_DIV_EXPR:
1100 /* This is a shortcut for a common special case. */
1101 if (int2h == 0 && (HOST_WIDE_INT) int2l > 0
1102 && ! TREE_CONSTANT_OVERFLOW (arg1)
1103 && ! TREE_CONSTANT_OVERFLOW (arg2)
1104 && int1h == 0 && (HOST_WIDE_INT) int1l >= 0)
1106 if (code == CEIL_DIV_EXPR)
1109 low = int1l / int2l, hi = 0;
1113 /* ... fall through ... */
1115 case ROUND_DIV_EXPR:
1116 if (int2h == 0 && int2l == 1)
1118 low = int1l, hi = int1h;
1121 if (int1l == int2l && int1h == int2h
1122 && ! (int1l == 0 && int1h == 0))
1127 overflow = div_and_round_double (code, uns, int1l, int1h, int2l, int2h,
1128 &low, &hi, &garbagel, &garbageh);
1131 case TRUNC_MOD_EXPR:
1132 case FLOOR_MOD_EXPR: case CEIL_MOD_EXPR:
1133 /* This is a shortcut for a common special case. */
1134 if (int2h == 0 && (HOST_WIDE_INT) int2l > 0
1135 && ! TREE_CONSTANT_OVERFLOW (arg1)
1136 && ! TREE_CONSTANT_OVERFLOW (arg2)
1137 && int1h == 0 && (HOST_WIDE_INT) int1l >= 0)
1139 if (code == CEIL_MOD_EXPR)
1141 low = int1l % int2l, hi = 0;
1145 /* ... fall through ... */
1147 case ROUND_MOD_EXPR:
1148 overflow = div_and_round_double (code, uns,
1149 int1l, int1h, int2l, int2h,
1150 &garbagel, &garbageh, &low, &hi);
1156 low = (((unsigned HOST_WIDE_INT) int1h
1157 < (unsigned HOST_WIDE_INT) int2h)
1158 || (((unsigned HOST_WIDE_INT) int1h
1159 == (unsigned HOST_WIDE_INT) int2h)
1162 low = (int1h < int2h
1163 || (int1h == int2h && int1l < int2l));
1165 if (low == (code == MIN_EXPR))
1166 low = int1l, hi = int1h;
1168 low = int2l, hi = int2h;
1175 /* If this is for a sizetype, can be represented as one (signed)
1176 HOST_WIDE_INT word, and doesn't overflow, use size_int since it caches
1179 && ((hi == 0 && (HOST_WIDE_INT) low >= 0)
1180 || (hi == -1 && (HOST_WIDE_INT) low < 0))
1181 && overflow == 0 && ! TREE_OVERFLOW (arg1) && ! TREE_OVERFLOW (arg2))
1182 return size_int_type_wide (low, type);
1185 t = build_int_2 (low, hi);
1186 TREE_TYPE (t) = TREE_TYPE (arg1);
1191 ? (!uns || is_sizetype) && overflow
1192 : (force_fit_type (t, (!uns || is_sizetype) && overflow)
1194 | TREE_OVERFLOW (arg1)
1195 | TREE_OVERFLOW (arg2));
1197 /* If we're doing a size calculation, unsigned arithmetic does overflow.
1198 So check if force_fit_type truncated the value. */
1200 && ! TREE_OVERFLOW (t)
1201 && (TREE_INT_CST_HIGH (t) != hi
1202 || TREE_INT_CST_LOW (t) != low))
1203 TREE_OVERFLOW (t) = 1;
1205 TREE_CONSTANT_OVERFLOW (t) = (TREE_OVERFLOW (t)
1206 | TREE_CONSTANT_OVERFLOW (arg1)
1207 | TREE_CONSTANT_OVERFLOW (arg2));
1211 /* Combine two constants ARG1 and ARG2 under operation CODE to produce a new
1212 constant. We assume ARG1 and ARG2 have the same data type, or at least
1213 are the same kind of constant and the same machine mode.
1215 If NOTRUNC is nonzero, do not truncate the result to fit the data type. */
1218 const_binop (code, arg1, arg2, notrunc)
1219 enum tree_code code;
1226 if (TREE_CODE (arg1) == INTEGER_CST)
1227 return int_const_binop (code, arg1, arg2, notrunc);
1229 if (TREE_CODE (arg1) == REAL_CST)
1233 REAL_VALUE_TYPE value;
1236 d1 = TREE_REAL_CST (arg1);
1237 d2 = TREE_REAL_CST (arg2);
1239 /* If either operand is a NaN, just return it. Otherwise, set up
1240 for floating-point trap; we return an overflow. */
1241 if (REAL_VALUE_ISNAN (d1))
1243 else if (REAL_VALUE_ISNAN (d2))
1246 REAL_ARITHMETIC (value, code, d1, d2);
1248 t = build_real (TREE_TYPE (arg1),
1249 real_value_truncate (TYPE_MODE (TREE_TYPE (arg1)),
1253 = (force_fit_type (t, 0)
1254 | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2));
1255 TREE_CONSTANT_OVERFLOW (t)
1257 | TREE_CONSTANT_OVERFLOW (arg1)
1258 | TREE_CONSTANT_OVERFLOW (arg2);
1261 if (TREE_CODE (arg1) == COMPLEX_CST)
1263 tree type = TREE_TYPE (arg1);
1264 tree r1 = TREE_REALPART (arg1);
1265 tree i1 = TREE_IMAGPART (arg1);
1266 tree r2 = TREE_REALPART (arg2);
1267 tree i2 = TREE_IMAGPART (arg2);
1273 t = build_complex (type,
1274 const_binop (PLUS_EXPR, r1, r2, notrunc),
1275 const_binop (PLUS_EXPR, i1, i2, notrunc));
1279 t = build_complex (type,
1280 const_binop (MINUS_EXPR, r1, r2, notrunc),
1281 const_binop (MINUS_EXPR, i1, i2, notrunc));
1285 t = build_complex (type,
1286 const_binop (MINUS_EXPR,
1287 const_binop (MULT_EXPR,
1289 const_binop (MULT_EXPR,
1292 const_binop (PLUS_EXPR,
1293 const_binop (MULT_EXPR,
1295 const_binop (MULT_EXPR,
1303 = const_binop (PLUS_EXPR,
1304 const_binop (MULT_EXPR, r2, r2, notrunc),
1305 const_binop (MULT_EXPR, i2, i2, notrunc),
1308 t = build_complex (type,
1310 (INTEGRAL_TYPE_P (TREE_TYPE (r1))
1311 ? TRUNC_DIV_EXPR : RDIV_EXPR,
1312 const_binop (PLUS_EXPR,
1313 const_binop (MULT_EXPR, r1, r2,
1315 const_binop (MULT_EXPR, i1, i2,
1318 magsquared, notrunc),
1320 (INTEGRAL_TYPE_P (TREE_TYPE (r1))
1321 ? TRUNC_DIV_EXPR : RDIV_EXPR,
1322 const_binop (MINUS_EXPR,
1323 const_binop (MULT_EXPR, i1, r2,
1325 const_binop (MULT_EXPR, r1, i2,
1328 magsquared, notrunc));
1340 /* These are the hash table functions for the hash table of INTEGER_CST
1341 nodes of a sizetype. */
1343 /* Return the hash code code X, an INTEGER_CST. */
1351 return (TREE_INT_CST_HIGH (t) ^ TREE_INT_CST_LOW (t)
1352 ^ (hashval_t) ((long) TREE_TYPE (t) >> 3)
1353 ^ (TREE_OVERFLOW (t) << 20));
1356 /* Return non-zero if the value represented by *X (an INTEGER_CST tree node)
1357 is the same as that given by *Y, which is the same. */
1367 return (TREE_INT_CST_HIGH (xt) == TREE_INT_CST_HIGH (yt)
1368 && TREE_INT_CST_LOW (xt) == TREE_INT_CST_LOW (yt)
1369 && TREE_TYPE (xt) == TREE_TYPE (yt)
1370 && TREE_OVERFLOW (xt) == TREE_OVERFLOW (yt));
1373 /* Return an INTEGER_CST with value whose low-order HOST_BITS_PER_WIDE_INT
1374 bits are given by NUMBER and of the sizetype represented by KIND. */
1377 size_int_wide (number, kind)
1378 HOST_WIDE_INT number;
1379 enum size_type_kind kind;
1381 return size_int_type_wide (number, sizetype_tab[(int) kind]);
1384 /* Likewise, but the desired type is specified explicitly. */
1386 static GTY (()) tree new_const;
1387 static GTY ((if_marked ("ggc_marked_p"), param_is (union tree_node)))
1391 size_int_type_wide (number, type)
1392 HOST_WIDE_INT number;
1399 size_htab = htab_create (1024, size_htab_hash, size_htab_eq, NULL);
1400 new_const = make_node (INTEGER_CST);
1403 /* Adjust NEW_CONST to be the constant we want. If it's already in the
1404 hash table, we return the value from the hash table. Otherwise, we
1405 place that in the hash table and make a new node for the next time. */
1406 TREE_INT_CST_LOW (new_const) = number;
1407 TREE_INT_CST_HIGH (new_const) = number < 0 ? -1 : 0;
1408 TREE_TYPE (new_const) = type;
1409 TREE_OVERFLOW (new_const) = TREE_CONSTANT_OVERFLOW (new_const)
1410 = force_fit_type (new_const, 0);
1412 slot = htab_find_slot (size_htab, new_const, INSERT);
1417 *slot = (PTR) new_const;
1418 new_const = make_node (INTEGER_CST);
1422 return (tree) *slot;
1425 /* Combine operands OP1 and OP2 with arithmetic operation CODE. CODE
1426 is a tree code. The type of the result is taken from the operands.
1427 Both must be the same type integer type and it must be a size type.
1428 If the operands are constant, so is the result. */
1431 size_binop (code, arg0, arg1)
1432 enum tree_code code;
1435 tree type = TREE_TYPE (arg0);
1437 if (TREE_CODE (type) != INTEGER_TYPE || ! TYPE_IS_SIZETYPE (type)
1438 || type != TREE_TYPE (arg1))
1441 /* Handle the special case of two integer constants faster. */
1442 if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
1444 /* And some specific cases even faster than that. */
1445 if (code == PLUS_EXPR && integer_zerop (arg0))
1447 else if ((code == MINUS_EXPR || code == PLUS_EXPR)
1448 && integer_zerop (arg1))
1450 else if (code == MULT_EXPR && integer_onep (arg0))
1453 /* Handle general case of two integer constants. */
1454 return int_const_binop (code, arg0, arg1, 0);
1457 if (arg0 == error_mark_node || arg1 == error_mark_node)
1458 return error_mark_node;
1460 return fold (build (code, type, arg0, arg1));
1463 /* Given two values, either both of sizetype or both of bitsizetype,
1464 compute the difference between the two values. Return the value
1465 in signed type corresponding to the type of the operands. */
1468 size_diffop (arg0, arg1)
1471 tree type = TREE_TYPE (arg0);
1474 if (TREE_CODE (type) != INTEGER_TYPE || ! TYPE_IS_SIZETYPE (type)
1475 || type != TREE_TYPE (arg1))
1478 /* If the type is already signed, just do the simple thing. */
1479 if (! TREE_UNSIGNED (type))
1480 return size_binop (MINUS_EXPR, arg0, arg1);
1482 ctype = (type == bitsizetype || type == ubitsizetype
1483 ? sbitsizetype : ssizetype);
1485 /* If either operand is not a constant, do the conversions to the signed
1486 type and subtract. The hardware will do the right thing with any
1487 overflow in the subtraction. */
1488 if (TREE_CODE (arg0) != INTEGER_CST || TREE_CODE (arg1) != INTEGER_CST)
1489 return size_binop (MINUS_EXPR, convert (ctype, arg0),
1490 convert (ctype, arg1));
1492 /* If ARG0 is larger than ARG1, subtract and return the result in CTYPE.
1493 Otherwise, subtract the other way, convert to CTYPE (we know that can't
1494 overflow) and negate (which can't either). Special-case a result
1495 of zero while we're here. */
1496 if (tree_int_cst_equal (arg0, arg1))
1497 return convert (ctype, integer_zero_node);
1498 else if (tree_int_cst_lt (arg1, arg0))
1499 return convert (ctype, size_binop (MINUS_EXPR, arg0, arg1));
1501 return size_binop (MINUS_EXPR, convert (ctype, integer_zero_node),
1502 convert (ctype, size_binop (MINUS_EXPR, arg1, arg0)));
1506 /* Given T, a tree representing type conversion of ARG1, a constant,
1507 return a constant tree representing the result of conversion. */
1510 fold_convert (t, arg1)
1514 tree type = TREE_TYPE (t);
1517 if (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type))
1519 if (TREE_CODE (arg1) == INTEGER_CST)
1521 /* If we would build a constant wider than GCC supports,
1522 leave the conversion unfolded. */
1523 if (TYPE_PRECISION (type) > 2 * HOST_BITS_PER_WIDE_INT)
1526 /* If we are trying to make a sizetype for a small integer, use
1527 size_int to pick up cached types to reduce duplicate nodes. */
1528 if (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type)
1529 && !TREE_CONSTANT_OVERFLOW (arg1)
1530 && compare_tree_int (arg1, 10000) < 0)
1531 return size_int_type_wide (TREE_INT_CST_LOW (arg1), type);
1533 /* Given an integer constant, make new constant with new type,
1534 appropriately sign-extended or truncated. */
1535 t = build_int_2 (TREE_INT_CST_LOW (arg1),
1536 TREE_INT_CST_HIGH (arg1));
1537 TREE_TYPE (t) = type;
1538 /* Indicate an overflow if (1) ARG1 already overflowed,
1539 or (2) force_fit_type indicates an overflow.
1540 Tell force_fit_type that an overflow has already occurred
1541 if ARG1 is a too-large unsigned value and T is signed.
1542 But don't indicate an overflow if converting a pointer. */
1544 = ((force_fit_type (t,
1545 (TREE_INT_CST_HIGH (arg1) < 0
1546 && (TREE_UNSIGNED (type)
1547 < TREE_UNSIGNED (TREE_TYPE (arg1)))))
1548 && ! POINTER_TYPE_P (TREE_TYPE (arg1)))
1549 || TREE_OVERFLOW (arg1));
1550 TREE_CONSTANT_OVERFLOW (t)
1551 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1553 else if (TREE_CODE (arg1) == REAL_CST)
1555 /* Don't initialize these, use assignments.
1556 Initialized local aggregates don't work on old compilers. */
1560 tree type1 = TREE_TYPE (arg1);
1563 x = TREE_REAL_CST (arg1);
1564 l = real_value_from_int_cst (type1, TYPE_MIN_VALUE (type));
1566 no_upper_bound = (TYPE_MAX_VALUE (type) == NULL);
1567 if (!no_upper_bound)
1568 u = real_value_from_int_cst (type1, TYPE_MAX_VALUE (type));
1570 /* See if X will be in range after truncation towards 0.
1571 To compensate for truncation, move the bounds away from 0,
1572 but reject if X exactly equals the adjusted bounds. */
1573 REAL_ARITHMETIC (l, MINUS_EXPR, l, dconst1);
1574 if (!no_upper_bound)
1575 REAL_ARITHMETIC (u, PLUS_EXPR, u, dconst1);
1576 /* If X is a NaN, use zero instead and show we have an overflow.
1577 Otherwise, range check. */
1578 if (REAL_VALUE_ISNAN (x))
1579 overflow = 1, x = dconst0;
1580 else if (! (REAL_VALUES_LESS (l, x)
1582 && REAL_VALUES_LESS (x, u)))
1586 HOST_WIDE_INT low, high;
1587 REAL_VALUE_TO_INT (&low, &high, x);
1588 t = build_int_2 (low, high);
1590 TREE_TYPE (t) = type;
1592 = TREE_OVERFLOW (arg1) | force_fit_type (t, overflow);
1593 TREE_CONSTANT_OVERFLOW (t)
1594 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1596 TREE_TYPE (t) = type;
1598 else if (TREE_CODE (type) == REAL_TYPE)
1600 if (TREE_CODE (arg1) == INTEGER_CST)
1601 return build_real_from_int_cst (type, arg1);
1602 if (TREE_CODE (arg1) == REAL_CST)
1604 if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
1606 /* We make a copy of ARG1 so that we don't modify an
1607 existing constant tree. */
1608 t = copy_node (arg1);
1609 TREE_TYPE (t) = type;
1613 t = build_real (type,
1614 real_value_truncate (TYPE_MODE (type),
1615 TREE_REAL_CST (arg1)));
1618 = TREE_OVERFLOW (arg1) | force_fit_type (t, 0);
1619 TREE_CONSTANT_OVERFLOW (t)
1620 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1624 TREE_CONSTANT (t) = 1;
1628 /* Return an expr equal to X but certainly not valid as an lvalue. */
1636 /* These things are certainly not lvalues. */
1637 if (TREE_CODE (x) == NON_LVALUE_EXPR
1638 || TREE_CODE (x) == INTEGER_CST
1639 || TREE_CODE (x) == REAL_CST
1640 || TREE_CODE (x) == STRING_CST
1641 || TREE_CODE (x) == ADDR_EXPR)
1644 result = build1 (NON_LVALUE_EXPR, TREE_TYPE (x), x);
1645 TREE_CONSTANT (result) = TREE_CONSTANT (x);
1649 /* Nonzero means lvalues are limited to those valid in pedantic ANSI C.
1650 Zero means allow extended lvalues. */
1652 int pedantic_lvalues;
1654 /* When pedantic, return an expr equal to X but certainly not valid as a
1655 pedantic lvalue. Otherwise, return X. */
1658 pedantic_non_lvalue (x)
1661 if (pedantic_lvalues)
1662 return non_lvalue (x);
1667 /* Given a tree comparison code, return the code that is the logical inverse
1668 of the given code. It is not safe to do this for floating-point
1669 comparisons, except for NE_EXPR and EQ_EXPR. */
1671 static enum tree_code
1672 invert_tree_comparison (code)
1673 enum tree_code code;
1694 /* Similar, but return the comparison that results if the operands are
1695 swapped. This is safe for floating-point. */
1697 static enum tree_code
1698 swap_tree_comparison (code)
1699 enum tree_code code;
1720 /* Convert a comparison tree code from an enum tree_code representation
1721 into a compcode bit-based encoding. This function is the inverse of
1722 compcode_to_comparison. */
1725 comparison_to_compcode (code)
1726 enum tree_code code;
1747 /* Convert a compcode bit-based encoding of a comparison operator back
1748 to GCC's enum tree_code representation. This function is the
1749 inverse of comparison_to_compcode. */
1751 static enum tree_code
1752 compcode_to_comparison (code)
1774 /* Return nonzero if CODE is a tree code that represents a truth value. */
1777 truth_value_p (code)
1778 enum tree_code code;
1780 return (TREE_CODE_CLASS (code) == '<'
1781 || code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR
1782 || code == TRUTH_OR_EXPR || code == TRUTH_ORIF_EXPR
1783 || code == TRUTH_XOR_EXPR || code == TRUTH_NOT_EXPR);
1786 /* Return nonzero if two operands are necessarily equal.
1787 If ONLY_CONST is non-zero, only return non-zero for constants.
1788 This function tests whether the operands are indistinguishable;
1789 it does not test whether they are equal using C's == operation.
1790 The distinction is important for IEEE floating point, because
1791 (1) -0.0 and 0.0 are distinguishable, but -0.0==0.0, and
1792 (2) two NaNs may be indistinguishable, but NaN!=NaN. */
1795 operand_equal_p (arg0, arg1, only_const)
1799 /* If both types don't have the same signedness, then we can't consider
1800 them equal. We must check this before the STRIP_NOPS calls
1801 because they may change the signedness of the arguments. */
1802 if (TREE_UNSIGNED (TREE_TYPE (arg0)) != TREE_UNSIGNED (TREE_TYPE (arg1)))
1808 if (TREE_CODE (arg0) != TREE_CODE (arg1)
1809 /* This is needed for conversions and for COMPONENT_REF.
1810 Might as well play it safe and always test this. */
1811 || TREE_CODE (TREE_TYPE (arg0)) == ERROR_MARK
1812 || TREE_CODE (TREE_TYPE (arg1)) == ERROR_MARK
1813 || TYPE_MODE (TREE_TYPE (arg0)) != TYPE_MODE (TREE_TYPE (arg1)))
1816 /* If ARG0 and ARG1 are the same SAVE_EXPR, they are necessarily equal.
1817 We don't care about side effects in that case because the SAVE_EXPR
1818 takes care of that for us. In all other cases, two expressions are
1819 equal if they have no side effects. If we have two identical
1820 expressions with side effects that should be treated the same due
1821 to the only side effects being identical SAVE_EXPR's, that will
1822 be detected in the recursive calls below. */
1823 if (arg0 == arg1 && ! only_const
1824 && (TREE_CODE (arg0) == SAVE_EXPR
1825 || (! TREE_SIDE_EFFECTS (arg0) && ! TREE_SIDE_EFFECTS (arg1))))
1828 /* Next handle constant cases, those for which we can return 1 even
1829 if ONLY_CONST is set. */
1830 if (TREE_CONSTANT (arg0) && TREE_CONSTANT (arg1))
1831 switch (TREE_CODE (arg0))
1834 return (! TREE_CONSTANT_OVERFLOW (arg0)
1835 && ! TREE_CONSTANT_OVERFLOW (arg1)
1836 && tree_int_cst_equal (arg0, arg1));
1839 return (! TREE_CONSTANT_OVERFLOW (arg0)
1840 && ! TREE_CONSTANT_OVERFLOW (arg1)
1841 && REAL_VALUES_IDENTICAL (TREE_REAL_CST (arg0),
1842 TREE_REAL_CST (arg1)));
1848 if (TREE_CONSTANT_OVERFLOW (arg0)
1849 || TREE_CONSTANT_OVERFLOW (arg1))
1852 v1 = TREE_VECTOR_CST_ELTS (arg0);
1853 v2 = TREE_VECTOR_CST_ELTS (arg1);
1856 if (!operand_equal_p (v1, v2, only_const))
1858 v1 = TREE_CHAIN (v1);
1859 v2 = TREE_CHAIN (v2);
1866 return (operand_equal_p (TREE_REALPART (arg0), TREE_REALPART (arg1),
1868 && operand_equal_p (TREE_IMAGPART (arg0), TREE_IMAGPART (arg1),
1872 return (TREE_STRING_LENGTH (arg0) == TREE_STRING_LENGTH (arg1)
1873 && ! memcmp (TREE_STRING_POINTER (arg0),
1874 TREE_STRING_POINTER (arg1),
1875 TREE_STRING_LENGTH (arg0)));
1878 return operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0),
1887 switch (TREE_CODE_CLASS (TREE_CODE (arg0)))
1890 /* Two conversions are equal only if signedness and modes match. */
1891 if ((TREE_CODE (arg0) == NOP_EXPR || TREE_CODE (arg0) == CONVERT_EXPR)
1892 && (TREE_UNSIGNED (TREE_TYPE (arg0))
1893 != TREE_UNSIGNED (TREE_TYPE (arg1))))
1896 return operand_equal_p (TREE_OPERAND (arg0, 0),
1897 TREE_OPERAND (arg1, 0), 0);
1901 if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0)
1902 && operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1),
1906 /* For commutative ops, allow the other order. */
1907 return ((TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MULT_EXPR
1908 || TREE_CODE (arg0) == MIN_EXPR || TREE_CODE (arg0) == MAX_EXPR
1909 || TREE_CODE (arg0) == BIT_IOR_EXPR
1910 || TREE_CODE (arg0) == BIT_XOR_EXPR
1911 || TREE_CODE (arg0) == BIT_AND_EXPR
1912 || TREE_CODE (arg0) == NE_EXPR || TREE_CODE (arg0) == EQ_EXPR)
1913 && operand_equal_p (TREE_OPERAND (arg0, 0),
1914 TREE_OPERAND (arg1, 1), 0)
1915 && operand_equal_p (TREE_OPERAND (arg0, 1),
1916 TREE_OPERAND (arg1, 0), 0));
1919 /* If either of the pointer (or reference) expressions we are dereferencing
1920 contain a side effect, these cannot be equal. */
1921 if (TREE_SIDE_EFFECTS (arg0)
1922 || TREE_SIDE_EFFECTS (arg1))
1925 switch (TREE_CODE (arg0))
1928 return operand_equal_p (TREE_OPERAND (arg0, 0),
1929 TREE_OPERAND (arg1, 0), 0);
1933 case ARRAY_RANGE_REF:
1934 return (operand_equal_p (TREE_OPERAND (arg0, 0),
1935 TREE_OPERAND (arg1, 0), 0)
1936 && operand_equal_p (TREE_OPERAND (arg0, 1),
1937 TREE_OPERAND (arg1, 1), 0));
1940 return (operand_equal_p (TREE_OPERAND (arg0, 0),
1941 TREE_OPERAND (arg1, 0), 0)
1942 && operand_equal_p (TREE_OPERAND (arg0, 1),
1943 TREE_OPERAND (arg1, 1), 0)
1944 && operand_equal_p (TREE_OPERAND (arg0, 2),
1945 TREE_OPERAND (arg1, 2), 0));
1951 if (TREE_CODE (arg0) == RTL_EXPR)
1952 return rtx_equal_p (RTL_EXPR_RTL (arg0), RTL_EXPR_RTL (arg1));
1960 /* Similar to operand_equal_p, but see if ARG0 might have been made by
1961 shorten_compare from ARG1 when ARG1 was being compared with OTHER.
1963 When in doubt, return 0. */
1966 operand_equal_for_comparison_p (arg0, arg1, other)
1970 int unsignedp1, unsignedpo;
1971 tree primarg0, primarg1, primother;
1972 unsigned int correct_width;
1974 if (operand_equal_p (arg0, arg1, 0))
1977 if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0))
1978 || ! INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
1981 /* Discard any conversions that don't change the modes of ARG0 and ARG1
1982 and see if the inner values are the same. This removes any
1983 signedness comparison, which doesn't matter here. */
1984 primarg0 = arg0, primarg1 = arg1;
1985 STRIP_NOPS (primarg0);
1986 STRIP_NOPS (primarg1);
1987 if (operand_equal_p (primarg0, primarg1, 0))
1990 /* Duplicate what shorten_compare does to ARG1 and see if that gives the
1991 actual comparison operand, ARG0.
1993 First throw away any conversions to wider types
1994 already present in the operands. */
1996 primarg1 = get_narrower (arg1, &unsignedp1);
1997 primother = get_narrower (other, &unsignedpo);
1999 correct_width = TYPE_PRECISION (TREE_TYPE (arg1));
2000 if (unsignedp1 == unsignedpo
2001 && TYPE_PRECISION (TREE_TYPE (primarg1)) < correct_width
2002 && TYPE_PRECISION (TREE_TYPE (primother)) < correct_width)
2004 tree type = TREE_TYPE (arg0);
2006 /* Make sure shorter operand is extended the right way
2007 to match the longer operand. */
2008 primarg1 = convert ((*lang_hooks.types.signed_or_unsigned_type)
2009 (unsignedp1, TREE_TYPE (primarg1)), primarg1);
2011 if (operand_equal_p (arg0, convert (type, primarg1), 0))
2018 /* See if ARG is an expression that is either a comparison or is performing
2019 arithmetic on comparisons. The comparisons must only be comparing
2020 two different values, which will be stored in *CVAL1 and *CVAL2; if
2021 they are non-zero it means that some operands have already been found.
2022 No variables may be used anywhere else in the expression except in the
2023 comparisons. If SAVE_P is true it means we removed a SAVE_EXPR around
2024 the expression and save_expr needs to be called with CVAL1 and CVAL2.
2026 If this is true, return 1. Otherwise, return zero. */
2029 twoval_comparison_p (arg, cval1, cval2, save_p)
2031 tree *cval1, *cval2;
2034 enum tree_code code = TREE_CODE (arg);
2035 char class = TREE_CODE_CLASS (code);
2037 /* We can handle some of the 'e' cases here. */
2038 if (class == 'e' && code == TRUTH_NOT_EXPR)
2040 else if (class == 'e'
2041 && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR
2042 || code == COMPOUND_EXPR))
2045 else if (class == 'e' && code == SAVE_EXPR && SAVE_EXPR_RTL (arg) == 0
2046 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg, 0)))
2048 /* If we've already found a CVAL1 or CVAL2, this expression is
2049 two complex to handle. */
2050 if (*cval1 || *cval2)
2060 return twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p);
2063 return (twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p)
2064 && twoval_comparison_p (TREE_OPERAND (arg, 1),
2065 cval1, cval2, save_p));
2071 if (code == COND_EXPR)
2072 return (twoval_comparison_p (TREE_OPERAND (arg, 0),
2073 cval1, cval2, save_p)
2074 && twoval_comparison_p (TREE_OPERAND (arg, 1),
2075 cval1, cval2, save_p)
2076 && twoval_comparison_p (TREE_OPERAND (arg, 2),
2077 cval1, cval2, save_p));
2081 /* First see if we can handle the first operand, then the second. For
2082 the second operand, we know *CVAL1 can't be zero. It must be that
2083 one side of the comparison is each of the values; test for the
2084 case where this isn't true by failing if the two operands
2087 if (operand_equal_p (TREE_OPERAND (arg, 0),
2088 TREE_OPERAND (arg, 1), 0))
2092 *cval1 = TREE_OPERAND (arg, 0);
2093 else if (operand_equal_p (*cval1, TREE_OPERAND (arg, 0), 0))
2095 else if (*cval2 == 0)
2096 *cval2 = TREE_OPERAND (arg, 0);
2097 else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 0), 0))
2102 if (operand_equal_p (*cval1, TREE_OPERAND (arg, 1), 0))
2104 else if (*cval2 == 0)
2105 *cval2 = TREE_OPERAND (arg, 1);
2106 else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 1), 0))
2118 /* ARG is a tree that is known to contain just arithmetic operations and
2119 comparisons. Evaluate the operations in the tree substituting NEW0 for
2120 any occurrence of OLD0 as an operand of a comparison and likewise for
2124 eval_subst (arg, old0, new0, old1, new1)
2126 tree old0, new0, old1, new1;
2128 tree type = TREE_TYPE (arg);
2129 enum tree_code code = TREE_CODE (arg);
2130 char class = TREE_CODE_CLASS (code);
2132 /* We can handle some of the 'e' cases here. */
2133 if (class == 'e' && code == TRUTH_NOT_EXPR)
2135 else if (class == 'e'
2136 && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
2142 return fold (build1 (code, type,
2143 eval_subst (TREE_OPERAND (arg, 0),
2144 old0, new0, old1, new1)));
2147 return fold (build (code, type,
2148 eval_subst (TREE_OPERAND (arg, 0),
2149 old0, new0, old1, new1),
2150 eval_subst (TREE_OPERAND (arg, 1),
2151 old0, new0, old1, new1)));
2157 return eval_subst (TREE_OPERAND (arg, 0), old0, new0, old1, new1);
2160 return eval_subst (TREE_OPERAND (arg, 1), old0, new0, old1, new1);
2163 return fold (build (code, type,
2164 eval_subst (TREE_OPERAND (arg, 0),
2165 old0, new0, old1, new1),
2166 eval_subst (TREE_OPERAND (arg, 1),
2167 old0, new0, old1, new1),
2168 eval_subst (TREE_OPERAND (arg, 2),
2169 old0, new0, old1, new1)));
2173 /* fall through - ??? */
2177 tree arg0 = TREE_OPERAND (arg, 0);
2178 tree arg1 = TREE_OPERAND (arg, 1);
2180 /* We need to check both for exact equality and tree equality. The
2181 former will be true if the operand has a side-effect. In that
2182 case, we know the operand occurred exactly once. */
2184 if (arg0 == old0 || operand_equal_p (arg0, old0, 0))
2186 else if (arg0 == old1 || operand_equal_p (arg0, old1, 0))
2189 if (arg1 == old0 || operand_equal_p (arg1, old0, 0))
2191 else if (arg1 == old1 || operand_equal_p (arg1, old1, 0))
2194 return fold (build (code, type, arg0, arg1));
2202 /* Return a tree for the case when the result of an expression is RESULT
2203 converted to TYPE and OMITTED was previously an operand of the expression
2204 but is now not needed (e.g., we folded OMITTED * 0).
2206 If OMITTED has side effects, we must evaluate it. Otherwise, just do
2207 the conversion of RESULT to TYPE. */
2210 omit_one_operand (type, result, omitted)
2211 tree type, result, omitted;
2213 tree t = convert (type, result);
2215 if (TREE_SIDE_EFFECTS (omitted))
2216 return build (COMPOUND_EXPR, type, omitted, t);
2218 return non_lvalue (t);
2221 /* Similar, but call pedantic_non_lvalue instead of non_lvalue. */
2224 pedantic_omit_one_operand (type, result, omitted)
2225 tree type, result, omitted;
2227 tree t = convert (type, result);
2229 if (TREE_SIDE_EFFECTS (omitted))
2230 return build (COMPOUND_EXPR, type, omitted, t);
2232 return pedantic_non_lvalue (t);
2235 /* Return a simplified tree node for the truth-negation of ARG. This
2236 never alters ARG itself. We assume that ARG is an operation that
2237 returns a truth value (0 or 1). */
2240 invert_truthvalue (arg)
2243 tree type = TREE_TYPE (arg);
2244 enum tree_code code = TREE_CODE (arg);
2246 if (code == ERROR_MARK)
2249 /* If this is a comparison, we can simply invert it, except for
2250 floating-point non-equality comparisons, in which case we just
2251 enclose a TRUTH_NOT_EXPR around what we have. */
2253 if (TREE_CODE_CLASS (code) == '<')
2255 if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg, 0)))
2256 && !flag_unsafe_math_optimizations
2259 return build1 (TRUTH_NOT_EXPR, type, arg);
2261 return build (invert_tree_comparison (code), type,
2262 TREE_OPERAND (arg, 0), TREE_OPERAND (arg, 1));
2268 return convert (type, build_int_2 (integer_zerop (arg), 0));
2270 case TRUTH_AND_EXPR:
2271 return build (TRUTH_OR_EXPR, type,
2272 invert_truthvalue (TREE_OPERAND (arg, 0)),
2273 invert_truthvalue (TREE_OPERAND (arg, 1)));
2276 return build (TRUTH_AND_EXPR, type,
2277 invert_truthvalue (TREE_OPERAND (arg, 0)),
2278 invert_truthvalue (TREE_OPERAND (arg, 1)));
2280 case TRUTH_XOR_EXPR:
2281 /* Here we can invert either operand. We invert the first operand
2282 unless the second operand is a TRUTH_NOT_EXPR in which case our
2283 result is the XOR of the first operand with the inside of the
2284 negation of the second operand. */
2286 if (TREE_CODE (TREE_OPERAND (arg, 1)) == TRUTH_NOT_EXPR)
2287 return build (TRUTH_XOR_EXPR, type, TREE_OPERAND (arg, 0),
2288 TREE_OPERAND (TREE_OPERAND (arg, 1), 0));
2290 return build (TRUTH_XOR_EXPR, type,
2291 invert_truthvalue (TREE_OPERAND (arg, 0)),
2292 TREE_OPERAND (arg, 1));
2294 case TRUTH_ANDIF_EXPR:
2295 return build (TRUTH_ORIF_EXPR, type,
2296 invert_truthvalue (TREE_OPERAND (arg, 0)),
2297 invert_truthvalue (TREE_OPERAND (arg, 1)));
2299 case TRUTH_ORIF_EXPR:
2300 return build (TRUTH_ANDIF_EXPR, type,
2301 invert_truthvalue (TREE_OPERAND (arg, 0)),
2302 invert_truthvalue (TREE_OPERAND (arg, 1)));
2304 case TRUTH_NOT_EXPR:
2305 return TREE_OPERAND (arg, 0);
2308 return build (COND_EXPR, type, TREE_OPERAND (arg, 0),
2309 invert_truthvalue (TREE_OPERAND (arg, 1)),
2310 invert_truthvalue (TREE_OPERAND (arg, 2)));
2313 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg, 0),
2314 invert_truthvalue (TREE_OPERAND (arg, 1)));
2316 case WITH_RECORD_EXPR:
2317 return build (WITH_RECORD_EXPR, type,
2318 invert_truthvalue (TREE_OPERAND (arg, 0)),
2319 TREE_OPERAND (arg, 1));
2321 case NON_LVALUE_EXPR:
2322 return invert_truthvalue (TREE_OPERAND (arg, 0));
2327 return build1 (TREE_CODE (arg), type,
2328 invert_truthvalue (TREE_OPERAND (arg, 0)));
2331 if (!integer_onep (TREE_OPERAND (arg, 1)))
2333 return build (EQ_EXPR, type, arg, convert (type, integer_zero_node));
2336 return build1 (TRUTH_NOT_EXPR, type, arg);
2338 case CLEANUP_POINT_EXPR:
2339 return build1 (CLEANUP_POINT_EXPR, type,
2340 invert_truthvalue (TREE_OPERAND (arg, 0)));
2345 if (TREE_CODE (TREE_TYPE (arg)) != BOOLEAN_TYPE)
2347 return build1 (TRUTH_NOT_EXPR, type, arg);
2350 /* Given a bit-wise operation CODE applied to ARG0 and ARG1, see if both
2351 operands are another bit-wise operation with a common input. If so,
2352 distribute the bit operations to save an operation and possibly two if
2353 constants are involved. For example, convert
2354 (A | B) & (A | C) into A | (B & C)
2355 Further simplification will occur if B and C are constants.
2357 If this optimization cannot be done, 0 will be returned. */
2360 distribute_bit_expr (code, type, arg0, arg1)
2361 enum tree_code code;
2368 if (TREE_CODE (arg0) != TREE_CODE (arg1)
2369 || TREE_CODE (arg0) == code
2370 || (TREE_CODE (arg0) != BIT_AND_EXPR
2371 && TREE_CODE (arg0) != BIT_IOR_EXPR))
2374 if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0))
2376 common = TREE_OPERAND (arg0, 0);
2377 left = TREE_OPERAND (arg0, 1);
2378 right = TREE_OPERAND (arg1, 1);
2380 else if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 1), 0))
2382 common = TREE_OPERAND (arg0, 0);
2383 left = TREE_OPERAND (arg0, 1);
2384 right = TREE_OPERAND (arg1, 0);
2386 else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 0), 0))
2388 common = TREE_OPERAND (arg0, 1);
2389 left = TREE_OPERAND (arg0, 0);
2390 right = TREE_OPERAND (arg1, 1);
2392 else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1), 0))
2394 common = TREE_OPERAND (arg0, 1);
2395 left = TREE_OPERAND (arg0, 0);
2396 right = TREE_OPERAND (arg1, 0);
2401 return fold (build (TREE_CODE (arg0), type, common,
2402 fold (build (code, type, left, right))));
2405 /* Return a BIT_FIELD_REF of type TYPE to refer to BITSIZE bits of INNER
2406 starting at BITPOS. The field is unsigned if UNSIGNEDP is non-zero. */
2409 make_bit_field_ref (inner, type, bitsize, bitpos, unsignedp)
2412 int bitsize, bitpos;
2415 tree result = build (BIT_FIELD_REF, type, inner,
2416 size_int (bitsize), bitsize_int (bitpos));
2418 TREE_UNSIGNED (result) = unsignedp;
2423 /* Optimize a bit-field compare.
2425 There are two cases: First is a compare against a constant and the
2426 second is a comparison of two items where the fields are at the same
2427 bit position relative to the start of a chunk (byte, halfword, word)
2428 large enough to contain it. In these cases we can avoid the shift
2429 implicit in bitfield extractions.
2431 For constants, we emit a compare of the shifted constant with the
2432 BIT_AND_EXPR of a mask and a byte, halfword, or word of the operand being
2433 compared. For two fields at the same position, we do the ANDs with the
2434 similar mask and compare the result of the ANDs.
2436 CODE is the comparison code, known to be either NE_EXPR or EQ_EXPR.
2437 COMPARE_TYPE is the type of the comparison, and LHS and RHS
2438 are the left and right operands of the comparison, respectively.
2440 If the optimization described above can be done, we return the resulting
2441 tree. Otherwise we return zero. */
2444 optimize_bit_field_compare (code, compare_type, lhs, rhs)
2445 enum tree_code code;
2449 HOST_WIDE_INT lbitpos, lbitsize, rbitpos, rbitsize, nbitpos, nbitsize;
2450 tree type = TREE_TYPE (lhs);
2451 tree signed_type, unsigned_type;
2452 int const_p = TREE_CODE (rhs) == INTEGER_CST;
2453 enum machine_mode lmode, rmode, nmode;
2454 int lunsignedp, runsignedp;
2455 int lvolatilep = 0, rvolatilep = 0;
2456 tree linner, rinner = NULL_TREE;
2460 /* Get all the information about the extractions being done. If the bit size
2461 if the same as the size of the underlying object, we aren't doing an
2462 extraction at all and so can do nothing. We also don't want to
2463 do anything if the inner expression is a PLACEHOLDER_EXPR since we
2464 then will no longer be able to replace it. */
2465 linner = get_inner_reference (lhs, &lbitsize, &lbitpos, &offset, &lmode,
2466 &lunsignedp, &lvolatilep);
2467 if (linner == lhs || lbitsize == GET_MODE_BITSIZE (lmode) || lbitsize < 0
2468 || offset != 0 || TREE_CODE (linner) == PLACEHOLDER_EXPR)
2473 /* If this is not a constant, we can only do something if bit positions,
2474 sizes, and signedness are the same. */
2475 rinner = get_inner_reference (rhs, &rbitsize, &rbitpos, &offset, &rmode,
2476 &runsignedp, &rvolatilep);
2478 if (rinner == rhs || lbitpos != rbitpos || lbitsize != rbitsize
2479 || lunsignedp != runsignedp || offset != 0
2480 || TREE_CODE (rinner) == PLACEHOLDER_EXPR)
2484 /* See if we can find a mode to refer to this field. We should be able to,
2485 but fail if we can't. */
2486 nmode = get_best_mode (lbitsize, lbitpos,
2487 const_p ? TYPE_ALIGN (TREE_TYPE (linner))
2488 : MIN (TYPE_ALIGN (TREE_TYPE (linner)),
2489 TYPE_ALIGN (TREE_TYPE (rinner))),
2490 word_mode, lvolatilep || rvolatilep);
2491 if (nmode == VOIDmode)
2494 /* Set signed and unsigned types of the precision of this mode for the
2496 signed_type = (*lang_hooks.types.type_for_mode) (nmode, 0);
2497 unsigned_type = (*lang_hooks.types.type_for_mode) (nmode, 1);
2499 /* Compute the bit position and size for the new reference and our offset
2500 within it. If the new reference is the same size as the original, we
2501 won't optimize anything, so return zero. */
2502 nbitsize = GET_MODE_BITSIZE (nmode);
2503 nbitpos = lbitpos & ~ (nbitsize - 1);
2505 if (nbitsize == lbitsize)
2508 if (BYTES_BIG_ENDIAN)
2509 lbitpos = nbitsize - lbitsize - lbitpos;
2511 /* Make the mask to be used against the extracted field. */
2512 mask = build_int_2 (~0, ~0);
2513 TREE_TYPE (mask) = unsigned_type;
2514 force_fit_type (mask, 0);
2515 mask = convert (unsigned_type, mask);
2516 mask = const_binop (LSHIFT_EXPR, mask, size_int (nbitsize - lbitsize), 0);
2517 mask = const_binop (RSHIFT_EXPR, mask,
2518 size_int (nbitsize - lbitsize - lbitpos), 0);
2521 /* If not comparing with constant, just rework the comparison
2523 return build (code, compare_type,
2524 build (BIT_AND_EXPR, unsigned_type,
2525 make_bit_field_ref (linner, unsigned_type,
2526 nbitsize, nbitpos, 1),
2528 build (BIT_AND_EXPR, unsigned_type,
2529 make_bit_field_ref (rinner, unsigned_type,
2530 nbitsize, nbitpos, 1),
2533 /* Otherwise, we are handling the constant case. See if the constant is too
2534 big for the field. Warn and return a tree of for 0 (false) if so. We do
2535 this not only for its own sake, but to avoid having to test for this
2536 error case below. If we didn't, we might generate wrong code.
2538 For unsigned fields, the constant shifted right by the field length should
2539 be all zero. For signed fields, the high-order bits should agree with
2544 if (! integer_zerop (const_binop (RSHIFT_EXPR,
2545 convert (unsigned_type, rhs),
2546 size_int (lbitsize), 0)))
2548 warning ("comparison is always %d due to width of bit-field",
2550 return convert (compare_type,
2552 ? integer_one_node : integer_zero_node));
2557 tree tem = const_binop (RSHIFT_EXPR, convert (signed_type, rhs),
2558 size_int (lbitsize - 1), 0);
2559 if (! integer_zerop (tem) && ! integer_all_onesp (tem))
2561 warning ("comparison is always %d due to width of bit-field",
2563 return convert (compare_type,
2565 ? integer_one_node : integer_zero_node));
2569 /* Single-bit compares should always be against zero. */
2570 if (lbitsize == 1 && ! integer_zerop (rhs))
2572 code = code == EQ_EXPR ? NE_EXPR : EQ_EXPR;
2573 rhs = convert (type, integer_zero_node);
2576 /* Make a new bitfield reference, shift the constant over the
2577 appropriate number of bits and mask it with the computed mask
2578 (in case this was a signed field). If we changed it, make a new one. */
2579 lhs = make_bit_field_ref (linner, unsigned_type, nbitsize, nbitpos, 1);
2582 TREE_SIDE_EFFECTS (lhs) = 1;
2583 TREE_THIS_VOLATILE (lhs) = 1;
2586 rhs = fold (const_binop (BIT_AND_EXPR,
2587 const_binop (LSHIFT_EXPR,
2588 convert (unsigned_type, rhs),
2589 size_int (lbitpos), 0),
2592 return build (code, compare_type,
2593 build (BIT_AND_EXPR, unsigned_type, lhs, mask),
2597 /* Subroutine for fold_truthop: decode a field reference.
2599 If EXP is a comparison reference, we return the innermost reference.
2601 *PBITSIZE is set to the number of bits in the reference, *PBITPOS is
2602 set to the starting bit number.
2604 If the innermost field can be completely contained in a mode-sized
2605 unit, *PMODE is set to that mode. Otherwise, it is set to VOIDmode.
2607 *PVOLATILEP is set to 1 if the any expression encountered is volatile;
2608 otherwise it is not changed.
2610 *PUNSIGNEDP is set to the signedness of the field.
2612 *PMASK is set to the mask used. This is either contained in a
2613 BIT_AND_EXPR or derived from the width of the field.
2615 *PAND_MASK is set to the mask found in a BIT_AND_EXPR, if any.
2617 Return 0 if this is not a component reference or is one that we can't
2618 do anything with. */
2621 decode_field_reference (exp, pbitsize, pbitpos, pmode, punsignedp,
2622 pvolatilep, pmask, pand_mask)
2624 HOST_WIDE_INT *pbitsize, *pbitpos;
2625 enum machine_mode *pmode;
2626 int *punsignedp, *pvolatilep;
2631 tree mask, inner, offset;
2633 unsigned int precision;
2635 /* All the optimizations using this function assume integer fields.
2636 There are problems with FP fields since the type_for_size call
2637 below can fail for, e.g., XFmode. */
2638 if (! INTEGRAL_TYPE_P (TREE_TYPE (exp)))
2643 if (TREE_CODE (exp) == BIT_AND_EXPR)
2645 and_mask = TREE_OPERAND (exp, 1);
2646 exp = TREE_OPERAND (exp, 0);
2647 STRIP_NOPS (exp); STRIP_NOPS (and_mask);
2648 if (TREE_CODE (and_mask) != INTEGER_CST)
2652 inner = get_inner_reference (exp, pbitsize, pbitpos, &offset, pmode,
2653 punsignedp, pvolatilep);
2654 if ((inner == exp && and_mask == 0)
2655 || *pbitsize < 0 || offset != 0
2656 || TREE_CODE (inner) == PLACEHOLDER_EXPR)
2659 /* Compute the mask to access the bitfield. */
2660 unsigned_type = (*lang_hooks.types.type_for_size) (*pbitsize, 1);
2661 precision = TYPE_PRECISION (unsigned_type);
2663 mask = build_int_2 (~0, ~0);
2664 TREE_TYPE (mask) = unsigned_type;
2665 force_fit_type (mask, 0);
2666 mask = const_binop (LSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
2667 mask = const_binop (RSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
2669 /* Merge it with the mask we found in the BIT_AND_EXPR, if any. */
2671 mask = fold (build (BIT_AND_EXPR, unsigned_type,
2672 convert (unsigned_type, and_mask), mask));
2675 *pand_mask = and_mask;
2679 /* Return non-zero if MASK represents a mask of SIZE ones in the low-order
2683 all_ones_mask_p (mask, size)
2687 tree type = TREE_TYPE (mask);
2688 unsigned int precision = TYPE_PRECISION (type);
2691 tmask = build_int_2 (~0, ~0);
2692 TREE_TYPE (tmask) = (*lang_hooks.types.signed_type) (type);
2693 force_fit_type (tmask, 0);
2695 tree_int_cst_equal (mask,
2696 const_binop (RSHIFT_EXPR,
2697 const_binop (LSHIFT_EXPR, tmask,
2698 size_int (precision - size),
2700 size_int (precision - size), 0));
2703 /* Subroutine for fold: determine if VAL is the INTEGER_CONST that
2704 represents the sign bit of EXP's type. If EXP represents a sign
2705 or zero extension, also test VAL against the unextended type.
2706 The return value is the (sub)expression whose sign bit is VAL,
2707 or NULL_TREE otherwise. */
2710 sign_bit_p (exp, val)
2714 unsigned HOST_WIDE_INT lo;
2719 /* Tree EXP must have a integral type. */
2720 t = TREE_TYPE (exp);
2721 if (! INTEGRAL_TYPE_P (t))
2724 /* Tree VAL must be an integer constant. */
2725 if (TREE_CODE (val) != INTEGER_CST
2726 || TREE_CONSTANT_OVERFLOW (val))
2729 width = TYPE_PRECISION (t);
2730 if (width > HOST_BITS_PER_WIDE_INT)
2732 hi = (unsigned HOST_WIDE_INT) 1 << (width - HOST_BITS_PER_WIDE_INT - 1);
2738 lo = (unsigned HOST_WIDE_INT) 1 << (width - 1);
2741 if (TREE_INT_CST_HIGH (val) == hi && TREE_INT_CST_LOW (val) == lo)
2744 /* Handle extension from a narrower type. */
2745 if (TREE_CODE (exp) == NOP_EXPR
2746 && TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (exp, 0))) < width)
2747 return sign_bit_p (TREE_OPERAND (exp, 0), val);
2752 /* Subroutine for fold_truthop: determine if an operand is simple enough
2753 to be evaluated unconditionally. */
2756 simple_operand_p (exp)
2759 /* Strip any conversions that don't change the machine mode. */
2760 while ((TREE_CODE (exp) == NOP_EXPR
2761 || TREE_CODE (exp) == CONVERT_EXPR)
2762 && (TYPE_MODE (TREE_TYPE (exp))
2763 == TYPE_MODE (TREE_TYPE (TREE_OPERAND (exp, 0)))))
2764 exp = TREE_OPERAND (exp, 0);
2766 return (TREE_CODE_CLASS (TREE_CODE (exp)) == 'c'
2768 && ! TREE_ADDRESSABLE (exp)
2769 && ! TREE_THIS_VOLATILE (exp)
2770 && ! DECL_NONLOCAL (exp)
2771 /* Don't regard global variables as simple. They may be
2772 allocated in ways unknown to the compiler (shared memory,
2773 #pragma weak, etc). */
2774 && ! TREE_PUBLIC (exp)
2775 && ! DECL_EXTERNAL (exp)
2776 /* Loading a static variable is unduly expensive, but global
2777 registers aren't expensive. */
2778 && (! TREE_STATIC (exp) || DECL_REGISTER (exp))));
2781 /* The following functions are subroutines to fold_range_test and allow it to
2782 try to change a logical combination of comparisons into a range test.
2785 X == 2 || X == 3 || X == 4 || X == 5
2789 (unsigned) (X - 2) <= 3
2791 We describe each set of comparisons as being either inside or outside
2792 a range, using a variable named like IN_P, and then describe the
2793 range with a lower and upper bound. If one of the bounds is omitted,
2794 it represents either the highest or lowest value of the type.
2796 In the comments below, we represent a range by two numbers in brackets
2797 preceded by a "+" to designate being inside that range, or a "-" to
2798 designate being outside that range, so the condition can be inverted by
2799 flipping the prefix. An omitted bound is represented by a "-". For
2800 example, "- [-, 10]" means being outside the range starting at the lowest
2801 possible value and ending at 10, in other words, being greater than 10.
2802 The range "+ [-, -]" is always true and hence the range "- [-, -]" is
2805 We set up things so that the missing bounds are handled in a consistent
2806 manner so neither a missing bound nor "true" and "false" need to be
2807 handled using a special case. */
2809 /* Return the result of applying CODE to ARG0 and ARG1, but handle the case
2810 of ARG0 and/or ARG1 being omitted, meaning an unlimited range. UPPER0_P
2811 and UPPER1_P are nonzero if the respective argument is an upper bound
2812 and zero for a lower. TYPE, if nonzero, is the type of the result; it
2813 must be specified for a comparison. ARG1 will be converted to ARG0's
2814 type if both are specified. */
2817 range_binop (code, type, arg0, upper0_p, arg1, upper1_p)
2818 enum tree_code code;
2821 int upper0_p, upper1_p;
2827 /* If neither arg represents infinity, do the normal operation.
2828 Else, if not a comparison, return infinity. Else handle the special
2829 comparison rules. Note that most of the cases below won't occur, but
2830 are handled for consistency. */
2832 if (arg0 != 0 && arg1 != 0)
2834 tem = fold (build (code, type != 0 ? type : TREE_TYPE (arg0),
2835 arg0, convert (TREE_TYPE (arg0), arg1)));
2837 return TREE_CODE (tem) == INTEGER_CST ? tem : 0;
2840 if (TREE_CODE_CLASS (code) != '<')
2843 /* Set SGN[01] to -1 if ARG[01] is a lower bound, 1 for upper, and 0
2844 for neither. In real maths, we cannot assume open ended ranges are
2845 the same. But, this is computer arithmetic, where numbers are finite.
2846 We can therefore make the transformation of any unbounded range with
2847 the value Z, Z being greater than any representable number. This permits
2848 us to treat unbounded ranges as equal. */
2849 sgn0 = arg0 != 0 ? 0 : (upper0_p ? 1 : -1);
2850 sgn1 = arg1 != 0 ? 0 : (upper1_p ? 1 : -1);
2854 result = sgn0 == sgn1;
2857 result = sgn0 != sgn1;
2860 result = sgn0 < sgn1;
2863 result = sgn0 <= sgn1;
2866 result = sgn0 > sgn1;
2869 result = sgn0 >= sgn1;
2875 return convert (type, result ? integer_one_node : integer_zero_node);
2878 /* Given EXP, a logical expression, set the range it is testing into
2879 variables denoted by PIN_P, PLOW, and PHIGH. Return the expression
2880 actually being tested. *PLOW and *PHIGH will be made of the same type
2881 as the returned expression. If EXP is not a comparison, we will most
2882 likely not be returning a useful value and range. */
2885 make_range (exp, pin_p, plow, phigh)
2890 enum tree_code code;
2891 tree arg0 = NULL_TREE, arg1 = NULL_TREE, type = NULL_TREE;
2892 tree orig_type = NULL_TREE;
2894 tree low, high, n_low, n_high;
2896 /* Start with simply saying "EXP != 0" and then look at the code of EXP
2897 and see if we can refine the range. Some of the cases below may not
2898 happen, but it doesn't seem worth worrying about this. We "continue"
2899 the outer loop when we've changed something; otherwise we "break"
2900 the switch, which will "break" the while. */
2902 in_p = 0, low = high = convert (TREE_TYPE (exp), integer_zero_node);
2906 code = TREE_CODE (exp);
2908 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
2910 arg0 = TREE_OPERAND (exp, 0);
2911 if (TREE_CODE_CLASS (code) == '<'
2912 || TREE_CODE_CLASS (code) == '1'
2913 || TREE_CODE_CLASS (code) == '2')
2914 type = TREE_TYPE (arg0);
2915 if (TREE_CODE_CLASS (code) == '2'
2916 || TREE_CODE_CLASS (code) == '<'
2917 || (TREE_CODE_CLASS (code) == 'e'
2918 && TREE_CODE_LENGTH (code) > 1))
2919 arg1 = TREE_OPERAND (exp, 1);
2922 /* Set ORIG_TYPE as soon as TYPE is non-null so that we do not
2923 lose a cast by accident. */
2924 if (type != NULL_TREE && orig_type == NULL_TREE)
2929 case TRUTH_NOT_EXPR:
2930 in_p = ! in_p, exp = arg0;
2933 case EQ_EXPR: case NE_EXPR:
2934 case LT_EXPR: case LE_EXPR: case GE_EXPR: case GT_EXPR:
2935 /* We can only do something if the range is testing for zero
2936 and if the second operand is an integer constant. Note that
2937 saying something is "in" the range we make is done by
2938 complementing IN_P since it will set in the initial case of
2939 being not equal to zero; "out" is leaving it alone. */
2940 if (low == 0 || high == 0
2941 || ! integer_zerop (low) || ! integer_zerop (high)
2942 || TREE_CODE (arg1) != INTEGER_CST)
2947 case NE_EXPR: /* - [c, c] */
2950 case EQ_EXPR: /* + [c, c] */
2951 in_p = ! in_p, low = high = arg1;
2953 case GT_EXPR: /* - [-, c] */
2954 low = 0, high = arg1;
2956 case GE_EXPR: /* + [c, -] */
2957 in_p = ! in_p, low = arg1, high = 0;
2959 case LT_EXPR: /* - [c, -] */
2960 low = arg1, high = 0;
2962 case LE_EXPR: /* + [-, c] */
2963 in_p = ! in_p, low = 0, high = arg1;
2971 /* If this is an unsigned comparison, we also know that EXP is
2972 greater than or equal to zero. We base the range tests we make
2973 on that fact, so we record it here so we can parse existing
2975 if (TREE_UNSIGNED (type) && (low == 0 || high == 0))
2977 if (! merge_ranges (&n_in_p, &n_low, &n_high, in_p, low, high,
2978 1, convert (type, integer_zero_node),
2982 in_p = n_in_p, low = n_low, high = n_high;
2984 /* If the high bound is missing, but we
2985 have a low bound, reverse the range so
2986 it goes from zero to the low bound minus 1. */
2987 if (high == 0 && low)
2990 high = range_binop (MINUS_EXPR, NULL_TREE, low, 0,
2991 integer_one_node, 0);
2992 low = convert (type, integer_zero_node);
2998 /* (-x) IN [a,b] -> x in [-b, -a] */
2999 n_low = range_binop (MINUS_EXPR, type,
3000 convert (type, integer_zero_node), 0, high, 1);
3001 n_high = range_binop (MINUS_EXPR, type,
3002 convert (type, integer_zero_node), 0, low, 0);
3003 low = n_low, high = n_high;
3009 exp = build (MINUS_EXPR, type, negate_expr (arg0),
3010 convert (type, integer_one_node));
3013 case PLUS_EXPR: case MINUS_EXPR:
3014 if (TREE_CODE (arg1) != INTEGER_CST)
3017 /* If EXP is signed, any overflow in the computation is undefined,
3018 so we don't worry about it so long as our computations on
3019 the bounds don't overflow. For unsigned, overflow is defined
3020 and this is exactly the right thing. */
3021 n_low = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
3022 type, low, 0, arg1, 0);
3023 n_high = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
3024 type, high, 1, arg1, 0);
3025 if ((n_low != 0 && TREE_OVERFLOW (n_low))
3026 || (n_high != 0 && TREE_OVERFLOW (n_high)))
3029 /* Check for an unsigned range which has wrapped around the maximum
3030 value thus making n_high < n_low, and normalize it. */
3031 if (n_low && n_high && tree_int_cst_lt (n_high, n_low))
3033 low = range_binop (PLUS_EXPR, type, n_high, 0,
3034 integer_one_node, 0);
3035 high = range_binop (MINUS_EXPR, type, n_low, 0,
3036 integer_one_node, 0);
3038 /* If the range is of the form +/- [ x+1, x ], we won't
3039 be able to normalize it. But then, it represents the
3040 whole range or the empty set, so make it
3042 if (tree_int_cst_equal (n_low, low)
3043 && tree_int_cst_equal (n_high, high))
3049 low = n_low, high = n_high;
3054 case NOP_EXPR: case NON_LVALUE_EXPR: case CONVERT_EXPR:
3055 if (TYPE_PRECISION (type) > TYPE_PRECISION (orig_type))
3058 if (! INTEGRAL_TYPE_P (type)
3059 || (low != 0 && ! int_fits_type_p (low, type))
3060 || (high != 0 && ! int_fits_type_p (high, type)))
3063 n_low = low, n_high = high;
3066 n_low = convert (type, n_low);
3069 n_high = convert (type, n_high);
3071 /* If we're converting from an unsigned to a signed type,
3072 we will be doing the comparison as unsigned. The tests above
3073 have already verified that LOW and HIGH are both positive.
3075 So we have to make sure that the original unsigned value will
3076 be interpreted as positive. */
3077 if (TREE_UNSIGNED (type) && ! TREE_UNSIGNED (TREE_TYPE (exp)))
3079 tree equiv_type = (*lang_hooks.types.type_for_mode)
3080 (TYPE_MODE (type), 1);
3083 /* A range without an upper bound is, naturally, unbounded.
3084 Since convert would have cropped a very large value, use
3085 the max value for the destination type. */
3087 = TYPE_MAX_VALUE (equiv_type) ? TYPE_MAX_VALUE (equiv_type)
3088 : TYPE_MAX_VALUE (type);
3090 high_positive = fold (build (RSHIFT_EXPR, type,
3091 convert (type, high_positive),
3092 convert (type, integer_one_node)));
3094 /* If the low bound is specified, "and" the range with the
3095 range for which the original unsigned value will be
3099 if (! merge_ranges (&n_in_p, &n_low, &n_high,
3101 1, convert (type, integer_zero_node),
3105 in_p = (n_in_p == in_p);
3109 /* Otherwise, "or" the range with the range of the input
3110 that will be interpreted as negative. */
3111 if (! merge_ranges (&n_in_p, &n_low, &n_high,
3113 1, convert (type, integer_zero_node),
3117 in_p = (in_p != n_in_p);
3122 low = n_low, high = n_high;
3132 /* If EXP is a constant, we can evaluate whether this is true or false. */
3133 if (TREE_CODE (exp) == INTEGER_CST)
3135 in_p = in_p == (integer_onep (range_binop (GE_EXPR, integer_type_node,
3137 && integer_onep (range_binop (LE_EXPR, integer_type_node,
3143 *pin_p = in_p, *plow = low, *phigh = high;
3147 /* Given a range, LOW, HIGH, and IN_P, an expression, EXP, and a result
3148 type, TYPE, return an expression to test if EXP is in (or out of, depending
3149 on IN_P) the range. */
3152 build_range_check (type, exp, in_p, low, high)
3158 tree etype = TREE_TYPE (exp);
3162 && (0 != (value = build_range_check (type, exp, 1, low, high))))
3163 return invert_truthvalue (value);
3165 if (low == 0 && high == 0)
3166 return convert (type, integer_one_node);
3169 return fold (build (LE_EXPR, type, exp, high));
3172 return fold (build (GE_EXPR, type, exp, low));
3174 if (operand_equal_p (low, high, 0))
3175 return fold (build (EQ_EXPR, type, exp, low));
3177 if (integer_zerop (low))
3179 if (! TREE_UNSIGNED (etype))
3181 etype = (*lang_hooks.types.unsigned_type) (etype);
3182 high = convert (etype, high);
3183 exp = convert (etype, exp);
3185 return build_range_check (type, exp, 1, 0, high);
3188 /* Optimize (c>=1) && (c<=127) into (signed char)c > 0. */
3189 if (integer_onep (low) && TREE_CODE (high) == INTEGER_CST)
3191 unsigned HOST_WIDE_INT lo;
3195 prec = TYPE_PRECISION (etype);
3196 if (prec <= HOST_BITS_PER_WIDE_INT)
3199 lo = ((unsigned HOST_WIDE_INT) 1 << (prec - 1)) - 1;
3203 hi = ((HOST_WIDE_INT) 1 << (prec - HOST_BITS_PER_WIDE_INT - 1)) - 1;
3204 lo = (unsigned HOST_WIDE_INT) -1;
3207 if (TREE_INT_CST_HIGH (high) == hi && TREE_INT_CST_LOW (high) == lo)
3209 if (TREE_UNSIGNED (etype))
3211 etype = (*lang_hooks.types.signed_type) (etype);
3212 exp = convert (etype, exp);
3214 return fold (build (GT_EXPR, type, exp,
3215 convert (etype, integer_zero_node)));
3219 if (0 != (value = const_binop (MINUS_EXPR, high, low, 0))
3220 && ! TREE_OVERFLOW (value))
3221 return build_range_check (type,
3222 fold (build (MINUS_EXPR, etype, exp, low)),
3223 1, convert (etype, integer_zero_node), value);
3228 /* Given two ranges, see if we can merge them into one. Return 1 if we
3229 can, 0 if we can't. Set the output range into the specified parameters. */
3232 merge_ranges (pin_p, plow, phigh, in0_p, low0, high0, in1_p, low1, high1)
3236 tree low0, high0, low1, high1;
3244 int lowequal = ((low0 == 0 && low1 == 0)
3245 || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3246 low0, 0, low1, 0)));
3247 int highequal = ((high0 == 0 && high1 == 0)
3248 || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3249 high0, 1, high1, 1)));
3251 /* Make range 0 be the range that starts first, or ends last if they
3252 start at the same value. Swap them if it isn't. */
3253 if (integer_onep (range_binop (GT_EXPR, integer_type_node,
3256 && integer_onep (range_binop (GT_EXPR, integer_type_node,
3257 high1, 1, high0, 1))))
3259 temp = in0_p, in0_p = in1_p, in1_p = temp;
3260 tem = low0, low0 = low1, low1 = tem;
3261 tem = high0, high0 = high1, high1 = tem;
3264 /* Now flag two cases, whether the ranges are disjoint or whether the
3265 second range is totally subsumed in the first. Note that the tests
3266 below are simplified by the ones above. */
3267 no_overlap = integer_onep (range_binop (LT_EXPR, integer_type_node,
3268 high0, 1, low1, 0));
3269 subset = integer_onep (range_binop (LE_EXPR, integer_type_node,
3270 high1, 1, high0, 1));
3272 /* We now have four cases, depending on whether we are including or
3273 excluding the two ranges. */
3276 /* If they don't overlap, the result is false. If the second range
3277 is a subset it is the result. Otherwise, the range is from the start
3278 of the second to the end of the first. */
3280 in_p = 0, low = high = 0;
3282 in_p = 1, low = low1, high = high1;
3284 in_p = 1, low = low1, high = high0;
3287 else if (in0_p && ! in1_p)
3289 /* If they don't overlap, the result is the first range. If they are
3290 equal, the result is false. If the second range is a subset of the
3291 first, and the ranges begin at the same place, we go from just after
3292 the end of the first range to the end of the second. If the second
3293 range is not a subset of the first, or if it is a subset and both
3294 ranges end at the same place, the range starts at the start of the
3295 first range and ends just before the second range.
3296 Otherwise, we can't describe this as a single range. */
3298 in_p = 1, low = low0, high = high0;
3299 else if (lowequal && highequal)
3300 in_p = 0, low = high = 0;
3301 else if (subset && lowequal)
3303 in_p = 1, high = high0;
3304 low = range_binop (PLUS_EXPR, NULL_TREE, high1, 0,
3305 integer_one_node, 0);
3307 else if (! subset || highequal)
3309 in_p = 1, low = low0;
3310 high = range_binop (MINUS_EXPR, NULL_TREE, low1, 0,
3311 integer_one_node, 0);
3317 else if (! in0_p && in1_p)
3319 /* If they don't overlap, the result is the second range. If the second
3320 is a subset of the first, the result is false. Otherwise,
3321 the range starts just after the first range and ends at the
3322 end of the second. */
3324 in_p = 1, low = low1, high = high1;
3325 else if (subset || highequal)
3326 in_p = 0, low = high = 0;
3329 in_p = 1, high = high1;
3330 low = range_binop (PLUS_EXPR, NULL_TREE, high0, 1,
3331 integer_one_node, 0);
3337 /* The case where we are excluding both ranges. Here the complex case
3338 is if they don't overlap. In that case, the only time we have a
3339 range is if they are adjacent. If the second is a subset of the
3340 first, the result is the first. Otherwise, the range to exclude
3341 starts at the beginning of the first range and ends at the end of the
3345 if (integer_onep (range_binop (EQ_EXPR, integer_type_node,
3346 range_binop (PLUS_EXPR, NULL_TREE,
3348 integer_one_node, 1),
3350 in_p = 0, low = low0, high = high1;
3355 in_p = 0, low = low0, high = high0;
3357 in_p = 0, low = low0, high = high1;
3360 *pin_p = in_p, *plow = low, *phigh = high;
3364 /* EXP is some logical combination of boolean tests. See if we can
3365 merge it into some range test. Return the new tree if so. */
3368 fold_range_test (exp)
3371 int or_op = (TREE_CODE (exp) == TRUTH_ORIF_EXPR
3372 || TREE_CODE (exp) == TRUTH_OR_EXPR);
3373 int in0_p, in1_p, in_p;
3374 tree low0, low1, low, high0, high1, high;
3375 tree lhs = make_range (TREE_OPERAND (exp, 0), &in0_p, &low0, &high0);
3376 tree rhs = make_range (TREE_OPERAND (exp, 1), &in1_p, &low1, &high1);
3379 /* If this is an OR operation, invert both sides; we will invert
3380 again at the end. */
3382 in0_p = ! in0_p, in1_p = ! in1_p;
3384 /* If both expressions are the same, if we can merge the ranges, and we
3385 can build the range test, return it or it inverted. If one of the
3386 ranges is always true or always false, consider it to be the same
3387 expression as the other. */
3388 if ((lhs == 0 || rhs == 0 || operand_equal_p (lhs, rhs, 0))
3389 && merge_ranges (&in_p, &low, &high, in0_p, low0, high0,
3391 && 0 != (tem = (build_range_check (TREE_TYPE (exp),
3393 : rhs != 0 ? rhs : integer_zero_node,
3395 return or_op ? invert_truthvalue (tem) : tem;
3397 /* On machines where the branch cost is expensive, if this is a
3398 short-circuited branch and the underlying object on both sides
3399 is the same, make a non-short-circuit operation. */
3400 else if (BRANCH_COST >= 2
3401 && lhs != 0 && rhs != 0
3402 && (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3403 || TREE_CODE (exp) == TRUTH_ORIF_EXPR)
3404 && operand_equal_p (lhs, rhs, 0))
3406 /* If simple enough, just rewrite. Otherwise, make a SAVE_EXPR
3407 unless we are at top level or LHS contains a PLACEHOLDER_EXPR, in
3408 which cases we can't do this. */
3409 if (simple_operand_p (lhs))
3410 return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3411 ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3412 TREE_TYPE (exp), TREE_OPERAND (exp, 0),
3413 TREE_OPERAND (exp, 1));
3415 else if ((*lang_hooks.decls.global_bindings_p) () == 0
3416 && ! contains_placeholder_p (lhs))
3418 tree common = save_expr (lhs);
3420 if (0 != (lhs = build_range_check (TREE_TYPE (exp), common,
3421 or_op ? ! in0_p : in0_p,
3423 && (0 != (rhs = build_range_check (TREE_TYPE (exp), common,
3424 or_op ? ! in1_p : in1_p,
3426 return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3427 ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3428 TREE_TYPE (exp), lhs, rhs);
3435 /* Subroutine for fold_truthop: C is an INTEGER_CST interpreted as a P
3436 bit value. Arrange things so the extra bits will be set to zero if and
3437 only if C is signed-extended to its full width. If MASK is nonzero,
3438 it is an INTEGER_CST that should be AND'ed with the extra bits. */
3441 unextend (c, p, unsignedp, mask)
3447 tree type = TREE_TYPE (c);
3448 int modesize = GET_MODE_BITSIZE (TYPE_MODE (type));
3451 if (p == modesize || unsignedp)
3454 /* We work by getting just the sign bit into the low-order bit, then
3455 into the high-order bit, then sign-extend. We then XOR that value
3457 temp = const_binop (RSHIFT_EXPR, c, size_int (p - 1), 0);
3458 temp = const_binop (BIT_AND_EXPR, temp, size_int (1), 0);
3460 /* We must use a signed type in order to get an arithmetic right shift.
3461 However, we must also avoid introducing accidental overflows, so that
3462 a subsequent call to integer_zerop will work. Hence we must
3463 do the type conversion here. At this point, the constant is either
3464 zero or one, and the conversion to a signed type can never overflow.
3465 We could get an overflow if this conversion is done anywhere else. */
3466 if (TREE_UNSIGNED (type))
3467 temp = convert ((*lang_hooks.types.signed_type) (type), temp);
3469 temp = const_binop (LSHIFT_EXPR, temp, size_int (modesize - 1), 0);
3470 temp = const_binop (RSHIFT_EXPR, temp, size_int (modesize - p - 1), 0);
3472 temp = const_binop (BIT_AND_EXPR, temp, convert (TREE_TYPE (c), mask), 0);
3473 /* If necessary, convert the type back to match the type of C. */
3474 if (TREE_UNSIGNED (type))
3475 temp = convert (type, temp);
3477 return convert (type, const_binop (BIT_XOR_EXPR, c, temp, 0));
3480 /* Find ways of folding logical expressions of LHS and RHS:
3481 Try to merge two comparisons to the same innermost item.
3482 Look for range tests like "ch >= '0' && ch <= '9'".
3483 Look for combinations of simple terms on machines with expensive branches
3484 and evaluate the RHS unconditionally.
3486 For example, if we have p->a == 2 && p->b == 4 and we can make an
3487 object large enough to span both A and B, we can do this with a comparison
3488 against the object ANDed with the a mask.
3490 If we have p->a == q->a && p->b == q->b, we may be able to use bit masking
3491 operations to do this with one comparison.
3493 We check for both normal comparisons and the BIT_AND_EXPRs made this by
3494 function and the one above.
3496 CODE is the logical operation being done. It can be TRUTH_ANDIF_EXPR,
3497 TRUTH_AND_EXPR, TRUTH_ORIF_EXPR, or TRUTH_OR_EXPR.
3499 TRUTH_TYPE is the type of the logical operand and LHS and RHS are its
3502 We return the simplified tree or 0 if no optimization is possible. */
3505 fold_truthop (code, truth_type, lhs, rhs)
3506 enum tree_code code;
3507 tree truth_type, lhs, rhs;
3509 /* If this is the "or" of two comparisons, we can do something if
3510 the comparisons are NE_EXPR. If this is the "and", we can do something
3511 if the comparisons are EQ_EXPR. I.e.,
3512 (a->b == 2 && a->c == 4) can become (a->new == NEW).
3514 WANTED_CODE is this operation code. For single bit fields, we can
3515 convert EQ_EXPR to NE_EXPR so we need not reject the "wrong"
3516 comparison for one-bit fields. */
3518 enum tree_code wanted_code;
3519 enum tree_code lcode, rcode;
3520 tree ll_arg, lr_arg, rl_arg, rr_arg;
3521 tree ll_inner, lr_inner, rl_inner, rr_inner;
3522 HOST_WIDE_INT ll_bitsize, ll_bitpos, lr_bitsize, lr_bitpos;
3523 HOST_WIDE_INT rl_bitsize, rl_bitpos, rr_bitsize, rr_bitpos;
3524 HOST_WIDE_INT xll_bitpos, xlr_bitpos, xrl_bitpos, xrr_bitpos;
3525 HOST_WIDE_INT lnbitsize, lnbitpos, rnbitsize, rnbitpos;
3526 int ll_unsignedp, lr_unsignedp, rl_unsignedp, rr_unsignedp;
3527 enum machine_mode ll_mode, lr_mode, rl_mode, rr_mode;
3528 enum machine_mode lnmode, rnmode;
3529 tree ll_mask, lr_mask, rl_mask, rr_mask;
3530 tree ll_and_mask, lr_and_mask, rl_and_mask, rr_and_mask;
3531 tree l_const, r_const;
3532 tree lntype, rntype, result;
3533 int first_bit, end_bit;
3536 /* Start by getting the comparison codes. Fail if anything is volatile.
3537 If one operand is a BIT_AND_EXPR with the constant one, treat it as if
3538 it were surrounded with a NE_EXPR. */
3540 if (TREE_SIDE_EFFECTS (lhs) || TREE_SIDE_EFFECTS (rhs))
3543 lcode = TREE_CODE (lhs);
3544 rcode = TREE_CODE (rhs);
3546 if (lcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (lhs, 1)))
3547 lcode = NE_EXPR, lhs = build (NE_EXPR, truth_type, lhs, integer_zero_node);
3549 if (rcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (rhs, 1)))
3550 rcode = NE_EXPR, rhs = build (NE_EXPR, truth_type, rhs, integer_zero_node);
3552 if (TREE_CODE_CLASS (lcode) != '<' || TREE_CODE_CLASS (rcode) != '<')
3555 code = ((code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR)
3556 ? TRUTH_AND_EXPR : TRUTH_OR_EXPR);
3558 ll_arg = TREE_OPERAND (lhs, 0);
3559 lr_arg = TREE_OPERAND (lhs, 1);
3560 rl_arg = TREE_OPERAND (rhs, 0);
3561 rr_arg = TREE_OPERAND (rhs, 1);
3563 /* Simplify (x<y) && (x==y) into (x<=y) and related optimizations. */
3564 if (simple_operand_p (ll_arg)
3565 && simple_operand_p (lr_arg)
3566 && !FLOAT_TYPE_P (TREE_TYPE (ll_arg)))
3570 if (operand_equal_p (ll_arg, rl_arg, 0)
3571 && operand_equal_p (lr_arg, rr_arg, 0))
3573 int lcompcode, rcompcode;
3575 lcompcode = comparison_to_compcode (lcode);
3576 rcompcode = comparison_to_compcode (rcode);
3577 compcode = (code == TRUTH_AND_EXPR)
3578 ? lcompcode & rcompcode
3579 : lcompcode | rcompcode;
3581 else if (operand_equal_p (ll_arg, rr_arg, 0)
3582 && operand_equal_p (lr_arg, rl_arg, 0))
3584 int lcompcode, rcompcode;
3586 rcode = swap_tree_comparison (rcode);
3587 lcompcode = comparison_to_compcode (lcode);
3588 rcompcode = comparison_to_compcode (rcode);
3589 compcode = (code == TRUTH_AND_EXPR)
3590 ? lcompcode & rcompcode
3591 : lcompcode | rcompcode;
3596 if (compcode == COMPCODE_TRUE)
3597 return convert (truth_type, integer_one_node);
3598 else if (compcode == COMPCODE_FALSE)
3599 return convert (truth_type, integer_zero_node);
3600 else if (compcode != -1)
3601 return build (compcode_to_comparison (compcode),
3602 truth_type, ll_arg, lr_arg);
3605 /* If the RHS can be evaluated unconditionally and its operands are
3606 simple, it wins to evaluate the RHS unconditionally on machines
3607 with expensive branches. In this case, this isn't a comparison
3608 that can be merged. Avoid doing this if the RHS is a floating-point
3609 comparison since those can trap. */
3611 if (BRANCH_COST >= 2
3612 && ! FLOAT_TYPE_P (TREE_TYPE (rl_arg))
3613 && simple_operand_p (rl_arg)
3614 && simple_operand_p (rr_arg))
3616 /* Convert (a != 0) || (b != 0) into (a | b) != 0. */
3617 if (code == TRUTH_OR_EXPR
3618 && lcode == NE_EXPR && integer_zerop (lr_arg)
3619 && rcode == NE_EXPR && integer_zerop (rr_arg)
3620 && TREE_TYPE (ll_arg) == TREE_TYPE (rl_arg))
3621 return build (NE_EXPR, truth_type,
3622 build (BIT_IOR_EXPR, TREE_TYPE (ll_arg),
3626 /* Convert (a == 0) && (b == 0) into (a | b) == 0. */
3627 if (code == TRUTH_AND_EXPR
3628 && lcode == EQ_EXPR && integer_zerop (lr_arg)
3629 && rcode == EQ_EXPR && integer_zerop (rr_arg)
3630 && TREE_TYPE (ll_arg) == TREE_TYPE (rl_arg))
3631 return build (EQ_EXPR, truth_type,
3632 build (BIT_IOR_EXPR, TREE_TYPE (ll_arg),
3636 return build (code, truth_type, lhs, rhs);
3639 /* See if the comparisons can be merged. Then get all the parameters for
3642 if ((lcode != EQ_EXPR && lcode != NE_EXPR)
3643 || (rcode != EQ_EXPR && rcode != NE_EXPR))
3647 ll_inner = decode_field_reference (ll_arg,
3648 &ll_bitsize, &ll_bitpos, &ll_mode,
3649 &ll_unsignedp, &volatilep, &ll_mask,
3651 lr_inner = decode_field_reference (lr_arg,
3652 &lr_bitsize, &lr_bitpos, &lr_mode,
3653 &lr_unsignedp, &volatilep, &lr_mask,
3655 rl_inner = decode_field_reference (rl_arg,
3656 &rl_bitsize, &rl_bitpos, &rl_mode,
3657 &rl_unsignedp, &volatilep, &rl_mask,
3659 rr_inner = decode_field_reference (rr_arg,
3660 &rr_bitsize, &rr_bitpos, &rr_mode,
3661 &rr_unsignedp, &volatilep, &rr_mask,
3664 /* It must be true that the inner operation on the lhs of each
3665 comparison must be the same if we are to be able to do anything.
3666 Then see if we have constants. If not, the same must be true for
3668 if (volatilep || ll_inner == 0 || rl_inner == 0
3669 || ! operand_equal_p (ll_inner, rl_inner, 0))
3672 if (TREE_CODE (lr_arg) == INTEGER_CST
3673 && TREE_CODE (rr_arg) == INTEGER_CST)
3674 l_const = lr_arg, r_const = rr_arg;
3675 else if (lr_inner == 0 || rr_inner == 0
3676 || ! operand_equal_p (lr_inner, rr_inner, 0))
3679 l_const = r_const = 0;
3681 /* If either comparison code is not correct for our logical operation,
3682 fail. However, we can convert a one-bit comparison against zero into
3683 the opposite comparison against that bit being set in the field. */
3685 wanted_code = (code == TRUTH_AND_EXPR ? EQ_EXPR : NE_EXPR);
3686 if (lcode != wanted_code)
3688 if (l_const && integer_zerop (l_const) && integer_pow2p (ll_mask))
3690 /* Make the left operand unsigned, since we are only interested
3691 in the value of one bit. Otherwise we are doing the wrong
3700 /* This is analogous to the code for l_const above. */
3701 if (rcode != wanted_code)
3703 if (r_const && integer_zerop (r_const) && integer_pow2p (rl_mask))
3712 /* See if we can find a mode that contains both fields being compared on
3713 the left. If we can't, fail. Otherwise, update all constants and masks
3714 to be relative to a field of that size. */
3715 first_bit = MIN (ll_bitpos, rl_bitpos);
3716 end_bit = MAX (ll_bitpos + ll_bitsize, rl_bitpos + rl_bitsize);
3717 lnmode = get_best_mode (end_bit - first_bit, first_bit,
3718 TYPE_ALIGN (TREE_TYPE (ll_inner)), word_mode,
3720 if (lnmode == VOIDmode)
3723 lnbitsize = GET_MODE_BITSIZE (lnmode);
3724 lnbitpos = first_bit & ~ (lnbitsize - 1);
3725 lntype = (*lang_hooks.types.type_for_size) (lnbitsize, 1);
3726 xll_bitpos = ll_bitpos - lnbitpos, xrl_bitpos = rl_bitpos - lnbitpos;
3728 if (BYTES_BIG_ENDIAN)
3730 xll_bitpos = lnbitsize - xll_bitpos - ll_bitsize;
3731 xrl_bitpos = lnbitsize - xrl_bitpos - rl_bitsize;
3734 ll_mask = const_binop (LSHIFT_EXPR, convert (lntype, ll_mask),
3735 size_int (xll_bitpos), 0);
3736 rl_mask = const_binop (LSHIFT_EXPR, convert (lntype, rl_mask),
3737 size_int (xrl_bitpos), 0);
3741 l_const = convert (lntype, l_const);
3742 l_const = unextend (l_const, ll_bitsize, ll_unsignedp, ll_and_mask);
3743 l_const = const_binop (LSHIFT_EXPR, l_const, size_int (xll_bitpos), 0);
3744 if (! integer_zerop (const_binop (BIT_AND_EXPR, l_const,
3745 fold (build1 (BIT_NOT_EXPR,
3749 warning ("comparison is always %d", wanted_code == NE_EXPR);
3751 return convert (truth_type,
3752 wanted_code == NE_EXPR
3753 ? integer_one_node : integer_zero_node);
3758 r_const = convert (lntype, r_const);
3759 r_const = unextend (r_const, rl_bitsize, rl_unsignedp, rl_and_mask);
3760 r_const = const_binop (LSHIFT_EXPR, r_const, size_int (xrl_bitpos), 0);
3761 if (! integer_zerop (const_binop (BIT_AND_EXPR, r_const,
3762 fold (build1 (BIT_NOT_EXPR,
3766 warning ("comparison is always %d", wanted_code == NE_EXPR);
3768 return convert (truth_type,
3769 wanted_code == NE_EXPR
3770 ? integer_one_node : integer_zero_node);
3774 /* If the right sides are not constant, do the same for it. Also,
3775 disallow this optimization if a size or signedness mismatch occurs
3776 between the left and right sides. */
3779 if (ll_bitsize != lr_bitsize || rl_bitsize != rr_bitsize
3780 || ll_unsignedp != lr_unsignedp || rl_unsignedp != rr_unsignedp
3781 /* Make sure the two fields on the right
3782 correspond to the left without being swapped. */
3783 || ll_bitpos - rl_bitpos != lr_bitpos - rr_bitpos)
3786 first_bit = MIN (lr_bitpos, rr_bitpos);
3787 end_bit = MAX (lr_bitpos + lr_bitsize, rr_bitpos + rr_bitsize);
3788 rnmode = get_best_mode (end_bit - first_bit, first_bit,
3789 TYPE_ALIGN (TREE_TYPE (lr_inner)), word_mode,
3791 if (rnmode == VOIDmode)
3794 rnbitsize = GET_MODE_BITSIZE (rnmode);
3795 rnbitpos = first_bit & ~ (rnbitsize - 1);
3796 rntype = (*lang_hooks.types.type_for_size) (rnbitsize, 1);
3797 xlr_bitpos = lr_bitpos - rnbitpos, xrr_bitpos = rr_bitpos - rnbitpos;
3799 if (BYTES_BIG_ENDIAN)
3801 xlr_bitpos = rnbitsize - xlr_bitpos - lr_bitsize;
3802 xrr_bitpos = rnbitsize - xrr_bitpos - rr_bitsize;
3805 lr_mask = const_binop (LSHIFT_EXPR, convert (rntype, lr_mask),
3806 size_int (xlr_bitpos), 0);
3807 rr_mask = const_binop (LSHIFT_EXPR, convert (rntype, rr_mask),
3808 size_int (xrr_bitpos), 0);
3810 /* Make a mask that corresponds to both fields being compared.
3811 Do this for both items being compared. If the operands are the
3812 same size and the bits being compared are in the same position
3813 then we can do this by masking both and comparing the masked
3815 ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
3816 lr_mask = const_binop (BIT_IOR_EXPR, lr_mask, rr_mask, 0);
3817 if (lnbitsize == rnbitsize && xll_bitpos == xlr_bitpos)
3819 lhs = make_bit_field_ref (ll_inner, lntype, lnbitsize, lnbitpos,
3820 ll_unsignedp || rl_unsignedp);
3821 if (! all_ones_mask_p (ll_mask, lnbitsize))
3822 lhs = build (BIT_AND_EXPR, lntype, lhs, ll_mask);
3824 rhs = make_bit_field_ref (lr_inner, rntype, rnbitsize, rnbitpos,
3825 lr_unsignedp || rr_unsignedp);
3826 if (! all_ones_mask_p (lr_mask, rnbitsize))
3827 rhs = build (BIT_AND_EXPR, rntype, rhs, lr_mask);
3829 return build (wanted_code, truth_type, lhs, rhs);
3832 /* There is still another way we can do something: If both pairs of
3833 fields being compared are adjacent, we may be able to make a wider
3834 field containing them both.
3836 Note that we still must mask the lhs/rhs expressions. Furthermore,
3837 the mask must be shifted to account for the shift done by
3838 make_bit_field_ref. */
3839 if ((ll_bitsize + ll_bitpos == rl_bitpos
3840 && lr_bitsize + lr_bitpos == rr_bitpos)
3841 || (ll_bitpos == rl_bitpos + rl_bitsize
3842 && lr_bitpos == rr_bitpos + rr_bitsize))
3846 lhs = make_bit_field_ref (ll_inner, lntype, ll_bitsize + rl_bitsize,
3847 MIN (ll_bitpos, rl_bitpos), ll_unsignedp);
3848 rhs = make_bit_field_ref (lr_inner, rntype, lr_bitsize + rr_bitsize,
3849 MIN (lr_bitpos, rr_bitpos), lr_unsignedp);
3851 ll_mask = const_binop (RSHIFT_EXPR, ll_mask,
3852 size_int (MIN (xll_bitpos, xrl_bitpos)), 0);
3853 lr_mask = const_binop (RSHIFT_EXPR, lr_mask,
3854 size_int (MIN (xlr_bitpos, xrr_bitpos)), 0);
3856 /* Convert to the smaller type before masking out unwanted bits. */
3858 if (lntype != rntype)
3860 if (lnbitsize > rnbitsize)
3862 lhs = convert (rntype, lhs);
3863 ll_mask = convert (rntype, ll_mask);
3866 else if (lnbitsize < rnbitsize)
3868 rhs = convert (lntype, rhs);
3869 lr_mask = convert (lntype, lr_mask);
3874 if (! all_ones_mask_p (ll_mask, ll_bitsize + rl_bitsize))
3875 lhs = build (BIT_AND_EXPR, type, lhs, ll_mask);
3877 if (! all_ones_mask_p (lr_mask, lr_bitsize + rr_bitsize))
3878 rhs = build (BIT_AND_EXPR, type, rhs, lr_mask);
3880 return build (wanted_code, truth_type, lhs, rhs);
3886 /* Handle the case of comparisons with constants. If there is something in
3887 common between the masks, those bits of the constants must be the same.
3888 If not, the condition is always false. Test for this to avoid generating
3889 incorrect code below. */
3890 result = const_binop (BIT_AND_EXPR, ll_mask, rl_mask, 0);
3891 if (! integer_zerop (result)
3892 && simple_cst_equal (const_binop (BIT_AND_EXPR, result, l_const, 0),
3893 const_binop (BIT_AND_EXPR, result, r_const, 0)) != 1)
3895 if (wanted_code == NE_EXPR)
3897 warning ("`or' of unmatched not-equal tests is always 1");
3898 return convert (truth_type, integer_one_node);
3902 warning ("`and' of mutually exclusive equal-tests is always 0");
3903 return convert (truth_type, integer_zero_node);
3907 /* Construct the expression we will return. First get the component
3908 reference we will make. Unless the mask is all ones the width of
3909 that field, perform the mask operation. Then compare with the
3911 result = make_bit_field_ref (ll_inner, lntype, lnbitsize, lnbitpos,
3912 ll_unsignedp || rl_unsignedp);
3914 ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
3915 if (! all_ones_mask_p (ll_mask, lnbitsize))
3916 result = build (BIT_AND_EXPR, lntype, result, ll_mask);
3918 return build (wanted_code, truth_type, result,
3919 const_binop (BIT_IOR_EXPR, l_const, r_const, 0));
3922 /* Optimize T, which is a comparison of a MIN_EXPR or MAX_EXPR with a
3926 optimize_minmax_comparison (t)
3929 tree type = TREE_TYPE (t);
3930 tree arg0 = TREE_OPERAND (t, 0);
3931 enum tree_code op_code;
3932 tree comp_const = TREE_OPERAND (t, 1);
3934 int consts_equal, consts_lt;
3937 STRIP_SIGN_NOPS (arg0);
3939 op_code = TREE_CODE (arg0);
3940 minmax_const = TREE_OPERAND (arg0, 1);
3941 consts_equal = tree_int_cst_equal (minmax_const, comp_const);
3942 consts_lt = tree_int_cst_lt (minmax_const, comp_const);
3943 inner = TREE_OPERAND (arg0, 0);
3945 /* If something does not permit us to optimize, return the original tree. */
3946 if ((op_code != MIN_EXPR && op_code != MAX_EXPR)
3947 || TREE_CODE (comp_const) != INTEGER_CST
3948 || TREE_CONSTANT_OVERFLOW (comp_const)
3949 || TREE_CODE (minmax_const) != INTEGER_CST
3950 || TREE_CONSTANT_OVERFLOW (minmax_const))
3953 /* Now handle all the various comparison codes. We only handle EQ_EXPR
3954 and GT_EXPR, doing the rest with recursive calls using logical
3956 switch (TREE_CODE (t))
3958 case NE_EXPR: case LT_EXPR: case LE_EXPR:
3960 invert_truthvalue (optimize_minmax_comparison (invert_truthvalue (t)));
3964 fold (build (TRUTH_ORIF_EXPR, type,
3965 optimize_minmax_comparison
3966 (build (EQ_EXPR, type, arg0, comp_const)),
3967 optimize_minmax_comparison
3968 (build (GT_EXPR, type, arg0, comp_const))));
3971 if (op_code == MAX_EXPR && consts_equal)
3972 /* MAX (X, 0) == 0 -> X <= 0 */
3973 return fold (build (LE_EXPR, type, inner, comp_const));
3975 else if (op_code == MAX_EXPR && consts_lt)
3976 /* MAX (X, 0) == 5 -> X == 5 */
3977 return fold (build (EQ_EXPR, type, inner, comp_const));
3979 else if (op_code == MAX_EXPR)
3980 /* MAX (X, 0) == -1 -> false */
3981 return omit_one_operand (type, integer_zero_node, inner);
3983 else if (consts_equal)
3984 /* MIN (X, 0) == 0 -> X >= 0 */
3985 return fold (build (GE_EXPR, type, inner, comp_const));
3988 /* MIN (X, 0) == 5 -> false */
3989 return omit_one_operand (type, integer_zero_node, inner);
3992 /* MIN (X, 0) == -1 -> X == -1 */
3993 return fold (build (EQ_EXPR, type, inner, comp_const));
3996 if (op_code == MAX_EXPR && (consts_equal || consts_lt))
3997 /* MAX (X, 0) > 0 -> X > 0
3998 MAX (X, 0) > 5 -> X > 5 */
3999 return fold (build (GT_EXPR, type, inner, comp_const));
4001 else if (op_code == MAX_EXPR)
4002 /* MAX (X, 0) > -1 -> true */
4003 return omit_one_operand (type, integer_one_node, inner);
4005 else if (op_code == MIN_EXPR && (consts_equal || consts_lt))
4006 /* MIN (X, 0) > 0 -> false
4007 MIN (X, 0) > 5 -> false */
4008 return omit_one_operand (type, integer_zero_node, inner);
4011 /* MIN (X, 0) > -1 -> X > -1 */
4012 return fold (build (GT_EXPR, type, inner, comp_const));
4019 /* T is an integer expression that is being multiplied, divided, or taken a
4020 modulus (CODE says which and what kind of divide or modulus) by a
4021 constant C. See if we can eliminate that operation by folding it with
4022 other operations already in T. WIDE_TYPE, if non-null, is a type that
4023 should be used for the computation if wider than our type.
4025 For example, if we are dividing (X * 8) + (Y * 16) by 4, we can return
4026 (X * 2) + (Y * 4). We must, however, be assured that either the original
4027 expression would not overflow or that overflow is undefined for the type
4028 in the language in question.
4030 We also canonicalize (X + 7) * 4 into X * 4 + 28 in the hope that either
4031 the machine has a multiply-accumulate insn or that this is part of an
4032 addressing calculation.
4034 If we return a non-null expression, it is an equivalent form of the
4035 original computation, but need not be in the original type. */
4038 extract_muldiv (t, c, code, wide_type)
4041 enum tree_code code;
4044 tree type = TREE_TYPE (t);
4045 enum tree_code tcode = TREE_CODE (t);
4046 tree ctype = (wide_type != 0 && (GET_MODE_SIZE (TYPE_MODE (wide_type))
4047 > GET_MODE_SIZE (TYPE_MODE (type)))
4048 ? wide_type : type);
4050 int same_p = tcode == code;
4051 tree op0 = NULL_TREE, op1 = NULL_TREE;
4053 /* Don't deal with constants of zero here; they confuse the code below. */
4054 if (integer_zerop (c))
4057 if (TREE_CODE_CLASS (tcode) == '1')
4058 op0 = TREE_OPERAND (t, 0);
4060 if (TREE_CODE_CLASS (tcode) == '2')
4061 op0 = TREE_OPERAND (t, 0), op1 = TREE_OPERAND (t, 1);
4063 /* Note that we need not handle conditional operations here since fold
4064 already handles those cases. So just do arithmetic here. */
4068 /* For a constant, we can always simplify if we are a multiply
4069 or (for divide and modulus) if it is a multiple of our constant. */
4070 if (code == MULT_EXPR
4071 || integer_zerop (const_binop (TRUNC_MOD_EXPR, t, c, 0)))
4072 return const_binop (code, convert (ctype, t), convert (ctype, c), 0);
4075 case CONVERT_EXPR: case NON_LVALUE_EXPR: case NOP_EXPR:
4076 /* If op0 is an expression ... */
4077 if ((TREE_CODE_CLASS (TREE_CODE (op0)) == '<'
4078 || TREE_CODE_CLASS (TREE_CODE (op0)) == '1'
4079 || TREE_CODE_CLASS (TREE_CODE (op0)) == '2'
4080 || TREE_CODE_CLASS (TREE_CODE (op0)) == 'e')
4081 /* ... and is unsigned, and its type is smaller than ctype,
4082 then we cannot pass through as widening. */
4083 && ((TREE_UNSIGNED (TREE_TYPE (op0))
4084 && ! (TREE_CODE (TREE_TYPE (op0)) == INTEGER_TYPE
4085 && TYPE_IS_SIZETYPE (TREE_TYPE (op0)))
4086 && (GET_MODE_SIZE (TYPE_MODE (ctype))
4087 > GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op0)))))
4088 /* ... or its type is larger than ctype,
4089 then we cannot pass through this truncation. */
4090 || (GET_MODE_SIZE (TYPE_MODE (ctype))
4091 < GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op0))))))
4094 /* Pass the constant down and see if we can make a simplification. If
4095 we can, replace this expression with the inner simplification for
4096 possible later conversion to our or some other type. */
4097 if (0 != (t1 = extract_muldiv (op0, convert (TREE_TYPE (op0), c), code,
4098 code == MULT_EXPR ? ctype : NULL_TREE)))
4102 case NEGATE_EXPR: case ABS_EXPR:
4103 if ((t1 = extract_muldiv (op0, c, code, wide_type)) != 0)
4104 return fold (build1 (tcode, ctype, convert (ctype, t1)));
4107 case MIN_EXPR: case MAX_EXPR:
4108 /* If widening the type changes the signedness, then we can't perform
4109 this optimization as that changes the result. */
4110 if (TREE_UNSIGNED (ctype) != TREE_UNSIGNED (type))
4113 /* MIN (a, b) / 5 -> MIN (a / 5, b / 5) */
4114 if ((t1 = extract_muldiv (op0, c, code, wide_type)) != 0
4115 && (t2 = extract_muldiv (op1, c, code, wide_type)) != 0)
4117 if (tree_int_cst_sgn (c) < 0)
4118 tcode = (tcode == MIN_EXPR ? MAX_EXPR : MIN_EXPR);
4120 return fold (build (tcode, ctype, convert (ctype, t1),
4121 convert (ctype, t2)));
4125 case WITH_RECORD_EXPR:
4126 if ((t1 = extract_muldiv (TREE_OPERAND (t, 0), c, code, wide_type)) != 0)
4127 return build (WITH_RECORD_EXPR, TREE_TYPE (t1), t1,
4128 TREE_OPERAND (t, 1));
4132 /* If this has not been evaluated and the operand has no side effects,
4133 we can see if we can do something inside it and make a new one.
4134 Note that this test is overly conservative since we can do this
4135 if the only reason it had side effects is that it was another
4136 similar SAVE_EXPR, but that isn't worth bothering with. */
4137 if (SAVE_EXPR_RTL (t) == 0 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (t, 0))
4138 && 0 != (t1 = extract_muldiv (TREE_OPERAND (t, 0), c, code,
4141 t1 = save_expr (t1);
4142 if (SAVE_EXPR_PERSISTENT_P (t) && TREE_CODE (t1) == SAVE_EXPR)
4143 SAVE_EXPR_PERSISTENT_P (t1) = 1;
4144 if (is_pending_size (t))
4145 put_pending_size (t1);
4150 case LSHIFT_EXPR: case RSHIFT_EXPR:
4151 /* If the second operand is constant, this is a multiplication
4152 or floor division, by a power of two, so we can treat it that
4153 way unless the multiplier or divisor overflows. */
4154 if (TREE_CODE (op1) == INTEGER_CST
4155 /* const_binop may not detect overflow correctly,
4156 so check for it explicitly here. */
4157 && TYPE_PRECISION (TREE_TYPE (size_one_node)) > TREE_INT_CST_LOW (op1)
4158 && TREE_INT_CST_HIGH (op1) == 0
4159 && 0 != (t1 = convert (ctype,
4160 const_binop (LSHIFT_EXPR, size_one_node,
4162 && ! TREE_OVERFLOW (t1))
4163 return extract_muldiv (build (tcode == LSHIFT_EXPR
4164 ? MULT_EXPR : FLOOR_DIV_EXPR,
4165 ctype, convert (ctype, op0), t1),
4166 c, code, wide_type);
4169 case PLUS_EXPR: case MINUS_EXPR:
4170 /* See if we can eliminate the operation on both sides. If we can, we
4171 can return a new PLUS or MINUS. If we can't, the only remaining
4172 cases where we can do anything are if the second operand is a
4174 t1 = extract_muldiv (op0, c, code, wide_type);
4175 t2 = extract_muldiv (op1, c, code, wide_type);
4176 if (t1 != 0 && t2 != 0
4177 && (code == MULT_EXPR
4178 /* If not multiplication, we can only do this if either operand
4179 is divisible by c. */
4180 || multiple_of_p (ctype, op0, c)
4181 || multiple_of_p (ctype, op1, c)))
4182 return fold (build (tcode, ctype, convert (ctype, t1),
4183 convert (ctype, t2)));
4185 /* If this was a subtraction, negate OP1 and set it to be an addition.
4186 This simplifies the logic below. */
4187 if (tcode == MINUS_EXPR)
4188 tcode = PLUS_EXPR, op1 = negate_expr (op1);
4190 if (TREE_CODE (op1) != INTEGER_CST)
4193 /* If either OP1 or C are negative, this optimization is not safe for
4194 some of the division and remainder types while for others we need
4195 to change the code. */
4196 if (tree_int_cst_sgn (op1) < 0 || tree_int_cst_sgn (c) < 0)
4198 if (code == CEIL_DIV_EXPR)
4199 code = FLOOR_DIV_EXPR;
4200 else if (code == FLOOR_DIV_EXPR)
4201 code = CEIL_DIV_EXPR;
4202 else if (code != MULT_EXPR
4203 && code != CEIL_MOD_EXPR && code != FLOOR_MOD_EXPR)
4207 /* If it's a multiply or a division/modulus operation of a multiple
4208 of our constant, do the operation and verify it doesn't overflow. */
4209 if (code == MULT_EXPR
4210 || integer_zerop (const_binop (TRUNC_MOD_EXPR, op1, c, 0)))
4212 op1 = const_binop (code, convert (ctype, op1), convert (ctype, c), 0);
4213 if (op1 == 0 || TREE_OVERFLOW (op1))
4219 /* If we have an unsigned type is not a sizetype, we cannot widen
4220 the operation since it will change the result if the original
4221 computation overflowed. */
4222 if (TREE_UNSIGNED (ctype)
4223 && ! (TREE_CODE (ctype) == INTEGER_TYPE && TYPE_IS_SIZETYPE (ctype))
4227 /* If we were able to eliminate our operation from the first side,
4228 apply our operation to the second side and reform the PLUS. */
4229 if (t1 != 0 && (TREE_CODE (t1) != code || code == MULT_EXPR))
4230 return fold (build (tcode, ctype, convert (ctype, t1), op1));
4232 /* The last case is if we are a multiply. In that case, we can
4233 apply the distributive law to commute the multiply and addition
4234 if the multiplication of the constants doesn't overflow. */
4235 if (code == MULT_EXPR)
4236 return fold (build (tcode, ctype, fold (build (code, ctype,
4237 convert (ctype, op0),
4238 convert (ctype, c))),
4244 /* We have a special case here if we are doing something like
4245 (C * 8) % 4 since we know that's zero. */
4246 if ((code == TRUNC_MOD_EXPR || code == CEIL_MOD_EXPR
4247 || code == FLOOR_MOD_EXPR || code == ROUND_MOD_EXPR)
4248 && TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST
4249 && integer_zerop (const_binop (TRUNC_MOD_EXPR, op1, c, 0)))
4250 return omit_one_operand (type, integer_zero_node, op0);
4252 /* ... fall through ... */
4254 case TRUNC_DIV_EXPR: case CEIL_DIV_EXPR: case FLOOR_DIV_EXPR:
4255 case ROUND_DIV_EXPR: case EXACT_DIV_EXPR:
4256 /* If we can extract our operation from the LHS, do so and return a
4257 new operation. Likewise for the RHS from a MULT_EXPR. Otherwise,
4258 do something only if the second operand is a constant. */
4260 && (t1 = extract_muldiv (op0, c, code, wide_type)) != 0)
4261 return fold (build (tcode, ctype, convert (ctype, t1),
4262 convert (ctype, op1)));
4263 else if (tcode == MULT_EXPR && code == MULT_EXPR
4264 && (t1 = extract_muldiv (op1, c, code, wide_type)) != 0)
4265 return fold (build (tcode, ctype, convert (ctype, op0),
4266 convert (ctype, t1)));
4267 else if (TREE_CODE (op1) != INTEGER_CST)
4270 /* If these are the same operation types, we can associate them
4271 assuming no overflow. */
4273 && 0 != (t1 = const_binop (MULT_EXPR, convert (ctype, op1),
4274 convert (ctype, c), 0))
4275 && ! TREE_OVERFLOW (t1))
4276 return fold (build (tcode, ctype, convert (ctype, op0), t1));
4278 /* If these operations "cancel" each other, we have the main
4279 optimizations of this pass, which occur when either constant is a
4280 multiple of the other, in which case we replace this with either an
4281 operation or CODE or TCODE.
4283 If we have an unsigned type that is not a sizetype, we cannot do
4284 this since it will change the result if the original computation
4286 if ((! TREE_UNSIGNED (ctype)
4287 || (TREE_CODE (ctype) == INTEGER_TYPE && TYPE_IS_SIZETYPE (ctype)))
4288 && ((code == MULT_EXPR && tcode == EXACT_DIV_EXPR)
4289 || (tcode == MULT_EXPR
4290 && code != TRUNC_MOD_EXPR && code != CEIL_MOD_EXPR
4291 && code != FLOOR_MOD_EXPR && code != ROUND_MOD_EXPR)))
4293 if (integer_zerop (const_binop (TRUNC_MOD_EXPR, op1, c, 0)))
4294 return fold (build (tcode, ctype, convert (ctype, op0),
4296 const_binop (TRUNC_DIV_EXPR,
4298 else if (integer_zerop (const_binop (TRUNC_MOD_EXPR, c, op1, 0)))
4299 return fold (build (code, ctype, convert (ctype, op0),
4301 const_binop (TRUNC_DIV_EXPR,
4313 /* If T contains a COMPOUND_EXPR which was inserted merely to evaluate
4314 S, a SAVE_EXPR, return the expression actually being evaluated. Note
4315 that we may sometimes modify the tree. */
4318 strip_compound_expr (t, s)
4322 enum tree_code code = TREE_CODE (t);
4324 /* See if this is the COMPOUND_EXPR we want to eliminate. */
4325 if (code == COMPOUND_EXPR && TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR
4326 && TREE_OPERAND (TREE_OPERAND (t, 0), 0) == s)
4327 return TREE_OPERAND (t, 1);
4329 /* See if this is a COND_EXPR or a simple arithmetic operator. We
4330 don't bother handling any other types. */
4331 else if (code == COND_EXPR)
4333 TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4334 TREE_OPERAND (t, 1) = strip_compound_expr (TREE_OPERAND (t, 1), s);
4335 TREE_OPERAND (t, 2) = strip_compound_expr (TREE_OPERAND (t, 2), s);
4337 else if (TREE_CODE_CLASS (code) == '1')
4338 TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4339 else if (TREE_CODE_CLASS (code) == '<'
4340 || TREE_CODE_CLASS (code) == '2')
4342 TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4343 TREE_OPERAND (t, 1) = strip_compound_expr (TREE_OPERAND (t, 1), s);
4349 /* Return a node which has the indicated constant VALUE (either 0 or
4350 1), and is of the indicated TYPE. */
4353 constant_boolean_node (value, type)
4357 if (type == integer_type_node)
4358 return value ? integer_one_node : integer_zero_node;
4359 else if (TREE_CODE (type) == BOOLEAN_TYPE)
4360 return (*lang_hooks.truthvalue_conversion) (value ? integer_one_node :
4364 tree t = build_int_2 (value, 0);
4366 TREE_TYPE (t) = type;
4371 /* Utility function for the following routine, to see how complex a nesting of
4372 COND_EXPRs can be. EXPR is the expression and LIMIT is a count beyond which
4373 we don't care (to avoid spending too much time on complex expressions.). */
4376 count_cond (expr, lim)
4382 if (TREE_CODE (expr) != COND_EXPR)
4387 ctrue = count_cond (TREE_OPERAND (expr, 1), lim - 1);
4388 cfalse = count_cond (TREE_OPERAND (expr, 2), lim - 1 - ctrue);
4389 return MIN (lim, 1 + ctrue + cfalse);
4392 /* Transform `a + (b ? x : y)' into `b ? (a + x) : (a + y)'.
4393 Transform, `a + (x < y)' into `(x < y) ? (a + 1) : (a + 0)'. Here
4394 CODE corresponds to the `+', COND to the `(b ? x : y)' or `(x < y)'
4395 expression, and ARG to `a'. If COND_FIRST_P is non-zero, then the
4396 COND is the first argument to CODE; otherwise (as in the example
4397 given here), it is the second argument. TYPE is the type of the
4398 original expression. */
4401 fold_binary_op_with_conditional_arg (code, type, cond, arg, cond_first_p)
4402 enum tree_code code;
4408 tree test, true_value, false_value;
4409 tree lhs = NULL_TREE;
4410 tree rhs = NULL_TREE;
4411 /* In the end, we'll produce a COND_EXPR. Both arms of the
4412 conditional expression will be binary operations. The left-hand
4413 side of the expression to be executed if the condition is true
4414 will be pointed to by TRUE_LHS. Similarly, the right-hand side
4415 of the expression to be executed if the condition is true will be
4416 pointed to by TRUE_RHS. FALSE_LHS and FALSE_RHS are analogous --
4417 but apply to the expression to be executed if the conditional is
4423 /* These are the codes to use for the left-hand side and right-hand
4424 side of the COND_EXPR. Normally, they are the same as CODE. */
4425 enum tree_code lhs_code = code;
4426 enum tree_code rhs_code = code;
4427 /* And these are the types of the expressions. */
4428 tree lhs_type = type;
4429 tree rhs_type = type;
4433 true_rhs = false_rhs = &arg;
4434 true_lhs = &true_value;
4435 false_lhs = &false_value;
4439 true_lhs = false_lhs = &arg;
4440 true_rhs = &true_value;
4441 false_rhs = &false_value;
4444 if (TREE_CODE (cond) == COND_EXPR)
4446 test = TREE_OPERAND (cond, 0);
4447 true_value = TREE_OPERAND (cond, 1);
4448 false_value = TREE_OPERAND (cond, 2);
4449 /* If this operand throws an expression, then it does not make
4450 sense to try to perform a logical or arithmetic operation
4451 involving it. Instead of building `a + throw 3' for example,
4452 we simply build `a, throw 3'. */
4453 if (VOID_TYPE_P (TREE_TYPE (true_value)))
4455 lhs_code = COMPOUND_EXPR;
4457 lhs_type = void_type_node;
4459 if (VOID_TYPE_P (TREE_TYPE (false_value)))
4461 rhs_code = COMPOUND_EXPR;
4463 rhs_type = void_type_node;
4468 tree testtype = TREE_TYPE (cond);
4470 true_value = convert (testtype, integer_one_node);
4471 false_value = convert (testtype, integer_zero_node);
4474 /* If ARG is complex we want to make sure we only evaluate
4475 it once. Though this is only required if it is volatile, it
4476 might be more efficient even if it is not. However, if we
4477 succeed in folding one part to a constant, we do not need
4478 to make this SAVE_EXPR. Since we do this optimization
4479 primarily to see if we do end up with constant and this
4480 SAVE_EXPR interferes with later optimizations, suppressing
4481 it when we can is important.
4483 If we are not in a function, we can't make a SAVE_EXPR, so don't
4484 try to do so. Don't try to see if the result is a constant
4485 if an arm is a COND_EXPR since we get exponential behavior
4488 if (TREE_CODE (arg) != SAVE_EXPR && ! TREE_CONSTANT (arg)
4489 && (*lang_hooks.decls.global_bindings_p) () == 0
4490 && ((TREE_CODE (arg) != VAR_DECL
4491 && TREE_CODE (arg) != PARM_DECL)
4492 || TREE_SIDE_EFFECTS (arg)))
4494 if (TREE_CODE (true_value) != COND_EXPR)
4495 lhs = fold (build (lhs_code, lhs_type, *true_lhs, *true_rhs));
4497 if (TREE_CODE (false_value) != COND_EXPR)
4498 rhs = fold (build (rhs_code, rhs_type, *false_lhs, *false_rhs));
4500 if ((lhs == 0 || ! TREE_CONSTANT (lhs))
4501 && (rhs == 0 || !TREE_CONSTANT (rhs)))
4502 arg = save_expr (arg), lhs = rhs = 0;
4506 lhs = fold (build (lhs_code, lhs_type, *true_lhs, *true_rhs));
4508 rhs = fold (build (rhs_code, rhs_type, *false_lhs, *false_rhs));
4510 test = fold (build (COND_EXPR, type, test, lhs, rhs));
4512 if (TREE_CODE (arg) == SAVE_EXPR)
4513 return build (COMPOUND_EXPR, type,
4514 convert (void_type_node, arg),
4515 strip_compound_expr (test, arg));
4517 return convert (type, test);
4521 /* Subroutine of fold() that checks for the addition of +/- 0.0.
4523 If !NEGATE, return true if ADDEND is +/-0.0 and, for all X of type
4524 TYPE, X + ADDEND is the same as X. If NEGATE, return true if X -
4525 ADDEND is the same as X.
4527 X + 0 and X - 0 both give X when X is NaN, infinite, or non-zero
4528 and finite. The problematic cases are when X is zero, and its mode
4529 has signed zeros. In the case of rounding towards -infinity,
4530 X - 0 is not the same as X because 0 - 0 is -0. In other rounding
4531 modes, X + 0 is not the same as X because -0 + 0 is 0. */
4534 fold_real_zero_addition_p (type, addend, negate)
4538 if (!real_zerop (addend))
4541 /* Allow the fold if zeros aren't signed, or their sign isn't important. */
4542 if (!HONOR_SIGNED_ZEROS (TYPE_MODE (type)))
4545 /* Treat x + -0 as x - 0 and x - -0 as x + 0. */
4546 if (TREE_CODE (addend) == REAL_CST
4547 && REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (addend)))
4550 /* The mode has signed zeros, and we have to honor their sign.
4551 In this situation, there is only one case we can return true for.
4552 X - 0 is the same as X unless rounding towards -infinity is
4554 return negate && !HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (type));
4558 /* Perform constant folding and related simplification of EXPR.
4559 The related simplifications include x*1 => x, x*0 => 0, etc.,
4560 and application of the associative law.
4561 NOP_EXPR conversions may be removed freely (as long as we
4562 are careful not to change the C type of the overall expression)
4563 We cannot simplify through a CONVERT_EXPR, FIX_EXPR or FLOAT_EXPR,
4564 but we can constant-fold them if they have constant operands. */
4571 tree t1 = NULL_TREE;
4573 tree type = TREE_TYPE (expr);
4574 tree arg0 = NULL_TREE, arg1 = NULL_TREE;
4575 enum tree_code code = TREE_CODE (t);
4576 int kind = TREE_CODE_CLASS (code);
4578 /* WINS will be nonzero when the switch is done
4579 if all operands are constant. */
4582 /* Don't try to process an RTL_EXPR since its operands aren't trees.
4583 Likewise for a SAVE_EXPR that's already been evaluated. */
4584 if (code == RTL_EXPR || (code == SAVE_EXPR && SAVE_EXPR_RTL (t) != 0))
4587 /* Return right away if a constant. */
4591 #ifdef MAX_INTEGER_COMPUTATION_MODE
4592 check_max_integer_computation_mode (expr);
4595 if (code == NOP_EXPR || code == FLOAT_EXPR || code == CONVERT_EXPR)
4599 /* Special case for conversion ops that can have fixed point args. */
4600 arg0 = TREE_OPERAND (t, 0);
4602 /* Don't use STRIP_NOPS, because signedness of argument type matters. */
4604 STRIP_SIGN_NOPS (arg0);
4606 if (arg0 != 0 && TREE_CODE (arg0) == COMPLEX_CST)
4607 subop = TREE_REALPART (arg0);
4611 if (subop != 0 && TREE_CODE (subop) != INTEGER_CST
4612 && TREE_CODE (subop) != REAL_CST
4614 /* Note that TREE_CONSTANT isn't enough:
4615 static var addresses are constant but we can't
4616 do arithmetic on them. */
4619 else if (IS_EXPR_CODE_CLASS (kind) || kind == 'r')
4621 int len = first_rtl_op (code);
4623 for (i = 0; i < len; i++)
4625 tree op = TREE_OPERAND (t, i);
4629 continue; /* Valid for CALL_EXPR, at least. */
4631 if (kind == '<' || code == RSHIFT_EXPR)
4633 /* Signedness matters here. Perhaps we can refine this
4635 STRIP_SIGN_NOPS (op);
4638 /* Strip any conversions that don't change the mode. */
4641 if (TREE_CODE (op) == COMPLEX_CST)
4642 subop = TREE_REALPART (op);
4646 if (TREE_CODE (subop) != INTEGER_CST
4647 && TREE_CODE (subop) != REAL_CST)
4648 /* Note that TREE_CONSTANT isn't enough:
4649 static var addresses are constant but we can't
4650 do arithmetic on them. */
4660 /* If this is a commutative operation, and ARG0 is a constant, move it
4661 to ARG1 to reduce the number of tests below. */
4662 if ((code == PLUS_EXPR || code == MULT_EXPR || code == MIN_EXPR
4663 || code == MAX_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR
4664 || code == BIT_AND_EXPR)
4665 && (TREE_CODE (arg0) == INTEGER_CST || TREE_CODE (arg0) == REAL_CST))
4667 tem = arg0; arg0 = arg1; arg1 = tem;
4669 tem = TREE_OPERAND (t, 0); TREE_OPERAND (t, 0) = TREE_OPERAND (t, 1);
4670 TREE_OPERAND (t, 1) = tem;
4673 /* Now WINS is set as described above,
4674 ARG0 is the first operand of EXPR,
4675 and ARG1 is the second operand (if it has more than one operand).
4677 First check for cases where an arithmetic operation is applied to a
4678 compound, conditional, or comparison operation. Push the arithmetic
4679 operation inside the compound or conditional to see if any folding
4680 can then be done. Convert comparison to conditional for this purpose.
4681 The also optimizes non-constant cases that used to be done in
4684 Before we do that, see if this is a BIT_AND_EXPR or a BIT_IOR_EXPR,
4685 one of the operands is a comparison and the other is a comparison, a
4686 BIT_AND_EXPR with the constant 1, or a truth value. In that case, the
4687 code below would make the expression more complex. Change it to a
4688 TRUTH_{AND,OR}_EXPR. Likewise, convert a similar NE_EXPR to
4689 TRUTH_XOR_EXPR and an EQ_EXPR to the inversion of a TRUTH_XOR_EXPR. */
4691 if ((code == BIT_AND_EXPR || code == BIT_IOR_EXPR
4692 || code == EQ_EXPR || code == NE_EXPR)
4693 && ((truth_value_p (TREE_CODE (arg0))
4694 && (truth_value_p (TREE_CODE (arg1))
4695 || (TREE_CODE (arg1) == BIT_AND_EXPR
4696 && integer_onep (TREE_OPERAND (arg1, 1)))))
4697 || (truth_value_p (TREE_CODE (arg1))
4698 && (truth_value_p (TREE_CODE (arg0))
4699 || (TREE_CODE (arg0) == BIT_AND_EXPR
4700 && integer_onep (TREE_OPERAND (arg0, 1)))))))
4702 t = fold (build (code == BIT_AND_EXPR ? TRUTH_AND_EXPR
4703 : code == BIT_IOR_EXPR ? TRUTH_OR_EXPR
4707 if (code == EQ_EXPR)
4708 t = invert_truthvalue (t);
4713 if (TREE_CODE_CLASS (code) == '1')
4715 if (TREE_CODE (arg0) == COMPOUND_EXPR)
4716 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4717 fold (build1 (code, type, TREE_OPERAND (arg0, 1))));
4718 else if (TREE_CODE (arg0) == COND_EXPR)
4720 t = fold (build (COND_EXPR, type, TREE_OPERAND (arg0, 0),
4721 fold (build1 (code, type, TREE_OPERAND (arg0, 1))),
4722 fold (build1 (code, type, TREE_OPERAND (arg0, 2)))));
4724 /* If this was a conversion, and all we did was to move into
4725 inside the COND_EXPR, bring it back out. But leave it if
4726 it is a conversion from integer to integer and the
4727 result precision is no wider than a word since such a
4728 conversion is cheap and may be optimized away by combine,
4729 while it couldn't if it were outside the COND_EXPR. Then return
4730 so we don't get into an infinite recursion loop taking the
4731 conversion out and then back in. */
4733 if ((code == NOP_EXPR || code == CONVERT_EXPR
4734 || code == NON_LVALUE_EXPR)
4735 && TREE_CODE (t) == COND_EXPR
4736 && TREE_CODE (TREE_OPERAND (t, 1)) == code
4737 && TREE_CODE (TREE_OPERAND (t, 2)) == code
4738 && (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0))
4739 == TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 2), 0)))
4740 && ! (INTEGRAL_TYPE_P (TREE_TYPE (t))
4742 (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0))))
4743 && TYPE_PRECISION (TREE_TYPE (t)) <= BITS_PER_WORD))
4744 t = build1 (code, type,
4746 TREE_TYPE (TREE_OPERAND
4747 (TREE_OPERAND (t, 1), 0)),
4748 TREE_OPERAND (t, 0),
4749 TREE_OPERAND (TREE_OPERAND (t, 1), 0),
4750 TREE_OPERAND (TREE_OPERAND (t, 2), 0)));
4753 else if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<')
4754 return fold (build (COND_EXPR, type, arg0,
4755 fold (build1 (code, type, integer_one_node)),
4756 fold (build1 (code, type, integer_zero_node))));
4758 else if (TREE_CODE_CLASS (code) == '2'
4759 || TREE_CODE_CLASS (code) == '<')
4761 if (TREE_CODE (arg1) == COMPOUND_EXPR)
4762 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
4763 fold (build (code, type,
4764 arg0, TREE_OPERAND (arg1, 1))));
4765 else if ((TREE_CODE (arg1) == COND_EXPR
4766 || (TREE_CODE_CLASS (TREE_CODE (arg1)) == '<'
4767 && TREE_CODE_CLASS (code) != '<'))
4768 && (TREE_CODE (arg0) != COND_EXPR
4769 || count_cond (arg0, 25) + count_cond (arg1, 25) <= 25)
4770 && (! TREE_SIDE_EFFECTS (arg0)
4771 || ((*lang_hooks.decls.global_bindings_p) () == 0
4772 && ! contains_placeholder_p (arg0))))
4774 fold_binary_op_with_conditional_arg (code, type, arg1, arg0,
4775 /*cond_first_p=*/0);
4776 else if (TREE_CODE (arg0) == COMPOUND_EXPR)
4777 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4778 fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4779 else if ((TREE_CODE (arg0) == COND_EXPR
4780 || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
4781 && TREE_CODE_CLASS (code) != '<'))
4782 && (TREE_CODE (arg1) != COND_EXPR
4783 || count_cond (arg0, 25) + count_cond (arg1, 25) <= 25)
4784 && (! TREE_SIDE_EFFECTS (arg1)
4785 || ((*lang_hooks.decls.global_bindings_p) () == 0
4786 && ! contains_placeholder_p (arg1))))
4788 fold_binary_op_with_conditional_arg (code, type, arg0, arg1,
4789 /*cond_first_p=*/1);
4791 else if (TREE_CODE_CLASS (code) == '<'
4792 && TREE_CODE (arg0) == COMPOUND_EXPR)
4793 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4794 fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4795 else if (TREE_CODE_CLASS (code) == '<'
4796 && TREE_CODE (arg1) == COMPOUND_EXPR)
4797 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
4798 fold (build (code, type, arg0, TREE_OPERAND (arg1, 1))));
4811 return fold (DECL_INITIAL (t));
4816 case FIX_TRUNC_EXPR:
4817 /* Other kinds of FIX are not handled properly by fold_convert. */
4819 if (TREE_TYPE (TREE_OPERAND (t, 0)) == TREE_TYPE (t))
4820 return TREE_OPERAND (t, 0);
4822 /* Handle cases of two conversions in a row. */
4823 if (TREE_CODE (TREE_OPERAND (t, 0)) == NOP_EXPR
4824 || TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR)
4826 tree inside_type = TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4827 tree inter_type = TREE_TYPE (TREE_OPERAND (t, 0));
4828 tree final_type = TREE_TYPE (t);
4829 int inside_int = INTEGRAL_TYPE_P (inside_type);
4830 int inside_ptr = POINTER_TYPE_P (inside_type);
4831 int inside_float = FLOAT_TYPE_P (inside_type);
4832 unsigned int inside_prec = TYPE_PRECISION (inside_type);
4833 int inside_unsignedp = TREE_UNSIGNED (inside_type);
4834 int inter_int = INTEGRAL_TYPE_P (inter_type);
4835 int inter_ptr = POINTER_TYPE_P (inter_type);
4836 int inter_float = FLOAT_TYPE_P (inter_type);
4837 unsigned int inter_prec = TYPE_PRECISION (inter_type);
4838 int inter_unsignedp = TREE_UNSIGNED (inter_type);
4839 int final_int = INTEGRAL_TYPE_P (final_type);
4840 int final_ptr = POINTER_TYPE_P (final_type);
4841 int final_float = FLOAT_TYPE_P (final_type);
4842 unsigned int final_prec = TYPE_PRECISION (final_type);
4843 int final_unsignedp = TREE_UNSIGNED (final_type);
4845 /* In addition to the cases of two conversions in a row
4846 handled below, if we are converting something to its own
4847 type via an object of identical or wider precision, neither
4848 conversion is needed. */
4849 if (TYPE_MAIN_VARIANT (inside_type) == TYPE_MAIN_VARIANT (final_type)
4850 && ((inter_int && final_int) || (inter_float && final_float))
4851 && inter_prec >= final_prec)
4852 return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4854 /* Likewise, if the intermediate and final types are either both
4855 float or both integer, we don't need the middle conversion if
4856 it is wider than the final type and doesn't change the signedness
4857 (for integers). Avoid this if the final type is a pointer
4858 since then we sometimes need the inner conversion. Likewise if
4859 the outer has a precision not equal to the size of its mode. */
4860 if ((((inter_int || inter_ptr) && (inside_int || inside_ptr))
4861 || (inter_float && inside_float))
4862 && inter_prec >= inside_prec
4863 && (inter_float || inter_unsignedp == inside_unsignedp)
4864 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4865 && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4867 return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4869 /* If we have a sign-extension of a zero-extended value, we can
4870 replace that by a single zero-extension. */
4871 if (inside_int && inter_int && final_int
4872 && inside_prec < inter_prec && inter_prec < final_prec
4873 && inside_unsignedp && !inter_unsignedp)
4874 return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4876 /* Two conversions in a row are not needed unless:
4877 - some conversion is floating-point (overstrict for now), or
4878 - the intermediate type is narrower than both initial and
4880 - the intermediate type and innermost type differ in signedness,
4881 and the outermost type is wider than the intermediate, or
4882 - the initial type is a pointer type and the precisions of the
4883 intermediate and final types differ, or
4884 - the final type is a pointer type and the precisions of the
4885 initial and intermediate types differ. */
4886 if (! inside_float && ! inter_float && ! final_float
4887 && (inter_prec > inside_prec || inter_prec > final_prec)
4888 && ! (inside_int && inter_int
4889 && inter_unsignedp != inside_unsignedp
4890 && inter_prec < final_prec)
4891 && ((inter_unsignedp && inter_prec > inside_prec)
4892 == (final_unsignedp && final_prec > inter_prec))
4893 && ! (inside_ptr && inter_prec != final_prec)
4894 && ! (final_ptr && inside_prec != inter_prec)
4895 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4896 && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4898 return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4901 if (TREE_CODE (TREE_OPERAND (t, 0)) == MODIFY_EXPR
4902 && TREE_CONSTANT (TREE_OPERAND (TREE_OPERAND (t, 0), 1))
4903 /* Detect assigning a bitfield. */
4904 && !(TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == COMPONENT_REF
4905 && DECL_BIT_FIELD (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 1))))
4907 /* Don't leave an assignment inside a conversion
4908 unless assigning a bitfield. */
4909 tree prev = TREE_OPERAND (t, 0);
4910 TREE_OPERAND (t, 0) = TREE_OPERAND (prev, 1);
4911 /* First do the assignment, then return converted constant. */
4912 t = build (COMPOUND_EXPR, TREE_TYPE (t), prev, fold (t));
4917 /* Convert (T)(x & c) into (T)x & (T)c, if c is an integer
4918 constants (if x has signed type, the sign bit cannot be set
4919 in c). This folds extension into the BIT_AND_EXPR. */
4920 if (INTEGRAL_TYPE_P (TREE_TYPE (t))
4921 && TREE_CODE (TREE_TYPE (t)) != BOOLEAN_TYPE
4922 && TREE_CODE (TREE_OPERAND (t, 0)) == BIT_AND_EXPR
4923 && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 1)) == INTEGER_CST)
4925 tree and = TREE_OPERAND (t, 0);
4926 tree and0 = TREE_OPERAND (and, 0), and1 = TREE_OPERAND (and, 1);
4929 if (TREE_UNSIGNED (TREE_TYPE (and))
4930 || (TYPE_PRECISION (TREE_TYPE (t))
4931 <= TYPE_PRECISION (TREE_TYPE (and))))
4933 else if (TYPE_PRECISION (TREE_TYPE (and1))
4934 <= HOST_BITS_PER_WIDE_INT
4935 && host_integerp (and1, 1))
4937 unsigned HOST_WIDE_INT cst;
4939 cst = tree_low_cst (and1, 1);
4940 cst &= (HOST_WIDE_INT) -1
4941 << (TYPE_PRECISION (TREE_TYPE (and1)) - 1);
4942 change = (cst == 0);
4943 #ifdef LOAD_EXTEND_OP
4945 && (LOAD_EXTEND_OP (TYPE_MODE (TREE_TYPE (and0)))
4948 tree uns = (*lang_hooks.types.unsigned_type) (TREE_TYPE (and0));
4949 and0 = convert (uns, and0);
4950 and1 = convert (uns, and1);
4955 return fold (build (BIT_AND_EXPR, TREE_TYPE (t),
4956 convert (TREE_TYPE (t), and0),
4957 convert (TREE_TYPE (t), and1)));
4962 TREE_CONSTANT (t) = TREE_CONSTANT (arg0);
4965 return fold_convert (t, arg0);
4967 case VIEW_CONVERT_EXPR:
4968 if (TREE_CODE (TREE_OPERAND (t, 0)) == VIEW_CONVERT_EXPR)
4969 return build1 (VIEW_CONVERT_EXPR, type,
4970 TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4974 if (TREE_CODE (arg0) == CONSTRUCTOR)
4976 tree m = purpose_member (arg1, CONSTRUCTOR_ELTS (arg0));
4983 TREE_CONSTANT (t) = wins;
4989 if (TREE_CODE (arg0) == INTEGER_CST)
4991 unsigned HOST_WIDE_INT low;
4993 int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4994 TREE_INT_CST_HIGH (arg0),
4996 t = build_int_2 (low, high);
4997 TREE_TYPE (t) = type;
4999 = (TREE_OVERFLOW (arg0)
5000 | force_fit_type (t, overflow && !TREE_UNSIGNED (type)));
5001 TREE_CONSTANT_OVERFLOW (t)
5002 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
5004 else if (TREE_CODE (arg0) == REAL_CST)
5005 t = build_real (type, REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
5007 else if (TREE_CODE (arg0) == NEGATE_EXPR)
5008 return TREE_OPERAND (arg0, 0);
5010 /* Convert - (a - b) to (b - a) for non-floating-point. */
5011 else if (TREE_CODE (arg0) == MINUS_EXPR
5012 && (! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations))
5013 return build (MINUS_EXPR, type, TREE_OPERAND (arg0, 1),
5014 TREE_OPERAND (arg0, 0));
5021 if (TREE_CODE (arg0) == INTEGER_CST)
5023 /* If the value is unsigned, then the absolute value is
5024 the same as the ordinary value. */
5025 if (TREE_UNSIGNED (type))
5027 /* Similarly, if the value is non-negative. */
5028 else if (INT_CST_LT (integer_minus_one_node, arg0))
5030 /* If the value is negative, then the absolute value is
5034 unsigned HOST_WIDE_INT low;
5036 int overflow = neg_double (TREE_INT_CST_LOW (arg0),
5037 TREE_INT_CST_HIGH (arg0),
5039 t = build_int_2 (low, high);
5040 TREE_TYPE (t) = type;
5042 = (TREE_OVERFLOW (arg0)
5043 | force_fit_type (t, overflow));
5044 TREE_CONSTANT_OVERFLOW (t)
5045 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
5048 else if (TREE_CODE (arg0) == REAL_CST)
5050 if (REAL_VALUE_NEGATIVE (TREE_REAL_CST (arg0)))
5051 t = build_real (type,
5052 REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
5055 else if (TREE_CODE (arg0) == ABS_EXPR || TREE_CODE (arg0) == NEGATE_EXPR)
5056 return build1 (ABS_EXPR, type, TREE_OPERAND (arg0, 0));
5060 if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
5061 return convert (type, arg0);
5062 else if (TREE_CODE (arg0) == COMPLEX_EXPR)
5063 return build (COMPLEX_EXPR, type,
5064 TREE_OPERAND (arg0, 0),
5065 negate_expr (TREE_OPERAND (arg0, 1)));
5066 else if (TREE_CODE (arg0) == COMPLEX_CST)
5067 return build_complex (type, TREE_REALPART (arg0),
5068 negate_expr (TREE_IMAGPART (arg0)));
5069 else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
5070 return fold (build (TREE_CODE (arg0), type,
5071 fold (build1 (CONJ_EXPR, type,
5072 TREE_OPERAND (arg0, 0))),
5073 fold (build1 (CONJ_EXPR,
5074 type, TREE_OPERAND (arg0, 1)))));
5075 else if (TREE_CODE (arg0) == CONJ_EXPR)
5076 return TREE_OPERAND (arg0, 0);
5082 t = build_int_2 (~ TREE_INT_CST_LOW (arg0),
5083 ~ TREE_INT_CST_HIGH (arg0));
5084 TREE_TYPE (t) = type;
5085 force_fit_type (t, 0);
5086 TREE_OVERFLOW (t) = TREE_OVERFLOW (arg0);
5087 TREE_CONSTANT_OVERFLOW (t) = TREE_CONSTANT_OVERFLOW (arg0);
5089 else if (TREE_CODE (arg0) == BIT_NOT_EXPR)
5090 return TREE_OPERAND (arg0, 0);
5094 /* A + (-B) -> A - B */
5095 if (TREE_CODE (arg1) == NEGATE_EXPR)
5096 return fold (build (MINUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
5097 /* (-A) + B -> B - A */
5098 if (TREE_CODE (arg0) == NEGATE_EXPR)
5099 return fold (build (MINUS_EXPR, type, arg1, TREE_OPERAND (arg0, 0)));
5100 else if (! FLOAT_TYPE_P (type))
5102 if (integer_zerop (arg1))
5103 return non_lvalue (convert (type, arg0));
5105 /* If we are adding two BIT_AND_EXPR's, both of which are and'ing
5106 with a constant, and the two constants have no bits in common,
5107 we should treat this as a BIT_IOR_EXPR since this may produce more
5109 if (TREE_CODE (arg0) == BIT_AND_EXPR
5110 && TREE_CODE (arg1) == BIT_AND_EXPR
5111 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5112 && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
5113 && integer_zerop (const_binop (BIT_AND_EXPR,
5114 TREE_OPERAND (arg0, 1),
5115 TREE_OPERAND (arg1, 1), 0)))
5117 code = BIT_IOR_EXPR;
5121 /* Reassociate (plus (plus (mult) (foo)) (mult)) as
5122 (plus (plus (mult) (mult)) (foo)) so that we can
5123 take advantage of the factoring cases below. */
5124 if ((TREE_CODE (arg0) == PLUS_EXPR
5125 && TREE_CODE (arg1) == MULT_EXPR)
5126 || (TREE_CODE (arg1) == PLUS_EXPR
5127 && TREE_CODE (arg0) == MULT_EXPR))
5129 tree parg0, parg1, parg, marg;
5131 if (TREE_CODE (arg0) == PLUS_EXPR)
5132 parg = arg0, marg = arg1;
5134 parg = arg1, marg = arg0;
5135 parg0 = TREE_OPERAND (parg, 0);
5136 parg1 = TREE_OPERAND (parg, 1);
5140 if (TREE_CODE (parg0) == MULT_EXPR
5141 && TREE_CODE (parg1) != MULT_EXPR)
5142 return fold (build (PLUS_EXPR, type,
5143 fold (build (PLUS_EXPR, type, parg0, marg)),
5145 if (TREE_CODE (parg0) != MULT_EXPR
5146 && TREE_CODE (parg1) == MULT_EXPR)
5147 return fold (build (PLUS_EXPR, type,
5148 fold (build (PLUS_EXPR, type, parg1, marg)),
5152 if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR)
5154 tree arg00, arg01, arg10, arg11;
5155 tree alt0 = NULL_TREE, alt1 = NULL_TREE, same;
5157 /* (A * C) + (B * C) -> (A+B) * C.
5158 We are most concerned about the case where C is a constant,
5159 but other combinations show up during loop reduction. Since
5160 it is not difficult, try all four possibilities. */
5162 arg00 = TREE_OPERAND (arg0, 0);
5163 arg01 = TREE_OPERAND (arg0, 1);
5164 arg10 = TREE_OPERAND (arg1, 0);
5165 arg11 = TREE_OPERAND (arg1, 1);
5168 if (operand_equal_p (arg01, arg11, 0))
5169 same = arg01, alt0 = arg00, alt1 = arg10;
5170 else if (operand_equal_p (arg00, arg10, 0))
5171 same = arg00, alt0 = arg01, alt1 = arg11;
5172 else if (operand_equal_p (arg00, arg11, 0))
5173 same = arg00, alt0 = arg01, alt1 = arg10;
5174 else if (operand_equal_p (arg01, arg10, 0))
5175 same = arg01, alt0 = arg00, alt1 = arg11;
5177 /* No identical multiplicands; see if we can find a common
5178 power-of-two factor in non-power-of-two multiplies. This
5179 can help in multi-dimensional array access. */
5180 else if (TREE_CODE (arg01) == INTEGER_CST
5181 && TREE_CODE (arg11) == INTEGER_CST
5182 && TREE_INT_CST_HIGH (arg01) == 0
5183 && TREE_INT_CST_HIGH (arg11) == 0)
5185 HOST_WIDE_INT int01, int11, tmp;
5186 int01 = TREE_INT_CST_LOW (arg01);
5187 int11 = TREE_INT_CST_LOW (arg11);
5189 /* Move min of absolute values to int11. */
5190 if ((int01 >= 0 ? int01 : -int01)
5191 < (int11 >= 0 ? int11 : -int11))
5193 tmp = int01, int01 = int11, int11 = tmp;
5194 alt0 = arg00, arg00 = arg10, arg10 = alt0;
5195 alt0 = arg01, arg01 = arg11, arg11 = alt0;
5198 if (exact_log2 (int11) > 0 && int01 % int11 == 0)
5200 alt0 = fold (build (MULT_EXPR, type, arg00,
5201 build_int_2 (int01 / int11, 0)));
5208 return fold (build (MULT_EXPR, type,
5209 fold (build (PLUS_EXPR, type, alt0, alt1)),
5214 /* See if ARG1 is zero and X + ARG1 reduces to X. */
5215 else if (fold_real_zero_addition_p (TREE_TYPE (arg0), arg1, 0))
5216 return non_lvalue (convert (type, arg0));
5218 /* Likewise if the operands are reversed. */
5219 else if (fold_real_zero_addition_p (TREE_TYPE (arg1), arg0, 0))
5220 return non_lvalue (convert (type, arg1));
5223 /* (A << C1) + (A >> C2) if A is unsigned and C1+C2 is the size of A
5224 is a rotate of A by C1 bits. */
5225 /* (A << B) + (A >> (Z - B)) if A is unsigned and Z is the size of A
5226 is a rotate of A by B bits. */
5228 enum tree_code code0, code1;
5229 code0 = TREE_CODE (arg0);
5230 code1 = TREE_CODE (arg1);
5231 if (((code0 == RSHIFT_EXPR && code1 == LSHIFT_EXPR)
5232 || (code1 == RSHIFT_EXPR && code0 == LSHIFT_EXPR))
5233 && operand_equal_p (TREE_OPERAND (arg0, 0),
5234 TREE_OPERAND (arg1, 0), 0)
5235 && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5237 tree tree01, tree11;
5238 enum tree_code code01, code11;
5240 tree01 = TREE_OPERAND (arg0, 1);
5241 tree11 = TREE_OPERAND (arg1, 1);
5242 STRIP_NOPS (tree01);
5243 STRIP_NOPS (tree11);
5244 code01 = TREE_CODE (tree01);
5245 code11 = TREE_CODE (tree11);
5246 if (code01 == INTEGER_CST
5247 && code11 == INTEGER_CST
5248 && TREE_INT_CST_HIGH (tree01) == 0
5249 && TREE_INT_CST_HIGH (tree11) == 0
5250 && ((TREE_INT_CST_LOW (tree01) + TREE_INT_CST_LOW (tree11))
5251 == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)))))
5252 return build (LROTATE_EXPR, type, TREE_OPERAND (arg0, 0),
5253 code0 == LSHIFT_EXPR ? tree01 : tree11);
5254 else if (code11 == MINUS_EXPR)
5256 tree tree110, tree111;
5257 tree110 = TREE_OPERAND (tree11, 0);
5258 tree111 = TREE_OPERAND (tree11, 1);
5259 STRIP_NOPS (tree110);
5260 STRIP_NOPS (tree111);
5261 if (TREE_CODE (tree110) == INTEGER_CST
5262 && 0 == compare_tree_int (tree110,
5264 (TREE_TYPE (TREE_OPERAND
5266 && operand_equal_p (tree01, tree111, 0))
5267 return build ((code0 == LSHIFT_EXPR
5270 type, TREE_OPERAND (arg0, 0), tree01);
5272 else if (code01 == MINUS_EXPR)
5274 tree tree010, tree011;
5275 tree010 = TREE_OPERAND (tree01, 0);
5276 tree011 = TREE_OPERAND (tree01, 1);
5277 STRIP_NOPS (tree010);
5278 STRIP_NOPS (tree011);
5279 if (TREE_CODE (tree010) == INTEGER_CST
5280 && 0 == compare_tree_int (tree010,
5282 (TREE_TYPE (TREE_OPERAND
5284 && operand_equal_p (tree11, tree011, 0))
5285 return build ((code0 != LSHIFT_EXPR
5288 type, TREE_OPERAND (arg0, 0), tree11);
5294 /* In most languages, can't associate operations on floats through
5295 parentheses. Rather than remember where the parentheses were, we
5296 don't associate floats at all. It shouldn't matter much. However,
5297 associating multiplications is only very slightly inaccurate, so do
5298 that if -funsafe-math-optimizations is specified. */
5301 && (! FLOAT_TYPE_P (type)
5302 || (flag_unsafe_math_optimizations && code == MULT_EXPR)))
5304 tree var0, con0, lit0, minus_lit0;
5305 tree var1, con1, lit1, minus_lit1;
5307 /* Split both trees into variables, constants, and literals. Then
5308 associate each group together, the constants with literals,
5309 then the result with variables. This increases the chances of
5310 literals being recombined later and of generating relocatable
5311 expressions for the sum of a constant and literal. */
5312 var0 = split_tree (arg0, code, &con0, &lit0, &minus_lit0, 0);
5313 var1 = split_tree (arg1, code, &con1, &lit1, &minus_lit1,
5314 code == MINUS_EXPR);
5316 /* Only do something if we found more than two objects. Otherwise,
5317 nothing has changed and we risk infinite recursion. */
5318 if (2 < ((var0 != 0) + (var1 != 0)
5319 + (con0 != 0) + (con1 != 0)
5320 + (lit0 != 0) + (lit1 != 0)
5321 + (minus_lit0 != 0) + (minus_lit1 != 0)))
5323 /* Recombine MINUS_EXPR operands by using PLUS_EXPR. */
5324 if (code == MINUS_EXPR)
5327 var0 = associate_trees (var0, var1, code, type);
5328 con0 = associate_trees (con0, con1, code, type);
5329 lit0 = associate_trees (lit0, lit1, code, type);
5330 minus_lit0 = associate_trees (minus_lit0, minus_lit1, code, type);
5332 /* Preserve the MINUS_EXPR if the negative part of the literal is
5333 greater than the positive part. Otherwise, the multiplicative
5334 folding code (i.e extract_muldiv) may be fooled in case
5335 unsigned constants are substracted, like in the following
5336 example: ((X*2 + 4) - 8U)/2. */
5337 if (minus_lit0 && lit0)
5339 if (tree_int_cst_lt (lit0, minus_lit0))
5341 minus_lit0 = associate_trees (minus_lit0, lit0,
5347 lit0 = associate_trees (lit0, minus_lit0,
5355 return convert (type, associate_trees (var0, minus_lit0,
5359 con0 = associate_trees (con0, minus_lit0,
5361 return convert (type, associate_trees (var0, con0,
5366 con0 = associate_trees (con0, lit0, code, type);
5367 return convert (type, associate_trees (var0, con0, code, type));
5373 t1 = const_binop (code, arg0, arg1, 0);
5374 if (t1 != NULL_TREE)
5376 /* The return value should always have
5377 the same type as the original expression. */
5378 if (TREE_TYPE (t1) != TREE_TYPE (t))
5379 t1 = convert (TREE_TYPE (t), t1);
5386 /* A - (-B) -> A + B */
5387 if (TREE_CODE (arg1) == NEGATE_EXPR)
5388 return fold (build (PLUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
5389 /* (-A) - CST -> (-CST) - A for floating point (what about ints ?) */
5390 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == REAL_CST)
5392 fold (build (MINUS_EXPR, type,
5393 build_real (TREE_TYPE (arg1),
5394 REAL_VALUE_NEGATE (TREE_REAL_CST (arg1))),
5395 TREE_OPERAND (arg0, 0)));
5397 if (! FLOAT_TYPE_P (type))
5399 if (! wins && integer_zerop (arg0))
5400 return negate_expr (convert (type, arg1));
5401 if (integer_zerop (arg1))
5402 return non_lvalue (convert (type, arg0));
5404 /* (A * C) - (B * C) -> (A-B) * C. Since we are most concerned
5405 about the case where C is a constant, just try one of the
5406 four possibilities. */
5408 if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR
5409 && operand_equal_p (TREE_OPERAND (arg0, 1),
5410 TREE_OPERAND (arg1, 1), 0))
5411 return fold (build (MULT_EXPR, type,
5412 fold (build (MINUS_EXPR, type,
5413 TREE_OPERAND (arg0, 0),
5414 TREE_OPERAND (arg1, 0))),
5415 TREE_OPERAND (arg0, 1)));
5418 /* See if ARG1 is zero and X - ARG1 reduces to X. */
5419 else if (fold_real_zero_addition_p (TREE_TYPE (arg0), arg1, 1))
5420 return non_lvalue (convert (type, arg0));
5422 /* (ARG0 - ARG1) is the same as (-ARG1 + ARG0). So check whether
5423 ARG0 is zero and X + ARG0 reduces to X, since that would mean
5424 (-ARG1 + ARG0) reduces to -ARG1. */
5425 else if (!wins && fold_real_zero_addition_p (TREE_TYPE (arg1), arg0, 0))
5426 return negate_expr (convert (type, arg1));
5428 /* Fold &x - &x. This can happen from &x.foo - &x.
5429 This is unsafe for certain floats even in non-IEEE formats.
5430 In IEEE, it is unsafe because it does wrong for NaNs.
5431 Also note that operand_equal_p is always false if an operand
5434 if ((! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations)
5435 && operand_equal_p (arg0, arg1, 0))
5436 return convert (type, integer_zero_node);
5441 /* (-A) * (-B) -> A * B */
5442 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == NEGATE_EXPR)
5443 return fold (build (MULT_EXPR, type, TREE_OPERAND (arg0, 0),
5444 TREE_OPERAND (arg1, 0)));
5446 if (! FLOAT_TYPE_P (type))
5448 if (integer_zerop (arg1))
5449 return omit_one_operand (type, arg1, arg0);
5450 if (integer_onep (arg1))
5451 return non_lvalue (convert (type, arg0));
5453 /* (a * (1 << b)) is (a << b) */
5454 if (TREE_CODE (arg1) == LSHIFT_EXPR
5455 && integer_onep (TREE_OPERAND (arg1, 0)))
5456 return fold (build (LSHIFT_EXPR, type, arg0,
5457 TREE_OPERAND (arg1, 1)));
5458 if (TREE_CODE (arg0) == LSHIFT_EXPR
5459 && integer_onep (TREE_OPERAND (arg0, 0)))
5460 return fold (build (LSHIFT_EXPR, type, arg1,
5461 TREE_OPERAND (arg0, 1)));
5463 if (TREE_CODE (arg1) == INTEGER_CST
5464 && 0 != (tem = extract_muldiv (TREE_OPERAND (t, 0), arg1,
5466 return convert (type, tem);
5471 /* Maybe fold x * 0 to 0. The expressions aren't the same
5472 when x is NaN, since x * 0 is also NaN. Nor are they the
5473 same in modes with signed zeros, since multiplying a
5474 negative value by 0 gives -0, not +0. */
5475 if (!HONOR_NANS (TYPE_MODE (TREE_TYPE (arg0)))
5476 && !HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg0)))
5477 && real_zerop (arg1))
5478 return omit_one_operand (type, arg1, arg0);
5479 /* In IEEE floating point, x*1 is not equivalent to x for snans.
5480 However, ANSI says we can drop signals,
5481 so we can do this anyway. */
5482 if (real_onep (arg1))
5483 return non_lvalue (convert (type, arg0));
5485 /* Transform x * -1.0 into -x. This should be safe for NaNs,
5486 signed zeros and signed infinities, but is currently
5487 restricted to "unsafe math optimizations" just in case. */
5488 if (flag_unsafe_math_optimizations
5489 && real_minus_onep (arg1))
5490 return fold (build1 (NEGATE_EXPR, type, arg0));
5493 if (! wins && real_twop (arg1)
5494 && (*lang_hooks.decls.global_bindings_p) () == 0
5495 && ! contains_placeholder_p (arg0))
5497 tree arg = save_expr (arg0);
5498 return build (PLUS_EXPR, type, arg, arg);
5505 if (integer_all_onesp (arg1))
5506 return omit_one_operand (type, arg1, arg0);
5507 if (integer_zerop (arg1))
5508 return non_lvalue (convert (type, arg0));
5509 t1 = distribute_bit_expr (code, type, arg0, arg1);
5510 if (t1 != NULL_TREE)
5513 /* Convert (or (not arg0) (not arg1)) to (not (and (arg0) (arg1))).
5515 This results in more efficient code for machines without a NAND
5516 instruction. Combine will canonicalize to the first form
5517 which will allow use of NAND instructions provided by the
5518 backend if they exist. */
5519 if (TREE_CODE (arg0) == BIT_NOT_EXPR
5520 && TREE_CODE (arg1) == BIT_NOT_EXPR)
5522 return fold (build1 (BIT_NOT_EXPR, type,
5523 build (BIT_AND_EXPR, type,
5524 TREE_OPERAND (arg0, 0),
5525 TREE_OPERAND (arg1, 0))));
5528 /* See if this can be simplified into a rotate first. If that
5529 is unsuccessful continue in the association code. */
5533 if (integer_zerop (arg1))
5534 return non_lvalue (convert (type, arg0));
5535 if (integer_all_onesp (arg1))
5536 return fold (build1 (BIT_NOT_EXPR, type, arg0));
5538 /* If we are XORing two BIT_AND_EXPR's, both of which are and'ing
5539 with a constant, and the two constants have no bits in common,
5540 we should treat this as a BIT_IOR_EXPR since this may produce more
5542 if (TREE_CODE (arg0) == BIT_AND_EXPR
5543 && TREE_CODE (arg1) == BIT_AND_EXPR
5544 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5545 && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
5546 && integer_zerop (const_binop (BIT_AND_EXPR,
5547 TREE_OPERAND (arg0, 1),
5548 TREE_OPERAND (arg1, 1), 0)))
5550 code = BIT_IOR_EXPR;
5554 /* See if this can be simplified into a rotate first. If that
5555 is unsuccessful continue in the association code. */
5560 if (integer_all_onesp (arg1))
5561 return non_lvalue (convert (type, arg0));
5562 if (integer_zerop (arg1))
5563 return omit_one_operand (type, arg1, arg0);
5564 t1 = distribute_bit_expr (code, type, arg0, arg1);
5565 if (t1 != NULL_TREE)
5567 /* Simplify ((int)c & 0x377) into (int)c, if c is unsigned char. */
5568 if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) == NOP_EXPR
5569 && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5572 = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)));
5574 if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
5575 && (~TREE_INT_CST_LOW (arg1)
5576 & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
5577 return build1 (NOP_EXPR, type, TREE_OPERAND (arg0, 0));
5580 /* Convert (and (not arg0) (not arg1)) to (not (or (arg0) (arg1))).
5582 This results in more efficient code for machines without a NOR
5583 instruction. Combine will canonicalize to the first form
5584 which will allow use of NOR instructions provided by the
5585 backend if they exist. */
5586 if (TREE_CODE (arg0) == BIT_NOT_EXPR
5587 && TREE_CODE (arg1) == BIT_NOT_EXPR)
5589 return fold (build1 (BIT_NOT_EXPR, type,
5590 build (BIT_IOR_EXPR, type,
5591 TREE_OPERAND (arg0, 0),
5592 TREE_OPERAND (arg1, 0))));
5597 case BIT_ANDTC_EXPR:
5598 if (integer_all_onesp (arg0))
5599 return non_lvalue (convert (type, arg1));
5600 if (integer_zerop (arg0))
5601 return omit_one_operand (type, arg0, arg1);
5602 if (TREE_CODE (arg1) == INTEGER_CST)
5604 arg1 = fold (build1 (BIT_NOT_EXPR, type, arg1));
5605 code = BIT_AND_EXPR;
5611 /* Don't touch a floating-point divide by zero unless the mode
5612 of the constant can represent infinity. */
5613 if (TREE_CODE (arg1) == REAL_CST
5614 && !MODE_HAS_INFINITIES (TYPE_MODE (TREE_TYPE (arg1)))
5615 && real_zerop (arg1))
5618 /* (-A) / (-B) -> A / B */
5619 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == NEGATE_EXPR)
5620 return fold (build (RDIV_EXPR, type, TREE_OPERAND (arg0, 0),
5621 TREE_OPERAND (arg1, 0)));
5623 /* In IEEE floating point, x/1 is not equivalent to x for snans.
5624 However, ANSI says we can drop signals, so we can do this anyway. */
5625 if (real_onep (arg1))
5626 return non_lvalue (convert (type, arg0));
5628 /* If ARG1 is a constant, we can convert this to a multiply by the
5629 reciprocal. This does not have the same rounding properties,
5630 so only do this if -funsafe-math-optimizations. We can actually
5631 always safely do it if ARG1 is a power of two, but it's hard to
5632 tell if it is or not in a portable manner. */
5633 if (TREE_CODE (arg1) == REAL_CST)
5635 if (flag_unsafe_math_optimizations
5636 && 0 != (tem = const_binop (code, build_real (type, dconst1),
5638 return fold (build (MULT_EXPR, type, arg0, tem));
5639 /* Find the reciprocal if optimizing and the result is exact. */
5643 r = TREE_REAL_CST (arg1);
5644 if (exact_real_inverse (TYPE_MODE(TREE_TYPE(arg0)), &r))
5646 tem = build_real (type, r);
5647 return fold (build (MULT_EXPR, type, arg0, tem));
5651 /* Convert A/B/C to A/(B*C). */
5652 if (flag_unsafe_math_optimizations
5653 && TREE_CODE (arg0) == RDIV_EXPR)
5655 return fold (build (RDIV_EXPR, type, TREE_OPERAND (arg0, 0),
5656 build (MULT_EXPR, type, TREE_OPERAND (arg0, 1),
5659 /* Convert A/(B/C) to (A/B)*C. */
5660 if (flag_unsafe_math_optimizations
5661 && TREE_CODE (arg1) == RDIV_EXPR)
5663 return fold (build (MULT_EXPR, type,
5664 build (RDIV_EXPR, type, arg0,
5665 TREE_OPERAND (arg1, 0)),
5666 TREE_OPERAND (arg1, 1)));
5670 case TRUNC_DIV_EXPR:
5671 case ROUND_DIV_EXPR:
5672 case FLOOR_DIV_EXPR:
5674 case EXACT_DIV_EXPR:
5675 if (integer_onep (arg1))
5676 return non_lvalue (convert (type, arg0));
5677 if (integer_zerop (arg1))
5680 /* If arg0 is a multiple of arg1, then rewrite to the fastest div
5681 operation, EXACT_DIV_EXPR.
5683 Note that only CEIL_DIV_EXPR and FLOOR_DIV_EXPR are rewritten now.
5684 At one time others generated faster code, it's not clear if they do
5685 after the last round to changes to the DIV code in expmed.c. */
5686 if ((code == CEIL_DIV_EXPR || code == FLOOR_DIV_EXPR)
5687 && multiple_of_p (type, arg0, arg1))
5688 return fold (build (EXACT_DIV_EXPR, type, arg0, arg1));
5690 if (TREE_CODE (arg1) == INTEGER_CST
5691 && 0 != (tem = extract_muldiv (TREE_OPERAND (t, 0), arg1,
5693 return convert (type, tem);
5698 case FLOOR_MOD_EXPR:
5699 case ROUND_MOD_EXPR:
5700 case TRUNC_MOD_EXPR:
5701 if (integer_onep (arg1))
5702 return omit_one_operand (type, integer_zero_node, arg0);
5703 if (integer_zerop (arg1))
5706 if (TREE_CODE (arg1) == INTEGER_CST
5707 && 0 != (tem = extract_muldiv (TREE_OPERAND (t, 0), arg1,
5709 return convert (type, tem);
5717 if (integer_zerop (arg1))
5718 return non_lvalue (convert (type, arg0));
5719 /* Since negative shift count is not well-defined,
5720 don't try to compute it in the compiler. */
5721 if (TREE_CODE (arg1) == INTEGER_CST && tree_int_cst_sgn (arg1) < 0)
5723 /* Rewrite an LROTATE_EXPR by a constant into an
5724 RROTATE_EXPR by a new constant. */
5725 if (code == LROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST)
5727 TREE_SET_CODE (t, RROTATE_EXPR);
5728 code = RROTATE_EXPR;
5729 TREE_OPERAND (t, 1) = arg1
5732 convert (TREE_TYPE (arg1),
5733 build_int_2 (GET_MODE_BITSIZE (TYPE_MODE (type)), 0)),
5735 if (tree_int_cst_sgn (arg1) < 0)
5739 /* If we have a rotate of a bit operation with the rotate count and
5740 the second operand of the bit operation both constant,
5741 permute the two operations. */
5742 if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5743 && (TREE_CODE (arg0) == BIT_AND_EXPR
5744 || TREE_CODE (arg0) == BIT_ANDTC_EXPR
5745 || TREE_CODE (arg0) == BIT_IOR_EXPR
5746 || TREE_CODE (arg0) == BIT_XOR_EXPR)
5747 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
5748 return fold (build (TREE_CODE (arg0), type,
5749 fold (build (code, type,
5750 TREE_OPERAND (arg0, 0), arg1)),
5751 fold (build (code, type,
5752 TREE_OPERAND (arg0, 1), arg1))));
5754 /* Two consecutive rotates adding up to the width of the mode can
5756 if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5757 && TREE_CODE (arg0) == RROTATE_EXPR
5758 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5759 && TREE_INT_CST_HIGH (arg1) == 0
5760 && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == 0
5761 && ((TREE_INT_CST_LOW (arg1)
5762 + TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)))
5763 == (unsigned int) GET_MODE_BITSIZE (TYPE_MODE (type))))
5764 return TREE_OPERAND (arg0, 0);
5769 if (operand_equal_p (arg0, arg1, 0))
5770 return omit_one_operand (type, arg0, arg1);
5771 if (INTEGRAL_TYPE_P (type)
5772 && operand_equal_p (arg1, TYPE_MIN_VALUE (type), 1))
5773 return omit_one_operand (type, arg1, arg0);
5777 if (operand_equal_p (arg0, arg1, 0))
5778 return omit_one_operand (type, arg0, arg1);
5779 if (INTEGRAL_TYPE_P (type)
5780 && TYPE_MAX_VALUE (type)
5781 && operand_equal_p (arg1, TYPE_MAX_VALUE (type), 1))
5782 return omit_one_operand (type, arg1, arg0);
5785 case TRUTH_NOT_EXPR:
5786 /* Note that the operand of this must be an int
5787 and its values must be 0 or 1.
5788 ("true" is a fixed value perhaps depending on the language,
5789 but we don't handle values other than 1 correctly yet.) */
5790 tem = invert_truthvalue (arg0);
5791 /* Avoid infinite recursion. */
5792 if (TREE_CODE (tem) == TRUTH_NOT_EXPR)
5794 return convert (type, tem);
5796 case TRUTH_ANDIF_EXPR:
5797 /* Note that the operands of this must be ints
5798 and their values must be 0 or 1.
5799 ("true" is a fixed value perhaps depending on the language.) */
5800 /* If first arg is constant zero, return it. */
5801 if (integer_zerop (arg0))
5802 return convert (type, arg0);
5803 case TRUTH_AND_EXPR:
5804 /* If either arg is constant true, drop it. */
5805 if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5806 return non_lvalue (convert (type, arg1));
5807 if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1)
5808 /* Preserve sequence points. */
5809 && (code != TRUTH_ANDIF_EXPR || ! TREE_SIDE_EFFECTS (arg0)))
5810 return non_lvalue (convert (type, arg0));
5811 /* If second arg is constant zero, result is zero, but first arg
5812 must be evaluated. */
5813 if (integer_zerop (arg1))
5814 return omit_one_operand (type, arg1, arg0);
5815 /* Likewise for first arg, but note that only the TRUTH_AND_EXPR
5816 case will be handled here. */
5817 if (integer_zerop (arg0))
5818 return omit_one_operand (type, arg0, arg1);
5821 /* We only do these simplifications if we are optimizing. */
5825 /* Check for things like (A || B) && (A || C). We can convert this
5826 to A || (B && C). Note that either operator can be any of the four
5827 truth and/or operations and the transformation will still be
5828 valid. Also note that we only care about order for the
5829 ANDIF and ORIF operators. If B contains side effects, this
5830 might change the truth-value of A. */
5831 if (TREE_CODE (arg0) == TREE_CODE (arg1)
5832 && (TREE_CODE (arg0) == TRUTH_ANDIF_EXPR
5833 || TREE_CODE (arg0) == TRUTH_ORIF_EXPR
5834 || TREE_CODE (arg0) == TRUTH_AND_EXPR
5835 || TREE_CODE (arg0) == TRUTH_OR_EXPR)
5836 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg0, 1)))
5838 tree a00 = TREE_OPERAND (arg0, 0);
5839 tree a01 = TREE_OPERAND (arg0, 1);
5840 tree a10 = TREE_OPERAND (arg1, 0);
5841 tree a11 = TREE_OPERAND (arg1, 1);
5842 int commutative = ((TREE_CODE (arg0) == TRUTH_OR_EXPR
5843 || TREE_CODE (arg0) == TRUTH_AND_EXPR)
5844 && (code == TRUTH_AND_EXPR
5845 || code == TRUTH_OR_EXPR));
5847 if (operand_equal_p (a00, a10, 0))
5848 return fold (build (TREE_CODE (arg0), type, a00,
5849 fold (build (code, type, a01, a11))));
5850 else if (commutative && operand_equal_p (a00, a11, 0))
5851 return fold (build (TREE_CODE (arg0), type, a00,
5852 fold (build (code, type, a01, a10))));
5853 else if (commutative && operand_equal_p (a01, a10, 0))
5854 return fold (build (TREE_CODE (arg0), type, a01,
5855 fold (build (code, type, a00, a11))));
5857 /* This case if tricky because we must either have commutative
5858 operators or else A10 must not have side-effects. */
5860 else if ((commutative || ! TREE_SIDE_EFFECTS (a10))
5861 && operand_equal_p (a01, a11, 0))
5862 return fold (build (TREE_CODE (arg0), type,
5863 fold (build (code, type, a00, a10)),
5867 /* See if we can build a range comparison. */
5868 if (0 != (tem = fold_range_test (t)))
5871 /* Check for the possibility of merging component references. If our
5872 lhs is another similar operation, try to merge its rhs with our
5873 rhs. Then try to merge our lhs and rhs. */
5874 if (TREE_CODE (arg0) == code
5875 && 0 != (tem = fold_truthop (code, type,
5876 TREE_OPERAND (arg0, 1), arg1)))
5877 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
5879 if ((tem = fold_truthop (code, type, arg0, arg1)) != 0)
5884 case TRUTH_ORIF_EXPR:
5885 /* Note that the operands of this must be ints
5886 and their values must be 0 or true.
5887 ("true" is a fixed value perhaps depending on the language.) */
5888 /* If first arg is constant true, return it. */
5889 if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5890 return convert (type, arg0);
5892 /* If either arg is constant zero, drop it. */
5893 if (TREE_CODE (arg0) == INTEGER_CST && integer_zerop (arg0))
5894 return non_lvalue (convert (type, arg1));
5895 if (TREE_CODE (arg1) == INTEGER_CST && integer_zerop (arg1)
5896 /* Preserve sequence points. */
5897 && (code != TRUTH_ORIF_EXPR || ! TREE_SIDE_EFFECTS (arg0)))
5898 return non_lvalue (convert (type, arg0));
5899 /* If second arg is constant true, result is true, but we must
5900 evaluate first arg. */
5901 if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
5902 return omit_one_operand (type, arg1, arg0);
5903 /* Likewise for first arg, but note this only occurs here for
5905 if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5906 return omit_one_operand (type, arg0, arg1);
5909 case TRUTH_XOR_EXPR:
5910 /* If either arg is constant zero, drop it. */
5911 if (integer_zerop (arg0))
5912 return non_lvalue (convert (type, arg1));
5913 if (integer_zerop (arg1))
5914 return non_lvalue (convert (type, arg0));
5915 /* If either arg is constant true, this is a logical inversion. */
5916 if (integer_onep (arg0))
5917 return non_lvalue (convert (type, invert_truthvalue (arg1)));
5918 if (integer_onep (arg1))
5919 return non_lvalue (convert (type, invert_truthvalue (arg0)));
5928 /* If one arg is a real or integer constant, put it last. */
5929 if ((TREE_CODE (arg0) == INTEGER_CST
5930 && TREE_CODE (arg1) != INTEGER_CST)
5931 || (TREE_CODE (arg0) == REAL_CST
5932 && TREE_CODE (arg0) != REAL_CST))
5934 TREE_OPERAND (t, 0) = arg1;
5935 TREE_OPERAND (t, 1) = arg0;
5936 arg0 = TREE_OPERAND (t, 0);
5937 arg1 = TREE_OPERAND (t, 1);
5938 code = swap_tree_comparison (code);
5939 TREE_SET_CODE (t, code);
5942 if (FLOAT_TYPE_P (TREE_TYPE (arg0)))
5944 /* (-a) CMP (-b) -> b CMP a */
5945 if (TREE_CODE (arg0) == NEGATE_EXPR
5946 && TREE_CODE (arg1) == NEGATE_EXPR)
5947 return fold (build (code, type, TREE_OPERAND (arg1, 0),
5948 TREE_OPERAND (arg0, 0)));
5949 /* (-a) CMP CST -> a swap(CMP) (-CST) */
5950 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == REAL_CST)
5953 (swap_tree_comparison (code), type,
5954 TREE_OPERAND (arg0, 0),
5955 build_real (TREE_TYPE (arg1),
5956 REAL_VALUE_NEGATE (TREE_REAL_CST (arg1)))));
5957 /* IEEE doesn't distinguish +0 and -0 in comparisons. */
5958 /* a CMP (-0) -> a CMP 0 */
5959 if (TREE_CODE (arg1) == REAL_CST
5960 && REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (arg1)))
5961 return fold (build (code, type, arg0,
5962 build_real (TREE_TYPE (arg1), dconst0)));
5964 /* If this is a comparison of a real constant with a PLUS_EXPR
5965 or a MINUS_EXPR of a real constant, we can convert it into a
5966 comparison with a revised real constant as long as no overflow
5967 occurs when unsafe_math_optimizations are enabled. */
5968 if (flag_unsafe_math_optimizations
5969 && TREE_CODE (arg1) == REAL_CST
5970 && (TREE_CODE (arg0) == PLUS_EXPR
5971 || TREE_CODE (arg0) == MINUS_EXPR)
5972 && TREE_CODE (TREE_OPERAND (arg0, 1)) == REAL_CST
5973 && 0 != (tem = const_binop (TREE_CODE (arg0) == PLUS_EXPR
5974 ? MINUS_EXPR : PLUS_EXPR,
5975 arg1, TREE_OPERAND (arg0, 1), 0))
5976 && ! TREE_CONSTANT_OVERFLOW (tem))
5977 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
5980 /* Convert foo++ == CONST into ++foo == CONST + INCR.
5981 First, see if one arg is constant; find the constant arg
5982 and the other one. */
5984 tree constop = 0, varop = NULL_TREE;
5985 int constopnum = -1;
5987 if (TREE_CONSTANT (arg1))
5988 constopnum = 1, constop = arg1, varop = arg0;
5989 if (TREE_CONSTANT (arg0))
5990 constopnum = 0, constop = arg0, varop = arg1;
5992 if (constop && TREE_CODE (varop) == POSTINCREMENT_EXPR)
5994 /* This optimization is invalid for ordered comparisons
5995 if CONST+INCR overflows or if foo+incr might overflow.
5996 This optimization is invalid for floating point due to rounding.
5997 For pointer types we assume overflow doesn't happen. */
5998 if (POINTER_TYPE_P (TREE_TYPE (varop))
5999 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
6000 && (code == EQ_EXPR || code == NE_EXPR)))
6003 = fold (build (PLUS_EXPR, TREE_TYPE (varop),
6004 constop, TREE_OPERAND (varop, 1)));
6006 /* Do not overwrite the current varop to be a preincrement,
6007 create a new node so that we won't confuse our caller who
6008 might create trees and throw them away, reusing the
6009 arguments that they passed to build. This shows up in
6010 the THEN or ELSE parts of ?: being postincrements. */
6011 varop = build (PREINCREMENT_EXPR, TREE_TYPE (varop),
6012 TREE_OPERAND (varop, 0),
6013 TREE_OPERAND (varop, 1));
6015 /* If VAROP is a reference to a bitfield, we must mask
6016 the constant by the width of the field. */
6017 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
6018 && DECL_BIT_FIELD(TREE_OPERAND
6019 (TREE_OPERAND (varop, 0), 1)))
6022 = TREE_INT_CST_LOW (DECL_SIZE
6024 (TREE_OPERAND (varop, 0), 1)));
6025 tree mask, unsigned_type;
6026 unsigned int precision;
6027 tree folded_compare;
6029 /* First check whether the comparison would come out
6030 always the same. If we don't do that we would
6031 change the meaning with the masking. */
6032 if (constopnum == 0)
6033 folded_compare = fold (build (code, type, constop,
6034 TREE_OPERAND (varop, 0)));
6036 folded_compare = fold (build (code, type,
6037 TREE_OPERAND (varop, 0),
6039 if (integer_zerop (folded_compare)
6040 || integer_onep (folded_compare))
6041 return omit_one_operand (type, folded_compare, varop);
6043 unsigned_type = (*lang_hooks.types.type_for_size)(size, 1);
6044 precision = TYPE_PRECISION (unsigned_type);
6045 mask = build_int_2 (~0, ~0);
6046 TREE_TYPE (mask) = unsigned_type;
6047 force_fit_type (mask, 0);
6048 mask = const_binop (RSHIFT_EXPR, mask,
6049 size_int (precision - size), 0);
6050 newconst = fold (build (BIT_AND_EXPR,
6051 TREE_TYPE (varop), newconst,
6052 convert (TREE_TYPE (varop),
6056 t = build (code, type,
6057 (constopnum == 0) ? newconst : varop,
6058 (constopnum == 1) ? newconst : varop);
6062 else if (constop && TREE_CODE (varop) == POSTDECREMENT_EXPR)
6064 if (POINTER_TYPE_P (TREE_TYPE (varop))
6065 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
6066 && (code == EQ_EXPR || code == NE_EXPR)))
6069 = fold (build (MINUS_EXPR, TREE_TYPE (varop),
6070 constop, TREE_OPERAND (varop, 1)));
6072 /* Do not overwrite the current varop to be a predecrement,
6073 create a new node so that we won't confuse our caller who
6074 might create trees and throw them away, reusing the
6075 arguments that they passed to build. This shows up in
6076 the THEN or ELSE parts of ?: being postdecrements. */
6077 varop = build (PREDECREMENT_EXPR, TREE_TYPE (varop),
6078 TREE_OPERAND (varop, 0),
6079 TREE_OPERAND (varop, 1));
6081 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
6082 && DECL_BIT_FIELD(TREE_OPERAND
6083 (TREE_OPERAND (varop, 0), 1)))
6086 = TREE_INT_CST_LOW (DECL_SIZE
6088 (TREE_OPERAND (varop, 0), 1)));
6089 tree mask, unsigned_type;
6090 unsigned int precision;
6091 tree folded_compare;
6093 if (constopnum == 0)
6094 folded_compare = fold (build (code, type, constop,
6095 TREE_OPERAND (varop, 0)));
6097 folded_compare = fold (build (code, type,
6098 TREE_OPERAND (varop, 0),
6100 if (integer_zerop (folded_compare)
6101 || integer_onep (folded_compare))
6102 return omit_one_operand (type, folded_compare, varop);
6104 unsigned_type = (*lang_hooks.types.type_for_size)(size, 1);
6105 precision = TYPE_PRECISION (unsigned_type);
6106 mask = build_int_2 (~0, ~0);
6107 TREE_TYPE (mask) = TREE_TYPE (varop);
6108 force_fit_type (mask, 0);
6109 mask = const_binop (RSHIFT_EXPR, mask,
6110 size_int (precision - size), 0);
6111 newconst = fold (build (BIT_AND_EXPR,
6112 TREE_TYPE (varop), newconst,
6113 convert (TREE_TYPE (varop),
6117 t = build (code, type,
6118 (constopnum == 0) ? newconst : varop,
6119 (constopnum == 1) ? newconst : varop);
6125 /* Change X >= C to X > (C - 1) and X < C to X <= (C - 1) if C > 0.
6126 This transformation affects the cases which are handled in later
6127 optimizations involving comparisons with non-negative constants. */
6128 if (TREE_CODE (arg1) == INTEGER_CST
6129 && TREE_CODE (arg0) != INTEGER_CST
6130 && tree_int_cst_sgn (arg1) > 0)
6136 arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
6137 t = build (code, type, TREE_OPERAND (t, 0), arg1);
6142 arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
6143 t = build (code, type, TREE_OPERAND (t, 0), arg1);
6151 /* Comparisons with the highest or lowest possible integer of
6152 the specified size will have known values. */
6154 int width = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (arg1)));
6156 if (TREE_CODE (arg1) == INTEGER_CST
6157 && ! TREE_CONSTANT_OVERFLOW (arg1)
6158 && width <= HOST_BITS_PER_WIDE_INT
6159 && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
6160 || POINTER_TYPE_P (TREE_TYPE (arg1))))
6162 unsigned HOST_WIDE_INT signed_max;
6163 unsigned HOST_WIDE_INT max, min;
6165 signed_max = ((unsigned HOST_WIDE_INT) 1 << (width - 1)) - 1;
6167 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6169 max = ((unsigned HOST_WIDE_INT) 2 << (width - 1)) - 1;
6175 min = ((unsigned HOST_WIDE_INT) -1 << (width - 1));
6178 if (TREE_INT_CST_HIGH (arg1) == 0
6179 && TREE_INT_CST_LOW (arg1) == max)
6183 return omit_one_operand (type,
6184 convert (type, integer_zero_node),
6188 TREE_SET_CODE (t, EQ_EXPR);
6191 return omit_one_operand (type,
6192 convert (type, integer_one_node),
6196 TREE_SET_CODE (t, NE_EXPR);
6199 /* The GE_EXPR and LT_EXPR cases above are not normally
6200 reached because of previous transformations. */
6205 else if (TREE_INT_CST_HIGH (arg1) == 0
6206 && TREE_INT_CST_LOW (arg1) == max - 1)
6211 arg1 = const_binop (PLUS_EXPR, arg1, integer_one_node, 0);
6212 t = build (code, type, TREE_OPERAND (t, 0), arg1);
6216 arg1 = const_binop (PLUS_EXPR, arg1, integer_one_node, 0);
6217 t = build (code, type, TREE_OPERAND (t, 0), arg1);
6222 else if (TREE_INT_CST_HIGH (arg1) == (min ? -1 : 0)
6223 && TREE_INT_CST_LOW (arg1) == min)
6227 return omit_one_operand (type,
6228 convert (type, integer_zero_node),
6232 TREE_SET_CODE (t, EQ_EXPR);
6236 return omit_one_operand (type,
6237 convert (type, integer_one_node),
6241 TREE_SET_CODE (t, NE_EXPR);
6247 else if (TREE_INT_CST_HIGH (arg1) == (min ? -1 : 0)
6248 && TREE_INT_CST_LOW (arg1) == min + 1)
6253 arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
6254 t = build (code, type, TREE_OPERAND (t, 0), arg1);
6258 arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
6259 t = build (code, type, TREE_OPERAND (t, 0), arg1);
6265 else if (TREE_INT_CST_HIGH (arg1) == 0
6266 && TREE_INT_CST_LOW (arg1) == signed_max
6267 && TREE_UNSIGNED (TREE_TYPE (arg1))
6268 /* signed_type does not work on pointer types. */
6269 && INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
6271 /* The following case also applies to X < signed_max+1
6272 and X >= signed_max+1 because previous transformations. */
6273 if (code == LE_EXPR || code == GT_EXPR)
6276 st0 = (*lang_hooks.types.signed_type) (TREE_TYPE (arg0));
6277 st1 = (*lang_hooks.types.signed_type) (TREE_TYPE (arg1));
6279 (build (code == LE_EXPR ? GE_EXPR: LT_EXPR,
6280 type, convert (st0, arg0),
6281 convert (st1, integer_zero_node)));
6287 /* If this is an EQ or NE comparison of a constant with a PLUS_EXPR or
6288 a MINUS_EXPR of a constant, we can convert it into a comparison with
6289 a revised constant as long as no overflow occurs. */
6290 if ((code == EQ_EXPR || code == NE_EXPR)
6291 && TREE_CODE (arg1) == INTEGER_CST
6292 && (TREE_CODE (arg0) == PLUS_EXPR
6293 || TREE_CODE (arg0) == MINUS_EXPR)
6294 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
6295 && 0 != (tem = const_binop (TREE_CODE (arg0) == PLUS_EXPR
6296 ? MINUS_EXPR : PLUS_EXPR,
6297 arg1, TREE_OPERAND (arg0, 1), 0))
6298 && ! TREE_CONSTANT_OVERFLOW (tem))
6299 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
6301 /* Similarly for a NEGATE_EXPR. */
6302 else if ((code == EQ_EXPR || code == NE_EXPR)
6303 && TREE_CODE (arg0) == NEGATE_EXPR
6304 && TREE_CODE (arg1) == INTEGER_CST
6305 && 0 != (tem = negate_expr (arg1))
6306 && TREE_CODE (tem) == INTEGER_CST
6307 && ! TREE_CONSTANT_OVERFLOW (tem))
6308 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
6310 /* If we have X - Y == 0, we can convert that to X == Y and similarly
6311 for !=. Don't do this for ordered comparisons due to overflow. */
6312 else if ((code == NE_EXPR || code == EQ_EXPR)
6313 && integer_zerop (arg1) && TREE_CODE (arg0) == MINUS_EXPR)
6314 return fold (build (code, type,
6315 TREE_OPERAND (arg0, 0), TREE_OPERAND (arg0, 1)));
6317 /* If we are widening one operand of an integer comparison,
6318 see if the other operand is similarly being widened. Perhaps we
6319 can do the comparison in the narrower type. */
6320 else if (TREE_CODE (TREE_TYPE (arg0)) == INTEGER_TYPE
6321 && TREE_CODE (arg0) == NOP_EXPR
6322 && (tem = get_unwidened (arg0, NULL_TREE)) != arg0
6323 && (t1 = get_unwidened (arg1, TREE_TYPE (tem))) != 0
6324 && (TREE_TYPE (t1) == TREE_TYPE (tem)
6325 || (TREE_CODE (t1) == INTEGER_CST
6326 && int_fits_type_p (t1, TREE_TYPE (tem)))))
6327 return fold (build (code, type, tem, convert (TREE_TYPE (tem), t1)));
6329 /* If this is comparing a constant with a MIN_EXPR or a MAX_EXPR of a
6330 constant, we can simplify it. */
6331 else if (TREE_CODE (arg1) == INTEGER_CST
6332 && (TREE_CODE (arg0) == MIN_EXPR
6333 || TREE_CODE (arg0) == MAX_EXPR)
6334 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
6335 return optimize_minmax_comparison (t);
6337 /* If we are comparing an ABS_EXPR with a constant, we can
6338 convert all the cases into explicit comparisons, but they may
6339 well not be faster than doing the ABS and one comparison.
6340 But ABS (X) <= C is a range comparison, which becomes a subtraction
6341 and a comparison, and is probably faster. */
6342 else if (code == LE_EXPR && TREE_CODE (arg1) == INTEGER_CST
6343 && TREE_CODE (arg0) == ABS_EXPR
6344 && ! TREE_SIDE_EFFECTS (arg0)
6345 && (0 != (tem = negate_expr (arg1)))
6346 && TREE_CODE (tem) == INTEGER_CST
6347 && ! TREE_CONSTANT_OVERFLOW (tem))
6348 return fold (build (TRUTH_ANDIF_EXPR, type,
6349 build (GE_EXPR, type, TREE_OPERAND (arg0, 0), tem),
6350 build (LE_EXPR, type,
6351 TREE_OPERAND (arg0, 0), arg1)));
6353 /* If this is an EQ or NE comparison with zero and ARG0 is
6354 (1 << foo) & bar, convert it to (bar >> foo) & 1. Both require
6355 two operations, but the latter can be done in one less insn
6356 on machines that have only two-operand insns or on which a
6357 constant cannot be the first operand. */
6358 if (integer_zerop (arg1) && (code == EQ_EXPR || code == NE_EXPR)
6359 && TREE_CODE (arg0) == BIT_AND_EXPR)
6361 if (TREE_CODE (TREE_OPERAND (arg0, 0)) == LSHIFT_EXPR
6362 && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 0), 0)))
6364 fold (build (code, type,
6365 build (BIT_AND_EXPR, TREE_TYPE (arg0),
6367 TREE_TYPE (TREE_OPERAND (arg0, 0)),
6368 TREE_OPERAND (arg0, 1),
6369 TREE_OPERAND (TREE_OPERAND (arg0, 0), 1)),
6370 convert (TREE_TYPE (arg0),
6373 else if (TREE_CODE (TREE_OPERAND (arg0, 1)) == LSHIFT_EXPR
6374 && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 1), 0)))
6376 fold (build (code, type,
6377 build (BIT_AND_EXPR, TREE_TYPE (arg0),
6379 TREE_TYPE (TREE_OPERAND (arg0, 1)),
6380 TREE_OPERAND (arg0, 0),
6381 TREE_OPERAND (TREE_OPERAND (arg0, 1), 1)),
6382 convert (TREE_TYPE (arg0),
6387 /* If this is an NE or EQ comparison of zero against the result of a
6388 signed MOD operation whose second operand is a power of 2, make
6389 the MOD operation unsigned since it is simpler and equivalent. */
6390 if ((code == NE_EXPR || code == EQ_EXPR)
6391 && integer_zerop (arg1)
6392 && ! TREE_UNSIGNED (TREE_TYPE (arg0))
6393 && (TREE_CODE (arg0) == TRUNC_MOD_EXPR
6394 || TREE_CODE (arg0) == CEIL_MOD_EXPR
6395 || TREE_CODE (arg0) == FLOOR_MOD_EXPR
6396 || TREE_CODE (arg0) == ROUND_MOD_EXPR)
6397 && integer_pow2p (TREE_OPERAND (arg0, 1)))
6399 tree newtype = (*lang_hooks.types.unsigned_type) (TREE_TYPE (arg0));
6400 tree newmod = build (TREE_CODE (arg0), newtype,
6401 convert (newtype, TREE_OPERAND (arg0, 0)),
6402 convert (newtype, TREE_OPERAND (arg0, 1)));
6404 return build (code, type, newmod, convert (newtype, arg1));
6407 /* If this is an NE comparison of zero with an AND of one, remove the
6408 comparison since the AND will give the correct value. */
6409 if (code == NE_EXPR && integer_zerop (arg1)
6410 && TREE_CODE (arg0) == BIT_AND_EXPR
6411 && integer_onep (TREE_OPERAND (arg0, 1)))
6412 return convert (type, arg0);
6414 /* If we have (A & C) == C where C is a power of 2, convert this into
6415 (A & C) != 0. Similarly for NE_EXPR. */
6416 if ((code == EQ_EXPR || code == NE_EXPR)
6417 && TREE_CODE (arg0) == BIT_AND_EXPR
6418 && integer_pow2p (TREE_OPERAND (arg0, 1))
6419 && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
6420 return fold (build (code == EQ_EXPR ? NE_EXPR : EQ_EXPR, type,
6421 arg0, integer_zero_node));
6423 /* If we have (A & C) != 0 where C is the sign bit of A, convert
6424 this into A < 0. Similarly for (A & C) == 0 into A >= 0. */
6425 if ((code == EQ_EXPR || code == NE_EXPR)
6426 && TREE_CODE (arg0) == BIT_AND_EXPR
6427 && integer_zerop (arg1))
6429 tree arg00 = sign_bit_p (TREE_OPERAND (arg0, 0),
6430 TREE_OPERAND (arg0, 1));
6431 if (arg00 != NULL_TREE)
6433 tree stype = (*lang_hooks.types.signed_type) (TREE_TYPE (arg00));
6434 return fold (build (code == EQ_EXPR ? GE_EXPR : LT_EXPR, type,
6435 convert (stype, arg00),
6436 convert (stype, integer_zero_node)));
6440 /* If X is unsigned, convert X < (1 << Y) into X >> Y == 0
6441 and similarly for >= into !=. */
6442 if ((code == LT_EXPR || code == GE_EXPR)
6443 && TREE_UNSIGNED (TREE_TYPE (arg0))
6444 && TREE_CODE (arg1) == LSHIFT_EXPR
6445 && integer_onep (TREE_OPERAND (arg1, 0)))
6446 return build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
6447 build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
6448 TREE_OPERAND (arg1, 1)),
6449 convert (TREE_TYPE (arg0), integer_zero_node));
6451 else if ((code == LT_EXPR || code == GE_EXPR)
6452 && TREE_UNSIGNED (TREE_TYPE (arg0))
6453 && (TREE_CODE (arg1) == NOP_EXPR
6454 || TREE_CODE (arg1) == CONVERT_EXPR)
6455 && TREE_CODE (TREE_OPERAND (arg1, 0)) == LSHIFT_EXPR
6456 && integer_onep (TREE_OPERAND (TREE_OPERAND (arg1, 0), 0)))
6458 build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
6459 convert (TREE_TYPE (arg0),
6460 build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
6461 TREE_OPERAND (TREE_OPERAND (arg1, 0), 1))),
6462 convert (TREE_TYPE (arg0), integer_zero_node));
6464 /* Simplify comparison of something with itself. (For IEEE
6465 floating-point, we can only do some of these simplifications.) */
6466 if (operand_equal_p (arg0, arg1, 0))
6473 if (! FLOAT_TYPE_P (TREE_TYPE (arg0)))
6474 return constant_boolean_node (1, type);
6476 TREE_SET_CODE (t, code);
6480 /* For NE, we can only do this simplification if integer. */
6481 if (FLOAT_TYPE_P (TREE_TYPE (arg0)))
6483 /* ... fall through ... */
6486 return constant_boolean_node (0, type);
6492 /* If we are comparing an expression that just has comparisons
6493 of two integer values, arithmetic expressions of those comparisons,
6494 and constants, we can simplify it. There are only three cases
6495 to check: the two values can either be equal, the first can be
6496 greater, or the second can be greater. Fold the expression for
6497 those three values. Since each value must be 0 or 1, we have
6498 eight possibilities, each of which corresponds to the constant 0
6499 or 1 or one of the six possible comparisons.
6501 This handles common cases like (a > b) == 0 but also handles
6502 expressions like ((x > y) - (y > x)) > 0, which supposedly
6503 occur in macroized code. */
6505 if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) != INTEGER_CST)
6507 tree cval1 = 0, cval2 = 0;
6510 if (twoval_comparison_p (arg0, &cval1, &cval2, &save_p)
6511 /* Don't handle degenerate cases here; they should already
6512 have been handled anyway. */
6513 && cval1 != 0 && cval2 != 0
6514 && ! (TREE_CONSTANT (cval1) && TREE_CONSTANT (cval2))
6515 && TREE_TYPE (cval1) == TREE_TYPE (cval2)
6516 && INTEGRAL_TYPE_P (TREE_TYPE (cval1))
6517 && TYPE_MAX_VALUE (TREE_TYPE (cval1))
6518 && TYPE_MAX_VALUE (TREE_TYPE (cval2))
6519 && ! operand_equal_p (TYPE_MIN_VALUE (TREE_TYPE (cval1)),
6520 TYPE_MAX_VALUE (TREE_TYPE (cval2)), 0))
6522 tree maxval = TYPE_MAX_VALUE (TREE_TYPE (cval1));
6523 tree minval = TYPE_MIN_VALUE (TREE_TYPE (cval1));
6525 /* We can't just pass T to eval_subst in case cval1 or cval2
6526 was the same as ARG1. */
6529 = fold (build (code, type,
6530 eval_subst (arg0, cval1, maxval, cval2, minval),
6533 = fold (build (code, type,
6534 eval_subst (arg0, cval1, maxval, cval2, maxval),
6537 = fold (build (code, type,
6538 eval_subst (arg0, cval1, minval, cval2, maxval),
6541 /* All three of these results should be 0 or 1. Confirm they
6542 are. Then use those values to select the proper code
6545 if ((integer_zerop (high_result)
6546 || integer_onep (high_result))
6547 && (integer_zerop (equal_result)
6548 || integer_onep (equal_result))
6549 && (integer_zerop (low_result)
6550 || integer_onep (low_result)))
6552 /* Make a 3-bit mask with the high-order bit being the
6553 value for `>', the next for '=', and the low for '<'. */
6554 switch ((integer_onep (high_result) * 4)
6555 + (integer_onep (equal_result) * 2)
6556 + integer_onep (low_result))
6560 return omit_one_operand (type, integer_zero_node, arg0);
6581 return omit_one_operand (type, integer_one_node, arg0);
6584 t = build (code, type, cval1, cval2);
6586 return save_expr (t);
6593 /* If this is a comparison of a field, we may be able to simplify it. */
6594 if ((TREE_CODE (arg0) == COMPONENT_REF
6595 || TREE_CODE (arg0) == BIT_FIELD_REF)
6596 && (code == EQ_EXPR || code == NE_EXPR)
6597 /* Handle the constant case even without -O
6598 to make sure the warnings are given. */
6599 && (optimize || TREE_CODE (arg1) == INTEGER_CST))
6601 t1 = optimize_bit_field_compare (code, type, arg0, arg1);
6605 /* If this is a comparison of complex values and either or both sides
6606 are a COMPLEX_EXPR or COMPLEX_CST, it is best to split up the
6607 comparisons and join them with a TRUTH_ANDIF_EXPR or TRUTH_ORIF_EXPR.
6608 This may prevent needless evaluations. */
6609 if ((code == EQ_EXPR || code == NE_EXPR)
6610 && TREE_CODE (TREE_TYPE (arg0)) == COMPLEX_TYPE
6611 && (TREE_CODE (arg0) == COMPLEX_EXPR
6612 || TREE_CODE (arg1) == COMPLEX_EXPR
6613 || TREE_CODE (arg0) == COMPLEX_CST
6614 || TREE_CODE (arg1) == COMPLEX_CST))
6616 tree subtype = TREE_TYPE (TREE_TYPE (arg0));
6617 tree real0, imag0, real1, imag1;
6619 arg0 = save_expr (arg0);
6620 arg1 = save_expr (arg1);
6621 real0 = fold (build1 (REALPART_EXPR, subtype, arg0));
6622 imag0 = fold (build1 (IMAGPART_EXPR, subtype, arg0));
6623 real1 = fold (build1 (REALPART_EXPR, subtype, arg1));
6624 imag1 = fold (build1 (IMAGPART_EXPR, subtype, arg1));
6626 return fold (build ((code == EQ_EXPR ? TRUTH_ANDIF_EXPR
6629 fold (build (code, type, real0, real1)),
6630 fold (build (code, type, imag0, imag1))));
6633 /* Optimize comparisons of strlen vs zero to a compare of the
6634 first character of the string vs zero. To wit,
6635 strlen(ptr) == 0 => *ptr == 0
6636 strlen(ptr) != 0 => *ptr != 0
6637 Other cases should reduce to one of these two (or a constant)
6638 due to the return value of strlen being unsigned. */
6639 if ((code == EQ_EXPR || code == NE_EXPR)
6640 && integer_zerop (arg1)
6641 && TREE_CODE (arg0) == CALL_EXPR
6642 && TREE_CODE (TREE_OPERAND (arg0, 0)) == ADDR_EXPR)
6644 tree fndecl = TREE_OPERAND (TREE_OPERAND (arg0, 0), 0);
6647 if (TREE_CODE (fndecl) == FUNCTION_DECL
6648 && DECL_BUILT_IN (fndecl)
6649 && DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_MD
6650 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STRLEN
6651 && (arglist = TREE_OPERAND (arg0, 1))
6652 && TREE_CODE (TREE_TYPE (TREE_VALUE (arglist))) == POINTER_TYPE
6653 && ! TREE_CHAIN (arglist))
6654 return fold (build (code, type,
6655 build1 (INDIRECT_REF, char_type_node,
6656 TREE_VALUE(arglist)),
6657 integer_zero_node));
6660 /* From here on, the only cases we handle are when the result is
6661 known to be a constant.
6663 To compute GT, swap the arguments and do LT.
6664 To compute GE, do LT and invert the result.
6665 To compute LE, swap the arguments, do LT and invert the result.
6666 To compute NE, do EQ and invert the result.
6668 Therefore, the code below must handle only EQ and LT. */
6670 if (code == LE_EXPR || code == GT_EXPR)
6672 tem = arg0, arg0 = arg1, arg1 = tem;
6673 code = swap_tree_comparison (code);
6676 /* Note that it is safe to invert for real values here because we
6677 will check below in the one case that it matters. */
6681 if (code == NE_EXPR || code == GE_EXPR)
6684 code = invert_tree_comparison (code);
6687 /* Compute a result for LT or EQ if args permit;
6688 otherwise return T. */
6689 if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
6691 if (code == EQ_EXPR)
6692 t1 = build_int_2 (tree_int_cst_equal (arg0, arg1), 0);
6694 t1 = build_int_2 ((TREE_UNSIGNED (TREE_TYPE (arg0))
6695 ? INT_CST_LT_UNSIGNED (arg0, arg1)
6696 : INT_CST_LT (arg0, arg1)),
6700 #if 0 /* This is no longer useful, but breaks some real code. */
6701 /* Assume a nonexplicit constant cannot equal an explicit one,
6702 since such code would be undefined anyway.
6703 Exception: on sysvr4, using #pragma weak,
6704 a label can come out as 0. */
6705 else if (TREE_CODE (arg1) == INTEGER_CST
6706 && !integer_zerop (arg1)
6707 && TREE_CONSTANT (arg0)
6708 && TREE_CODE (arg0) == ADDR_EXPR
6710 t1 = build_int_2 (0, 0);
6712 /* Two real constants can be compared explicitly. */
6713 else if (TREE_CODE (arg0) == REAL_CST && TREE_CODE (arg1) == REAL_CST)
6715 /* If either operand is a NaN, the result is false with two
6716 exceptions: First, an NE_EXPR is true on NaNs, but that case
6717 is already handled correctly since we will be inverting the
6718 result for NE_EXPR. Second, if we had inverted a LE_EXPR
6719 or a GE_EXPR into a LT_EXPR, we must return true so that it
6720 will be inverted into false. */
6722 if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg0))
6723 || REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
6724 t1 = build_int_2 (invert && code == LT_EXPR, 0);
6726 else if (code == EQ_EXPR)
6727 t1 = build_int_2 (REAL_VALUES_EQUAL (TREE_REAL_CST (arg0),
6728 TREE_REAL_CST (arg1)),
6731 t1 = build_int_2 (REAL_VALUES_LESS (TREE_REAL_CST (arg0),
6732 TREE_REAL_CST (arg1)),
6736 if (t1 == NULL_TREE)
6740 TREE_INT_CST_LOW (t1) ^= 1;
6742 TREE_TYPE (t1) = type;
6743 if (TREE_CODE (type) == BOOLEAN_TYPE)
6744 return (*lang_hooks.truthvalue_conversion) (t1);
6748 /* Pedantic ANSI C says that a conditional expression is never an lvalue,
6749 so all simple results must be passed through pedantic_non_lvalue. */
6750 if (TREE_CODE (arg0) == INTEGER_CST)
6751 return pedantic_non_lvalue
6752 (TREE_OPERAND (t, (integer_zerop (arg0) ? 2 : 1)));
6753 else if (operand_equal_p (arg1, TREE_OPERAND (expr, 2), 0))
6754 return pedantic_omit_one_operand (type, arg1, arg0);
6756 /* If the second operand is zero, invert the comparison and swap
6757 the second and third operands. Likewise if the second operand
6758 is constant and the third is not or if the third operand is
6759 equivalent to the first operand of the comparison. */
6761 if (integer_zerop (arg1)
6762 || (TREE_CONSTANT (arg1) && ! TREE_CONSTANT (TREE_OPERAND (t, 2)))
6763 || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
6764 && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
6765 TREE_OPERAND (t, 2),
6766 TREE_OPERAND (arg0, 1))))
6768 /* See if this can be inverted. If it can't, possibly because
6769 it was a floating-point inequality comparison, don't do
6771 tem = invert_truthvalue (arg0);
6773 if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
6775 t = build (code, type, tem,
6776 TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
6778 /* arg1 should be the first argument of the new T. */
6779 arg1 = TREE_OPERAND (t, 1);
6784 /* If we have A op B ? A : C, we may be able to convert this to a
6785 simpler expression, depending on the operation and the values
6786 of B and C. Signed zeros prevent all of these transformations,
6787 for reasons given above each one. */
6789 if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
6790 && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
6791 arg1, TREE_OPERAND (arg0, 1))
6792 && !HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
6794 tree arg2 = TREE_OPERAND (t, 2);
6795 enum tree_code comp_code = TREE_CODE (arg0);
6799 /* If we have A op 0 ? A : -A, consider applying the following
6802 A == 0? A : -A same as -A
6803 A != 0? A : -A same as A
6804 A >= 0? A : -A same as abs (A)
6805 A > 0? A : -A same as abs (A)
6806 A <= 0? A : -A same as -abs (A)
6807 A < 0? A : -A same as -abs (A)
6809 None of these transformations work for modes with signed
6810 zeros. If A is +/-0, the first two transformations will
6811 change the sign of the result (from +0 to -0, or vice
6812 versa). The last four will fix the sign of the result,
6813 even though the original expressions could be positive or
6814 negative, depending on the sign of A.
6816 Note that all these transformations are correct if A is
6817 NaN, since the two alternatives (A and -A) are also NaNs. */
6818 if ((FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 1)))
6819 ? real_zerop (TREE_OPERAND (arg0, 1))
6820 : integer_zerop (TREE_OPERAND (arg0, 1)))
6821 && TREE_CODE (arg2) == NEGATE_EXPR
6822 && operand_equal_p (TREE_OPERAND (arg2, 0), arg1, 0))
6830 (convert (TREE_TYPE (TREE_OPERAND (t, 1)),
6833 return pedantic_non_lvalue (convert (type, arg1));
6836 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6837 arg1 = convert ((*lang_hooks.types.signed_type)
6838 (TREE_TYPE (arg1)), arg1);
6839 return pedantic_non_lvalue
6840 (convert (type, fold (build1 (ABS_EXPR,
6841 TREE_TYPE (arg1), arg1))));
6844 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6845 arg1 = convert ((lang_hooks.types.signed_type)
6846 (TREE_TYPE (arg1)), arg1);
6847 return pedantic_non_lvalue
6848 (negate_expr (convert (type,
6849 fold (build1 (ABS_EXPR,
6856 /* A != 0 ? A : 0 is simply A, unless A is -0. Likewise
6857 A == 0 ? A : 0 is always 0 unless A is -0. Note that
6858 both transformations are correct when A is NaN: A != 0
6859 is then true, and A == 0 is false. */
6861 if (integer_zerop (TREE_OPERAND (arg0, 1)) && integer_zerop (arg2))
6863 if (comp_code == NE_EXPR)
6864 return pedantic_non_lvalue (convert (type, arg1));
6865 else if (comp_code == EQ_EXPR)
6866 return pedantic_non_lvalue (convert (type, integer_zero_node));
6869 /* Try some transformations of A op B ? A : B.
6871 A == B? A : B same as B
6872 A != B? A : B same as A
6873 A >= B? A : B same as max (A, B)
6874 A > B? A : B same as max (B, A)
6875 A <= B? A : B same as min (A, B)
6876 A < B? A : B same as min (B, A)
6878 As above, these transformations don't work in the presence
6879 of signed zeros. For example, if A and B are zeros of
6880 opposite sign, the first two transformations will change
6881 the sign of the result. In the last four, the original
6882 expressions give different results for (A=+0, B=-0) and
6883 (A=-0, B=+0), but the transformed expressions do not.
6885 The first two transformations are correct if either A or B
6886 is a NaN. In the first transformation, the condition will
6887 be false, and B will indeed be chosen. In the case of the
6888 second transformation, the condition A != B will be true,
6889 and A will be chosen.
6891 The conversions to max() and min() are not correct if B is
6892 a number and A is not. The conditions in the original
6893 expressions will be false, so all four give B. The min()
6894 and max() versions would give a NaN instead. */
6895 if (operand_equal_for_comparison_p (TREE_OPERAND (arg0, 1),
6896 arg2, TREE_OPERAND (arg0, 0)))
6898 tree comp_op0 = TREE_OPERAND (arg0, 0);
6899 tree comp_op1 = TREE_OPERAND (arg0, 1);
6900 tree comp_type = TREE_TYPE (comp_op0);
6902 /* Avoid adding NOP_EXPRs in case this is an lvalue. */
6903 if (TYPE_MAIN_VARIANT (comp_type) == TYPE_MAIN_VARIANT (type))
6909 return pedantic_non_lvalue (convert (type, arg2));
6911 return pedantic_non_lvalue (convert (type, arg1));
6914 /* In C++ a ?: expression can be an lvalue, so put the
6915 operand which will be used if they are equal first
6916 so that we can convert this back to the
6917 corresponding COND_EXPR. */
6918 if (!HONOR_NANS (TYPE_MODE (TREE_TYPE (arg1))))
6919 return pedantic_non_lvalue
6920 (convert (type, fold (build (MIN_EXPR, comp_type,
6921 (comp_code == LE_EXPR
6922 ? comp_op0 : comp_op1),
6923 (comp_code == LE_EXPR
6924 ? comp_op1 : comp_op0)))));
6928 if (!HONOR_NANS (TYPE_MODE (TREE_TYPE (arg1))))
6929 return pedantic_non_lvalue
6930 (convert (type, fold (build (MAX_EXPR, comp_type,
6931 (comp_code == GE_EXPR
6932 ? comp_op0 : comp_op1),
6933 (comp_code == GE_EXPR
6934 ? comp_op1 : comp_op0)))));
6941 /* If this is A op C1 ? A : C2 with C1 and C2 constant integers,
6942 we might still be able to simplify this. For example,
6943 if C1 is one less or one more than C2, this might have started
6944 out as a MIN or MAX and been transformed by this function.
6945 Only good for INTEGER_TYPEs, because we need TYPE_MAX_VALUE. */
6947 if (INTEGRAL_TYPE_P (type)
6948 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
6949 && TREE_CODE (arg2) == INTEGER_CST)
6953 /* We can replace A with C1 in this case. */
6954 arg1 = convert (type, TREE_OPERAND (arg0, 1));
6955 t = build (code, type, TREE_OPERAND (t, 0), arg1,
6956 TREE_OPERAND (t, 2));
6960 /* If C1 is C2 + 1, this is min(A, C2). */
6961 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
6962 && operand_equal_p (TREE_OPERAND (arg0, 1),
6963 const_binop (PLUS_EXPR, arg2,
6964 integer_one_node, 0), 1))
6965 return pedantic_non_lvalue
6966 (fold (build (MIN_EXPR, type, arg1, arg2)));
6970 /* If C1 is C2 - 1, this is min(A, C2). */
6971 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
6972 && operand_equal_p (TREE_OPERAND (arg0, 1),
6973 const_binop (MINUS_EXPR, arg2,
6974 integer_one_node, 0), 1))
6975 return pedantic_non_lvalue
6976 (fold (build (MIN_EXPR, type, arg1, arg2)));
6980 /* If C1 is C2 - 1, this is max(A, C2). */
6981 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
6982 && operand_equal_p (TREE_OPERAND (arg0, 1),
6983 const_binop (MINUS_EXPR, arg2,
6984 integer_one_node, 0), 1))
6985 return pedantic_non_lvalue
6986 (fold (build (MAX_EXPR, type, arg1, arg2)));
6990 /* If C1 is C2 + 1, this is max(A, C2). */
6991 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
6992 && operand_equal_p (TREE_OPERAND (arg0, 1),
6993 const_binop (PLUS_EXPR, arg2,
6994 integer_one_node, 0), 1))
6995 return pedantic_non_lvalue
6996 (fold (build (MAX_EXPR, type, arg1, arg2)));
7005 /* If the second operand is simpler than the third, swap them
7006 since that produces better jump optimization results. */
7007 if ((TREE_CONSTANT (arg1) || DECL_P (arg1)
7008 || TREE_CODE (arg1) == SAVE_EXPR)
7009 && ! (TREE_CONSTANT (TREE_OPERAND (t, 2))
7010 || DECL_P (TREE_OPERAND (t, 2))
7011 || TREE_CODE (TREE_OPERAND (t, 2)) == SAVE_EXPR))
7013 /* See if this can be inverted. If it can't, possibly because
7014 it was a floating-point inequality comparison, don't do
7016 tem = invert_truthvalue (arg0);
7018 if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
7020 t = build (code, type, tem,
7021 TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
7023 /* arg1 should be the first argument of the new T. */
7024 arg1 = TREE_OPERAND (t, 1);
7029 /* Convert A ? 1 : 0 to simply A. */
7030 if (integer_onep (TREE_OPERAND (t, 1))
7031 && integer_zerop (TREE_OPERAND (t, 2))
7032 /* If we try to convert TREE_OPERAND (t, 0) to our type, the
7033 call to fold will try to move the conversion inside
7034 a COND, which will recurse. In that case, the COND_EXPR
7035 is probably the best choice, so leave it alone. */
7036 && type == TREE_TYPE (arg0))
7037 return pedantic_non_lvalue (arg0);
7039 /* Look for expressions of the form A & 2 ? 2 : 0. The result of this
7040 operation is simply A & 2. */
7042 if (integer_zerop (TREE_OPERAND (t, 2))
7043 && TREE_CODE (arg0) == NE_EXPR
7044 && integer_zerop (TREE_OPERAND (arg0, 1))
7045 && integer_pow2p (arg1)
7046 && TREE_CODE (TREE_OPERAND (arg0, 0)) == BIT_AND_EXPR
7047 && operand_equal_p (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1),
7049 return pedantic_non_lvalue (convert (type, TREE_OPERAND (arg0, 0)));
7054 /* When pedantic, a compound expression can be neither an lvalue
7055 nor an integer constant expression. */
7056 if (TREE_SIDE_EFFECTS (arg0) || pedantic)
7058 /* Don't let (0, 0) be null pointer constant. */
7059 if (integer_zerop (arg1))
7060 return build1 (NOP_EXPR, type, arg1);
7061 return convert (type, arg1);
7065 return build_complex (type, arg0, arg1);
7069 if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
7071 else if (TREE_CODE (arg0) == COMPLEX_EXPR)
7072 return omit_one_operand (type, TREE_OPERAND (arg0, 0),
7073 TREE_OPERAND (arg0, 1));
7074 else if (TREE_CODE (arg0) == COMPLEX_CST)
7075 return TREE_REALPART (arg0);
7076 else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
7077 return fold (build (TREE_CODE (arg0), type,
7078 fold (build1 (REALPART_EXPR, type,
7079 TREE_OPERAND (arg0, 0))),
7080 fold (build1 (REALPART_EXPR,
7081 type, TREE_OPERAND (arg0, 1)))));
7085 if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
7086 return convert (type, integer_zero_node);
7087 else if (TREE_CODE (arg0) == COMPLEX_EXPR)
7088 return omit_one_operand (type, TREE_OPERAND (arg0, 1),
7089 TREE_OPERAND (arg0, 0));
7090 else if (TREE_CODE (arg0) == COMPLEX_CST)
7091 return TREE_IMAGPART (arg0);
7092 else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
7093 return fold (build (TREE_CODE (arg0), type,
7094 fold (build1 (IMAGPART_EXPR, type,
7095 TREE_OPERAND (arg0, 0))),
7096 fold (build1 (IMAGPART_EXPR, type,
7097 TREE_OPERAND (arg0, 1)))));
7100 /* Pull arithmetic ops out of the CLEANUP_POINT_EXPR where
7102 case CLEANUP_POINT_EXPR:
7103 if (! has_cleanups (arg0))
7104 return TREE_OPERAND (t, 0);
7107 enum tree_code code0 = TREE_CODE (arg0);
7108 int kind0 = TREE_CODE_CLASS (code0);
7109 tree arg00 = TREE_OPERAND (arg0, 0);
7112 if (kind0 == '1' || code0 == TRUTH_NOT_EXPR)
7113 return fold (build1 (code0, type,
7114 fold (build1 (CLEANUP_POINT_EXPR,
7115 TREE_TYPE (arg00), arg00))));
7117 if (kind0 == '<' || kind0 == '2'
7118 || code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR
7119 || code0 == TRUTH_AND_EXPR || code0 == TRUTH_OR_EXPR
7120 || code0 == TRUTH_XOR_EXPR)
7122 arg01 = TREE_OPERAND (arg0, 1);
7124 if (TREE_CONSTANT (arg00)
7125 || ((code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR)
7126 && ! has_cleanups (arg00)))
7127 return fold (build (code0, type, arg00,
7128 fold (build1 (CLEANUP_POINT_EXPR,
7129 TREE_TYPE (arg01), arg01))));
7131 if (TREE_CONSTANT (arg01))
7132 return fold (build (code0, type,
7133 fold (build1 (CLEANUP_POINT_EXPR,
7134 TREE_TYPE (arg00), arg00)),
7142 /* Check for a built-in function. */
7143 if (TREE_CODE (TREE_OPERAND (expr, 0)) == ADDR_EXPR
7144 && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (expr, 0), 0))
7146 && DECL_BUILT_IN (TREE_OPERAND (TREE_OPERAND (expr, 0), 0)))
7148 tree tmp = fold_builtin (expr);
7156 } /* switch (code) */
7159 /* Determine if first argument is a multiple of second argument. Return 0 if
7160 it is not, or we cannot easily determined it to be.
7162 An example of the sort of thing we care about (at this point; this routine
7163 could surely be made more general, and expanded to do what the *_DIV_EXPR's
7164 fold cases do now) is discovering that
7166 SAVE_EXPR (I) * SAVE_EXPR (J * 8)
7172 when we know that the two SAVE_EXPR (J * 8) nodes are the same node.
7174 This code also handles discovering that
7176 SAVE_EXPR (I) * SAVE_EXPR (J * 8)
7178 is a multiple of 8 so we don't have to worry about dealing with a
7181 Note that we *look* inside a SAVE_EXPR only to determine how it was
7182 calculated; it is not safe for fold to do much of anything else with the
7183 internals of a SAVE_EXPR, since it cannot know when it will be evaluated
7184 at run time. For example, the latter example above *cannot* be implemented
7185 as SAVE_EXPR (I) * J or any variant thereof, since the value of J at
7186 evaluation time of the original SAVE_EXPR is not necessarily the same at
7187 the time the new expression is evaluated. The only optimization of this
7188 sort that would be valid is changing
7190 SAVE_EXPR (I) * SAVE_EXPR (SAVE_EXPR (J) * 8)
7194 SAVE_EXPR (I) * SAVE_EXPR (J)
7196 (where the same SAVE_EXPR (J) is used in the original and the
7197 transformed version). */
7200 multiple_of_p (type, top, bottom)
7205 if (operand_equal_p (top, bottom, 0))
7208 if (TREE_CODE (type) != INTEGER_TYPE)
7211 switch (TREE_CODE (top))
7214 return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
7215 || multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
7219 return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
7220 && multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
7223 if (TREE_CODE (TREE_OPERAND (top, 1)) == INTEGER_CST)
7227 op1 = TREE_OPERAND (top, 1);
7228 /* const_binop may not detect overflow correctly,
7229 so check for it explicitly here. */
7230 if (TYPE_PRECISION (TREE_TYPE (size_one_node))
7231 > TREE_INT_CST_LOW (op1)
7232 && TREE_INT_CST_HIGH (op1) == 0
7233 && 0 != (t1 = convert (type,
7234 const_binop (LSHIFT_EXPR, size_one_node,
7236 && ! TREE_OVERFLOW (t1))
7237 return multiple_of_p (type, t1, bottom);
7242 /* Can't handle conversions from non-integral or wider integral type. */
7243 if ((TREE_CODE (TREE_TYPE (TREE_OPERAND (top, 0))) != INTEGER_TYPE)
7244 || (TYPE_PRECISION (type)
7245 < TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (top, 0)))))
7248 /* .. fall through ... */
7251 return multiple_of_p (type, TREE_OPERAND (top, 0), bottom);
7254 if (TREE_CODE (bottom) != INTEGER_CST
7255 || (TREE_UNSIGNED (type)
7256 && (tree_int_cst_sgn (top) < 0
7257 || tree_int_cst_sgn (bottom) < 0)))
7259 return integer_zerop (const_binop (TRUNC_MOD_EXPR,
7267 /* Return true if `t' is known to be non-negative. */
7270 tree_expr_nonnegative_p (t)
7273 switch (TREE_CODE (t))
7279 return tree_int_cst_sgn (t) >= 0;
7280 case TRUNC_DIV_EXPR:
7282 case FLOOR_DIV_EXPR:
7283 case ROUND_DIV_EXPR:
7284 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
7285 && tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7286 case TRUNC_MOD_EXPR:
7288 case FLOOR_MOD_EXPR:
7289 case ROUND_MOD_EXPR:
7290 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
7292 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1))
7293 && tree_expr_nonnegative_p (TREE_OPERAND (t, 2));
7295 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7297 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
7298 && tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7300 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
7301 || tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7303 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7305 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7307 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
7308 case NON_LVALUE_EXPR:
7309 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
7311 return rtl_expr_nonnegative_p (RTL_EXPR_RTL (t));
7314 if (truth_value_p (TREE_CODE (t)))
7315 /* Truth values evaluate to 0 or 1, which is nonnegative. */
7318 /* We don't know sign of `t', so be conservative and return false. */
7323 /* Return true if `r' is known to be non-negative.
7324 Only handles constants at the moment. */
7327 rtl_expr_nonnegative_p (r)
7330 switch (GET_CODE (r))
7333 return INTVAL (r) >= 0;
7336 if (GET_MODE (r) == VOIDmode)
7337 return CONST_DOUBLE_HIGH (r) >= 0;
7345 units = CONST_VECTOR_NUNITS (r);
7347 for (i = 0; i < units; ++i)
7349 elt = CONST_VECTOR_ELT (r, i);
7350 if (!rtl_expr_nonnegative_p (elt))
7359 /* These are always nonnegative. */
7367 #include "gt-fold-const.h"