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, 2002,
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 (code == PLUS_EXPR)
1006 if (TREE_CODE (t1) == NEGATE_EXPR)
1007 return build (MINUS_EXPR, type, convert (type, t2),
1008 convert (type, TREE_OPERAND (t1, 0)));
1009 else if (TREE_CODE (t2) == NEGATE_EXPR)
1010 return build (MINUS_EXPR, type, convert (type, t1),
1011 convert (type, TREE_OPERAND (t2, 0)));
1013 return build (code, type, convert (type, t1), convert (type, t2));
1016 return fold (build (code, type, convert (type, t1), convert (type, t2)));
1019 /* Combine two integer constants ARG1 and ARG2 under operation CODE
1020 to produce a new constant.
1022 If NOTRUNC is nonzero, do not truncate the result to fit the data type. */
1025 int_const_binop (code, arg1, arg2, notrunc)
1026 enum tree_code code;
1030 unsigned HOST_WIDE_INT int1l, int2l;
1031 HOST_WIDE_INT int1h, int2h;
1032 unsigned HOST_WIDE_INT low;
1034 unsigned HOST_WIDE_INT garbagel;
1035 HOST_WIDE_INT garbageh;
1037 tree type = TREE_TYPE (arg1);
1038 int uns = TREE_UNSIGNED (type);
1040 = (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type));
1042 int no_overflow = 0;
1044 int1l = TREE_INT_CST_LOW (arg1);
1045 int1h = TREE_INT_CST_HIGH (arg1);
1046 int2l = TREE_INT_CST_LOW (arg2);
1047 int2h = TREE_INT_CST_HIGH (arg2);
1052 low = int1l | int2l, hi = int1h | int2h;
1056 low = int1l ^ int2l, hi = int1h ^ int2h;
1060 low = int1l & int2l, hi = int1h & int2h;
1063 case BIT_ANDTC_EXPR:
1064 low = int1l & ~int2l, hi = int1h & ~int2h;
1070 /* It's unclear from the C standard whether shifts can overflow.
1071 The following code ignores overflow; perhaps a C standard
1072 interpretation ruling is needed. */
1073 lshift_double (int1l, int1h, int2l, TYPE_PRECISION (type),
1081 lrotate_double (int1l, int1h, int2l, TYPE_PRECISION (type),
1086 overflow = add_double (int1l, int1h, int2l, int2h, &low, &hi);
1090 neg_double (int2l, int2h, &low, &hi);
1091 add_double (int1l, int1h, low, hi, &low, &hi);
1092 overflow = OVERFLOW_SUM_SIGN (hi, int2h, int1h);
1096 overflow = mul_double (int1l, int1h, int2l, int2h, &low, &hi);
1099 case TRUNC_DIV_EXPR:
1100 case FLOOR_DIV_EXPR: case CEIL_DIV_EXPR:
1101 case EXACT_DIV_EXPR:
1102 /* This is a shortcut for a common special case. */
1103 if (int2h == 0 && (HOST_WIDE_INT) int2l > 0
1104 && ! TREE_CONSTANT_OVERFLOW (arg1)
1105 && ! TREE_CONSTANT_OVERFLOW (arg2)
1106 && int1h == 0 && (HOST_WIDE_INT) int1l >= 0)
1108 if (code == CEIL_DIV_EXPR)
1111 low = int1l / int2l, hi = 0;
1115 /* ... fall through ... */
1117 case ROUND_DIV_EXPR:
1118 if (int2h == 0 && int2l == 1)
1120 low = int1l, hi = int1h;
1123 if (int1l == int2l && int1h == int2h
1124 && ! (int1l == 0 && int1h == 0))
1129 overflow = div_and_round_double (code, uns, int1l, int1h, int2l, int2h,
1130 &low, &hi, &garbagel, &garbageh);
1133 case TRUNC_MOD_EXPR:
1134 case FLOOR_MOD_EXPR: case CEIL_MOD_EXPR:
1135 /* This is a shortcut for a common special case. */
1136 if (int2h == 0 && (HOST_WIDE_INT) int2l > 0
1137 && ! TREE_CONSTANT_OVERFLOW (arg1)
1138 && ! TREE_CONSTANT_OVERFLOW (arg2)
1139 && int1h == 0 && (HOST_WIDE_INT) int1l >= 0)
1141 if (code == CEIL_MOD_EXPR)
1143 low = int1l % int2l, hi = 0;
1147 /* ... fall through ... */
1149 case ROUND_MOD_EXPR:
1150 overflow = div_and_round_double (code, uns,
1151 int1l, int1h, int2l, int2h,
1152 &garbagel, &garbageh, &low, &hi);
1158 low = (((unsigned HOST_WIDE_INT) int1h
1159 < (unsigned HOST_WIDE_INT) int2h)
1160 || (((unsigned HOST_WIDE_INT) int1h
1161 == (unsigned HOST_WIDE_INT) int2h)
1164 low = (int1h < int2h
1165 || (int1h == int2h && int1l < int2l));
1167 if (low == (code == MIN_EXPR))
1168 low = int1l, hi = int1h;
1170 low = int2l, hi = int2h;
1177 /* If this is for a sizetype, can be represented as one (signed)
1178 HOST_WIDE_INT word, and doesn't overflow, use size_int since it caches
1181 && ((hi == 0 && (HOST_WIDE_INT) low >= 0)
1182 || (hi == -1 && (HOST_WIDE_INT) low < 0))
1183 && overflow == 0 && ! TREE_OVERFLOW (arg1) && ! TREE_OVERFLOW (arg2))
1184 return size_int_type_wide (low, type);
1187 t = build_int_2 (low, hi);
1188 TREE_TYPE (t) = TREE_TYPE (arg1);
1193 ? (!uns || is_sizetype) && overflow
1194 : (force_fit_type (t, (!uns || is_sizetype) && overflow)
1196 | TREE_OVERFLOW (arg1)
1197 | TREE_OVERFLOW (arg2));
1199 /* If we're doing a size calculation, unsigned arithmetic does overflow.
1200 So check if force_fit_type truncated the value. */
1202 && ! TREE_OVERFLOW (t)
1203 && (TREE_INT_CST_HIGH (t) != hi
1204 || TREE_INT_CST_LOW (t) != low))
1205 TREE_OVERFLOW (t) = 1;
1207 TREE_CONSTANT_OVERFLOW (t) = (TREE_OVERFLOW (t)
1208 | TREE_CONSTANT_OVERFLOW (arg1)
1209 | TREE_CONSTANT_OVERFLOW (arg2));
1213 /* Combine two constants ARG1 and ARG2 under operation CODE to produce a new
1214 constant. We assume ARG1 and ARG2 have the same data type, or at least
1215 are the same kind of constant and the same machine mode.
1217 If NOTRUNC is nonzero, do not truncate the result to fit the data type. */
1220 const_binop (code, arg1, arg2, notrunc)
1221 enum tree_code code;
1228 if (TREE_CODE (arg1) == INTEGER_CST)
1229 return int_const_binop (code, arg1, arg2, notrunc);
1231 if (TREE_CODE (arg1) == REAL_CST)
1235 REAL_VALUE_TYPE value;
1238 d1 = TREE_REAL_CST (arg1);
1239 d2 = TREE_REAL_CST (arg2);
1241 /* If either operand is a NaN, just return it. Otherwise, set up
1242 for floating-point trap; we return an overflow. */
1243 if (REAL_VALUE_ISNAN (d1))
1245 else if (REAL_VALUE_ISNAN (d2))
1248 REAL_ARITHMETIC (value, code, d1, d2);
1250 t = build_real (TREE_TYPE (arg1),
1251 real_value_truncate (TYPE_MODE (TREE_TYPE (arg1)),
1255 = (force_fit_type (t, 0)
1256 | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2));
1257 TREE_CONSTANT_OVERFLOW (t)
1259 | TREE_CONSTANT_OVERFLOW (arg1)
1260 | TREE_CONSTANT_OVERFLOW (arg2);
1263 if (TREE_CODE (arg1) == COMPLEX_CST)
1265 tree type = TREE_TYPE (arg1);
1266 tree r1 = TREE_REALPART (arg1);
1267 tree i1 = TREE_IMAGPART (arg1);
1268 tree r2 = TREE_REALPART (arg2);
1269 tree i2 = TREE_IMAGPART (arg2);
1275 t = build_complex (type,
1276 const_binop (PLUS_EXPR, r1, r2, notrunc),
1277 const_binop (PLUS_EXPR, i1, i2, notrunc));
1281 t = build_complex (type,
1282 const_binop (MINUS_EXPR, r1, r2, notrunc),
1283 const_binop (MINUS_EXPR, i1, i2, notrunc));
1287 t = build_complex (type,
1288 const_binop (MINUS_EXPR,
1289 const_binop (MULT_EXPR,
1291 const_binop (MULT_EXPR,
1294 const_binop (PLUS_EXPR,
1295 const_binop (MULT_EXPR,
1297 const_binop (MULT_EXPR,
1305 = const_binop (PLUS_EXPR,
1306 const_binop (MULT_EXPR, r2, r2, notrunc),
1307 const_binop (MULT_EXPR, i2, i2, notrunc),
1310 t = build_complex (type,
1312 (INTEGRAL_TYPE_P (TREE_TYPE (r1))
1313 ? TRUNC_DIV_EXPR : RDIV_EXPR,
1314 const_binop (PLUS_EXPR,
1315 const_binop (MULT_EXPR, r1, r2,
1317 const_binop (MULT_EXPR, i1, i2,
1320 magsquared, notrunc),
1322 (INTEGRAL_TYPE_P (TREE_TYPE (r1))
1323 ? TRUNC_DIV_EXPR : RDIV_EXPR,
1324 const_binop (MINUS_EXPR,
1325 const_binop (MULT_EXPR, i1, r2,
1327 const_binop (MULT_EXPR, r1, i2,
1330 magsquared, notrunc));
1342 /* These are the hash table functions for the hash table of INTEGER_CST
1343 nodes of a sizetype. */
1345 /* Return the hash code code X, an INTEGER_CST. */
1353 return (TREE_INT_CST_HIGH (t) ^ TREE_INT_CST_LOW (t)
1354 ^ (hashval_t) ((long) TREE_TYPE (t) >> 3)
1355 ^ (TREE_OVERFLOW (t) << 20));
1358 /* Return non-zero if the value represented by *X (an INTEGER_CST tree node)
1359 is the same as that given by *Y, which is the same. */
1369 return (TREE_INT_CST_HIGH (xt) == TREE_INT_CST_HIGH (yt)
1370 && TREE_INT_CST_LOW (xt) == TREE_INT_CST_LOW (yt)
1371 && TREE_TYPE (xt) == TREE_TYPE (yt)
1372 && TREE_OVERFLOW (xt) == TREE_OVERFLOW (yt));
1375 /* Return an INTEGER_CST with value whose low-order HOST_BITS_PER_WIDE_INT
1376 bits are given by NUMBER and of the sizetype represented by KIND. */
1379 size_int_wide (number, kind)
1380 HOST_WIDE_INT number;
1381 enum size_type_kind kind;
1383 return size_int_type_wide (number, sizetype_tab[(int) kind]);
1386 /* Likewise, but the desired type is specified explicitly. */
1388 static GTY (()) tree new_const;
1389 static GTY ((if_marked ("ggc_marked_p"), param_is (union tree_node)))
1393 size_int_type_wide (number, type)
1394 HOST_WIDE_INT number;
1401 size_htab = htab_create (1024, size_htab_hash, size_htab_eq, NULL);
1402 new_const = make_node (INTEGER_CST);
1405 /* Adjust NEW_CONST to be the constant we want. If it's already in the
1406 hash table, we return the value from the hash table. Otherwise, we
1407 place that in the hash table and make a new node for the next time. */
1408 TREE_INT_CST_LOW (new_const) = number;
1409 TREE_INT_CST_HIGH (new_const) = number < 0 ? -1 : 0;
1410 TREE_TYPE (new_const) = type;
1411 TREE_OVERFLOW (new_const) = TREE_CONSTANT_OVERFLOW (new_const)
1412 = force_fit_type (new_const, 0);
1414 slot = htab_find_slot (size_htab, new_const, INSERT);
1419 *slot = (PTR) new_const;
1420 new_const = make_node (INTEGER_CST);
1424 return (tree) *slot;
1427 /* Combine operands OP1 and OP2 with arithmetic operation CODE. CODE
1428 is a tree code. The type of the result is taken from the operands.
1429 Both must be the same type integer type and it must be a size type.
1430 If the operands are constant, so is the result. */
1433 size_binop (code, arg0, arg1)
1434 enum tree_code code;
1437 tree type = TREE_TYPE (arg0);
1439 if (TREE_CODE (type) != INTEGER_TYPE || ! TYPE_IS_SIZETYPE (type)
1440 || type != TREE_TYPE (arg1))
1443 /* Handle the special case of two integer constants faster. */
1444 if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
1446 /* And some specific cases even faster than that. */
1447 if (code == PLUS_EXPR && integer_zerop (arg0))
1449 else if ((code == MINUS_EXPR || code == PLUS_EXPR)
1450 && integer_zerop (arg1))
1452 else if (code == MULT_EXPR && integer_onep (arg0))
1455 /* Handle general case of two integer constants. */
1456 return int_const_binop (code, arg0, arg1, 0);
1459 if (arg0 == error_mark_node || arg1 == error_mark_node)
1460 return error_mark_node;
1462 return fold (build (code, type, arg0, arg1));
1465 /* Given two values, either both of sizetype or both of bitsizetype,
1466 compute the difference between the two values. Return the value
1467 in signed type corresponding to the type of the operands. */
1470 size_diffop (arg0, arg1)
1473 tree type = TREE_TYPE (arg0);
1476 if (TREE_CODE (type) != INTEGER_TYPE || ! TYPE_IS_SIZETYPE (type)
1477 || type != TREE_TYPE (arg1))
1480 /* If the type is already signed, just do the simple thing. */
1481 if (! TREE_UNSIGNED (type))
1482 return size_binop (MINUS_EXPR, arg0, arg1);
1484 ctype = (type == bitsizetype || type == ubitsizetype
1485 ? sbitsizetype : ssizetype);
1487 /* If either operand is not a constant, do the conversions to the signed
1488 type and subtract. The hardware will do the right thing with any
1489 overflow in the subtraction. */
1490 if (TREE_CODE (arg0) != INTEGER_CST || TREE_CODE (arg1) != INTEGER_CST)
1491 return size_binop (MINUS_EXPR, convert (ctype, arg0),
1492 convert (ctype, arg1));
1494 /* If ARG0 is larger than ARG1, subtract and return the result in CTYPE.
1495 Otherwise, subtract the other way, convert to CTYPE (we know that can't
1496 overflow) and negate (which can't either). Special-case a result
1497 of zero while we're here. */
1498 if (tree_int_cst_equal (arg0, arg1))
1499 return convert (ctype, integer_zero_node);
1500 else if (tree_int_cst_lt (arg1, arg0))
1501 return convert (ctype, size_binop (MINUS_EXPR, arg0, arg1));
1503 return size_binop (MINUS_EXPR, convert (ctype, integer_zero_node),
1504 convert (ctype, size_binop (MINUS_EXPR, arg1, arg0)));
1508 /* Given T, a tree representing type conversion of ARG1, a constant,
1509 return a constant tree representing the result of conversion. */
1512 fold_convert (t, arg1)
1516 tree type = TREE_TYPE (t);
1519 if (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type))
1521 if (TREE_CODE (arg1) == INTEGER_CST)
1523 /* If we would build a constant wider than GCC supports,
1524 leave the conversion unfolded. */
1525 if (TYPE_PRECISION (type) > 2 * HOST_BITS_PER_WIDE_INT)
1528 /* If we are trying to make a sizetype for a small integer, use
1529 size_int to pick up cached types to reduce duplicate nodes. */
1530 if (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type)
1531 && !TREE_CONSTANT_OVERFLOW (arg1)
1532 && compare_tree_int (arg1, 10000) < 0)
1533 return size_int_type_wide (TREE_INT_CST_LOW (arg1), type);
1535 /* Given an integer constant, make new constant with new type,
1536 appropriately sign-extended or truncated. */
1537 t = build_int_2 (TREE_INT_CST_LOW (arg1),
1538 TREE_INT_CST_HIGH (arg1));
1539 TREE_TYPE (t) = type;
1540 /* Indicate an overflow if (1) ARG1 already overflowed,
1541 or (2) force_fit_type indicates an overflow.
1542 Tell force_fit_type that an overflow has already occurred
1543 if ARG1 is a too-large unsigned value and T is signed.
1544 But don't indicate an overflow if converting a pointer. */
1546 = ((force_fit_type (t,
1547 (TREE_INT_CST_HIGH (arg1) < 0
1548 && (TREE_UNSIGNED (type)
1549 < TREE_UNSIGNED (TREE_TYPE (arg1)))))
1550 && ! POINTER_TYPE_P (TREE_TYPE (arg1)))
1551 || TREE_OVERFLOW (arg1));
1552 TREE_CONSTANT_OVERFLOW (t)
1553 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1555 else if (TREE_CODE (arg1) == REAL_CST)
1557 /* Don't initialize these, use assignments.
1558 Initialized local aggregates don't work on old compilers. */
1562 tree type1 = TREE_TYPE (arg1);
1565 x = TREE_REAL_CST (arg1);
1566 l = real_value_from_int_cst (type1, TYPE_MIN_VALUE (type));
1568 no_upper_bound = (TYPE_MAX_VALUE (type) == NULL);
1569 if (!no_upper_bound)
1570 u = real_value_from_int_cst (type1, TYPE_MAX_VALUE (type));
1572 /* See if X will be in range after truncation towards 0.
1573 To compensate for truncation, move the bounds away from 0,
1574 but reject if X exactly equals the adjusted bounds. */
1575 REAL_ARITHMETIC (l, MINUS_EXPR, l, dconst1);
1576 if (!no_upper_bound)
1577 REAL_ARITHMETIC (u, PLUS_EXPR, u, dconst1);
1578 /* If X is a NaN, use zero instead and show we have an overflow.
1579 Otherwise, range check. */
1580 if (REAL_VALUE_ISNAN (x))
1581 overflow = 1, x = dconst0;
1582 else if (! (REAL_VALUES_LESS (l, x)
1584 && REAL_VALUES_LESS (x, u)))
1588 HOST_WIDE_INT low, high;
1589 REAL_VALUE_TO_INT (&low, &high, x);
1590 t = build_int_2 (low, high);
1592 TREE_TYPE (t) = type;
1594 = TREE_OVERFLOW (arg1) | force_fit_type (t, overflow);
1595 TREE_CONSTANT_OVERFLOW (t)
1596 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1598 TREE_TYPE (t) = type;
1600 else if (TREE_CODE (type) == REAL_TYPE)
1602 if (TREE_CODE (arg1) == INTEGER_CST)
1603 return build_real_from_int_cst (type, arg1);
1604 if (TREE_CODE (arg1) == REAL_CST)
1606 if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
1608 /* We make a copy of ARG1 so that we don't modify an
1609 existing constant tree. */
1610 t = copy_node (arg1);
1611 TREE_TYPE (t) = type;
1615 t = build_real (type,
1616 real_value_truncate (TYPE_MODE (type),
1617 TREE_REAL_CST (arg1)));
1620 = TREE_OVERFLOW (arg1) | force_fit_type (t, 0);
1621 TREE_CONSTANT_OVERFLOW (t)
1622 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1626 TREE_CONSTANT (t) = 1;
1630 /* Return an expr equal to X but certainly not valid as an lvalue. */
1638 /* These things are certainly not lvalues. */
1639 if (TREE_CODE (x) == NON_LVALUE_EXPR
1640 || TREE_CODE (x) == INTEGER_CST
1641 || TREE_CODE (x) == REAL_CST
1642 || TREE_CODE (x) == STRING_CST
1643 || TREE_CODE (x) == ADDR_EXPR)
1646 result = build1 (NON_LVALUE_EXPR, TREE_TYPE (x), x);
1647 TREE_CONSTANT (result) = TREE_CONSTANT (x);
1651 /* Nonzero means lvalues are limited to those valid in pedantic ANSI C.
1652 Zero means allow extended lvalues. */
1654 int pedantic_lvalues;
1656 /* When pedantic, return an expr equal to X but certainly not valid as a
1657 pedantic lvalue. Otherwise, return X. */
1660 pedantic_non_lvalue (x)
1663 if (pedantic_lvalues)
1664 return non_lvalue (x);
1669 /* Given a tree comparison code, return the code that is the logical inverse
1670 of the given code. It is not safe to do this for floating-point
1671 comparisons, except for NE_EXPR and EQ_EXPR. */
1673 static enum tree_code
1674 invert_tree_comparison (code)
1675 enum tree_code code;
1696 /* Similar, but return the comparison that results if the operands are
1697 swapped. This is safe for floating-point. */
1699 static enum tree_code
1700 swap_tree_comparison (code)
1701 enum tree_code code;
1722 /* Convert a comparison tree code from an enum tree_code representation
1723 into a compcode bit-based encoding. This function is the inverse of
1724 compcode_to_comparison. */
1727 comparison_to_compcode (code)
1728 enum tree_code code;
1749 /* Convert a compcode bit-based encoding of a comparison operator back
1750 to GCC's enum tree_code representation. This function is the
1751 inverse of comparison_to_compcode. */
1753 static enum tree_code
1754 compcode_to_comparison (code)
1776 /* Return nonzero if CODE is a tree code that represents a truth value. */
1779 truth_value_p (code)
1780 enum tree_code code;
1782 return (TREE_CODE_CLASS (code) == '<'
1783 || code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR
1784 || code == TRUTH_OR_EXPR || code == TRUTH_ORIF_EXPR
1785 || code == TRUTH_XOR_EXPR || code == TRUTH_NOT_EXPR);
1788 /* Return nonzero if two operands are necessarily equal.
1789 If ONLY_CONST is non-zero, only return non-zero for constants.
1790 This function tests whether the operands are indistinguishable;
1791 it does not test whether they are equal using C's == operation.
1792 The distinction is important for IEEE floating point, because
1793 (1) -0.0 and 0.0 are distinguishable, but -0.0==0.0, and
1794 (2) two NaNs may be indistinguishable, but NaN!=NaN. */
1797 operand_equal_p (arg0, arg1, only_const)
1801 /* If both types don't have the same signedness, then we can't consider
1802 them equal. We must check this before the STRIP_NOPS calls
1803 because they may change the signedness of the arguments. */
1804 if (TREE_UNSIGNED (TREE_TYPE (arg0)) != TREE_UNSIGNED (TREE_TYPE (arg1)))
1810 if (TREE_CODE (arg0) != TREE_CODE (arg1)
1811 /* This is needed for conversions and for COMPONENT_REF.
1812 Might as well play it safe and always test this. */
1813 || TREE_CODE (TREE_TYPE (arg0)) == ERROR_MARK
1814 || TREE_CODE (TREE_TYPE (arg1)) == ERROR_MARK
1815 || TYPE_MODE (TREE_TYPE (arg0)) != TYPE_MODE (TREE_TYPE (arg1)))
1818 /* If ARG0 and ARG1 are the same SAVE_EXPR, they are necessarily equal.
1819 We don't care about side effects in that case because the SAVE_EXPR
1820 takes care of that for us. In all other cases, two expressions are
1821 equal if they have no side effects. If we have two identical
1822 expressions with side effects that should be treated the same due
1823 to the only side effects being identical SAVE_EXPR's, that will
1824 be detected in the recursive calls below. */
1825 if (arg0 == arg1 && ! only_const
1826 && (TREE_CODE (arg0) == SAVE_EXPR
1827 || (! TREE_SIDE_EFFECTS (arg0) && ! TREE_SIDE_EFFECTS (arg1))))
1830 /* Next handle constant cases, those for which we can return 1 even
1831 if ONLY_CONST is set. */
1832 if (TREE_CONSTANT (arg0) && TREE_CONSTANT (arg1))
1833 switch (TREE_CODE (arg0))
1836 return (! TREE_CONSTANT_OVERFLOW (arg0)
1837 && ! TREE_CONSTANT_OVERFLOW (arg1)
1838 && tree_int_cst_equal (arg0, arg1));
1841 return (! TREE_CONSTANT_OVERFLOW (arg0)
1842 && ! TREE_CONSTANT_OVERFLOW (arg1)
1843 && REAL_VALUES_IDENTICAL (TREE_REAL_CST (arg0),
1844 TREE_REAL_CST (arg1)));
1850 if (TREE_CONSTANT_OVERFLOW (arg0)
1851 || TREE_CONSTANT_OVERFLOW (arg1))
1854 v1 = TREE_VECTOR_CST_ELTS (arg0);
1855 v2 = TREE_VECTOR_CST_ELTS (arg1);
1858 if (!operand_equal_p (v1, v2, only_const))
1860 v1 = TREE_CHAIN (v1);
1861 v2 = TREE_CHAIN (v2);
1868 return (operand_equal_p (TREE_REALPART (arg0), TREE_REALPART (arg1),
1870 && operand_equal_p (TREE_IMAGPART (arg0), TREE_IMAGPART (arg1),
1874 return (TREE_STRING_LENGTH (arg0) == TREE_STRING_LENGTH (arg1)
1875 && ! memcmp (TREE_STRING_POINTER (arg0),
1876 TREE_STRING_POINTER (arg1),
1877 TREE_STRING_LENGTH (arg0)));
1880 return operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0),
1889 switch (TREE_CODE_CLASS (TREE_CODE (arg0)))
1892 /* Two conversions are equal only if signedness and modes match. */
1893 if ((TREE_CODE (arg0) == NOP_EXPR || TREE_CODE (arg0) == CONVERT_EXPR)
1894 && (TREE_UNSIGNED (TREE_TYPE (arg0))
1895 != TREE_UNSIGNED (TREE_TYPE (arg1))))
1898 return operand_equal_p (TREE_OPERAND (arg0, 0),
1899 TREE_OPERAND (arg1, 0), 0);
1903 if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0)
1904 && operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1),
1908 /* For commutative ops, allow the other order. */
1909 return ((TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MULT_EXPR
1910 || TREE_CODE (arg0) == MIN_EXPR || TREE_CODE (arg0) == MAX_EXPR
1911 || TREE_CODE (arg0) == BIT_IOR_EXPR
1912 || TREE_CODE (arg0) == BIT_XOR_EXPR
1913 || TREE_CODE (arg0) == BIT_AND_EXPR
1914 || TREE_CODE (arg0) == NE_EXPR || TREE_CODE (arg0) == EQ_EXPR)
1915 && operand_equal_p (TREE_OPERAND (arg0, 0),
1916 TREE_OPERAND (arg1, 1), 0)
1917 && operand_equal_p (TREE_OPERAND (arg0, 1),
1918 TREE_OPERAND (arg1, 0), 0));
1921 /* If either of the pointer (or reference) expressions we are dereferencing
1922 contain a side effect, these cannot be equal. */
1923 if (TREE_SIDE_EFFECTS (arg0)
1924 || TREE_SIDE_EFFECTS (arg1))
1927 switch (TREE_CODE (arg0))
1930 return operand_equal_p (TREE_OPERAND (arg0, 0),
1931 TREE_OPERAND (arg1, 0), 0);
1935 case ARRAY_RANGE_REF:
1936 return (operand_equal_p (TREE_OPERAND (arg0, 0),
1937 TREE_OPERAND (arg1, 0), 0)
1938 && operand_equal_p (TREE_OPERAND (arg0, 1),
1939 TREE_OPERAND (arg1, 1), 0));
1942 return (operand_equal_p (TREE_OPERAND (arg0, 0),
1943 TREE_OPERAND (arg1, 0), 0)
1944 && operand_equal_p (TREE_OPERAND (arg0, 1),
1945 TREE_OPERAND (arg1, 1), 0)
1946 && operand_equal_p (TREE_OPERAND (arg0, 2),
1947 TREE_OPERAND (arg1, 2), 0));
1953 if (TREE_CODE (arg0) == RTL_EXPR)
1954 return rtx_equal_p (RTL_EXPR_RTL (arg0), RTL_EXPR_RTL (arg1));
1962 /* Similar to operand_equal_p, but see if ARG0 might have been made by
1963 shorten_compare from ARG1 when ARG1 was being compared with OTHER.
1965 When in doubt, return 0. */
1968 operand_equal_for_comparison_p (arg0, arg1, other)
1972 int unsignedp1, unsignedpo;
1973 tree primarg0, primarg1, primother;
1974 unsigned int correct_width;
1976 if (operand_equal_p (arg0, arg1, 0))
1979 if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0))
1980 || ! INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
1983 /* Discard any conversions that don't change the modes of ARG0 and ARG1
1984 and see if the inner values are the same. This removes any
1985 signedness comparison, which doesn't matter here. */
1986 primarg0 = arg0, primarg1 = arg1;
1987 STRIP_NOPS (primarg0);
1988 STRIP_NOPS (primarg1);
1989 if (operand_equal_p (primarg0, primarg1, 0))
1992 /* Duplicate what shorten_compare does to ARG1 and see if that gives the
1993 actual comparison operand, ARG0.
1995 First throw away any conversions to wider types
1996 already present in the operands. */
1998 primarg1 = get_narrower (arg1, &unsignedp1);
1999 primother = get_narrower (other, &unsignedpo);
2001 correct_width = TYPE_PRECISION (TREE_TYPE (arg1));
2002 if (unsignedp1 == unsignedpo
2003 && TYPE_PRECISION (TREE_TYPE (primarg1)) < correct_width
2004 && TYPE_PRECISION (TREE_TYPE (primother)) < correct_width)
2006 tree type = TREE_TYPE (arg0);
2008 /* Make sure shorter operand is extended the right way
2009 to match the longer operand. */
2010 primarg1 = convert ((*lang_hooks.types.signed_or_unsigned_type)
2011 (unsignedp1, TREE_TYPE (primarg1)), primarg1);
2013 if (operand_equal_p (arg0, convert (type, primarg1), 0))
2020 /* See if ARG is an expression that is either a comparison or is performing
2021 arithmetic on comparisons. The comparisons must only be comparing
2022 two different values, which will be stored in *CVAL1 and *CVAL2; if
2023 they are non-zero it means that some operands have already been found.
2024 No variables may be used anywhere else in the expression except in the
2025 comparisons. If SAVE_P is true it means we removed a SAVE_EXPR around
2026 the expression and save_expr needs to be called with CVAL1 and CVAL2.
2028 If this is true, return 1. Otherwise, return zero. */
2031 twoval_comparison_p (arg, cval1, cval2, save_p)
2033 tree *cval1, *cval2;
2036 enum tree_code code = TREE_CODE (arg);
2037 char class = TREE_CODE_CLASS (code);
2039 /* We can handle some of the 'e' cases here. */
2040 if (class == 'e' && code == TRUTH_NOT_EXPR)
2042 else if (class == 'e'
2043 && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR
2044 || code == COMPOUND_EXPR))
2047 else if (class == 'e' && code == SAVE_EXPR && SAVE_EXPR_RTL (arg) == 0
2048 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg, 0)))
2050 /* If we've already found a CVAL1 or CVAL2, this expression is
2051 two complex to handle. */
2052 if (*cval1 || *cval2)
2062 return twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p);
2065 return (twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p)
2066 && twoval_comparison_p (TREE_OPERAND (arg, 1),
2067 cval1, cval2, save_p));
2073 if (code == COND_EXPR)
2074 return (twoval_comparison_p (TREE_OPERAND (arg, 0),
2075 cval1, cval2, save_p)
2076 && twoval_comparison_p (TREE_OPERAND (arg, 1),
2077 cval1, cval2, save_p)
2078 && twoval_comparison_p (TREE_OPERAND (arg, 2),
2079 cval1, cval2, save_p));
2083 /* First see if we can handle the first operand, then the second. For
2084 the second operand, we know *CVAL1 can't be zero. It must be that
2085 one side of the comparison is each of the values; test for the
2086 case where this isn't true by failing if the two operands
2089 if (operand_equal_p (TREE_OPERAND (arg, 0),
2090 TREE_OPERAND (arg, 1), 0))
2094 *cval1 = TREE_OPERAND (arg, 0);
2095 else if (operand_equal_p (*cval1, TREE_OPERAND (arg, 0), 0))
2097 else if (*cval2 == 0)
2098 *cval2 = TREE_OPERAND (arg, 0);
2099 else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 0), 0))
2104 if (operand_equal_p (*cval1, TREE_OPERAND (arg, 1), 0))
2106 else if (*cval2 == 0)
2107 *cval2 = TREE_OPERAND (arg, 1);
2108 else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 1), 0))
2120 /* ARG is a tree that is known to contain just arithmetic operations and
2121 comparisons. Evaluate the operations in the tree substituting NEW0 for
2122 any occurrence of OLD0 as an operand of a comparison and likewise for
2126 eval_subst (arg, old0, new0, old1, new1)
2128 tree old0, new0, old1, new1;
2130 tree type = TREE_TYPE (arg);
2131 enum tree_code code = TREE_CODE (arg);
2132 char class = TREE_CODE_CLASS (code);
2134 /* We can handle some of the 'e' cases here. */
2135 if (class == 'e' && code == TRUTH_NOT_EXPR)
2137 else if (class == 'e'
2138 && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
2144 return fold (build1 (code, type,
2145 eval_subst (TREE_OPERAND (arg, 0),
2146 old0, new0, old1, new1)));
2149 return fold (build (code, type,
2150 eval_subst (TREE_OPERAND (arg, 0),
2151 old0, new0, old1, new1),
2152 eval_subst (TREE_OPERAND (arg, 1),
2153 old0, new0, old1, new1)));
2159 return eval_subst (TREE_OPERAND (arg, 0), old0, new0, old1, new1);
2162 return eval_subst (TREE_OPERAND (arg, 1), old0, new0, old1, new1);
2165 return fold (build (code, type,
2166 eval_subst (TREE_OPERAND (arg, 0),
2167 old0, new0, old1, new1),
2168 eval_subst (TREE_OPERAND (arg, 1),
2169 old0, new0, old1, new1),
2170 eval_subst (TREE_OPERAND (arg, 2),
2171 old0, new0, old1, new1)));
2175 /* fall through - ??? */
2179 tree arg0 = TREE_OPERAND (arg, 0);
2180 tree arg1 = TREE_OPERAND (arg, 1);
2182 /* We need to check both for exact equality and tree equality. The
2183 former will be true if the operand has a side-effect. In that
2184 case, we know the operand occurred exactly once. */
2186 if (arg0 == old0 || operand_equal_p (arg0, old0, 0))
2188 else if (arg0 == old1 || operand_equal_p (arg0, old1, 0))
2191 if (arg1 == old0 || operand_equal_p (arg1, old0, 0))
2193 else if (arg1 == old1 || operand_equal_p (arg1, old1, 0))
2196 return fold (build (code, type, arg0, arg1));
2204 /* Return a tree for the case when the result of an expression is RESULT
2205 converted to TYPE and OMITTED was previously an operand of the expression
2206 but is now not needed (e.g., we folded OMITTED * 0).
2208 If OMITTED has side effects, we must evaluate it. Otherwise, just do
2209 the conversion of RESULT to TYPE. */
2212 omit_one_operand (type, result, omitted)
2213 tree type, result, omitted;
2215 tree t = convert (type, result);
2217 if (TREE_SIDE_EFFECTS (omitted))
2218 return build (COMPOUND_EXPR, type, omitted, t);
2220 return non_lvalue (t);
2223 /* Similar, but call pedantic_non_lvalue instead of non_lvalue. */
2226 pedantic_omit_one_operand (type, result, omitted)
2227 tree type, result, omitted;
2229 tree t = convert (type, result);
2231 if (TREE_SIDE_EFFECTS (omitted))
2232 return build (COMPOUND_EXPR, type, omitted, t);
2234 return pedantic_non_lvalue (t);
2237 /* Return a simplified tree node for the truth-negation of ARG. This
2238 never alters ARG itself. We assume that ARG is an operation that
2239 returns a truth value (0 or 1). */
2242 invert_truthvalue (arg)
2245 tree type = TREE_TYPE (arg);
2246 enum tree_code code = TREE_CODE (arg);
2248 if (code == ERROR_MARK)
2251 /* If this is a comparison, we can simply invert it, except for
2252 floating-point non-equality comparisons, in which case we just
2253 enclose a TRUTH_NOT_EXPR around what we have. */
2255 if (TREE_CODE_CLASS (code) == '<')
2257 if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg, 0)))
2258 && !flag_unsafe_math_optimizations
2261 return build1 (TRUTH_NOT_EXPR, type, arg);
2263 return build (invert_tree_comparison (code), type,
2264 TREE_OPERAND (arg, 0), TREE_OPERAND (arg, 1));
2270 return convert (type, build_int_2 (integer_zerop (arg), 0));
2272 case TRUTH_AND_EXPR:
2273 return build (TRUTH_OR_EXPR, type,
2274 invert_truthvalue (TREE_OPERAND (arg, 0)),
2275 invert_truthvalue (TREE_OPERAND (arg, 1)));
2278 return build (TRUTH_AND_EXPR, type,
2279 invert_truthvalue (TREE_OPERAND (arg, 0)),
2280 invert_truthvalue (TREE_OPERAND (arg, 1)));
2282 case TRUTH_XOR_EXPR:
2283 /* Here we can invert either operand. We invert the first operand
2284 unless the second operand is a TRUTH_NOT_EXPR in which case our
2285 result is the XOR of the first operand with the inside of the
2286 negation of the second operand. */
2288 if (TREE_CODE (TREE_OPERAND (arg, 1)) == TRUTH_NOT_EXPR)
2289 return build (TRUTH_XOR_EXPR, type, TREE_OPERAND (arg, 0),
2290 TREE_OPERAND (TREE_OPERAND (arg, 1), 0));
2292 return build (TRUTH_XOR_EXPR, type,
2293 invert_truthvalue (TREE_OPERAND (arg, 0)),
2294 TREE_OPERAND (arg, 1));
2296 case TRUTH_ANDIF_EXPR:
2297 return build (TRUTH_ORIF_EXPR, type,
2298 invert_truthvalue (TREE_OPERAND (arg, 0)),
2299 invert_truthvalue (TREE_OPERAND (arg, 1)));
2301 case TRUTH_ORIF_EXPR:
2302 return build (TRUTH_ANDIF_EXPR, type,
2303 invert_truthvalue (TREE_OPERAND (arg, 0)),
2304 invert_truthvalue (TREE_OPERAND (arg, 1)));
2306 case TRUTH_NOT_EXPR:
2307 return TREE_OPERAND (arg, 0);
2310 return build (COND_EXPR, type, TREE_OPERAND (arg, 0),
2311 invert_truthvalue (TREE_OPERAND (arg, 1)),
2312 invert_truthvalue (TREE_OPERAND (arg, 2)));
2315 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg, 0),
2316 invert_truthvalue (TREE_OPERAND (arg, 1)));
2318 case WITH_RECORD_EXPR:
2319 return build (WITH_RECORD_EXPR, type,
2320 invert_truthvalue (TREE_OPERAND (arg, 0)),
2321 TREE_OPERAND (arg, 1));
2323 case NON_LVALUE_EXPR:
2324 return invert_truthvalue (TREE_OPERAND (arg, 0));
2329 return build1 (TREE_CODE (arg), type,
2330 invert_truthvalue (TREE_OPERAND (arg, 0)));
2333 if (!integer_onep (TREE_OPERAND (arg, 1)))
2335 return build (EQ_EXPR, type, arg, convert (type, integer_zero_node));
2338 return build1 (TRUTH_NOT_EXPR, type, arg);
2340 case CLEANUP_POINT_EXPR:
2341 return build1 (CLEANUP_POINT_EXPR, type,
2342 invert_truthvalue (TREE_OPERAND (arg, 0)));
2347 if (TREE_CODE (TREE_TYPE (arg)) != BOOLEAN_TYPE)
2349 return build1 (TRUTH_NOT_EXPR, type, arg);
2352 /* Given a bit-wise operation CODE applied to ARG0 and ARG1, see if both
2353 operands are another bit-wise operation with a common input. If so,
2354 distribute the bit operations to save an operation and possibly two if
2355 constants are involved. For example, convert
2356 (A | B) & (A | C) into A | (B & C)
2357 Further simplification will occur if B and C are constants.
2359 If this optimization cannot be done, 0 will be returned. */
2362 distribute_bit_expr (code, type, arg0, arg1)
2363 enum tree_code code;
2370 if (TREE_CODE (arg0) != TREE_CODE (arg1)
2371 || TREE_CODE (arg0) == code
2372 || (TREE_CODE (arg0) != BIT_AND_EXPR
2373 && TREE_CODE (arg0) != BIT_IOR_EXPR))
2376 if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0))
2378 common = TREE_OPERAND (arg0, 0);
2379 left = TREE_OPERAND (arg0, 1);
2380 right = TREE_OPERAND (arg1, 1);
2382 else if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 1), 0))
2384 common = TREE_OPERAND (arg0, 0);
2385 left = TREE_OPERAND (arg0, 1);
2386 right = TREE_OPERAND (arg1, 0);
2388 else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 0), 0))
2390 common = TREE_OPERAND (arg0, 1);
2391 left = TREE_OPERAND (arg0, 0);
2392 right = TREE_OPERAND (arg1, 1);
2394 else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1), 0))
2396 common = TREE_OPERAND (arg0, 1);
2397 left = TREE_OPERAND (arg0, 0);
2398 right = TREE_OPERAND (arg1, 0);
2403 return fold (build (TREE_CODE (arg0), type, common,
2404 fold (build (code, type, left, right))));
2407 /* Return a BIT_FIELD_REF of type TYPE to refer to BITSIZE bits of INNER
2408 starting at BITPOS. The field is unsigned if UNSIGNEDP is non-zero. */
2411 make_bit_field_ref (inner, type, bitsize, bitpos, unsignedp)
2414 int bitsize, bitpos;
2417 tree result = build (BIT_FIELD_REF, type, inner,
2418 size_int (bitsize), bitsize_int (bitpos));
2420 TREE_UNSIGNED (result) = unsignedp;
2425 /* Optimize a bit-field compare.
2427 There are two cases: First is a compare against a constant and the
2428 second is a comparison of two items where the fields are at the same
2429 bit position relative to the start of a chunk (byte, halfword, word)
2430 large enough to contain it. In these cases we can avoid the shift
2431 implicit in bitfield extractions.
2433 For constants, we emit a compare of the shifted constant with the
2434 BIT_AND_EXPR of a mask and a byte, halfword, or word of the operand being
2435 compared. For two fields at the same position, we do the ANDs with the
2436 similar mask and compare the result of the ANDs.
2438 CODE is the comparison code, known to be either NE_EXPR or EQ_EXPR.
2439 COMPARE_TYPE is the type of the comparison, and LHS and RHS
2440 are the left and right operands of the comparison, respectively.
2442 If the optimization described above can be done, we return the resulting
2443 tree. Otherwise we return zero. */
2446 optimize_bit_field_compare (code, compare_type, lhs, rhs)
2447 enum tree_code code;
2451 HOST_WIDE_INT lbitpos, lbitsize, rbitpos, rbitsize, nbitpos, nbitsize;
2452 tree type = TREE_TYPE (lhs);
2453 tree signed_type, unsigned_type;
2454 int const_p = TREE_CODE (rhs) == INTEGER_CST;
2455 enum machine_mode lmode, rmode, nmode;
2456 int lunsignedp, runsignedp;
2457 int lvolatilep = 0, rvolatilep = 0;
2458 tree linner, rinner = NULL_TREE;
2462 /* Get all the information about the extractions being done. If the bit size
2463 if the same as the size of the underlying object, we aren't doing an
2464 extraction at all and so can do nothing. We also don't want to
2465 do anything if the inner expression is a PLACEHOLDER_EXPR since we
2466 then will no longer be able to replace it. */
2467 linner = get_inner_reference (lhs, &lbitsize, &lbitpos, &offset, &lmode,
2468 &lunsignedp, &lvolatilep);
2469 if (linner == lhs || lbitsize == GET_MODE_BITSIZE (lmode) || lbitsize < 0
2470 || offset != 0 || TREE_CODE (linner) == PLACEHOLDER_EXPR)
2475 /* If this is not a constant, we can only do something if bit positions,
2476 sizes, and signedness are the same. */
2477 rinner = get_inner_reference (rhs, &rbitsize, &rbitpos, &offset, &rmode,
2478 &runsignedp, &rvolatilep);
2480 if (rinner == rhs || lbitpos != rbitpos || lbitsize != rbitsize
2481 || lunsignedp != runsignedp || offset != 0
2482 || TREE_CODE (rinner) == PLACEHOLDER_EXPR)
2486 /* See if we can find a mode to refer to this field. We should be able to,
2487 but fail if we can't. */
2488 nmode = get_best_mode (lbitsize, lbitpos,
2489 const_p ? TYPE_ALIGN (TREE_TYPE (linner))
2490 : MIN (TYPE_ALIGN (TREE_TYPE (linner)),
2491 TYPE_ALIGN (TREE_TYPE (rinner))),
2492 word_mode, lvolatilep || rvolatilep);
2493 if (nmode == VOIDmode)
2496 /* Set signed and unsigned types of the precision of this mode for the
2498 signed_type = (*lang_hooks.types.type_for_mode) (nmode, 0);
2499 unsigned_type = (*lang_hooks.types.type_for_mode) (nmode, 1);
2501 /* Compute the bit position and size for the new reference and our offset
2502 within it. If the new reference is the same size as the original, we
2503 won't optimize anything, so return zero. */
2504 nbitsize = GET_MODE_BITSIZE (nmode);
2505 nbitpos = lbitpos & ~ (nbitsize - 1);
2507 if (nbitsize == lbitsize)
2510 if (BYTES_BIG_ENDIAN)
2511 lbitpos = nbitsize - lbitsize - lbitpos;
2513 /* Make the mask to be used against the extracted field. */
2514 mask = build_int_2 (~0, ~0);
2515 TREE_TYPE (mask) = unsigned_type;
2516 force_fit_type (mask, 0);
2517 mask = convert (unsigned_type, mask);
2518 mask = const_binop (LSHIFT_EXPR, mask, size_int (nbitsize - lbitsize), 0);
2519 mask = const_binop (RSHIFT_EXPR, mask,
2520 size_int (nbitsize - lbitsize - lbitpos), 0);
2523 /* If not comparing with constant, just rework the comparison
2525 return build (code, compare_type,
2526 build (BIT_AND_EXPR, unsigned_type,
2527 make_bit_field_ref (linner, unsigned_type,
2528 nbitsize, nbitpos, 1),
2530 build (BIT_AND_EXPR, unsigned_type,
2531 make_bit_field_ref (rinner, unsigned_type,
2532 nbitsize, nbitpos, 1),
2535 /* Otherwise, we are handling the constant case. See if the constant is too
2536 big for the field. Warn and return a tree of for 0 (false) if so. We do
2537 this not only for its own sake, but to avoid having to test for this
2538 error case below. If we didn't, we might generate wrong code.
2540 For unsigned fields, the constant shifted right by the field length should
2541 be all zero. For signed fields, the high-order bits should agree with
2546 if (! integer_zerop (const_binop (RSHIFT_EXPR,
2547 convert (unsigned_type, rhs),
2548 size_int (lbitsize), 0)))
2550 warning ("comparison is always %d due to width of bit-field",
2552 return convert (compare_type,
2554 ? integer_one_node : integer_zero_node));
2559 tree tem = const_binop (RSHIFT_EXPR, convert (signed_type, rhs),
2560 size_int (lbitsize - 1), 0);
2561 if (! integer_zerop (tem) && ! integer_all_onesp (tem))
2563 warning ("comparison is always %d due to width of bit-field",
2565 return convert (compare_type,
2567 ? integer_one_node : integer_zero_node));
2571 /* Single-bit compares should always be against zero. */
2572 if (lbitsize == 1 && ! integer_zerop (rhs))
2574 code = code == EQ_EXPR ? NE_EXPR : EQ_EXPR;
2575 rhs = convert (type, integer_zero_node);
2578 /* Make a new bitfield reference, shift the constant over the
2579 appropriate number of bits and mask it with the computed mask
2580 (in case this was a signed field). If we changed it, make a new one. */
2581 lhs = make_bit_field_ref (linner, unsigned_type, nbitsize, nbitpos, 1);
2584 TREE_SIDE_EFFECTS (lhs) = 1;
2585 TREE_THIS_VOLATILE (lhs) = 1;
2588 rhs = fold (const_binop (BIT_AND_EXPR,
2589 const_binop (LSHIFT_EXPR,
2590 convert (unsigned_type, rhs),
2591 size_int (lbitpos), 0),
2594 return build (code, compare_type,
2595 build (BIT_AND_EXPR, unsigned_type, lhs, mask),
2599 /* Subroutine for fold_truthop: decode a field reference.
2601 If EXP is a comparison reference, we return the innermost reference.
2603 *PBITSIZE is set to the number of bits in the reference, *PBITPOS is
2604 set to the starting bit number.
2606 If the innermost field can be completely contained in a mode-sized
2607 unit, *PMODE is set to that mode. Otherwise, it is set to VOIDmode.
2609 *PVOLATILEP is set to 1 if the any expression encountered is volatile;
2610 otherwise it is not changed.
2612 *PUNSIGNEDP is set to the signedness of the field.
2614 *PMASK is set to the mask used. This is either contained in a
2615 BIT_AND_EXPR or derived from the width of the field.
2617 *PAND_MASK is set to the mask found in a BIT_AND_EXPR, if any.
2619 Return 0 if this is not a component reference or is one that we can't
2620 do anything with. */
2623 decode_field_reference (exp, pbitsize, pbitpos, pmode, punsignedp,
2624 pvolatilep, pmask, pand_mask)
2626 HOST_WIDE_INT *pbitsize, *pbitpos;
2627 enum machine_mode *pmode;
2628 int *punsignedp, *pvolatilep;
2633 tree mask, inner, offset;
2635 unsigned int precision;
2637 /* All the optimizations using this function assume integer fields.
2638 There are problems with FP fields since the type_for_size call
2639 below can fail for, e.g., XFmode. */
2640 if (! INTEGRAL_TYPE_P (TREE_TYPE (exp)))
2645 if (TREE_CODE (exp) == BIT_AND_EXPR)
2647 and_mask = TREE_OPERAND (exp, 1);
2648 exp = TREE_OPERAND (exp, 0);
2649 STRIP_NOPS (exp); STRIP_NOPS (and_mask);
2650 if (TREE_CODE (and_mask) != INTEGER_CST)
2654 inner = get_inner_reference (exp, pbitsize, pbitpos, &offset, pmode,
2655 punsignedp, pvolatilep);
2656 if ((inner == exp && and_mask == 0)
2657 || *pbitsize < 0 || offset != 0
2658 || TREE_CODE (inner) == PLACEHOLDER_EXPR)
2661 /* Compute the mask to access the bitfield. */
2662 unsigned_type = (*lang_hooks.types.type_for_size) (*pbitsize, 1);
2663 precision = TYPE_PRECISION (unsigned_type);
2665 mask = build_int_2 (~0, ~0);
2666 TREE_TYPE (mask) = unsigned_type;
2667 force_fit_type (mask, 0);
2668 mask = const_binop (LSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
2669 mask = const_binop (RSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
2671 /* Merge it with the mask we found in the BIT_AND_EXPR, if any. */
2673 mask = fold (build (BIT_AND_EXPR, unsigned_type,
2674 convert (unsigned_type, and_mask), mask));
2677 *pand_mask = and_mask;
2681 /* Return non-zero if MASK represents a mask of SIZE ones in the low-order
2685 all_ones_mask_p (mask, size)
2689 tree type = TREE_TYPE (mask);
2690 unsigned int precision = TYPE_PRECISION (type);
2693 tmask = build_int_2 (~0, ~0);
2694 TREE_TYPE (tmask) = (*lang_hooks.types.signed_type) (type);
2695 force_fit_type (tmask, 0);
2697 tree_int_cst_equal (mask,
2698 const_binop (RSHIFT_EXPR,
2699 const_binop (LSHIFT_EXPR, tmask,
2700 size_int (precision - size),
2702 size_int (precision - size), 0));
2705 /* Subroutine for fold: determine if VAL is the INTEGER_CONST that
2706 represents the sign bit of EXP's type. If EXP represents a sign
2707 or zero extension, also test VAL against the unextended type.
2708 The return value is the (sub)expression whose sign bit is VAL,
2709 or NULL_TREE otherwise. */
2712 sign_bit_p (exp, val)
2716 unsigned HOST_WIDE_INT lo;
2721 /* Tree EXP must have an integral type. */
2722 t = TREE_TYPE (exp);
2723 if (! INTEGRAL_TYPE_P (t))
2726 /* Tree VAL must be an integer constant. */
2727 if (TREE_CODE (val) != INTEGER_CST
2728 || TREE_CONSTANT_OVERFLOW (val))
2731 width = TYPE_PRECISION (t);
2732 if (width > HOST_BITS_PER_WIDE_INT)
2734 hi = (unsigned HOST_WIDE_INT) 1 << (width - HOST_BITS_PER_WIDE_INT - 1);
2740 lo = (unsigned HOST_WIDE_INT) 1 << (width - 1);
2743 if (TREE_INT_CST_HIGH (val) == hi && TREE_INT_CST_LOW (val) == lo)
2746 /* Handle extension from a narrower type. */
2747 if (TREE_CODE (exp) == NOP_EXPR
2748 && TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (exp, 0))) < width)
2749 return sign_bit_p (TREE_OPERAND (exp, 0), val);
2754 /* Subroutine for fold_truthop: determine if an operand is simple enough
2755 to be evaluated unconditionally. */
2758 simple_operand_p (exp)
2761 /* Strip any conversions that don't change the machine mode. */
2762 while ((TREE_CODE (exp) == NOP_EXPR
2763 || TREE_CODE (exp) == CONVERT_EXPR)
2764 && (TYPE_MODE (TREE_TYPE (exp))
2765 == TYPE_MODE (TREE_TYPE (TREE_OPERAND (exp, 0)))))
2766 exp = TREE_OPERAND (exp, 0);
2768 return (TREE_CODE_CLASS (TREE_CODE (exp)) == 'c'
2770 && ! TREE_ADDRESSABLE (exp)
2771 && ! TREE_THIS_VOLATILE (exp)
2772 && ! DECL_NONLOCAL (exp)
2773 /* Don't regard global variables as simple. They may be
2774 allocated in ways unknown to the compiler (shared memory,
2775 #pragma weak, etc). */
2776 && ! TREE_PUBLIC (exp)
2777 && ! DECL_EXTERNAL (exp)
2778 /* Loading a static variable is unduly expensive, but global
2779 registers aren't expensive. */
2780 && (! TREE_STATIC (exp) || DECL_REGISTER (exp))));
2783 /* The following functions are subroutines to fold_range_test and allow it to
2784 try to change a logical combination of comparisons into a range test.
2787 X == 2 || X == 3 || X == 4 || X == 5
2791 (unsigned) (X - 2) <= 3
2793 We describe each set of comparisons as being either inside or outside
2794 a range, using a variable named like IN_P, and then describe the
2795 range with a lower and upper bound. If one of the bounds is omitted,
2796 it represents either the highest or lowest value of the type.
2798 In the comments below, we represent a range by two numbers in brackets
2799 preceded by a "+" to designate being inside that range, or a "-" to
2800 designate being outside that range, so the condition can be inverted by
2801 flipping the prefix. An omitted bound is represented by a "-". For
2802 example, "- [-, 10]" means being outside the range starting at the lowest
2803 possible value and ending at 10, in other words, being greater than 10.
2804 The range "+ [-, -]" is always true and hence the range "- [-, -]" is
2807 We set up things so that the missing bounds are handled in a consistent
2808 manner so neither a missing bound nor "true" and "false" need to be
2809 handled using a special case. */
2811 /* Return the result of applying CODE to ARG0 and ARG1, but handle the case
2812 of ARG0 and/or ARG1 being omitted, meaning an unlimited range. UPPER0_P
2813 and UPPER1_P are nonzero if the respective argument is an upper bound
2814 and zero for a lower. TYPE, if nonzero, is the type of the result; it
2815 must be specified for a comparison. ARG1 will be converted to ARG0's
2816 type if both are specified. */
2819 range_binop (code, type, arg0, upper0_p, arg1, upper1_p)
2820 enum tree_code code;
2823 int upper0_p, upper1_p;
2829 /* If neither arg represents infinity, do the normal operation.
2830 Else, if not a comparison, return infinity. Else handle the special
2831 comparison rules. Note that most of the cases below won't occur, but
2832 are handled for consistency. */
2834 if (arg0 != 0 && arg1 != 0)
2836 tem = fold (build (code, type != 0 ? type : TREE_TYPE (arg0),
2837 arg0, convert (TREE_TYPE (arg0), arg1)));
2839 return TREE_CODE (tem) == INTEGER_CST ? tem : 0;
2842 if (TREE_CODE_CLASS (code) != '<')
2845 /* Set SGN[01] to -1 if ARG[01] is a lower bound, 1 for upper, and 0
2846 for neither. In real maths, we cannot assume open ended ranges are
2847 the same. But, this is computer arithmetic, where numbers are finite.
2848 We can therefore make the transformation of any unbounded range with
2849 the value Z, Z being greater than any representable number. This permits
2850 us to treat unbounded ranges as equal. */
2851 sgn0 = arg0 != 0 ? 0 : (upper0_p ? 1 : -1);
2852 sgn1 = arg1 != 0 ? 0 : (upper1_p ? 1 : -1);
2856 result = sgn0 == sgn1;
2859 result = sgn0 != sgn1;
2862 result = sgn0 < sgn1;
2865 result = sgn0 <= sgn1;
2868 result = sgn0 > sgn1;
2871 result = sgn0 >= sgn1;
2877 return convert (type, result ? integer_one_node : integer_zero_node);
2880 /* Given EXP, a logical expression, set the range it is testing into
2881 variables denoted by PIN_P, PLOW, and PHIGH. Return the expression
2882 actually being tested. *PLOW and *PHIGH will be made of the same type
2883 as the returned expression. If EXP is not a comparison, we will most
2884 likely not be returning a useful value and range. */
2887 make_range (exp, pin_p, plow, phigh)
2892 enum tree_code code;
2893 tree arg0 = NULL_TREE, arg1 = NULL_TREE, type = NULL_TREE;
2894 tree orig_type = NULL_TREE;
2896 tree low, high, n_low, n_high;
2898 /* Start with simply saying "EXP != 0" and then look at the code of EXP
2899 and see if we can refine the range. Some of the cases below may not
2900 happen, but it doesn't seem worth worrying about this. We "continue"
2901 the outer loop when we've changed something; otherwise we "break"
2902 the switch, which will "break" the while. */
2904 in_p = 0, low = high = convert (TREE_TYPE (exp), integer_zero_node);
2908 code = TREE_CODE (exp);
2910 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
2912 arg0 = TREE_OPERAND (exp, 0);
2913 if (TREE_CODE_CLASS (code) == '<'
2914 || TREE_CODE_CLASS (code) == '1'
2915 || TREE_CODE_CLASS (code) == '2')
2916 type = TREE_TYPE (arg0);
2917 if (TREE_CODE_CLASS (code) == '2'
2918 || TREE_CODE_CLASS (code) == '<'
2919 || (TREE_CODE_CLASS (code) == 'e'
2920 && TREE_CODE_LENGTH (code) > 1))
2921 arg1 = TREE_OPERAND (exp, 1);
2924 /* Set ORIG_TYPE as soon as TYPE is non-null so that we do not
2925 lose a cast by accident. */
2926 if (type != NULL_TREE && orig_type == NULL_TREE)
2931 case TRUTH_NOT_EXPR:
2932 in_p = ! in_p, exp = arg0;
2935 case EQ_EXPR: case NE_EXPR:
2936 case LT_EXPR: case LE_EXPR: case GE_EXPR: case GT_EXPR:
2937 /* We can only do something if the range is testing for zero
2938 and if the second operand is an integer constant. Note that
2939 saying something is "in" the range we make is done by
2940 complementing IN_P since it will set in the initial case of
2941 being not equal to zero; "out" is leaving it alone. */
2942 if (low == 0 || high == 0
2943 || ! integer_zerop (low) || ! integer_zerop (high)
2944 || TREE_CODE (arg1) != INTEGER_CST)
2949 case NE_EXPR: /* - [c, c] */
2952 case EQ_EXPR: /* + [c, c] */
2953 in_p = ! in_p, low = high = arg1;
2955 case GT_EXPR: /* - [-, c] */
2956 low = 0, high = arg1;
2958 case GE_EXPR: /* + [c, -] */
2959 in_p = ! in_p, low = arg1, high = 0;
2961 case LT_EXPR: /* - [c, -] */
2962 low = arg1, high = 0;
2964 case LE_EXPR: /* + [-, c] */
2965 in_p = ! in_p, low = 0, high = arg1;
2973 /* If this is an unsigned comparison, we also know that EXP is
2974 greater than or equal to zero. We base the range tests we make
2975 on that fact, so we record it here so we can parse existing
2977 if (TREE_UNSIGNED (type) && (low == 0 || high == 0))
2979 if (! merge_ranges (&n_in_p, &n_low, &n_high, in_p, low, high,
2980 1, convert (type, integer_zero_node),
2984 in_p = n_in_p, low = n_low, high = n_high;
2986 /* If the high bound is missing, but we
2987 have a low bound, reverse the range so
2988 it goes from zero to the low bound minus 1. */
2989 if (high == 0 && low)
2992 high = range_binop (MINUS_EXPR, NULL_TREE, low, 0,
2993 integer_one_node, 0);
2994 low = convert (type, integer_zero_node);
3000 /* (-x) IN [a,b] -> x in [-b, -a] */
3001 n_low = range_binop (MINUS_EXPR, type,
3002 convert (type, integer_zero_node), 0, high, 1);
3003 n_high = range_binop (MINUS_EXPR, type,
3004 convert (type, integer_zero_node), 0, low, 0);
3005 low = n_low, high = n_high;
3011 exp = build (MINUS_EXPR, type, negate_expr (arg0),
3012 convert (type, integer_one_node));
3015 case PLUS_EXPR: case MINUS_EXPR:
3016 if (TREE_CODE (arg1) != INTEGER_CST)
3019 /* If EXP is signed, any overflow in the computation is undefined,
3020 so we don't worry about it so long as our computations on
3021 the bounds don't overflow. For unsigned, overflow is defined
3022 and this is exactly the right thing. */
3023 n_low = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
3024 type, low, 0, arg1, 0);
3025 n_high = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
3026 type, high, 1, arg1, 0);
3027 if ((n_low != 0 && TREE_OVERFLOW (n_low))
3028 || (n_high != 0 && TREE_OVERFLOW (n_high)))
3031 /* Check for an unsigned range which has wrapped around the maximum
3032 value thus making n_high < n_low, and normalize it. */
3033 if (n_low && n_high && tree_int_cst_lt (n_high, n_low))
3035 low = range_binop (PLUS_EXPR, type, n_high, 0,
3036 integer_one_node, 0);
3037 high = range_binop (MINUS_EXPR, type, n_low, 0,
3038 integer_one_node, 0);
3040 /* If the range is of the form +/- [ x+1, x ], we won't
3041 be able to normalize it. But then, it represents the
3042 whole range or the empty set, so make it
3044 if (tree_int_cst_equal (n_low, low)
3045 && tree_int_cst_equal (n_high, high))
3051 low = n_low, high = n_high;
3056 case NOP_EXPR: case NON_LVALUE_EXPR: case CONVERT_EXPR:
3057 if (TYPE_PRECISION (type) > TYPE_PRECISION (orig_type))
3060 if (! INTEGRAL_TYPE_P (type)
3061 || (low != 0 && ! int_fits_type_p (low, type))
3062 || (high != 0 && ! int_fits_type_p (high, type)))
3065 n_low = low, n_high = high;
3068 n_low = convert (type, n_low);
3071 n_high = convert (type, n_high);
3073 /* If we're converting from an unsigned to a signed type,
3074 we will be doing the comparison as unsigned. The tests above
3075 have already verified that LOW and HIGH are both positive.
3077 So we have to make sure that the original unsigned value will
3078 be interpreted as positive. */
3079 if (TREE_UNSIGNED (type) && ! TREE_UNSIGNED (TREE_TYPE (exp)))
3081 tree equiv_type = (*lang_hooks.types.type_for_mode)
3082 (TYPE_MODE (type), 1);
3085 /* A range without an upper bound is, naturally, unbounded.
3086 Since convert would have cropped a very large value, use
3087 the max value for the destination type. */
3089 = TYPE_MAX_VALUE (equiv_type) ? TYPE_MAX_VALUE (equiv_type)
3090 : TYPE_MAX_VALUE (type);
3092 high_positive = fold (build (RSHIFT_EXPR, type,
3093 convert (type, high_positive),
3094 convert (type, integer_one_node)));
3096 /* If the low bound is specified, "and" the range with the
3097 range for which the original unsigned value will be
3101 if (! merge_ranges (&n_in_p, &n_low, &n_high,
3103 1, convert (type, integer_zero_node),
3107 in_p = (n_in_p == in_p);
3111 /* Otherwise, "or" the range with the range of the input
3112 that will be interpreted as negative. */
3113 if (! merge_ranges (&n_in_p, &n_low, &n_high,
3115 1, convert (type, integer_zero_node),
3119 in_p = (in_p != n_in_p);
3124 low = n_low, high = n_high;
3134 /* If EXP is a constant, we can evaluate whether this is true or false. */
3135 if (TREE_CODE (exp) == INTEGER_CST)
3137 in_p = in_p == (integer_onep (range_binop (GE_EXPR, integer_type_node,
3139 && integer_onep (range_binop (LE_EXPR, integer_type_node,
3145 *pin_p = in_p, *plow = low, *phigh = high;
3149 /* Given a range, LOW, HIGH, and IN_P, an expression, EXP, and a result
3150 type, TYPE, return an expression to test if EXP is in (or out of, depending
3151 on IN_P) the range. */
3154 build_range_check (type, exp, in_p, low, high)
3160 tree etype = TREE_TYPE (exp);
3164 && (0 != (value = build_range_check (type, exp, 1, low, high))))
3165 return invert_truthvalue (value);
3167 if (low == 0 && high == 0)
3168 return convert (type, integer_one_node);
3171 return fold (build (LE_EXPR, type, exp, high));
3174 return fold (build (GE_EXPR, type, exp, low));
3176 if (operand_equal_p (low, high, 0))
3177 return fold (build (EQ_EXPR, type, exp, low));
3179 if (integer_zerop (low))
3181 if (! TREE_UNSIGNED (etype))
3183 etype = (*lang_hooks.types.unsigned_type) (etype);
3184 high = convert (etype, high);
3185 exp = convert (etype, exp);
3187 return build_range_check (type, exp, 1, 0, high);
3190 /* Optimize (c>=1) && (c<=127) into (signed char)c > 0. */
3191 if (integer_onep (low) && TREE_CODE (high) == INTEGER_CST)
3193 unsigned HOST_WIDE_INT lo;
3197 prec = TYPE_PRECISION (etype);
3198 if (prec <= HOST_BITS_PER_WIDE_INT)
3201 lo = ((unsigned HOST_WIDE_INT) 1 << (prec - 1)) - 1;
3205 hi = ((HOST_WIDE_INT) 1 << (prec - HOST_BITS_PER_WIDE_INT - 1)) - 1;
3206 lo = (unsigned HOST_WIDE_INT) -1;
3209 if (TREE_INT_CST_HIGH (high) == hi && TREE_INT_CST_LOW (high) == lo)
3211 if (TREE_UNSIGNED (etype))
3213 etype = (*lang_hooks.types.signed_type) (etype);
3214 exp = convert (etype, exp);
3216 return fold (build (GT_EXPR, type, exp,
3217 convert (etype, integer_zero_node)));
3221 if (0 != (value = const_binop (MINUS_EXPR, high, low, 0))
3222 && ! TREE_OVERFLOW (value))
3223 return build_range_check (type,
3224 fold (build (MINUS_EXPR, etype, exp, low)),
3225 1, convert (etype, integer_zero_node), value);
3230 /* Given two ranges, see if we can merge them into one. Return 1 if we
3231 can, 0 if we can't. Set the output range into the specified parameters. */
3234 merge_ranges (pin_p, plow, phigh, in0_p, low0, high0, in1_p, low1, high1)
3238 tree low0, high0, low1, high1;
3246 int lowequal = ((low0 == 0 && low1 == 0)
3247 || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3248 low0, 0, low1, 0)));
3249 int highequal = ((high0 == 0 && high1 == 0)
3250 || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3251 high0, 1, high1, 1)));
3253 /* Make range 0 be the range that starts first, or ends last if they
3254 start at the same value. Swap them if it isn't. */
3255 if (integer_onep (range_binop (GT_EXPR, integer_type_node,
3258 && integer_onep (range_binop (GT_EXPR, integer_type_node,
3259 high1, 1, high0, 1))))
3261 temp = in0_p, in0_p = in1_p, in1_p = temp;
3262 tem = low0, low0 = low1, low1 = tem;
3263 tem = high0, high0 = high1, high1 = tem;
3266 /* Now flag two cases, whether the ranges are disjoint or whether the
3267 second range is totally subsumed in the first. Note that the tests
3268 below are simplified by the ones above. */
3269 no_overlap = integer_onep (range_binop (LT_EXPR, integer_type_node,
3270 high0, 1, low1, 0));
3271 subset = integer_onep (range_binop (LE_EXPR, integer_type_node,
3272 high1, 1, high0, 1));
3274 /* We now have four cases, depending on whether we are including or
3275 excluding the two ranges. */
3278 /* If they don't overlap, the result is false. If the second range
3279 is a subset it is the result. Otherwise, the range is from the start
3280 of the second to the end of the first. */
3282 in_p = 0, low = high = 0;
3284 in_p = 1, low = low1, high = high1;
3286 in_p = 1, low = low1, high = high0;
3289 else if (in0_p && ! in1_p)
3291 /* If they don't overlap, the result is the first range. If they are
3292 equal, the result is false. If the second range is a subset of the
3293 first, and the ranges begin at the same place, we go from just after
3294 the end of the first range to the end of the second. If the second
3295 range is not a subset of the first, or if it is a subset and both
3296 ranges end at the same place, the range starts at the start of the
3297 first range and ends just before the second range.
3298 Otherwise, we can't describe this as a single range. */
3300 in_p = 1, low = low0, high = high0;
3301 else if (lowequal && highequal)
3302 in_p = 0, low = high = 0;
3303 else if (subset && lowequal)
3305 in_p = 1, high = high0;
3306 low = range_binop (PLUS_EXPR, NULL_TREE, high1, 0,
3307 integer_one_node, 0);
3309 else if (! subset || highequal)
3311 in_p = 1, low = low0;
3312 high = range_binop (MINUS_EXPR, NULL_TREE, low1, 0,
3313 integer_one_node, 0);
3319 else if (! in0_p && in1_p)
3321 /* If they don't overlap, the result is the second range. If the second
3322 is a subset of the first, the result is false. Otherwise,
3323 the range starts just after the first range and ends at the
3324 end of the second. */
3326 in_p = 1, low = low1, high = high1;
3327 else if (subset || highequal)
3328 in_p = 0, low = high = 0;
3331 in_p = 1, high = high1;
3332 low = range_binop (PLUS_EXPR, NULL_TREE, high0, 1,
3333 integer_one_node, 0);
3339 /* The case where we are excluding both ranges. Here the complex case
3340 is if they don't overlap. In that case, the only time we have a
3341 range is if they are adjacent. If the second is a subset of the
3342 first, the result is the first. Otherwise, the range to exclude
3343 starts at the beginning of the first range and ends at the end of the
3347 if (integer_onep (range_binop (EQ_EXPR, integer_type_node,
3348 range_binop (PLUS_EXPR, NULL_TREE,
3350 integer_one_node, 1),
3352 in_p = 0, low = low0, high = high1;
3357 in_p = 0, low = low0, high = high0;
3359 in_p = 0, low = low0, high = high1;
3362 *pin_p = in_p, *plow = low, *phigh = high;
3366 /* EXP is some logical combination of boolean tests. See if we can
3367 merge it into some range test. Return the new tree if so. */
3370 fold_range_test (exp)
3373 int or_op = (TREE_CODE (exp) == TRUTH_ORIF_EXPR
3374 || TREE_CODE (exp) == TRUTH_OR_EXPR);
3375 int in0_p, in1_p, in_p;
3376 tree low0, low1, low, high0, high1, high;
3377 tree lhs = make_range (TREE_OPERAND (exp, 0), &in0_p, &low0, &high0);
3378 tree rhs = make_range (TREE_OPERAND (exp, 1), &in1_p, &low1, &high1);
3381 /* If this is an OR operation, invert both sides; we will invert
3382 again at the end. */
3384 in0_p = ! in0_p, in1_p = ! in1_p;
3386 /* If both expressions are the same, if we can merge the ranges, and we
3387 can build the range test, return it or it inverted. If one of the
3388 ranges is always true or always false, consider it to be the same
3389 expression as the other. */
3390 if ((lhs == 0 || rhs == 0 || operand_equal_p (lhs, rhs, 0))
3391 && merge_ranges (&in_p, &low, &high, in0_p, low0, high0,
3393 && 0 != (tem = (build_range_check (TREE_TYPE (exp),
3395 : rhs != 0 ? rhs : integer_zero_node,
3397 return or_op ? invert_truthvalue (tem) : tem;
3399 /* On machines where the branch cost is expensive, if this is a
3400 short-circuited branch and the underlying object on both sides
3401 is the same, make a non-short-circuit operation. */
3402 else if (BRANCH_COST >= 2
3403 && lhs != 0 && rhs != 0
3404 && (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3405 || TREE_CODE (exp) == TRUTH_ORIF_EXPR)
3406 && operand_equal_p (lhs, rhs, 0))
3408 /* If simple enough, just rewrite. Otherwise, make a SAVE_EXPR
3409 unless we are at top level or LHS contains a PLACEHOLDER_EXPR, in
3410 which cases we can't do this. */
3411 if (simple_operand_p (lhs))
3412 return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3413 ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3414 TREE_TYPE (exp), TREE_OPERAND (exp, 0),
3415 TREE_OPERAND (exp, 1));
3417 else if ((*lang_hooks.decls.global_bindings_p) () == 0
3418 && ! contains_placeholder_p (lhs))
3420 tree common = save_expr (lhs);
3422 if (0 != (lhs = build_range_check (TREE_TYPE (exp), common,
3423 or_op ? ! in0_p : in0_p,
3425 && (0 != (rhs = build_range_check (TREE_TYPE (exp), common,
3426 or_op ? ! in1_p : in1_p,
3428 return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3429 ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3430 TREE_TYPE (exp), lhs, rhs);
3437 /* Subroutine for fold_truthop: C is an INTEGER_CST interpreted as a P
3438 bit value. Arrange things so the extra bits will be set to zero if and
3439 only if C is signed-extended to its full width. If MASK is nonzero,
3440 it is an INTEGER_CST that should be AND'ed with the extra bits. */
3443 unextend (c, p, unsignedp, mask)
3449 tree type = TREE_TYPE (c);
3450 int modesize = GET_MODE_BITSIZE (TYPE_MODE (type));
3453 if (p == modesize || unsignedp)
3456 /* We work by getting just the sign bit into the low-order bit, then
3457 into the high-order bit, then sign-extend. We then XOR that value
3459 temp = const_binop (RSHIFT_EXPR, c, size_int (p - 1), 0);
3460 temp = const_binop (BIT_AND_EXPR, temp, size_int (1), 0);
3462 /* We must use a signed type in order to get an arithmetic right shift.
3463 However, we must also avoid introducing accidental overflows, so that
3464 a subsequent call to integer_zerop will work. Hence we must
3465 do the type conversion here. At this point, the constant is either
3466 zero or one, and the conversion to a signed type can never overflow.
3467 We could get an overflow if this conversion is done anywhere else. */
3468 if (TREE_UNSIGNED (type))
3469 temp = convert ((*lang_hooks.types.signed_type) (type), temp);
3471 temp = const_binop (LSHIFT_EXPR, temp, size_int (modesize - 1), 0);
3472 temp = const_binop (RSHIFT_EXPR, temp, size_int (modesize - p - 1), 0);
3474 temp = const_binop (BIT_AND_EXPR, temp, convert (TREE_TYPE (c), mask), 0);
3475 /* If necessary, convert the type back to match the type of C. */
3476 if (TREE_UNSIGNED (type))
3477 temp = convert (type, temp);
3479 return convert (type, const_binop (BIT_XOR_EXPR, c, temp, 0));
3482 /* Find ways of folding logical expressions of LHS and RHS:
3483 Try to merge two comparisons to the same innermost item.
3484 Look for range tests like "ch >= '0' && ch <= '9'".
3485 Look for combinations of simple terms on machines with expensive branches
3486 and evaluate the RHS unconditionally.
3488 For example, if we have p->a == 2 && p->b == 4 and we can make an
3489 object large enough to span both A and B, we can do this with a comparison
3490 against the object ANDed with the a mask.
3492 If we have p->a == q->a && p->b == q->b, we may be able to use bit masking
3493 operations to do this with one comparison.
3495 We check for both normal comparisons and the BIT_AND_EXPRs made this by
3496 function and the one above.
3498 CODE is the logical operation being done. It can be TRUTH_ANDIF_EXPR,
3499 TRUTH_AND_EXPR, TRUTH_ORIF_EXPR, or TRUTH_OR_EXPR.
3501 TRUTH_TYPE is the type of the logical operand and LHS and RHS are its
3504 We return the simplified tree or 0 if no optimization is possible. */
3507 fold_truthop (code, truth_type, lhs, rhs)
3508 enum tree_code code;
3509 tree truth_type, lhs, rhs;
3511 /* If this is the "or" of two comparisons, we can do something if
3512 the comparisons are NE_EXPR. If this is the "and", we can do something
3513 if the comparisons are EQ_EXPR. I.e.,
3514 (a->b == 2 && a->c == 4) can become (a->new == NEW).
3516 WANTED_CODE is this operation code. For single bit fields, we can
3517 convert EQ_EXPR to NE_EXPR so we need not reject the "wrong"
3518 comparison for one-bit fields. */
3520 enum tree_code wanted_code;
3521 enum tree_code lcode, rcode;
3522 tree ll_arg, lr_arg, rl_arg, rr_arg;
3523 tree ll_inner, lr_inner, rl_inner, rr_inner;
3524 HOST_WIDE_INT ll_bitsize, ll_bitpos, lr_bitsize, lr_bitpos;
3525 HOST_WIDE_INT rl_bitsize, rl_bitpos, rr_bitsize, rr_bitpos;
3526 HOST_WIDE_INT xll_bitpos, xlr_bitpos, xrl_bitpos, xrr_bitpos;
3527 HOST_WIDE_INT lnbitsize, lnbitpos, rnbitsize, rnbitpos;
3528 int ll_unsignedp, lr_unsignedp, rl_unsignedp, rr_unsignedp;
3529 enum machine_mode ll_mode, lr_mode, rl_mode, rr_mode;
3530 enum machine_mode lnmode, rnmode;
3531 tree ll_mask, lr_mask, rl_mask, rr_mask;
3532 tree ll_and_mask, lr_and_mask, rl_and_mask, rr_and_mask;
3533 tree l_const, r_const;
3534 tree lntype, rntype, result;
3535 int first_bit, end_bit;
3538 /* Start by getting the comparison codes. Fail if anything is volatile.
3539 If one operand is a BIT_AND_EXPR with the constant one, treat it as if
3540 it were surrounded with a NE_EXPR. */
3542 if (TREE_SIDE_EFFECTS (lhs) || TREE_SIDE_EFFECTS (rhs))
3545 lcode = TREE_CODE (lhs);
3546 rcode = TREE_CODE (rhs);
3548 if (lcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (lhs, 1)))
3549 lcode = NE_EXPR, lhs = build (NE_EXPR, truth_type, lhs, integer_zero_node);
3551 if (rcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (rhs, 1)))
3552 rcode = NE_EXPR, rhs = build (NE_EXPR, truth_type, rhs, integer_zero_node);
3554 if (TREE_CODE_CLASS (lcode) != '<' || TREE_CODE_CLASS (rcode) != '<')
3557 code = ((code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR)
3558 ? TRUTH_AND_EXPR : TRUTH_OR_EXPR);
3560 ll_arg = TREE_OPERAND (lhs, 0);
3561 lr_arg = TREE_OPERAND (lhs, 1);
3562 rl_arg = TREE_OPERAND (rhs, 0);
3563 rr_arg = TREE_OPERAND (rhs, 1);
3565 /* Simplify (x<y) && (x==y) into (x<=y) and related optimizations. */
3566 if (simple_operand_p (ll_arg)
3567 && simple_operand_p (lr_arg)
3568 && !FLOAT_TYPE_P (TREE_TYPE (ll_arg)))
3572 if (operand_equal_p (ll_arg, rl_arg, 0)
3573 && operand_equal_p (lr_arg, rr_arg, 0))
3575 int lcompcode, rcompcode;
3577 lcompcode = comparison_to_compcode (lcode);
3578 rcompcode = comparison_to_compcode (rcode);
3579 compcode = (code == TRUTH_AND_EXPR)
3580 ? lcompcode & rcompcode
3581 : lcompcode | rcompcode;
3583 else if (operand_equal_p (ll_arg, rr_arg, 0)
3584 && operand_equal_p (lr_arg, rl_arg, 0))
3586 int lcompcode, rcompcode;
3588 rcode = swap_tree_comparison (rcode);
3589 lcompcode = comparison_to_compcode (lcode);
3590 rcompcode = comparison_to_compcode (rcode);
3591 compcode = (code == TRUTH_AND_EXPR)
3592 ? lcompcode & rcompcode
3593 : lcompcode | rcompcode;
3598 if (compcode == COMPCODE_TRUE)
3599 return convert (truth_type, integer_one_node);
3600 else if (compcode == COMPCODE_FALSE)
3601 return convert (truth_type, integer_zero_node);
3602 else if (compcode != -1)
3603 return build (compcode_to_comparison (compcode),
3604 truth_type, ll_arg, lr_arg);
3607 /* If the RHS can be evaluated unconditionally and its operands are
3608 simple, it wins to evaluate the RHS unconditionally on machines
3609 with expensive branches. In this case, this isn't a comparison
3610 that can be merged. Avoid doing this if the RHS is a floating-point
3611 comparison since those can trap. */
3613 if (BRANCH_COST >= 2
3614 && ! FLOAT_TYPE_P (TREE_TYPE (rl_arg))
3615 && simple_operand_p (rl_arg)
3616 && simple_operand_p (rr_arg))
3618 /* Convert (a != 0) || (b != 0) into (a | b) != 0. */
3619 if (code == TRUTH_OR_EXPR
3620 && lcode == NE_EXPR && integer_zerop (lr_arg)
3621 && rcode == NE_EXPR && integer_zerop (rr_arg)
3622 && TREE_TYPE (ll_arg) == TREE_TYPE (rl_arg))
3623 return build (NE_EXPR, truth_type,
3624 build (BIT_IOR_EXPR, TREE_TYPE (ll_arg),
3628 /* Convert (a == 0) && (b == 0) into (a | b) == 0. */
3629 if (code == TRUTH_AND_EXPR
3630 && lcode == EQ_EXPR && integer_zerop (lr_arg)
3631 && rcode == EQ_EXPR && integer_zerop (rr_arg)
3632 && TREE_TYPE (ll_arg) == TREE_TYPE (rl_arg))
3633 return build (EQ_EXPR, truth_type,
3634 build (BIT_IOR_EXPR, TREE_TYPE (ll_arg),
3638 return build (code, truth_type, lhs, rhs);
3641 /* See if the comparisons can be merged. Then get all the parameters for
3644 if ((lcode != EQ_EXPR && lcode != NE_EXPR)
3645 || (rcode != EQ_EXPR && rcode != NE_EXPR))
3649 ll_inner = decode_field_reference (ll_arg,
3650 &ll_bitsize, &ll_bitpos, &ll_mode,
3651 &ll_unsignedp, &volatilep, &ll_mask,
3653 lr_inner = decode_field_reference (lr_arg,
3654 &lr_bitsize, &lr_bitpos, &lr_mode,
3655 &lr_unsignedp, &volatilep, &lr_mask,
3657 rl_inner = decode_field_reference (rl_arg,
3658 &rl_bitsize, &rl_bitpos, &rl_mode,
3659 &rl_unsignedp, &volatilep, &rl_mask,
3661 rr_inner = decode_field_reference (rr_arg,
3662 &rr_bitsize, &rr_bitpos, &rr_mode,
3663 &rr_unsignedp, &volatilep, &rr_mask,
3666 /* It must be true that the inner operation on the lhs of each
3667 comparison must be the same if we are to be able to do anything.
3668 Then see if we have constants. If not, the same must be true for
3670 if (volatilep || ll_inner == 0 || rl_inner == 0
3671 || ! operand_equal_p (ll_inner, rl_inner, 0))
3674 if (TREE_CODE (lr_arg) == INTEGER_CST
3675 && TREE_CODE (rr_arg) == INTEGER_CST)
3676 l_const = lr_arg, r_const = rr_arg;
3677 else if (lr_inner == 0 || rr_inner == 0
3678 || ! operand_equal_p (lr_inner, rr_inner, 0))
3681 l_const = r_const = 0;
3683 /* If either comparison code is not correct for our logical operation,
3684 fail. However, we can convert a one-bit comparison against zero into
3685 the opposite comparison against that bit being set in the field. */
3687 wanted_code = (code == TRUTH_AND_EXPR ? EQ_EXPR : NE_EXPR);
3688 if (lcode != wanted_code)
3690 if (l_const && integer_zerop (l_const) && integer_pow2p (ll_mask))
3692 /* Make the left operand unsigned, since we are only interested
3693 in the value of one bit. Otherwise we are doing the wrong
3702 /* This is analogous to the code for l_const above. */
3703 if (rcode != wanted_code)
3705 if (r_const && integer_zerop (r_const) && integer_pow2p (rl_mask))
3714 /* After this point all optimizations will generate bit-field
3715 references, which we might not want. */
3716 if (! (*lang_hooks.can_use_bit_fields_p) ())
3719 /* See if we can find a mode that contains both fields being compared on
3720 the left. If we can't, fail. Otherwise, update all constants and masks
3721 to be relative to a field of that size. */
3722 first_bit = MIN (ll_bitpos, rl_bitpos);
3723 end_bit = MAX (ll_bitpos + ll_bitsize, rl_bitpos + rl_bitsize);
3724 lnmode = get_best_mode (end_bit - first_bit, first_bit,
3725 TYPE_ALIGN (TREE_TYPE (ll_inner)), word_mode,
3727 if (lnmode == VOIDmode)
3730 lnbitsize = GET_MODE_BITSIZE (lnmode);
3731 lnbitpos = first_bit & ~ (lnbitsize - 1);
3732 lntype = (*lang_hooks.types.type_for_size) (lnbitsize, 1);
3733 xll_bitpos = ll_bitpos - lnbitpos, xrl_bitpos = rl_bitpos - lnbitpos;
3735 if (BYTES_BIG_ENDIAN)
3737 xll_bitpos = lnbitsize - xll_bitpos - ll_bitsize;
3738 xrl_bitpos = lnbitsize - xrl_bitpos - rl_bitsize;
3741 ll_mask = const_binop (LSHIFT_EXPR, convert (lntype, ll_mask),
3742 size_int (xll_bitpos), 0);
3743 rl_mask = const_binop (LSHIFT_EXPR, convert (lntype, rl_mask),
3744 size_int (xrl_bitpos), 0);
3748 l_const = convert (lntype, l_const);
3749 l_const = unextend (l_const, ll_bitsize, ll_unsignedp, ll_and_mask);
3750 l_const = const_binop (LSHIFT_EXPR, l_const, size_int (xll_bitpos), 0);
3751 if (! integer_zerop (const_binop (BIT_AND_EXPR, l_const,
3752 fold (build1 (BIT_NOT_EXPR,
3756 warning ("comparison is always %d", wanted_code == NE_EXPR);
3758 return convert (truth_type,
3759 wanted_code == NE_EXPR
3760 ? integer_one_node : integer_zero_node);
3765 r_const = convert (lntype, r_const);
3766 r_const = unextend (r_const, rl_bitsize, rl_unsignedp, rl_and_mask);
3767 r_const = const_binop (LSHIFT_EXPR, r_const, size_int (xrl_bitpos), 0);
3768 if (! integer_zerop (const_binop (BIT_AND_EXPR, r_const,
3769 fold (build1 (BIT_NOT_EXPR,
3773 warning ("comparison is always %d", wanted_code == NE_EXPR);
3775 return convert (truth_type,
3776 wanted_code == NE_EXPR
3777 ? integer_one_node : integer_zero_node);
3781 /* If the right sides are not constant, do the same for it. Also,
3782 disallow this optimization if a size or signedness mismatch occurs
3783 between the left and right sides. */
3786 if (ll_bitsize != lr_bitsize || rl_bitsize != rr_bitsize
3787 || ll_unsignedp != lr_unsignedp || rl_unsignedp != rr_unsignedp
3788 /* Make sure the two fields on the right
3789 correspond to the left without being swapped. */
3790 || ll_bitpos - rl_bitpos != lr_bitpos - rr_bitpos)
3793 first_bit = MIN (lr_bitpos, rr_bitpos);
3794 end_bit = MAX (lr_bitpos + lr_bitsize, rr_bitpos + rr_bitsize);
3795 rnmode = get_best_mode (end_bit - first_bit, first_bit,
3796 TYPE_ALIGN (TREE_TYPE (lr_inner)), word_mode,
3798 if (rnmode == VOIDmode)
3801 rnbitsize = GET_MODE_BITSIZE (rnmode);
3802 rnbitpos = first_bit & ~ (rnbitsize - 1);
3803 rntype = (*lang_hooks.types.type_for_size) (rnbitsize, 1);
3804 xlr_bitpos = lr_bitpos - rnbitpos, xrr_bitpos = rr_bitpos - rnbitpos;
3806 if (BYTES_BIG_ENDIAN)
3808 xlr_bitpos = rnbitsize - xlr_bitpos - lr_bitsize;
3809 xrr_bitpos = rnbitsize - xrr_bitpos - rr_bitsize;
3812 lr_mask = const_binop (LSHIFT_EXPR, convert (rntype, lr_mask),
3813 size_int (xlr_bitpos), 0);
3814 rr_mask = const_binop (LSHIFT_EXPR, convert (rntype, rr_mask),
3815 size_int (xrr_bitpos), 0);
3817 /* Make a mask that corresponds to both fields being compared.
3818 Do this for both items being compared. If the operands are the
3819 same size and the bits being compared are in the same position
3820 then we can do this by masking both and comparing the masked
3822 ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
3823 lr_mask = const_binop (BIT_IOR_EXPR, lr_mask, rr_mask, 0);
3824 if (lnbitsize == rnbitsize && xll_bitpos == xlr_bitpos)
3826 lhs = make_bit_field_ref (ll_inner, lntype, lnbitsize, lnbitpos,
3827 ll_unsignedp || rl_unsignedp);
3828 if (! all_ones_mask_p (ll_mask, lnbitsize))
3829 lhs = build (BIT_AND_EXPR, lntype, lhs, ll_mask);
3831 rhs = make_bit_field_ref (lr_inner, rntype, rnbitsize, rnbitpos,
3832 lr_unsignedp || rr_unsignedp);
3833 if (! all_ones_mask_p (lr_mask, rnbitsize))
3834 rhs = build (BIT_AND_EXPR, rntype, rhs, lr_mask);
3836 return build (wanted_code, truth_type, lhs, rhs);
3839 /* There is still another way we can do something: If both pairs of
3840 fields being compared are adjacent, we may be able to make a wider
3841 field containing them both.
3843 Note that we still must mask the lhs/rhs expressions. Furthermore,
3844 the mask must be shifted to account for the shift done by
3845 make_bit_field_ref. */
3846 if ((ll_bitsize + ll_bitpos == rl_bitpos
3847 && lr_bitsize + lr_bitpos == rr_bitpos)
3848 || (ll_bitpos == rl_bitpos + rl_bitsize
3849 && lr_bitpos == rr_bitpos + rr_bitsize))
3853 lhs = make_bit_field_ref (ll_inner, lntype, ll_bitsize + rl_bitsize,
3854 MIN (ll_bitpos, rl_bitpos), ll_unsignedp);
3855 rhs = make_bit_field_ref (lr_inner, rntype, lr_bitsize + rr_bitsize,
3856 MIN (lr_bitpos, rr_bitpos), lr_unsignedp);
3858 ll_mask = const_binop (RSHIFT_EXPR, ll_mask,
3859 size_int (MIN (xll_bitpos, xrl_bitpos)), 0);
3860 lr_mask = const_binop (RSHIFT_EXPR, lr_mask,
3861 size_int (MIN (xlr_bitpos, xrr_bitpos)), 0);
3863 /* Convert to the smaller type before masking out unwanted bits. */
3865 if (lntype != rntype)
3867 if (lnbitsize > rnbitsize)
3869 lhs = convert (rntype, lhs);
3870 ll_mask = convert (rntype, ll_mask);
3873 else if (lnbitsize < rnbitsize)
3875 rhs = convert (lntype, rhs);
3876 lr_mask = convert (lntype, lr_mask);
3881 if (! all_ones_mask_p (ll_mask, ll_bitsize + rl_bitsize))
3882 lhs = build (BIT_AND_EXPR, type, lhs, ll_mask);
3884 if (! all_ones_mask_p (lr_mask, lr_bitsize + rr_bitsize))
3885 rhs = build (BIT_AND_EXPR, type, rhs, lr_mask);
3887 return build (wanted_code, truth_type, lhs, rhs);
3893 /* Handle the case of comparisons with constants. If there is something in
3894 common between the masks, those bits of the constants must be the same.
3895 If not, the condition is always false. Test for this to avoid generating
3896 incorrect code below. */
3897 result = const_binop (BIT_AND_EXPR, ll_mask, rl_mask, 0);
3898 if (! integer_zerop (result)
3899 && simple_cst_equal (const_binop (BIT_AND_EXPR, result, l_const, 0),
3900 const_binop (BIT_AND_EXPR, result, r_const, 0)) != 1)
3902 if (wanted_code == NE_EXPR)
3904 warning ("`or' of unmatched not-equal tests is always 1");
3905 return convert (truth_type, integer_one_node);
3909 warning ("`and' of mutually exclusive equal-tests is always 0");
3910 return convert (truth_type, integer_zero_node);
3914 /* Construct the expression we will return. First get the component
3915 reference we will make. Unless the mask is all ones the width of
3916 that field, perform the mask operation. Then compare with the
3918 result = make_bit_field_ref (ll_inner, lntype, lnbitsize, lnbitpos,
3919 ll_unsignedp || rl_unsignedp);
3921 ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
3922 if (! all_ones_mask_p (ll_mask, lnbitsize))
3923 result = build (BIT_AND_EXPR, lntype, result, ll_mask);
3925 return build (wanted_code, truth_type, result,
3926 const_binop (BIT_IOR_EXPR, l_const, r_const, 0));
3929 /* Optimize T, which is a comparison of a MIN_EXPR or MAX_EXPR with a
3933 optimize_minmax_comparison (t)
3936 tree type = TREE_TYPE (t);
3937 tree arg0 = TREE_OPERAND (t, 0);
3938 enum tree_code op_code;
3939 tree comp_const = TREE_OPERAND (t, 1);
3941 int consts_equal, consts_lt;
3944 STRIP_SIGN_NOPS (arg0);
3946 op_code = TREE_CODE (arg0);
3947 minmax_const = TREE_OPERAND (arg0, 1);
3948 consts_equal = tree_int_cst_equal (minmax_const, comp_const);
3949 consts_lt = tree_int_cst_lt (minmax_const, comp_const);
3950 inner = TREE_OPERAND (arg0, 0);
3952 /* If something does not permit us to optimize, return the original tree. */
3953 if ((op_code != MIN_EXPR && op_code != MAX_EXPR)
3954 || TREE_CODE (comp_const) != INTEGER_CST
3955 || TREE_CONSTANT_OVERFLOW (comp_const)
3956 || TREE_CODE (minmax_const) != INTEGER_CST
3957 || TREE_CONSTANT_OVERFLOW (minmax_const))
3960 /* Now handle all the various comparison codes. We only handle EQ_EXPR
3961 and GT_EXPR, doing the rest with recursive calls using logical
3963 switch (TREE_CODE (t))
3965 case NE_EXPR: case LT_EXPR: case LE_EXPR:
3967 invert_truthvalue (optimize_minmax_comparison (invert_truthvalue (t)));
3971 fold (build (TRUTH_ORIF_EXPR, type,
3972 optimize_minmax_comparison
3973 (build (EQ_EXPR, type, arg0, comp_const)),
3974 optimize_minmax_comparison
3975 (build (GT_EXPR, type, arg0, comp_const))));
3978 if (op_code == MAX_EXPR && consts_equal)
3979 /* MAX (X, 0) == 0 -> X <= 0 */
3980 return fold (build (LE_EXPR, type, inner, comp_const));
3982 else if (op_code == MAX_EXPR && consts_lt)
3983 /* MAX (X, 0) == 5 -> X == 5 */
3984 return fold (build (EQ_EXPR, type, inner, comp_const));
3986 else if (op_code == MAX_EXPR)
3987 /* MAX (X, 0) == -1 -> false */
3988 return omit_one_operand (type, integer_zero_node, inner);
3990 else if (consts_equal)
3991 /* MIN (X, 0) == 0 -> X >= 0 */
3992 return fold (build (GE_EXPR, type, inner, comp_const));
3995 /* MIN (X, 0) == 5 -> false */
3996 return omit_one_operand (type, integer_zero_node, inner);
3999 /* MIN (X, 0) == -1 -> X == -1 */
4000 return fold (build (EQ_EXPR, type, inner, comp_const));
4003 if (op_code == MAX_EXPR && (consts_equal || consts_lt))
4004 /* MAX (X, 0) > 0 -> X > 0
4005 MAX (X, 0) > 5 -> X > 5 */
4006 return fold (build (GT_EXPR, type, inner, comp_const));
4008 else if (op_code == MAX_EXPR)
4009 /* MAX (X, 0) > -1 -> true */
4010 return omit_one_operand (type, integer_one_node, inner);
4012 else if (op_code == MIN_EXPR && (consts_equal || consts_lt))
4013 /* MIN (X, 0) > 0 -> false
4014 MIN (X, 0) > 5 -> false */
4015 return omit_one_operand (type, integer_zero_node, inner);
4018 /* MIN (X, 0) > -1 -> X > -1 */
4019 return fold (build (GT_EXPR, type, inner, comp_const));
4026 /* T is an integer expression that is being multiplied, divided, or taken a
4027 modulus (CODE says which and what kind of divide or modulus) by a
4028 constant C. See if we can eliminate that operation by folding it with
4029 other operations already in T. WIDE_TYPE, if non-null, is a type that
4030 should be used for the computation if wider than our type.
4032 For example, if we are dividing (X * 8) + (Y * 16) by 4, we can return
4033 (X * 2) + (Y * 4). We must, however, be assured that either the original
4034 expression would not overflow or that overflow is undefined for the type
4035 in the language in question.
4037 We also canonicalize (X + 7) * 4 into X * 4 + 28 in the hope that either
4038 the machine has a multiply-accumulate insn or that this is part of an
4039 addressing calculation.
4041 If we return a non-null expression, it is an equivalent form of the
4042 original computation, but need not be in the original type. */
4045 extract_muldiv (t, c, code, wide_type)
4048 enum tree_code code;
4051 tree type = TREE_TYPE (t);
4052 enum tree_code tcode = TREE_CODE (t);
4053 tree ctype = (wide_type != 0 && (GET_MODE_SIZE (TYPE_MODE (wide_type))
4054 > GET_MODE_SIZE (TYPE_MODE (type)))
4055 ? wide_type : type);
4057 int same_p = tcode == code;
4058 tree op0 = NULL_TREE, op1 = NULL_TREE;
4060 /* Don't deal with constants of zero here; they confuse the code below. */
4061 if (integer_zerop (c))
4064 if (TREE_CODE_CLASS (tcode) == '1')
4065 op0 = TREE_OPERAND (t, 0);
4067 if (TREE_CODE_CLASS (tcode) == '2')
4068 op0 = TREE_OPERAND (t, 0), op1 = TREE_OPERAND (t, 1);
4070 /* Note that we need not handle conditional operations here since fold
4071 already handles those cases. So just do arithmetic here. */
4075 /* For a constant, we can always simplify if we are a multiply
4076 or (for divide and modulus) if it is a multiple of our constant. */
4077 if (code == MULT_EXPR
4078 || integer_zerop (const_binop (TRUNC_MOD_EXPR, t, c, 0)))
4079 return const_binop (code, convert (ctype, t), convert (ctype, c), 0);
4082 case CONVERT_EXPR: case NON_LVALUE_EXPR: case NOP_EXPR:
4083 /* If op0 is an expression ... */
4084 if ((TREE_CODE_CLASS (TREE_CODE (op0)) == '<'
4085 || TREE_CODE_CLASS (TREE_CODE (op0)) == '1'
4086 || TREE_CODE_CLASS (TREE_CODE (op0)) == '2'
4087 || TREE_CODE_CLASS (TREE_CODE (op0)) == 'e')
4088 /* ... and is unsigned, and its type is smaller than ctype,
4089 then we cannot pass through as widening. */
4090 && ((TREE_UNSIGNED (TREE_TYPE (op0))
4091 && ! (TREE_CODE (TREE_TYPE (op0)) == INTEGER_TYPE
4092 && TYPE_IS_SIZETYPE (TREE_TYPE (op0)))
4093 && (GET_MODE_SIZE (TYPE_MODE (ctype))
4094 > GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op0)))))
4095 /* ... or its type is larger than ctype,
4096 then we cannot pass through this truncation. */
4097 || (GET_MODE_SIZE (TYPE_MODE (ctype))
4098 < GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op0))))))
4101 /* Pass the constant down and see if we can make a simplification. If
4102 we can, replace this expression with the inner simplification for
4103 possible later conversion to our or some other type. */
4104 if (0 != (t1 = extract_muldiv (op0, convert (TREE_TYPE (op0), c), code,
4105 code == MULT_EXPR ? ctype : NULL_TREE)))
4109 case NEGATE_EXPR: case ABS_EXPR:
4110 if ((t1 = extract_muldiv (op0, c, code, wide_type)) != 0)
4111 return fold (build1 (tcode, ctype, convert (ctype, t1)));
4114 case MIN_EXPR: case MAX_EXPR:
4115 /* If widening the type changes the signedness, then we can't perform
4116 this optimization as that changes the result. */
4117 if (TREE_UNSIGNED (ctype) != TREE_UNSIGNED (type))
4120 /* MIN (a, b) / 5 -> MIN (a / 5, b / 5) */
4121 if ((t1 = extract_muldiv (op0, c, code, wide_type)) != 0
4122 && (t2 = extract_muldiv (op1, c, code, wide_type)) != 0)
4124 if (tree_int_cst_sgn (c) < 0)
4125 tcode = (tcode == MIN_EXPR ? MAX_EXPR : MIN_EXPR);
4127 return fold (build (tcode, ctype, convert (ctype, t1),
4128 convert (ctype, t2)));
4132 case WITH_RECORD_EXPR:
4133 if ((t1 = extract_muldiv (TREE_OPERAND (t, 0), c, code, wide_type)) != 0)
4134 return build (WITH_RECORD_EXPR, TREE_TYPE (t1), t1,
4135 TREE_OPERAND (t, 1));
4139 /* If this has not been evaluated and the operand has no side effects,
4140 we can see if we can do something inside it and make a new one.
4141 Note that this test is overly conservative since we can do this
4142 if the only reason it had side effects is that it was another
4143 similar SAVE_EXPR, but that isn't worth bothering with. */
4144 if (SAVE_EXPR_RTL (t) == 0 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (t, 0))
4145 && 0 != (t1 = extract_muldiv (TREE_OPERAND (t, 0), c, code,
4148 t1 = save_expr (t1);
4149 if (SAVE_EXPR_PERSISTENT_P (t) && TREE_CODE (t1) == SAVE_EXPR)
4150 SAVE_EXPR_PERSISTENT_P (t1) = 1;
4151 if (is_pending_size (t))
4152 put_pending_size (t1);
4157 case LSHIFT_EXPR: case RSHIFT_EXPR:
4158 /* If the second operand is constant, this is a multiplication
4159 or floor division, by a power of two, so we can treat it that
4160 way unless the multiplier or divisor overflows. */
4161 if (TREE_CODE (op1) == INTEGER_CST
4162 /* const_binop may not detect overflow correctly,
4163 so check for it explicitly here. */
4164 && TYPE_PRECISION (TREE_TYPE (size_one_node)) > TREE_INT_CST_LOW (op1)
4165 && TREE_INT_CST_HIGH (op1) == 0
4166 && 0 != (t1 = convert (ctype,
4167 const_binop (LSHIFT_EXPR, size_one_node,
4169 && ! TREE_OVERFLOW (t1))
4170 return extract_muldiv (build (tcode == LSHIFT_EXPR
4171 ? MULT_EXPR : FLOOR_DIV_EXPR,
4172 ctype, convert (ctype, op0), t1),
4173 c, code, wide_type);
4176 case PLUS_EXPR: case MINUS_EXPR:
4177 /* See if we can eliminate the operation on both sides. If we can, we
4178 can return a new PLUS or MINUS. If we can't, the only remaining
4179 cases where we can do anything are if the second operand is a
4181 t1 = extract_muldiv (op0, c, code, wide_type);
4182 t2 = extract_muldiv (op1, c, code, wide_type);
4183 if (t1 != 0 && t2 != 0
4184 && (code == MULT_EXPR
4185 /* If not multiplication, we can only do this if either operand
4186 is divisible by c. */
4187 || multiple_of_p (ctype, op0, c)
4188 || multiple_of_p (ctype, op1, c)))
4189 return fold (build (tcode, ctype, convert (ctype, t1),
4190 convert (ctype, t2)));
4192 /* If this was a subtraction, negate OP1 and set it to be an addition.
4193 This simplifies the logic below. */
4194 if (tcode == MINUS_EXPR)
4195 tcode = PLUS_EXPR, op1 = negate_expr (op1);
4197 if (TREE_CODE (op1) != INTEGER_CST)
4200 /* If either OP1 or C are negative, this optimization is not safe for
4201 some of the division and remainder types while for others we need
4202 to change the code. */
4203 if (tree_int_cst_sgn (op1) < 0 || tree_int_cst_sgn (c) < 0)
4205 if (code == CEIL_DIV_EXPR)
4206 code = FLOOR_DIV_EXPR;
4207 else if (code == FLOOR_DIV_EXPR)
4208 code = CEIL_DIV_EXPR;
4209 else if (code != MULT_EXPR
4210 && code != CEIL_MOD_EXPR && code != FLOOR_MOD_EXPR)
4214 /* If it's a multiply or a division/modulus operation of a multiple
4215 of our constant, do the operation and verify it doesn't overflow. */
4216 if (code == MULT_EXPR
4217 || integer_zerop (const_binop (TRUNC_MOD_EXPR, op1, c, 0)))
4219 op1 = const_binop (code, convert (ctype, op1), convert (ctype, c), 0);
4220 if (op1 == 0 || TREE_OVERFLOW (op1))
4226 /* If we have an unsigned type is not a sizetype, we cannot widen
4227 the operation since it will change the result if the original
4228 computation overflowed. */
4229 if (TREE_UNSIGNED (ctype)
4230 && ! (TREE_CODE (ctype) == INTEGER_TYPE && TYPE_IS_SIZETYPE (ctype))
4234 /* If we were able to eliminate our operation from the first side,
4235 apply our operation to the second side and reform the PLUS. */
4236 if (t1 != 0 && (TREE_CODE (t1) != code || code == MULT_EXPR))
4237 return fold (build (tcode, ctype, convert (ctype, t1), op1));
4239 /* The last case is if we are a multiply. In that case, we can
4240 apply the distributive law to commute the multiply and addition
4241 if the multiplication of the constants doesn't overflow. */
4242 if (code == MULT_EXPR)
4243 return fold (build (tcode, ctype, fold (build (code, ctype,
4244 convert (ctype, op0),
4245 convert (ctype, c))),
4251 /* We have a special case here if we are doing something like
4252 (C * 8) % 4 since we know that's zero. */
4253 if ((code == TRUNC_MOD_EXPR || code == CEIL_MOD_EXPR
4254 || code == FLOOR_MOD_EXPR || code == ROUND_MOD_EXPR)
4255 && TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST
4256 && integer_zerop (const_binop (TRUNC_MOD_EXPR, op1, c, 0)))
4257 return omit_one_operand (type, integer_zero_node, op0);
4259 /* ... fall through ... */
4261 case TRUNC_DIV_EXPR: case CEIL_DIV_EXPR: case FLOOR_DIV_EXPR:
4262 case ROUND_DIV_EXPR: case EXACT_DIV_EXPR:
4263 /* If we can extract our operation from the LHS, do so and return a
4264 new operation. Likewise for the RHS from a MULT_EXPR. Otherwise,
4265 do something only if the second operand is a constant. */
4267 && (t1 = extract_muldiv (op0, c, code, wide_type)) != 0)
4268 return fold (build (tcode, ctype, convert (ctype, t1),
4269 convert (ctype, op1)));
4270 else if (tcode == MULT_EXPR && code == MULT_EXPR
4271 && (t1 = extract_muldiv (op1, c, code, wide_type)) != 0)
4272 return fold (build (tcode, ctype, convert (ctype, op0),
4273 convert (ctype, t1)));
4274 else if (TREE_CODE (op1) != INTEGER_CST)
4277 /* If these are the same operation types, we can associate them
4278 assuming no overflow. */
4280 && 0 != (t1 = const_binop (MULT_EXPR, convert (ctype, op1),
4281 convert (ctype, c), 0))
4282 && ! TREE_OVERFLOW (t1))
4283 return fold (build (tcode, ctype, convert (ctype, op0), t1));
4285 /* If these operations "cancel" each other, we have the main
4286 optimizations of this pass, which occur when either constant is a
4287 multiple of the other, in which case we replace this with either an
4288 operation or CODE or TCODE.
4290 If we have an unsigned type that is not a sizetype, we cannot do
4291 this since it will change the result if the original computation
4293 if ((! TREE_UNSIGNED (ctype)
4294 || (TREE_CODE (ctype) == INTEGER_TYPE && TYPE_IS_SIZETYPE (ctype)))
4295 && ((code == MULT_EXPR && tcode == EXACT_DIV_EXPR)
4296 || (tcode == MULT_EXPR
4297 && code != TRUNC_MOD_EXPR && code != CEIL_MOD_EXPR
4298 && code != FLOOR_MOD_EXPR && code != ROUND_MOD_EXPR)))
4300 if (integer_zerop (const_binop (TRUNC_MOD_EXPR, op1, c, 0)))
4301 return fold (build (tcode, ctype, convert (ctype, op0),
4303 const_binop (TRUNC_DIV_EXPR,
4305 else if (integer_zerop (const_binop (TRUNC_MOD_EXPR, c, op1, 0)))
4306 return fold (build (code, ctype, convert (ctype, op0),
4308 const_binop (TRUNC_DIV_EXPR,
4320 /* If T contains a COMPOUND_EXPR which was inserted merely to evaluate
4321 S, a SAVE_EXPR, return the expression actually being evaluated. Note
4322 that we may sometimes modify the tree. */
4325 strip_compound_expr (t, s)
4329 enum tree_code code = TREE_CODE (t);
4331 /* See if this is the COMPOUND_EXPR we want to eliminate. */
4332 if (code == COMPOUND_EXPR && TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR
4333 && TREE_OPERAND (TREE_OPERAND (t, 0), 0) == s)
4334 return TREE_OPERAND (t, 1);
4336 /* See if this is a COND_EXPR or a simple arithmetic operator. We
4337 don't bother handling any other types. */
4338 else if (code == COND_EXPR)
4340 TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4341 TREE_OPERAND (t, 1) = strip_compound_expr (TREE_OPERAND (t, 1), s);
4342 TREE_OPERAND (t, 2) = strip_compound_expr (TREE_OPERAND (t, 2), s);
4344 else if (TREE_CODE_CLASS (code) == '1')
4345 TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4346 else if (TREE_CODE_CLASS (code) == '<'
4347 || TREE_CODE_CLASS (code) == '2')
4349 TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4350 TREE_OPERAND (t, 1) = strip_compound_expr (TREE_OPERAND (t, 1), s);
4356 /* Return a node which has the indicated constant VALUE (either 0 or
4357 1), and is of the indicated TYPE. */
4360 constant_boolean_node (value, type)
4364 if (type == integer_type_node)
4365 return value ? integer_one_node : integer_zero_node;
4366 else if (TREE_CODE (type) == BOOLEAN_TYPE)
4367 return (*lang_hooks.truthvalue_conversion) (value ? integer_one_node :
4371 tree t = build_int_2 (value, 0);
4373 TREE_TYPE (t) = type;
4378 /* Utility function for the following routine, to see how complex a nesting of
4379 COND_EXPRs can be. EXPR is the expression and LIMIT is a count beyond which
4380 we don't care (to avoid spending too much time on complex expressions.). */
4383 count_cond (expr, lim)
4389 if (TREE_CODE (expr) != COND_EXPR)
4394 ctrue = count_cond (TREE_OPERAND (expr, 1), lim - 1);
4395 cfalse = count_cond (TREE_OPERAND (expr, 2), lim - 1 - ctrue);
4396 return MIN (lim, 1 + ctrue + cfalse);
4399 /* Transform `a + (b ? x : y)' into `b ? (a + x) : (a + y)'.
4400 Transform, `a + (x < y)' into `(x < y) ? (a + 1) : (a + 0)'. Here
4401 CODE corresponds to the `+', COND to the `(b ? x : y)' or `(x < y)'
4402 expression, and ARG to `a'. If COND_FIRST_P is non-zero, then the
4403 COND is the first argument to CODE; otherwise (as in the example
4404 given here), it is the second argument. TYPE is the type of the
4405 original expression. */
4408 fold_binary_op_with_conditional_arg (code, type, cond, arg, cond_first_p)
4409 enum tree_code code;
4415 tree test, true_value, false_value;
4416 tree lhs = NULL_TREE;
4417 tree rhs = NULL_TREE;
4418 /* In the end, we'll produce a COND_EXPR. Both arms of the
4419 conditional expression will be binary operations. The left-hand
4420 side of the expression to be executed if the condition is true
4421 will be pointed to by TRUE_LHS. Similarly, the right-hand side
4422 of the expression to be executed if the condition is true will be
4423 pointed to by TRUE_RHS. FALSE_LHS and FALSE_RHS are analogous --
4424 but apply to the expression to be executed if the conditional is
4430 /* These are the codes to use for the left-hand side and right-hand
4431 side of the COND_EXPR. Normally, they are the same as CODE. */
4432 enum tree_code lhs_code = code;
4433 enum tree_code rhs_code = code;
4434 /* And these are the types of the expressions. */
4435 tree lhs_type = type;
4436 tree rhs_type = type;
4440 true_rhs = false_rhs = &arg;
4441 true_lhs = &true_value;
4442 false_lhs = &false_value;
4446 true_lhs = false_lhs = &arg;
4447 true_rhs = &true_value;
4448 false_rhs = &false_value;
4451 if (TREE_CODE (cond) == COND_EXPR)
4453 test = TREE_OPERAND (cond, 0);
4454 true_value = TREE_OPERAND (cond, 1);
4455 false_value = TREE_OPERAND (cond, 2);
4456 /* If this operand throws an expression, then it does not make
4457 sense to try to perform a logical or arithmetic operation
4458 involving it. Instead of building `a + throw 3' for example,
4459 we simply build `a, throw 3'. */
4460 if (VOID_TYPE_P (TREE_TYPE (true_value)))
4462 lhs_code = COMPOUND_EXPR;
4464 lhs_type = void_type_node;
4466 if (VOID_TYPE_P (TREE_TYPE (false_value)))
4468 rhs_code = COMPOUND_EXPR;
4470 rhs_type = void_type_node;
4475 tree testtype = TREE_TYPE (cond);
4477 true_value = convert (testtype, integer_one_node);
4478 false_value = convert (testtype, integer_zero_node);
4481 /* If ARG is complex we want to make sure we only evaluate
4482 it once. Though this is only required if it is volatile, it
4483 might be more efficient even if it is not. However, if we
4484 succeed in folding one part to a constant, we do not need
4485 to make this SAVE_EXPR. Since we do this optimization
4486 primarily to see if we do end up with constant and this
4487 SAVE_EXPR interferes with later optimizations, suppressing
4488 it when we can is important.
4490 If we are not in a function, we can't make a SAVE_EXPR, so don't
4491 try to do so. Don't try to see if the result is a constant
4492 if an arm is a COND_EXPR since we get exponential behavior
4495 if (TREE_CODE (arg) != SAVE_EXPR && ! TREE_CONSTANT (arg)
4496 && (*lang_hooks.decls.global_bindings_p) () == 0
4497 && ((TREE_CODE (arg) != VAR_DECL
4498 && TREE_CODE (arg) != PARM_DECL)
4499 || TREE_SIDE_EFFECTS (arg)))
4501 if (TREE_CODE (true_value) != COND_EXPR)
4502 lhs = fold (build (lhs_code, lhs_type, *true_lhs, *true_rhs));
4504 if (TREE_CODE (false_value) != COND_EXPR)
4505 rhs = fold (build (rhs_code, rhs_type, *false_lhs, *false_rhs));
4507 if ((lhs == 0 || ! TREE_CONSTANT (lhs))
4508 && (rhs == 0 || !TREE_CONSTANT (rhs)))
4509 arg = save_expr (arg), lhs = rhs = 0;
4513 lhs = fold (build (lhs_code, lhs_type, *true_lhs, *true_rhs));
4515 rhs = fold (build (rhs_code, rhs_type, *false_lhs, *false_rhs));
4517 test = fold (build (COND_EXPR, type, test, lhs, rhs));
4519 if (TREE_CODE (arg) == SAVE_EXPR)
4520 return build (COMPOUND_EXPR, type,
4521 convert (void_type_node, arg),
4522 strip_compound_expr (test, arg));
4524 return convert (type, test);
4528 /* Subroutine of fold() that checks for the addition of +/- 0.0.
4530 If !NEGATE, return true if ADDEND is +/-0.0 and, for all X of type
4531 TYPE, X + ADDEND is the same as X. If NEGATE, return true if X -
4532 ADDEND is the same as X.
4534 X + 0 and X - 0 both give X when X is NaN, infinite, or non-zero
4535 and finite. The problematic cases are when X is zero, and its mode
4536 has signed zeros. In the case of rounding towards -infinity,
4537 X - 0 is not the same as X because 0 - 0 is -0. In other rounding
4538 modes, X + 0 is not the same as X because -0 + 0 is 0. */
4541 fold_real_zero_addition_p (type, addend, negate)
4545 if (!real_zerop (addend))
4548 /* Allow the fold if zeros aren't signed, or their sign isn't important. */
4549 if (!HONOR_SIGNED_ZEROS (TYPE_MODE (type)))
4552 /* Treat x + -0 as x - 0 and x - -0 as x + 0. */
4553 if (TREE_CODE (addend) == REAL_CST
4554 && REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (addend)))
4557 /* The mode has signed zeros, and we have to honor their sign.
4558 In this situation, there is only one case we can return true for.
4559 X - 0 is the same as X unless rounding towards -infinity is
4561 return negate && !HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (type));
4565 /* Perform constant folding and related simplification of EXPR.
4566 The related simplifications include x*1 => x, x*0 => 0, etc.,
4567 and application of the associative law.
4568 NOP_EXPR conversions may be removed freely (as long as we
4569 are careful not to change the C type of the overall expression)
4570 We cannot simplify through a CONVERT_EXPR, FIX_EXPR or FLOAT_EXPR,
4571 but we can constant-fold them if they have constant operands. */
4578 tree t1 = NULL_TREE;
4580 tree type = TREE_TYPE (expr);
4581 tree arg0 = NULL_TREE, arg1 = NULL_TREE;
4582 enum tree_code code = TREE_CODE (t);
4583 int kind = TREE_CODE_CLASS (code);
4585 /* WINS will be nonzero when the switch is done
4586 if all operands are constant. */
4589 /* Don't try to process an RTL_EXPR since its operands aren't trees.
4590 Likewise for a SAVE_EXPR that's already been evaluated. */
4591 if (code == RTL_EXPR || (code == SAVE_EXPR && SAVE_EXPR_RTL (t) != 0))
4594 /* Return right away if a constant. */
4598 #ifdef MAX_INTEGER_COMPUTATION_MODE
4599 check_max_integer_computation_mode (expr);
4602 if (code == NOP_EXPR || code == FLOAT_EXPR || code == CONVERT_EXPR)
4606 /* Special case for conversion ops that can have fixed point args. */
4607 arg0 = TREE_OPERAND (t, 0);
4609 /* Don't use STRIP_NOPS, because signedness of argument type matters. */
4611 STRIP_SIGN_NOPS (arg0);
4613 if (arg0 != 0 && TREE_CODE (arg0) == COMPLEX_CST)
4614 subop = TREE_REALPART (arg0);
4618 if (subop != 0 && TREE_CODE (subop) != INTEGER_CST
4619 && TREE_CODE (subop) != REAL_CST
4621 /* Note that TREE_CONSTANT isn't enough:
4622 static var addresses are constant but we can't
4623 do arithmetic on them. */
4626 else if (IS_EXPR_CODE_CLASS (kind) || kind == 'r')
4628 int len = first_rtl_op (code);
4630 for (i = 0; i < len; i++)
4632 tree op = TREE_OPERAND (t, i);
4636 continue; /* Valid for CALL_EXPR, at least. */
4638 if (kind == '<' || code == RSHIFT_EXPR)
4640 /* Signedness matters here. Perhaps we can refine this
4642 STRIP_SIGN_NOPS (op);
4645 /* Strip any conversions that don't change the mode. */
4648 if (TREE_CODE (op) == COMPLEX_CST)
4649 subop = TREE_REALPART (op);
4653 if (TREE_CODE (subop) != INTEGER_CST
4654 && TREE_CODE (subop) != REAL_CST)
4655 /* Note that TREE_CONSTANT isn't enough:
4656 static var addresses are constant but we can't
4657 do arithmetic on them. */
4667 /* If this is a commutative operation, and ARG0 is a constant, move it
4668 to ARG1 to reduce the number of tests below. */
4669 if ((code == PLUS_EXPR || code == MULT_EXPR || code == MIN_EXPR
4670 || code == MAX_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR
4671 || code == BIT_AND_EXPR)
4672 && (TREE_CODE (arg0) == INTEGER_CST || TREE_CODE (arg0) == REAL_CST))
4674 tem = arg0; arg0 = arg1; arg1 = tem;
4676 tem = TREE_OPERAND (t, 0); TREE_OPERAND (t, 0) = TREE_OPERAND (t, 1);
4677 TREE_OPERAND (t, 1) = tem;
4680 /* Now WINS is set as described above,
4681 ARG0 is the first operand of EXPR,
4682 and ARG1 is the second operand (if it has more than one operand).
4684 First check for cases where an arithmetic operation is applied to a
4685 compound, conditional, or comparison operation. Push the arithmetic
4686 operation inside the compound or conditional to see if any folding
4687 can then be done. Convert comparison to conditional for this purpose.
4688 The also optimizes non-constant cases that used to be done in
4691 Before we do that, see if this is a BIT_AND_EXPR or a BIT_IOR_EXPR,
4692 one of the operands is a comparison and the other is a comparison, a
4693 BIT_AND_EXPR with the constant 1, or a truth value. In that case, the
4694 code below would make the expression more complex. Change it to a
4695 TRUTH_{AND,OR}_EXPR. Likewise, convert a similar NE_EXPR to
4696 TRUTH_XOR_EXPR and an EQ_EXPR to the inversion of a TRUTH_XOR_EXPR. */
4698 if ((code == BIT_AND_EXPR || code == BIT_IOR_EXPR
4699 || code == EQ_EXPR || code == NE_EXPR)
4700 && ((truth_value_p (TREE_CODE (arg0))
4701 && (truth_value_p (TREE_CODE (arg1))
4702 || (TREE_CODE (arg1) == BIT_AND_EXPR
4703 && integer_onep (TREE_OPERAND (arg1, 1)))))
4704 || (truth_value_p (TREE_CODE (arg1))
4705 && (truth_value_p (TREE_CODE (arg0))
4706 || (TREE_CODE (arg0) == BIT_AND_EXPR
4707 && integer_onep (TREE_OPERAND (arg0, 1)))))))
4709 t = fold (build (code == BIT_AND_EXPR ? TRUTH_AND_EXPR
4710 : code == BIT_IOR_EXPR ? TRUTH_OR_EXPR
4714 if (code == EQ_EXPR)
4715 t = invert_truthvalue (t);
4720 if (TREE_CODE_CLASS (code) == '1')
4722 if (TREE_CODE (arg0) == COMPOUND_EXPR)
4723 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4724 fold (build1 (code, type, TREE_OPERAND (arg0, 1))));
4725 else if (TREE_CODE (arg0) == COND_EXPR)
4727 t = fold (build (COND_EXPR, type, TREE_OPERAND (arg0, 0),
4728 fold (build1 (code, type, TREE_OPERAND (arg0, 1))),
4729 fold (build1 (code, type, TREE_OPERAND (arg0, 2)))));
4731 /* If this was a conversion, and all we did was to move into
4732 inside the COND_EXPR, bring it back out. But leave it if
4733 it is a conversion from integer to integer and the
4734 result precision is no wider than a word since such a
4735 conversion is cheap and may be optimized away by combine,
4736 while it couldn't if it were outside the COND_EXPR. Then return
4737 so we don't get into an infinite recursion loop taking the
4738 conversion out and then back in. */
4740 if ((code == NOP_EXPR || code == CONVERT_EXPR
4741 || code == NON_LVALUE_EXPR)
4742 && TREE_CODE (t) == COND_EXPR
4743 && TREE_CODE (TREE_OPERAND (t, 1)) == code
4744 && TREE_CODE (TREE_OPERAND (t, 2)) == code
4745 && (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0))
4746 == TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 2), 0)))
4747 && ! (INTEGRAL_TYPE_P (TREE_TYPE (t))
4749 (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0))))
4750 && TYPE_PRECISION (TREE_TYPE (t)) <= BITS_PER_WORD))
4751 t = build1 (code, type,
4753 TREE_TYPE (TREE_OPERAND
4754 (TREE_OPERAND (t, 1), 0)),
4755 TREE_OPERAND (t, 0),
4756 TREE_OPERAND (TREE_OPERAND (t, 1), 0),
4757 TREE_OPERAND (TREE_OPERAND (t, 2), 0)));
4760 else if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<')
4761 return fold (build (COND_EXPR, type, arg0,
4762 fold (build1 (code, type, integer_one_node)),
4763 fold (build1 (code, type, integer_zero_node))));
4765 else if (TREE_CODE_CLASS (code) == '2'
4766 || TREE_CODE_CLASS (code) == '<')
4768 if (TREE_CODE (arg1) == COMPOUND_EXPR)
4769 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
4770 fold (build (code, type,
4771 arg0, TREE_OPERAND (arg1, 1))));
4772 else if ((TREE_CODE (arg1) == COND_EXPR
4773 || (TREE_CODE_CLASS (TREE_CODE (arg1)) == '<'
4774 && TREE_CODE_CLASS (code) != '<'))
4775 && (TREE_CODE (arg0) != COND_EXPR
4776 || count_cond (arg0, 25) + count_cond (arg1, 25) <= 25)
4777 && (! TREE_SIDE_EFFECTS (arg0)
4778 || ((*lang_hooks.decls.global_bindings_p) () == 0
4779 && ! contains_placeholder_p (arg0))))
4781 fold_binary_op_with_conditional_arg (code, type, arg1, arg0,
4782 /*cond_first_p=*/0);
4783 else if (TREE_CODE (arg0) == COMPOUND_EXPR)
4784 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4785 fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4786 else if ((TREE_CODE (arg0) == COND_EXPR
4787 || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
4788 && TREE_CODE_CLASS (code) != '<'))
4789 && (TREE_CODE (arg1) != COND_EXPR
4790 || count_cond (arg0, 25) + count_cond (arg1, 25) <= 25)
4791 && (! TREE_SIDE_EFFECTS (arg1)
4792 || ((*lang_hooks.decls.global_bindings_p) () == 0
4793 && ! contains_placeholder_p (arg1))))
4795 fold_binary_op_with_conditional_arg (code, type, arg0, arg1,
4796 /*cond_first_p=*/1);
4798 else if (TREE_CODE_CLASS (code) == '<'
4799 && TREE_CODE (arg0) == COMPOUND_EXPR)
4800 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4801 fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4802 else if (TREE_CODE_CLASS (code) == '<'
4803 && TREE_CODE (arg1) == COMPOUND_EXPR)
4804 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
4805 fold (build (code, type, arg0, TREE_OPERAND (arg1, 1))));
4818 return fold (DECL_INITIAL (t));
4823 case FIX_TRUNC_EXPR:
4824 /* Other kinds of FIX are not handled properly by fold_convert. */
4826 if (TREE_TYPE (TREE_OPERAND (t, 0)) == TREE_TYPE (t))
4827 return TREE_OPERAND (t, 0);
4829 /* Handle cases of two conversions in a row. */
4830 if (TREE_CODE (TREE_OPERAND (t, 0)) == NOP_EXPR
4831 || TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR)
4833 tree inside_type = TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4834 tree inter_type = TREE_TYPE (TREE_OPERAND (t, 0));
4835 tree final_type = TREE_TYPE (t);
4836 int inside_int = INTEGRAL_TYPE_P (inside_type);
4837 int inside_ptr = POINTER_TYPE_P (inside_type);
4838 int inside_float = FLOAT_TYPE_P (inside_type);
4839 unsigned int inside_prec = TYPE_PRECISION (inside_type);
4840 int inside_unsignedp = TREE_UNSIGNED (inside_type);
4841 int inter_int = INTEGRAL_TYPE_P (inter_type);
4842 int inter_ptr = POINTER_TYPE_P (inter_type);
4843 int inter_float = FLOAT_TYPE_P (inter_type);
4844 unsigned int inter_prec = TYPE_PRECISION (inter_type);
4845 int inter_unsignedp = TREE_UNSIGNED (inter_type);
4846 int final_int = INTEGRAL_TYPE_P (final_type);
4847 int final_ptr = POINTER_TYPE_P (final_type);
4848 int final_float = FLOAT_TYPE_P (final_type);
4849 unsigned int final_prec = TYPE_PRECISION (final_type);
4850 int final_unsignedp = TREE_UNSIGNED (final_type);
4852 /* In addition to the cases of two conversions in a row
4853 handled below, if we are converting something to its own
4854 type via an object of identical or wider precision, neither
4855 conversion is needed. */
4856 if (TYPE_MAIN_VARIANT (inside_type) == TYPE_MAIN_VARIANT (final_type)
4857 && ((inter_int && final_int) || (inter_float && final_float))
4858 && inter_prec >= final_prec)
4859 return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4861 /* Likewise, if the intermediate and final types are either both
4862 float or both integer, we don't need the middle conversion if
4863 it is wider than the final type and doesn't change the signedness
4864 (for integers). Avoid this if the final type is a pointer
4865 since then we sometimes need the inner conversion. Likewise if
4866 the outer has a precision not equal to the size of its mode. */
4867 if ((((inter_int || inter_ptr) && (inside_int || inside_ptr))
4868 || (inter_float && inside_float))
4869 && inter_prec >= inside_prec
4870 && (inter_float || inter_unsignedp == inside_unsignedp)
4871 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4872 && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4874 return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4876 /* If we have a sign-extension of a zero-extended value, we can
4877 replace that by a single zero-extension. */
4878 if (inside_int && inter_int && final_int
4879 && inside_prec < inter_prec && inter_prec < final_prec
4880 && inside_unsignedp && !inter_unsignedp)
4881 return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4883 /* Two conversions in a row are not needed unless:
4884 - some conversion is floating-point (overstrict for now), or
4885 - the intermediate type is narrower than both initial and
4887 - the intermediate type and innermost type differ in signedness,
4888 and the outermost type is wider than the intermediate, or
4889 - the initial type is a pointer type and the precisions of the
4890 intermediate and final types differ, or
4891 - the final type is a pointer type and the precisions of the
4892 initial and intermediate types differ. */
4893 if (! inside_float && ! inter_float && ! final_float
4894 && (inter_prec > inside_prec || inter_prec > final_prec)
4895 && ! (inside_int && inter_int
4896 && inter_unsignedp != inside_unsignedp
4897 && inter_prec < final_prec)
4898 && ((inter_unsignedp && inter_prec > inside_prec)
4899 == (final_unsignedp && final_prec > inter_prec))
4900 && ! (inside_ptr && inter_prec != final_prec)
4901 && ! (final_ptr && inside_prec != inter_prec)
4902 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4903 && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4905 return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4908 if (TREE_CODE (TREE_OPERAND (t, 0)) == MODIFY_EXPR
4909 && TREE_CONSTANT (TREE_OPERAND (TREE_OPERAND (t, 0), 1))
4910 /* Detect assigning a bitfield. */
4911 && !(TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == COMPONENT_REF
4912 && DECL_BIT_FIELD (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 1))))
4914 /* Don't leave an assignment inside a conversion
4915 unless assigning a bitfield. */
4916 tree prev = TREE_OPERAND (t, 0);
4917 TREE_OPERAND (t, 0) = TREE_OPERAND (prev, 1);
4918 /* First do the assignment, then return converted constant. */
4919 t = build (COMPOUND_EXPR, TREE_TYPE (t), prev, fold (t));
4924 /* Convert (T)(x & c) into (T)x & (T)c, if c is an integer
4925 constants (if x has signed type, the sign bit cannot be set
4926 in c). This folds extension into the BIT_AND_EXPR. */
4927 if (INTEGRAL_TYPE_P (TREE_TYPE (t))
4928 && TREE_CODE (TREE_TYPE (t)) != BOOLEAN_TYPE
4929 && TREE_CODE (TREE_OPERAND (t, 0)) == BIT_AND_EXPR
4930 && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 1)) == INTEGER_CST)
4932 tree and = TREE_OPERAND (t, 0);
4933 tree and0 = TREE_OPERAND (and, 0), and1 = TREE_OPERAND (and, 1);
4936 if (TREE_UNSIGNED (TREE_TYPE (and))
4937 || (TYPE_PRECISION (TREE_TYPE (t))
4938 <= TYPE_PRECISION (TREE_TYPE (and))))
4940 else if (TYPE_PRECISION (TREE_TYPE (and1))
4941 <= HOST_BITS_PER_WIDE_INT
4942 && host_integerp (and1, 1))
4944 unsigned HOST_WIDE_INT cst;
4946 cst = tree_low_cst (and1, 1);
4947 cst &= (HOST_WIDE_INT) -1
4948 << (TYPE_PRECISION (TREE_TYPE (and1)) - 1);
4949 change = (cst == 0);
4950 #ifdef LOAD_EXTEND_OP
4952 && (LOAD_EXTEND_OP (TYPE_MODE (TREE_TYPE (and0)))
4955 tree uns = (*lang_hooks.types.unsigned_type) (TREE_TYPE (and0));
4956 and0 = convert (uns, and0);
4957 and1 = convert (uns, and1);
4962 return fold (build (BIT_AND_EXPR, TREE_TYPE (t),
4963 convert (TREE_TYPE (t), and0),
4964 convert (TREE_TYPE (t), and1)));
4969 TREE_CONSTANT (t) = TREE_CONSTANT (arg0);
4972 return fold_convert (t, arg0);
4974 case VIEW_CONVERT_EXPR:
4975 if (TREE_CODE (TREE_OPERAND (t, 0)) == VIEW_CONVERT_EXPR)
4976 return build1 (VIEW_CONVERT_EXPR, type,
4977 TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4981 if (TREE_CODE (arg0) == CONSTRUCTOR)
4983 tree m = purpose_member (arg1, CONSTRUCTOR_ELTS (arg0));
4990 TREE_CONSTANT (t) = wins;
4996 if (TREE_CODE (arg0) == INTEGER_CST)
4998 unsigned HOST_WIDE_INT low;
5000 int overflow = neg_double (TREE_INT_CST_LOW (arg0),
5001 TREE_INT_CST_HIGH (arg0),
5003 t = build_int_2 (low, high);
5004 TREE_TYPE (t) = type;
5006 = (TREE_OVERFLOW (arg0)
5007 | force_fit_type (t, overflow && !TREE_UNSIGNED (type)));
5008 TREE_CONSTANT_OVERFLOW (t)
5009 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
5011 else if (TREE_CODE (arg0) == REAL_CST)
5012 t = build_real (type, REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
5014 else if (TREE_CODE (arg0) == NEGATE_EXPR)
5015 return TREE_OPERAND (arg0, 0);
5017 /* Convert - (a - b) to (b - a) for non-floating-point. */
5018 else if (TREE_CODE (arg0) == MINUS_EXPR
5019 && (! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations))
5020 return build (MINUS_EXPR, type, TREE_OPERAND (arg0, 1),
5021 TREE_OPERAND (arg0, 0));
5028 if (TREE_CODE (arg0) == INTEGER_CST)
5030 /* If the value is unsigned, then the absolute value is
5031 the same as the ordinary value. */
5032 if (TREE_UNSIGNED (type))
5034 /* Similarly, if the value is non-negative. */
5035 else if (INT_CST_LT (integer_minus_one_node, arg0))
5037 /* If the value is negative, then the absolute value is
5041 unsigned HOST_WIDE_INT low;
5043 int overflow = neg_double (TREE_INT_CST_LOW (arg0),
5044 TREE_INT_CST_HIGH (arg0),
5046 t = build_int_2 (low, high);
5047 TREE_TYPE (t) = type;
5049 = (TREE_OVERFLOW (arg0)
5050 | force_fit_type (t, overflow));
5051 TREE_CONSTANT_OVERFLOW (t)
5052 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
5055 else if (TREE_CODE (arg0) == REAL_CST)
5057 if (REAL_VALUE_NEGATIVE (TREE_REAL_CST (arg0)))
5058 t = build_real (type,
5059 REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
5062 else if (TREE_CODE (arg0) == ABS_EXPR || TREE_CODE (arg0) == NEGATE_EXPR)
5063 return build1 (ABS_EXPR, type, TREE_OPERAND (arg0, 0));
5067 if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
5068 return convert (type, arg0);
5069 else if (TREE_CODE (arg0) == COMPLEX_EXPR)
5070 return build (COMPLEX_EXPR, type,
5071 TREE_OPERAND (arg0, 0),
5072 negate_expr (TREE_OPERAND (arg0, 1)));
5073 else if (TREE_CODE (arg0) == COMPLEX_CST)
5074 return build_complex (type, TREE_REALPART (arg0),
5075 negate_expr (TREE_IMAGPART (arg0)));
5076 else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
5077 return fold (build (TREE_CODE (arg0), type,
5078 fold (build1 (CONJ_EXPR, type,
5079 TREE_OPERAND (arg0, 0))),
5080 fold (build1 (CONJ_EXPR,
5081 type, TREE_OPERAND (arg0, 1)))));
5082 else if (TREE_CODE (arg0) == CONJ_EXPR)
5083 return TREE_OPERAND (arg0, 0);
5089 t = build_int_2 (~ TREE_INT_CST_LOW (arg0),
5090 ~ TREE_INT_CST_HIGH (arg0));
5091 TREE_TYPE (t) = type;
5092 force_fit_type (t, 0);
5093 TREE_OVERFLOW (t) = TREE_OVERFLOW (arg0);
5094 TREE_CONSTANT_OVERFLOW (t) = TREE_CONSTANT_OVERFLOW (arg0);
5096 else if (TREE_CODE (arg0) == BIT_NOT_EXPR)
5097 return TREE_OPERAND (arg0, 0);
5101 /* A + (-B) -> A - B */
5102 if (TREE_CODE (arg1) == NEGATE_EXPR)
5103 return fold (build (MINUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
5104 /* (-A) + B -> B - A */
5105 if (TREE_CODE (arg0) == NEGATE_EXPR)
5106 return fold (build (MINUS_EXPR, type, arg1, TREE_OPERAND (arg0, 0)));
5107 else if (! FLOAT_TYPE_P (type))
5109 if (integer_zerop (arg1))
5110 return non_lvalue (convert (type, arg0));
5112 /* If we are adding two BIT_AND_EXPR's, both of which are and'ing
5113 with a constant, and the two constants have no bits in common,
5114 we should treat this as a BIT_IOR_EXPR since this may produce more
5116 if (TREE_CODE (arg0) == BIT_AND_EXPR
5117 && TREE_CODE (arg1) == BIT_AND_EXPR
5118 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5119 && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
5120 && integer_zerop (const_binop (BIT_AND_EXPR,
5121 TREE_OPERAND (arg0, 1),
5122 TREE_OPERAND (arg1, 1), 0)))
5124 code = BIT_IOR_EXPR;
5128 /* Reassociate (plus (plus (mult) (foo)) (mult)) as
5129 (plus (plus (mult) (mult)) (foo)) so that we can
5130 take advantage of the factoring cases below. */
5131 if ((TREE_CODE (arg0) == PLUS_EXPR
5132 && TREE_CODE (arg1) == MULT_EXPR)
5133 || (TREE_CODE (arg1) == PLUS_EXPR
5134 && TREE_CODE (arg0) == MULT_EXPR))
5136 tree parg0, parg1, parg, marg;
5138 if (TREE_CODE (arg0) == PLUS_EXPR)
5139 parg = arg0, marg = arg1;
5141 parg = arg1, marg = arg0;
5142 parg0 = TREE_OPERAND (parg, 0);
5143 parg1 = TREE_OPERAND (parg, 1);
5147 if (TREE_CODE (parg0) == MULT_EXPR
5148 && TREE_CODE (parg1) != MULT_EXPR)
5149 return fold (build (PLUS_EXPR, type,
5150 fold (build (PLUS_EXPR, type, parg0, marg)),
5152 if (TREE_CODE (parg0) != MULT_EXPR
5153 && TREE_CODE (parg1) == MULT_EXPR)
5154 return fold (build (PLUS_EXPR, type,
5155 fold (build (PLUS_EXPR, type, parg1, marg)),
5159 if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR)
5161 tree arg00, arg01, arg10, arg11;
5162 tree alt0 = NULL_TREE, alt1 = NULL_TREE, same;
5164 /* (A * C) + (B * C) -> (A+B) * C.
5165 We are most concerned about the case where C is a constant,
5166 but other combinations show up during loop reduction. Since
5167 it is not difficult, try all four possibilities. */
5169 arg00 = TREE_OPERAND (arg0, 0);
5170 arg01 = TREE_OPERAND (arg0, 1);
5171 arg10 = TREE_OPERAND (arg1, 0);
5172 arg11 = TREE_OPERAND (arg1, 1);
5175 if (operand_equal_p (arg01, arg11, 0))
5176 same = arg01, alt0 = arg00, alt1 = arg10;
5177 else if (operand_equal_p (arg00, arg10, 0))
5178 same = arg00, alt0 = arg01, alt1 = arg11;
5179 else if (operand_equal_p (arg00, arg11, 0))
5180 same = arg00, alt0 = arg01, alt1 = arg10;
5181 else if (operand_equal_p (arg01, arg10, 0))
5182 same = arg01, alt0 = arg00, alt1 = arg11;
5184 /* No identical multiplicands; see if we can find a common
5185 power-of-two factor in non-power-of-two multiplies. This
5186 can help in multi-dimensional array access. */
5187 else if (TREE_CODE (arg01) == INTEGER_CST
5188 && TREE_CODE (arg11) == INTEGER_CST
5189 && TREE_INT_CST_HIGH (arg01) == 0
5190 && TREE_INT_CST_HIGH (arg11) == 0)
5192 HOST_WIDE_INT int01, int11, tmp;
5193 int01 = TREE_INT_CST_LOW (arg01);
5194 int11 = TREE_INT_CST_LOW (arg11);
5196 /* Move min of absolute values to int11. */
5197 if ((int01 >= 0 ? int01 : -int01)
5198 < (int11 >= 0 ? int11 : -int11))
5200 tmp = int01, int01 = int11, int11 = tmp;
5201 alt0 = arg00, arg00 = arg10, arg10 = alt0;
5202 alt0 = arg01, arg01 = arg11, arg11 = alt0;
5205 if (exact_log2 (int11) > 0 && int01 % int11 == 0)
5207 alt0 = fold (build (MULT_EXPR, type, arg00,
5208 build_int_2 (int01 / int11, 0)));
5215 return fold (build (MULT_EXPR, type,
5216 fold (build (PLUS_EXPR, type, alt0, alt1)),
5221 /* See if ARG1 is zero and X + ARG1 reduces to X. */
5222 else if (fold_real_zero_addition_p (TREE_TYPE (arg0), arg1, 0))
5223 return non_lvalue (convert (type, arg0));
5225 /* Likewise if the operands are reversed. */
5226 else if (fold_real_zero_addition_p (TREE_TYPE (arg1), arg0, 0))
5227 return non_lvalue (convert (type, arg1));
5230 /* (A << C1) + (A >> C2) if A is unsigned and C1+C2 is the size of A
5231 is a rotate of A by C1 bits. */
5232 /* (A << B) + (A >> (Z - B)) if A is unsigned and Z is the size of A
5233 is a rotate of A by B bits. */
5235 enum tree_code code0, code1;
5236 code0 = TREE_CODE (arg0);
5237 code1 = TREE_CODE (arg1);
5238 if (((code0 == RSHIFT_EXPR && code1 == LSHIFT_EXPR)
5239 || (code1 == RSHIFT_EXPR && code0 == LSHIFT_EXPR))
5240 && operand_equal_p (TREE_OPERAND (arg0, 0),
5241 TREE_OPERAND (arg1, 0), 0)
5242 && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5244 tree tree01, tree11;
5245 enum tree_code code01, code11;
5247 tree01 = TREE_OPERAND (arg0, 1);
5248 tree11 = TREE_OPERAND (arg1, 1);
5249 STRIP_NOPS (tree01);
5250 STRIP_NOPS (tree11);
5251 code01 = TREE_CODE (tree01);
5252 code11 = TREE_CODE (tree11);
5253 if (code01 == INTEGER_CST
5254 && code11 == INTEGER_CST
5255 && TREE_INT_CST_HIGH (tree01) == 0
5256 && TREE_INT_CST_HIGH (tree11) == 0
5257 && ((TREE_INT_CST_LOW (tree01) + TREE_INT_CST_LOW (tree11))
5258 == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)))))
5259 return build (LROTATE_EXPR, type, TREE_OPERAND (arg0, 0),
5260 code0 == LSHIFT_EXPR ? tree01 : tree11);
5261 else if (code11 == MINUS_EXPR)
5263 tree tree110, tree111;
5264 tree110 = TREE_OPERAND (tree11, 0);
5265 tree111 = TREE_OPERAND (tree11, 1);
5266 STRIP_NOPS (tree110);
5267 STRIP_NOPS (tree111);
5268 if (TREE_CODE (tree110) == INTEGER_CST
5269 && 0 == compare_tree_int (tree110,
5271 (TREE_TYPE (TREE_OPERAND
5273 && operand_equal_p (tree01, tree111, 0))
5274 return build ((code0 == LSHIFT_EXPR
5277 type, TREE_OPERAND (arg0, 0), tree01);
5279 else if (code01 == MINUS_EXPR)
5281 tree tree010, tree011;
5282 tree010 = TREE_OPERAND (tree01, 0);
5283 tree011 = TREE_OPERAND (tree01, 1);
5284 STRIP_NOPS (tree010);
5285 STRIP_NOPS (tree011);
5286 if (TREE_CODE (tree010) == INTEGER_CST
5287 && 0 == compare_tree_int (tree010,
5289 (TREE_TYPE (TREE_OPERAND
5291 && operand_equal_p (tree11, tree011, 0))
5292 return build ((code0 != LSHIFT_EXPR
5295 type, TREE_OPERAND (arg0, 0), tree11);
5301 /* In most languages, can't associate operations on floats through
5302 parentheses. Rather than remember where the parentheses were, we
5303 don't associate floats at all. It shouldn't matter much. However,
5304 associating multiplications is only very slightly inaccurate, so do
5305 that if -funsafe-math-optimizations is specified. */
5308 && (! FLOAT_TYPE_P (type)
5309 || (flag_unsafe_math_optimizations && code == MULT_EXPR)))
5311 tree var0, con0, lit0, minus_lit0;
5312 tree var1, con1, lit1, minus_lit1;
5314 /* Split both trees into variables, constants, and literals. Then
5315 associate each group together, the constants with literals,
5316 then the result with variables. This increases the chances of
5317 literals being recombined later and of generating relocatable
5318 expressions for the sum of a constant and literal. */
5319 var0 = split_tree (arg0, code, &con0, &lit0, &minus_lit0, 0);
5320 var1 = split_tree (arg1, code, &con1, &lit1, &minus_lit1,
5321 code == MINUS_EXPR);
5323 /* Only do something if we found more than two objects. Otherwise,
5324 nothing has changed and we risk infinite recursion. */
5325 if (2 < ((var0 != 0) + (var1 != 0)
5326 + (con0 != 0) + (con1 != 0)
5327 + (lit0 != 0) + (lit1 != 0)
5328 + (minus_lit0 != 0) + (minus_lit1 != 0)))
5330 /* Recombine MINUS_EXPR operands by using PLUS_EXPR. */
5331 if (code == MINUS_EXPR)
5334 var0 = associate_trees (var0, var1, code, type);
5335 con0 = associate_trees (con0, con1, code, type);
5336 lit0 = associate_trees (lit0, lit1, code, type);
5337 minus_lit0 = associate_trees (minus_lit0, minus_lit1, code, type);
5339 /* Preserve the MINUS_EXPR if the negative part of the literal is
5340 greater than the positive part. Otherwise, the multiplicative
5341 folding code (i.e extract_muldiv) may be fooled in case
5342 unsigned constants are substracted, like in the following
5343 example: ((X*2 + 4) - 8U)/2. */
5344 if (minus_lit0 && lit0)
5346 if (tree_int_cst_lt (lit0, minus_lit0))
5348 minus_lit0 = associate_trees (minus_lit0, lit0,
5354 lit0 = associate_trees (lit0, minus_lit0,
5362 return convert (type, associate_trees (var0, minus_lit0,
5366 con0 = associate_trees (con0, minus_lit0,
5368 return convert (type, associate_trees (var0, con0,
5373 con0 = associate_trees (con0, lit0, code, type);
5374 return convert (type, associate_trees (var0, con0, code, type));
5380 t1 = const_binop (code, arg0, arg1, 0);
5381 if (t1 != NULL_TREE)
5383 /* The return value should always have
5384 the same type as the original expression. */
5385 if (TREE_TYPE (t1) != TREE_TYPE (t))
5386 t1 = convert (TREE_TYPE (t), t1);
5393 /* A - (-B) -> A + B */
5394 if (TREE_CODE (arg1) == NEGATE_EXPR)
5395 return fold (build (PLUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
5396 /* (-A) - CST -> (-CST) - A for floating point (what about ints ?) */
5397 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == REAL_CST)
5399 fold (build (MINUS_EXPR, type,
5400 build_real (TREE_TYPE (arg1),
5401 REAL_VALUE_NEGATE (TREE_REAL_CST (arg1))),
5402 TREE_OPERAND (arg0, 0)));
5404 if (! FLOAT_TYPE_P (type))
5406 if (! wins && integer_zerop (arg0))
5407 return negate_expr (convert (type, arg1));
5408 if (integer_zerop (arg1))
5409 return non_lvalue (convert (type, arg0));
5411 /* (A * C) - (B * C) -> (A-B) * C. Since we are most concerned
5412 about the case where C is a constant, just try one of the
5413 four possibilities. */
5415 if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR
5416 && operand_equal_p (TREE_OPERAND (arg0, 1),
5417 TREE_OPERAND (arg1, 1), 0))
5418 return fold (build (MULT_EXPR, type,
5419 fold (build (MINUS_EXPR, type,
5420 TREE_OPERAND (arg0, 0),
5421 TREE_OPERAND (arg1, 0))),
5422 TREE_OPERAND (arg0, 1)));
5425 /* See if ARG1 is zero and X - ARG1 reduces to X. */
5426 else if (fold_real_zero_addition_p (TREE_TYPE (arg0), arg1, 1))
5427 return non_lvalue (convert (type, arg0));
5429 /* (ARG0 - ARG1) is the same as (-ARG1 + ARG0). So check whether
5430 ARG0 is zero and X + ARG0 reduces to X, since that would mean
5431 (-ARG1 + ARG0) reduces to -ARG1. */
5432 else if (!wins && fold_real_zero_addition_p (TREE_TYPE (arg1), arg0, 0))
5433 return negate_expr (convert (type, arg1));
5435 /* Fold &x - &x. This can happen from &x.foo - &x.
5436 This is unsafe for certain floats even in non-IEEE formats.
5437 In IEEE, it is unsafe because it does wrong for NaNs.
5438 Also note that operand_equal_p is always false if an operand
5441 if ((! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations)
5442 && operand_equal_p (arg0, arg1, 0))
5443 return convert (type, integer_zero_node);
5448 /* (-A) * (-B) -> A * B */
5449 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == NEGATE_EXPR)
5450 return fold (build (MULT_EXPR, type, TREE_OPERAND (arg0, 0),
5451 TREE_OPERAND (arg1, 0)));
5453 if (! FLOAT_TYPE_P (type))
5455 if (integer_zerop (arg1))
5456 return omit_one_operand (type, arg1, arg0);
5457 if (integer_onep (arg1))
5458 return non_lvalue (convert (type, arg0));
5460 /* (a * (1 << b)) is (a << b) */
5461 if (TREE_CODE (arg1) == LSHIFT_EXPR
5462 && integer_onep (TREE_OPERAND (arg1, 0)))
5463 return fold (build (LSHIFT_EXPR, type, arg0,
5464 TREE_OPERAND (arg1, 1)));
5465 if (TREE_CODE (arg0) == LSHIFT_EXPR
5466 && integer_onep (TREE_OPERAND (arg0, 0)))
5467 return fold (build (LSHIFT_EXPR, type, arg1,
5468 TREE_OPERAND (arg0, 1)));
5470 if (TREE_CODE (arg1) == INTEGER_CST
5471 && 0 != (tem = extract_muldiv (TREE_OPERAND (t, 0), arg1,
5473 return convert (type, tem);
5478 /* Maybe fold x * 0 to 0. The expressions aren't the same
5479 when x is NaN, since x * 0 is also NaN. Nor are they the
5480 same in modes with signed zeros, since multiplying a
5481 negative value by 0 gives -0, not +0. */
5482 if (!HONOR_NANS (TYPE_MODE (TREE_TYPE (arg0)))
5483 && !HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg0)))
5484 && real_zerop (arg1))
5485 return omit_one_operand (type, arg1, arg0);
5486 /* In IEEE floating point, x*1 is not equivalent to x for snans. */
5487 if (!HONOR_SNANS (TYPE_MODE (TREE_TYPE (arg0)))
5488 && real_onep (arg1))
5489 return non_lvalue (convert (type, arg0));
5491 /* Transform x * -1.0 into -x. */
5492 if (!HONOR_SNANS (TYPE_MODE (TREE_TYPE (arg0)))
5493 && real_minus_onep (arg1))
5494 return fold (build1 (NEGATE_EXPR, type, arg0));
5497 if (! wins && real_twop (arg1)
5498 && (*lang_hooks.decls.global_bindings_p) () == 0
5499 && ! contains_placeholder_p (arg0))
5501 tree arg = save_expr (arg0);
5502 return build (PLUS_EXPR, type, arg, arg);
5509 if (integer_all_onesp (arg1))
5510 return omit_one_operand (type, arg1, arg0);
5511 if (integer_zerop (arg1))
5512 return non_lvalue (convert (type, arg0));
5513 t1 = distribute_bit_expr (code, type, arg0, arg1);
5514 if (t1 != NULL_TREE)
5517 /* Convert (or (not arg0) (not arg1)) to (not (and (arg0) (arg1))).
5519 This results in more efficient code for machines without a NAND
5520 instruction. Combine will canonicalize to the first form
5521 which will allow use of NAND instructions provided by the
5522 backend if they exist. */
5523 if (TREE_CODE (arg0) == BIT_NOT_EXPR
5524 && TREE_CODE (arg1) == BIT_NOT_EXPR)
5526 return fold (build1 (BIT_NOT_EXPR, type,
5527 build (BIT_AND_EXPR, type,
5528 TREE_OPERAND (arg0, 0),
5529 TREE_OPERAND (arg1, 0))));
5532 /* See if this can be simplified into a rotate first. If that
5533 is unsuccessful continue in the association code. */
5537 if (integer_zerop (arg1))
5538 return non_lvalue (convert (type, arg0));
5539 if (integer_all_onesp (arg1))
5540 return fold (build1 (BIT_NOT_EXPR, type, arg0));
5542 /* If we are XORing two BIT_AND_EXPR's, both of which are and'ing
5543 with a constant, and the two constants have no bits in common,
5544 we should treat this as a BIT_IOR_EXPR since this may produce more
5546 if (TREE_CODE (arg0) == BIT_AND_EXPR
5547 && TREE_CODE (arg1) == BIT_AND_EXPR
5548 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5549 && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
5550 && integer_zerop (const_binop (BIT_AND_EXPR,
5551 TREE_OPERAND (arg0, 1),
5552 TREE_OPERAND (arg1, 1), 0)))
5554 code = BIT_IOR_EXPR;
5558 /* See if this can be simplified into a rotate first. If that
5559 is unsuccessful continue in the association code. */
5564 if (integer_all_onesp (arg1))
5565 return non_lvalue (convert (type, arg0));
5566 if (integer_zerop (arg1))
5567 return omit_one_operand (type, arg1, arg0);
5568 t1 = distribute_bit_expr (code, type, arg0, arg1);
5569 if (t1 != NULL_TREE)
5571 /* Simplify ((int)c & 0x377) into (int)c, if c is unsigned char. */
5572 if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) == NOP_EXPR
5573 && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5576 = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)));
5578 if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
5579 && (~TREE_INT_CST_LOW (arg1)
5580 & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
5581 return build1 (NOP_EXPR, type, TREE_OPERAND (arg0, 0));
5584 /* Convert (and (not arg0) (not arg1)) to (not (or (arg0) (arg1))).
5586 This results in more efficient code for machines without a NOR
5587 instruction. Combine will canonicalize to the first form
5588 which will allow use of NOR instructions provided by the
5589 backend if they exist. */
5590 if (TREE_CODE (arg0) == BIT_NOT_EXPR
5591 && TREE_CODE (arg1) == BIT_NOT_EXPR)
5593 return fold (build1 (BIT_NOT_EXPR, type,
5594 build (BIT_IOR_EXPR, type,
5595 TREE_OPERAND (arg0, 0),
5596 TREE_OPERAND (arg1, 0))));
5601 case BIT_ANDTC_EXPR:
5602 if (integer_all_onesp (arg0))
5603 return non_lvalue (convert (type, arg1));
5604 if (integer_zerop (arg0))
5605 return omit_one_operand (type, arg0, arg1);
5606 if (TREE_CODE (arg1) == INTEGER_CST)
5608 arg1 = fold (build1 (BIT_NOT_EXPR, type, arg1));
5609 code = BIT_AND_EXPR;
5615 /* Don't touch a floating-point divide by zero unless the mode
5616 of the constant can represent infinity. */
5617 if (TREE_CODE (arg1) == REAL_CST
5618 && !MODE_HAS_INFINITIES (TYPE_MODE (TREE_TYPE (arg1)))
5619 && real_zerop (arg1))
5622 /* (-A) / (-B) -> A / B */
5623 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == NEGATE_EXPR)
5624 return fold (build (RDIV_EXPR, type, TREE_OPERAND (arg0, 0),
5625 TREE_OPERAND (arg1, 0)));
5627 /* In IEEE floating point, x/1 is not equivalent to x for snans. */
5628 if (!HONOR_SNANS (TYPE_MODE (TREE_TYPE (arg0)))
5629 && real_onep (arg1))
5630 return non_lvalue (convert (type, arg0));
5632 /* If ARG1 is a constant, we can convert this to a multiply by the
5633 reciprocal. This does not have the same rounding properties,
5634 so only do this if -funsafe-math-optimizations. We can actually
5635 always safely do it if ARG1 is a power of two, but it's hard to
5636 tell if it is or not in a portable manner. */
5637 if (TREE_CODE (arg1) == REAL_CST)
5639 if (flag_unsafe_math_optimizations
5640 && 0 != (tem = const_binop (code, build_real (type, dconst1),
5642 return fold (build (MULT_EXPR, type, arg0, tem));
5643 /* Find the reciprocal if optimizing and the result is exact. */
5647 r = TREE_REAL_CST (arg1);
5648 if (exact_real_inverse (TYPE_MODE(TREE_TYPE(arg0)), &r))
5650 tem = build_real (type, r);
5651 return fold (build (MULT_EXPR, type, arg0, tem));
5655 /* Convert A/B/C to A/(B*C). */
5656 if (flag_unsafe_math_optimizations
5657 && TREE_CODE (arg0) == RDIV_EXPR)
5659 return fold (build (RDIV_EXPR, type, TREE_OPERAND (arg0, 0),
5660 build (MULT_EXPR, type, TREE_OPERAND (arg0, 1),
5663 /* Convert A/(B/C) to (A/B)*C. */
5664 if (flag_unsafe_math_optimizations
5665 && TREE_CODE (arg1) == RDIV_EXPR)
5667 return fold (build (MULT_EXPR, type,
5668 build (RDIV_EXPR, type, arg0,
5669 TREE_OPERAND (arg1, 0)),
5670 TREE_OPERAND (arg1, 1)));
5674 case TRUNC_DIV_EXPR:
5675 case ROUND_DIV_EXPR:
5676 case FLOOR_DIV_EXPR:
5678 case EXACT_DIV_EXPR:
5679 if (integer_onep (arg1))
5680 return non_lvalue (convert (type, arg0));
5681 if (integer_zerop (arg1))
5684 /* If arg0 is a multiple of arg1, then rewrite to the fastest div
5685 operation, EXACT_DIV_EXPR.
5687 Note that only CEIL_DIV_EXPR and FLOOR_DIV_EXPR are rewritten now.
5688 At one time others generated faster code, it's not clear if they do
5689 after the last round to changes to the DIV code in expmed.c. */
5690 if ((code == CEIL_DIV_EXPR || code == FLOOR_DIV_EXPR)
5691 && multiple_of_p (type, arg0, arg1))
5692 return fold (build (EXACT_DIV_EXPR, type, arg0, arg1));
5694 if (TREE_CODE (arg1) == INTEGER_CST
5695 && 0 != (tem = extract_muldiv (TREE_OPERAND (t, 0), arg1,
5697 return convert (type, tem);
5702 case FLOOR_MOD_EXPR:
5703 case ROUND_MOD_EXPR:
5704 case TRUNC_MOD_EXPR:
5705 if (integer_onep (arg1))
5706 return omit_one_operand (type, integer_zero_node, arg0);
5707 if (integer_zerop (arg1))
5710 if (TREE_CODE (arg1) == INTEGER_CST
5711 && 0 != (tem = extract_muldiv (TREE_OPERAND (t, 0), arg1,
5713 return convert (type, tem);
5721 if (integer_zerop (arg1))
5722 return non_lvalue (convert (type, arg0));
5723 /* Since negative shift count is not well-defined,
5724 don't try to compute it in the compiler. */
5725 if (TREE_CODE (arg1) == INTEGER_CST && tree_int_cst_sgn (arg1) < 0)
5727 /* Rewrite an LROTATE_EXPR by a constant into an
5728 RROTATE_EXPR by a new constant. */
5729 if (code == LROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST)
5731 TREE_SET_CODE (t, RROTATE_EXPR);
5732 code = RROTATE_EXPR;
5733 TREE_OPERAND (t, 1) = arg1
5736 convert (TREE_TYPE (arg1),
5737 build_int_2 (GET_MODE_BITSIZE (TYPE_MODE (type)), 0)),
5739 if (tree_int_cst_sgn (arg1) < 0)
5743 /* If we have a rotate of a bit operation with the rotate count and
5744 the second operand of the bit operation both constant,
5745 permute the two operations. */
5746 if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5747 && (TREE_CODE (arg0) == BIT_AND_EXPR
5748 || TREE_CODE (arg0) == BIT_ANDTC_EXPR
5749 || TREE_CODE (arg0) == BIT_IOR_EXPR
5750 || TREE_CODE (arg0) == BIT_XOR_EXPR)
5751 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
5752 return fold (build (TREE_CODE (arg0), type,
5753 fold (build (code, type,
5754 TREE_OPERAND (arg0, 0), arg1)),
5755 fold (build (code, type,
5756 TREE_OPERAND (arg0, 1), arg1))));
5758 /* Two consecutive rotates adding up to the width of the mode can
5760 if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5761 && TREE_CODE (arg0) == RROTATE_EXPR
5762 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5763 && TREE_INT_CST_HIGH (arg1) == 0
5764 && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == 0
5765 && ((TREE_INT_CST_LOW (arg1)
5766 + TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)))
5767 == (unsigned int) GET_MODE_BITSIZE (TYPE_MODE (type))))
5768 return TREE_OPERAND (arg0, 0);
5773 if (operand_equal_p (arg0, arg1, 0))
5774 return omit_one_operand (type, arg0, arg1);
5775 if (INTEGRAL_TYPE_P (type)
5776 && operand_equal_p (arg1, TYPE_MIN_VALUE (type), 1))
5777 return omit_one_operand (type, arg1, arg0);
5781 if (operand_equal_p (arg0, arg1, 0))
5782 return omit_one_operand (type, arg0, arg1);
5783 if (INTEGRAL_TYPE_P (type)
5784 && TYPE_MAX_VALUE (type)
5785 && operand_equal_p (arg1, TYPE_MAX_VALUE (type), 1))
5786 return omit_one_operand (type, arg1, arg0);
5789 case TRUTH_NOT_EXPR:
5790 /* Note that the operand of this must be an int
5791 and its values must be 0 or 1.
5792 ("true" is a fixed value perhaps depending on the language,
5793 but we don't handle values other than 1 correctly yet.) */
5794 tem = invert_truthvalue (arg0);
5795 /* Avoid infinite recursion. */
5796 if (TREE_CODE (tem) == TRUTH_NOT_EXPR)
5798 return convert (type, tem);
5800 case TRUTH_ANDIF_EXPR:
5801 /* Note that the operands of this must be ints
5802 and their values must be 0 or 1.
5803 ("true" is a fixed value perhaps depending on the language.) */
5804 /* If first arg is constant zero, return it. */
5805 if (integer_zerop (arg0))
5806 return convert (type, arg0);
5807 case TRUTH_AND_EXPR:
5808 /* If either arg is constant true, drop it. */
5809 if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5810 return non_lvalue (convert (type, arg1));
5811 if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1)
5812 /* Preserve sequence points. */
5813 && (code != TRUTH_ANDIF_EXPR || ! TREE_SIDE_EFFECTS (arg0)))
5814 return non_lvalue (convert (type, arg0));
5815 /* If second arg is constant zero, result is zero, but first arg
5816 must be evaluated. */
5817 if (integer_zerop (arg1))
5818 return omit_one_operand (type, arg1, arg0);
5819 /* Likewise for first arg, but note that only the TRUTH_AND_EXPR
5820 case will be handled here. */
5821 if (integer_zerop (arg0))
5822 return omit_one_operand (type, arg0, arg1);
5825 /* We only do these simplifications if we are optimizing. */
5829 /* Check for things like (A || B) && (A || C). We can convert this
5830 to A || (B && C). Note that either operator can be any of the four
5831 truth and/or operations and the transformation will still be
5832 valid. Also note that we only care about order for the
5833 ANDIF and ORIF operators. If B contains side effects, this
5834 might change the truth-value of A. */
5835 if (TREE_CODE (arg0) == TREE_CODE (arg1)
5836 && (TREE_CODE (arg0) == TRUTH_ANDIF_EXPR
5837 || TREE_CODE (arg0) == TRUTH_ORIF_EXPR
5838 || TREE_CODE (arg0) == TRUTH_AND_EXPR
5839 || TREE_CODE (arg0) == TRUTH_OR_EXPR)
5840 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg0, 1)))
5842 tree a00 = TREE_OPERAND (arg0, 0);
5843 tree a01 = TREE_OPERAND (arg0, 1);
5844 tree a10 = TREE_OPERAND (arg1, 0);
5845 tree a11 = TREE_OPERAND (arg1, 1);
5846 int commutative = ((TREE_CODE (arg0) == TRUTH_OR_EXPR
5847 || TREE_CODE (arg0) == TRUTH_AND_EXPR)
5848 && (code == TRUTH_AND_EXPR
5849 || code == TRUTH_OR_EXPR));
5851 if (operand_equal_p (a00, a10, 0))
5852 return fold (build (TREE_CODE (arg0), type, a00,
5853 fold (build (code, type, a01, a11))));
5854 else if (commutative && operand_equal_p (a00, a11, 0))
5855 return fold (build (TREE_CODE (arg0), type, a00,
5856 fold (build (code, type, a01, a10))));
5857 else if (commutative && operand_equal_p (a01, a10, 0))
5858 return fold (build (TREE_CODE (arg0), type, a01,
5859 fold (build (code, type, a00, a11))));
5861 /* This case if tricky because we must either have commutative
5862 operators or else A10 must not have side-effects. */
5864 else if ((commutative || ! TREE_SIDE_EFFECTS (a10))
5865 && operand_equal_p (a01, a11, 0))
5866 return fold (build (TREE_CODE (arg0), type,
5867 fold (build (code, type, a00, a10)),
5871 /* See if we can build a range comparison. */
5872 if (0 != (tem = fold_range_test (t)))
5875 /* Check for the possibility of merging component references. If our
5876 lhs is another similar operation, try to merge its rhs with our
5877 rhs. Then try to merge our lhs and rhs. */
5878 if (TREE_CODE (arg0) == code
5879 && 0 != (tem = fold_truthop (code, type,
5880 TREE_OPERAND (arg0, 1), arg1)))
5881 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
5883 if ((tem = fold_truthop (code, type, arg0, arg1)) != 0)
5888 case TRUTH_ORIF_EXPR:
5889 /* Note that the operands of this must be ints
5890 and their values must be 0 or true.
5891 ("true" is a fixed value perhaps depending on the language.) */
5892 /* If first arg is constant true, return it. */
5893 if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5894 return convert (type, arg0);
5896 /* If either arg is constant zero, drop it. */
5897 if (TREE_CODE (arg0) == INTEGER_CST && integer_zerop (arg0))
5898 return non_lvalue (convert (type, arg1));
5899 if (TREE_CODE (arg1) == INTEGER_CST && integer_zerop (arg1)
5900 /* Preserve sequence points. */
5901 && (code != TRUTH_ORIF_EXPR || ! TREE_SIDE_EFFECTS (arg0)))
5902 return non_lvalue (convert (type, arg0));
5903 /* If second arg is constant true, result is true, but we must
5904 evaluate first arg. */
5905 if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
5906 return omit_one_operand (type, arg1, arg0);
5907 /* Likewise for first arg, but note this only occurs here for
5909 if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5910 return omit_one_operand (type, arg0, arg1);
5913 case TRUTH_XOR_EXPR:
5914 /* If either arg is constant zero, drop it. */
5915 if (integer_zerop (arg0))
5916 return non_lvalue (convert (type, arg1));
5917 if (integer_zerop (arg1))
5918 return non_lvalue (convert (type, arg0));
5919 /* If either arg is constant true, this is a logical inversion. */
5920 if (integer_onep (arg0))
5921 return non_lvalue (convert (type, invert_truthvalue (arg1)));
5922 if (integer_onep (arg1))
5923 return non_lvalue (convert (type, invert_truthvalue (arg0)));
5932 /* If one arg is a real or integer constant, put it last. */
5933 if ((TREE_CODE (arg0) == INTEGER_CST
5934 && TREE_CODE (arg1) != INTEGER_CST)
5935 || (TREE_CODE (arg0) == REAL_CST
5936 && TREE_CODE (arg0) != REAL_CST))
5938 TREE_OPERAND (t, 0) = arg1;
5939 TREE_OPERAND (t, 1) = arg0;
5940 arg0 = TREE_OPERAND (t, 0);
5941 arg1 = TREE_OPERAND (t, 1);
5942 code = swap_tree_comparison (code);
5943 TREE_SET_CODE (t, code);
5946 if (FLOAT_TYPE_P (TREE_TYPE (arg0)))
5948 /* (-a) CMP (-b) -> b CMP a */
5949 if (TREE_CODE (arg0) == NEGATE_EXPR
5950 && TREE_CODE (arg1) == NEGATE_EXPR)
5951 return fold (build (code, type, TREE_OPERAND (arg1, 0),
5952 TREE_OPERAND (arg0, 0)));
5953 /* (-a) CMP CST -> a swap(CMP) (-CST) */
5954 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == REAL_CST)
5957 (swap_tree_comparison (code), type,
5958 TREE_OPERAND (arg0, 0),
5959 build_real (TREE_TYPE (arg1),
5960 REAL_VALUE_NEGATE (TREE_REAL_CST (arg1)))));
5961 /* IEEE doesn't distinguish +0 and -0 in comparisons. */
5962 /* a CMP (-0) -> a CMP 0 */
5963 if (TREE_CODE (arg1) == REAL_CST
5964 && REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (arg1)))
5965 return fold (build (code, type, arg0,
5966 build_real (TREE_TYPE (arg1), dconst0)));
5968 /* If this is a comparison of a real constant with a PLUS_EXPR
5969 or a MINUS_EXPR of a real constant, we can convert it into a
5970 comparison with a revised real constant as long as no overflow
5971 occurs when unsafe_math_optimizations are enabled. */
5972 if (flag_unsafe_math_optimizations
5973 && TREE_CODE (arg1) == REAL_CST
5974 && (TREE_CODE (arg0) == PLUS_EXPR
5975 || TREE_CODE (arg0) == MINUS_EXPR)
5976 && TREE_CODE (TREE_OPERAND (arg0, 1)) == REAL_CST
5977 && 0 != (tem = const_binop (TREE_CODE (arg0) == PLUS_EXPR
5978 ? MINUS_EXPR : PLUS_EXPR,
5979 arg1, TREE_OPERAND (arg0, 1), 0))
5980 && ! TREE_CONSTANT_OVERFLOW (tem))
5981 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
5984 /* Convert foo++ == CONST into ++foo == CONST + INCR.
5985 First, see if one arg is constant; find the constant arg
5986 and the other one. */
5988 tree constop = 0, varop = NULL_TREE;
5989 int constopnum = -1;
5991 if (TREE_CONSTANT (arg1))
5992 constopnum = 1, constop = arg1, varop = arg0;
5993 if (TREE_CONSTANT (arg0))
5994 constopnum = 0, constop = arg0, varop = arg1;
5996 if (constop && TREE_CODE (varop) == POSTINCREMENT_EXPR)
5998 /* This optimization is invalid for ordered comparisons
5999 if CONST+INCR overflows or if foo+incr might overflow.
6000 This optimization is invalid for floating point due to rounding.
6001 For pointer types we assume overflow doesn't happen. */
6002 if (POINTER_TYPE_P (TREE_TYPE (varop))
6003 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
6004 && (code == EQ_EXPR || code == NE_EXPR)))
6007 = fold (build (PLUS_EXPR, TREE_TYPE (varop),
6008 constop, TREE_OPERAND (varop, 1)));
6010 /* Do not overwrite the current varop to be a preincrement,
6011 create a new node so that we won't confuse our caller who
6012 might create trees and throw them away, reusing the
6013 arguments that they passed to build. This shows up in
6014 the THEN or ELSE parts of ?: being postincrements. */
6015 varop = build (PREINCREMENT_EXPR, TREE_TYPE (varop),
6016 TREE_OPERAND (varop, 0),
6017 TREE_OPERAND (varop, 1));
6019 /* If VAROP is a reference to a bitfield, we must mask
6020 the constant by the width of the field. */
6021 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
6022 && DECL_BIT_FIELD(TREE_OPERAND
6023 (TREE_OPERAND (varop, 0), 1)))
6026 = TREE_INT_CST_LOW (DECL_SIZE
6028 (TREE_OPERAND (varop, 0), 1)));
6029 tree mask, unsigned_type;
6030 unsigned int precision;
6031 tree folded_compare;
6033 /* First check whether the comparison would come out
6034 always the same. If we don't do that we would
6035 change the meaning with the masking. */
6036 if (constopnum == 0)
6037 folded_compare = fold (build (code, type, constop,
6038 TREE_OPERAND (varop, 0)));
6040 folded_compare = fold (build (code, type,
6041 TREE_OPERAND (varop, 0),
6043 if (integer_zerop (folded_compare)
6044 || integer_onep (folded_compare))
6045 return omit_one_operand (type, folded_compare, varop);
6047 unsigned_type = (*lang_hooks.types.type_for_size)(size, 1);
6048 precision = TYPE_PRECISION (unsigned_type);
6049 mask = build_int_2 (~0, ~0);
6050 TREE_TYPE (mask) = unsigned_type;
6051 force_fit_type (mask, 0);
6052 mask = const_binop (RSHIFT_EXPR, mask,
6053 size_int (precision - size), 0);
6054 newconst = fold (build (BIT_AND_EXPR,
6055 TREE_TYPE (varop), newconst,
6056 convert (TREE_TYPE (varop),
6060 t = build (code, type,
6061 (constopnum == 0) ? newconst : varop,
6062 (constopnum == 1) ? newconst : varop);
6066 else if (constop && TREE_CODE (varop) == POSTDECREMENT_EXPR)
6068 if (POINTER_TYPE_P (TREE_TYPE (varop))
6069 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
6070 && (code == EQ_EXPR || code == NE_EXPR)))
6073 = fold (build (MINUS_EXPR, TREE_TYPE (varop),
6074 constop, TREE_OPERAND (varop, 1)));
6076 /* Do not overwrite the current varop to be a predecrement,
6077 create a new node so that we won't confuse our caller who
6078 might create trees and throw them away, reusing the
6079 arguments that they passed to build. This shows up in
6080 the THEN or ELSE parts of ?: being postdecrements. */
6081 varop = build (PREDECREMENT_EXPR, TREE_TYPE (varop),
6082 TREE_OPERAND (varop, 0),
6083 TREE_OPERAND (varop, 1));
6085 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
6086 && DECL_BIT_FIELD(TREE_OPERAND
6087 (TREE_OPERAND (varop, 0), 1)))
6090 = TREE_INT_CST_LOW (DECL_SIZE
6092 (TREE_OPERAND (varop, 0), 1)));
6093 tree mask, unsigned_type;
6094 unsigned int precision;
6095 tree folded_compare;
6097 if (constopnum == 0)
6098 folded_compare = fold (build (code, type, constop,
6099 TREE_OPERAND (varop, 0)));
6101 folded_compare = fold (build (code, type,
6102 TREE_OPERAND (varop, 0),
6104 if (integer_zerop (folded_compare)
6105 || integer_onep (folded_compare))
6106 return omit_one_operand (type, folded_compare, varop);
6108 unsigned_type = (*lang_hooks.types.type_for_size)(size, 1);
6109 precision = TYPE_PRECISION (unsigned_type);
6110 mask = build_int_2 (~0, ~0);
6111 TREE_TYPE (mask) = TREE_TYPE (varop);
6112 force_fit_type (mask, 0);
6113 mask = const_binop (RSHIFT_EXPR, mask,
6114 size_int (precision - size), 0);
6115 newconst = fold (build (BIT_AND_EXPR,
6116 TREE_TYPE (varop), newconst,
6117 convert (TREE_TYPE (varop),
6121 t = build (code, type,
6122 (constopnum == 0) ? newconst : varop,
6123 (constopnum == 1) ? newconst : varop);
6129 /* Change X >= C to X > (C - 1) and X < C to X <= (C - 1) if C > 0.
6130 This transformation affects the cases which are handled in later
6131 optimizations involving comparisons with non-negative constants. */
6132 if (TREE_CODE (arg1) == INTEGER_CST
6133 && TREE_CODE (arg0) != INTEGER_CST
6134 && tree_int_cst_sgn (arg1) > 0)
6140 arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
6141 t = build (code, type, TREE_OPERAND (t, 0), arg1);
6146 arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
6147 t = build (code, type, TREE_OPERAND (t, 0), arg1);
6155 /* Comparisons with the highest or lowest possible integer of
6156 the specified size will have known values. */
6158 int width = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (arg1)));
6160 if (TREE_CODE (arg1) == INTEGER_CST
6161 && ! TREE_CONSTANT_OVERFLOW (arg1)
6162 && width <= HOST_BITS_PER_WIDE_INT
6163 && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
6164 || POINTER_TYPE_P (TREE_TYPE (arg1))))
6166 unsigned HOST_WIDE_INT signed_max;
6167 unsigned HOST_WIDE_INT max, min;
6169 signed_max = ((unsigned HOST_WIDE_INT) 1 << (width - 1)) - 1;
6171 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6173 max = ((unsigned HOST_WIDE_INT) 2 << (width - 1)) - 1;
6179 min = ((unsigned HOST_WIDE_INT) -1 << (width - 1));
6182 if (TREE_INT_CST_HIGH (arg1) == 0
6183 && TREE_INT_CST_LOW (arg1) == max)
6187 return omit_one_operand (type,
6188 convert (type, integer_zero_node),
6192 TREE_SET_CODE (t, EQ_EXPR);
6195 return omit_one_operand (type,
6196 convert (type, integer_one_node),
6200 TREE_SET_CODE (t, NE_EXPR);
6203 /* The GE_EXPR and LT_EXPR cases above are not normally
6204 reached because of previous transformations. */
6209 else if (TREE_INT_CST_HIGH (arg1) == 0
6210 && TREE_INT_CST_LOW (arg1) == max - 1)
6215 arg1 = const_binop (PLUS_EXPR, arg1, integer_one_node, 0);
6216 t = build (code, type, TREE_OPERAND (t, 0), arg1);
6220 arg1 = const_binop (PLUS_EXPR, arg1, integer_one_node, 0);
6221 t = build (code, type, TREE_OPERAND (t, 0), arg1);
6226 else if (TREE_INT_CST_HIGH (arg1) == (min ? -1 : 0)
6227 && TREE_INT_CST_LOW (arg1) == min)
6231 return omit_one_operand (type,
6232 convert (type, integer_zero_node),
6236 TREE_SET_CODE (t, EQ_EXPR);
6240 return omit_one_operand (type,
6241 convert (type, integer_one_node),
6245 TREE_SET_CODE (t, NE_EXPR);
6251 else if (TREE_INT_CST_HIGH (arg1) == (min ? -1 : 0)
6252 && TREE_INT_CST_LOW (arg1) == min + 1)
6257 arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
6258 t = build (code, type, TREE_OPERAND (t, 0), arg1);
6262 arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
6263 t = build (code, type, TREE_OPERAND (t, 0), arg1);
6269 else if (TREE_INT_CST_HIGH (arg1) == 0
6270 && TREE_INT_CST_LOW (arg1) == signed_max
6271 && TREE_UNSIGNED (TREE_TYPE (arg1))
6272 /* signed_type does not work on pointer types. */
6273 && INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
6275 /* The following case also applies to X < signed_max+1
6276 and X >= signed_max+1 because previous transformations. */
6277 if (code == LE_EXPR || code == GT_EXPR)
6280 st0 = (*lang_hooks.types.signed_type) (TREE_TYPE (arg0));
6281 st1 = (*lang_hooks.types.signed_type) (TREE_TYPE (arg1));
6283 (build (code == LE_EXPR ? GE_EXPR: LT_EXPR,
6284 type, convert (st0, arg0),
6285 convert (st1, integer_zero_node)));
6291 /* If this is an EQ or NE comparison of a constant with a PLUS_EXPR or
6292 a MINUS_EXPR of a constant, we can convert it into a comparison with
6293 a revised constant as long as no overflow occurs. */
6294 if ((code == EQ_EXPR || code == NE_EXPR)
6295 && TREE_CODE (arg1) == INTEGER_CST
6296 && (TREE_CODE (arg0) == PLUS_EXPR
6297 || TREE_CODE (arg0) == MINUS_EXPR)
6298 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
6299 && 0 != (tem = const_binop (TREE_CODE (arg0) == PLUS_EXPR
6300 ? MINUS_EXPR : PLUS_EXPR,
6301 arg1, TREE_OPERAND (arg0, 1), 0))
6302 && ! TREE_CONSTANT_OVERFLOW (tem))
6303 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
6305 /* Similarly for a NEGATE_EXPR. */
6306 else if ((code == EQ_EXPR || code == NE_EXPR)
6307 && TREE_CODE (arg0) == NEGATE_EXPR
6308 && TREE_CODE (arg1) == INTEGER_CST
6309 && 0 != (tem = negate_expr (arg1))
6310 && TREE_CODE (tem) == INTEGER_CST
6311 && ! TREE_CONSTANT_OVERFLOW (tem))
6312 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
6314 /* If we have X - Y == 0, we can convert that to X == Y and similarly
6315 for !=. Don't do this for ordered comparisons due to overflow. */
6316 else if ((code == NE_EXPR || code == EQ_EXPR)
6317 && integer_zerop (arg1) && TREE_CODE (arg0) == MINUS_EXPR)
6318 return fold (build (code, type,
6319 TREE_OPERAND (arg0, 0), TREE_OPERAND (arg0, 1)));
6321 /* If we are widening one operand of an integer comparison,
6322 see if the other operand is similarly being widened. Perhaps we
6323 can do the comparison in the narrower type. */
6324 else if (TREE_CODE (TREE_TYPE (arg0)) == INTEGER_TYPE
6325 && TREE_CODE (arg0) == NOP_EXPR
6326 && (tem = get_unwidened (arg0, NULL_TREE)) != arg0
6327 && (t1 = get_unwidened (arg1, TREE_TYPE (tem))) != 0
6328 && (TREE_TYPE (t1) == TREE_TYPE (tem)
6329 || (TREE_CODE (t1) == INTEGER_CST
6330 && int_fits_type_p (t1, TREE_TYPE (tem)))))
6331 return fold (build (code, type, tem, convert (TREE_TYPE (tem), t1)));
6333 /* If this is comparing a constant with a MIN_EXPR or a MAX_EXPR of a
6334 constant, we can simplify it. */
6335 else if (TREE_CODE (arg1) == INTEGER_CST
6336 && (TREE_CODE (arg0) == MIN_EXPR
6337 || TREE_CODE (arg0) == MAX_EXPR)
6338 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
6339 return optimize_minmax_comparison (t);
6341 /* If we are comparing an ABS_EXPR with a constant, we can
6342 convert all the cases into explicit comparisons, but they may
6343 well not be faster than doing the ABS and one comparison.
6344 But ABS (X) <= C is a range comparison, which becomes a subtraction
6345 and a comparison, and is probably faster. */
6346 else if (code == LE_EXPR && TREE_CODE (arg1) == INTEGER_CST
6347 && TREE_CODE (arg0) == ABS_EXPR
6348 && ! TREE_SIDE_EFFECTS (arg0)
6349 && (0 != (tem = negate_expr (arg1)))
6350 && TREE_CODE (tem) == INTEGER_CST
6351 && ! TREE_CONSTANT_OVERFLOW (tem))
6352 return fold (build (TRUTH_ANDIF_EXPR, type,
6353 build (GE_EXPR, type, TREE_OPERAND (arg0, 0), tem),
6354 build (LE_EXPR, type,
6355 TREE_OPERAND (arg0, 0), arg1)));
6357 /* If this is an EQ or NE comparison with zero and ARG0 is
6358 (1 << foo) & bar, convert it to (bar >> foo) & 1. Both require
6359 two operations, but the latter can be done in one less insn
6360 on machines that have only two-operand insns or on which a
6361 constant cannot be the first operand. */
6362 if (integer_zerop (arg1) && (code == EQ_EXPR || code == NE_EXPR)
6363 && TREE_CODE (arg0) == BIT_AND_EXPR)
6365 if (TREE_CODE (TREE_OPERAND (arg0, 0)) == LSHIFT_EXPR
6366 && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 0), 0)))
6368 fold (build (code, type,
6369 build (BIT_AND_EXPR, TREE_TYPE (arg0),
6371 TREE_TYPE (TREE_OPERAND (arg0, 0)),
6372 TREE_OPERAND (arg0, 1),
6373 TREE_OPERAND (TREE_OPERAND (arg0, 0), 1)),
6374 convert (TREE_TYPE (arg0),
6377 else if (TREE_CODE (TREE_OPERAND (arg0, 1)) == LSHIFT_EXPR
6378 && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 1), 0)))
6380 fold (build (code, type,
6381 build (BIT_AND_EXPR, TREE_TYPE (arg0),
6383 TREE_TYPE (TREE_OPERAND (arg0, 1)),
6384 TREE_OPERAND (arg0, 0),
6385 TREE_OPERAND (TREE_OPERAND (arg0, 1), 1)),
6386 convert (TREE_TYPE (arg0),
6391 /* If this is an NE or EQ comparison of zero against the result of a
6392 signed MOD operation whose second operand is a power of 2, make
6393 the MOD operation unsigned since it is simpler and equivalent. */
6394 if ((code == NE_EXPR || code == EQ_EXPR)
6395 && integer_zerop (arg1)
6396 && ! TREE_UNSIGNED (TREE_TYPE (arg0))
6397 && (TREE_CODE (arg0) == TRUNC_MOD_EXPR
6398 || TREE_CODE (arg0) == CEIL_MOD_EXPR
6399 || TREE_CODE (arg0) == FLOOR_MOD_EXPR
6400 || TREE_CODE (arg0) == ROUND_MOD_EXPR)
6401 && integer_pow2p (TREE_OPERAND (arg0, 1)))
6403 tree newtype = (*lang_hooks.types.unsigned_type) (TREE_TYPE (arg0));
6404 tree newmod = build (TREE_CODE (arg0), newtype,
6405 convert (newtype, TREE_OPERAND (arg0, 0)),
6406 convert (newtype, TREE_OPERAND (arg0, 1)));
6408 return build (code, type, newmod, convert (newtype, arg1));
6411 /* If this is an NE comparison of zero with an AND of one, remove the
6412 comparison since the AND will give the correct value. */
6413 if (code == NE_EXPR && integer_zerop (arg1)
6414 && TREE_CODE (arg0) == BIT_AND_EXPR
6415 && integer_onep (TREE_OPERAND (arg0, 1)))
6416 return convert (type, arg0);
6418 /* If we have (A & C) == C where C is a power of 2, convert this into
6419 (A & C) != 0. Similarly for NE_EXPR. */
6420 if ((code == EQ_EXPR || code == NE_EXPR)
6421 && TREE_CODE (arg0) == BIT_AND_EXPR
6422 && integer_pow2p (TREE_OPERAND (arg0, 1))
6423 && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
6424 return fold (build (code == EQ_EXPR ? NE_EXPR : EQ_EXPR, type,
6425 arg0, integer_zero_node));
6427 /* If we have (A & C) != 0 where C is the sign bit of A, convert
6428 this into A < 0. Similarly for (A & C) == 0 into A >= 0. */
6429 if ((code == EQ_EXPR || code == NE_EXPR)
6430 && TREE_CODE (arg0) == BIT_AND_EXPR
6431 && integer_zerop (arg1))
6433 tree arg00 = sign_bit_p (TREE_OPERAND (arg0, 0),
6434 TREE_OPERAND (arg0, 1));
6435 if (arg00 != NULL_TREE)
6437 tree stype = (*lang_hooks.types.signed_type) (TREE_TYPE (arg00));
6438 return fold (build (code == EQ_EXPR ? GE_EXPR : LT_EXPR, type,
6439 convert (stype, arg00),
6440 convert (stype, integer_zero_node)));
6444 /* If X is unsigned, convert X < (1 << Y) into X >> Y == 0
6445 and similarly for >= into !=. */
6446 if ((code == LT_EXPR || code == GE_EXPR)
6447 && TREE_UNSIGNED (TREE_TYPE (arg0))
6448 && TREE_CODE (arg1) == LSHIFT_EXPR
6449 && integer_onep (TREE_OPERAND (arg1, 0)))
6450 return build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
6451 build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
6452 TREE_OPERAND (arg1, 1)),
6453 convert (TREE_TYPE (arg0), integer_zero_node));
6455 else if ((code == LT_EXPR || code == GE_EXPR)
6456 && TREE_UNSIGNED (TREE_TYPE (arg0))
6457 && (TREE_CODE (arg1) == NOP_EXPR
6458 || TREE_CODE (arg1) == CONVERT_EXPR)
6459 && TREE_CODE (TREE_OPERAND (arg1, 0)) == LSHIFT_EXPR
6460 && integer_onep (TREE_OPERAND (TREE_OPERAND (arg1, 0), 0)))
6462 build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
6463 convert (TREE_TYPE (arg0),
6464 build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
6465 TREE_OPERAND (TREE_OPERAND (arg1, 0), 1))),
6466 convert (TREE_TYPE (arg0), integer_zero_node));
6468 /* Simplify comparison of something with itself. (For IEEE
6469 floating-point, we can only do some of these simplifications.) */
6470 if (operand_equal_p (arg0, arg1, 0))
6477 if (! FLOAT_TYPE_P (TREE_TYPE (arg0)))
6478 return constant_boolean_node (1, type);
6480 TREE_SET_CODE (t, code);
6484 /* For NE, we can only do this simplification if integer. */
6485 if (FLOAT_TYPE_P (TREE_TYPE (arg0)))
6487 /* ... fall through ... */
6490 return constant_boolean_node (0, type);
6496 /* If we are comparing an expression that just has comparisons
6497 of two integer values, arithmetic expressions of those comparisons,
6498 and constants, we can simplify it. There are only three cases
6499 to check: the two values can either be equal, the first can be
6500 greater, or the second can be greater. Fold the expression for
6501 those three values. Since each value must be 0 or 1, we have
6502 eight possibilities, each of which corresponds to the constant 0
6503 or 1 or one of the six possible comparisons.
6505 This handles common cases like (a > b) == 0 but also handles
6506 expressions like ((x > y) - (y > x)) > 0, which supposedly
6507 occur in macroized code. */
6509 if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) != INTEGER_CST)
6511 tree cval1 = 0, cval2 = 0;
6514 if (twoval_comparison_p (arg0, &cval1, &cval2, &save_p)
6515 /* Don't handle degenerate cases here; they should already
6516 have been handled anyway. */
6517 && cval1 != 0 && cval2 != 0
6518 && ! (TREE_CONSTANT (cval1) && TREE_CONSTANT (cval2))
6519 && TREE_TYPE (cval1) == TREE_TYPE (cval2)
6520 && INTEGRAL_TYPE_P (TREE_TYPE (cval1))
6521 && TYPE_MAX_VALUE (TREE_TYPE (cval1))
6522 && TYPE_MAX_VALUE (TREE_TYPE (cval2))
6523 && ! operand_equal_p (TYPE_MIN_VALUE (TREE_TYPE (cval1)),
6524 TYPE_MAX_VALUE (TREE_TYPE (cval2)), 0))
6526 tree maxval = TYPE_MAX_VALUE (TREE_TYPE (cval1));
6527 tree minval = TYPE_MIN_VALUE (TREE_TYPE (cval1));
6529 /* We can't just pass T to eval_subst in case cval1 or cval2
6530 was the same as ARG1. */
6533 = fold (build (code, type,
6534 eval_subst (arg0, cval1, maxval, cval2, minval),
6537 = fold (build (code, type,
6538 eval_subst (arg0, cval1, maxval, cval2, maxval),
6541 = fold (build (code, type,
6542 eval_subst (arg0, cval1, minval, cval2, maxval),
6545 /* All three of these results should be 0 or 1. Confirm they
6546 are. Then use those values to select the proper code
6549 if ((integer_zerop (high_result)
6550 || integer_onep (high_result))
6551 && (integer_zerop (equal_result)
6552 || integer_onep (equal_result))
6553 && (integer_zerop (low_result)
6554 || integer_onep (low_result)))
6556 /* Make a 3-bit mask with the high-order bit being the
6557 value for `>', the next for '=', and the low for '<'. */
6558 switch ((integer_onep (high_result) * 4)
6559 + (integer_onep (equal_result) * 2)
6560 + integer_onep (low_result))
6564 return omit_one_operand (type, integer_zero_node, arg0);
6585 return omit_one_operand (type, integer_one_node, arg0);
6588 t = build (code, type, cval1, cval2);
6590 return save_expr (t);
6597 /* If this is a comparison of a field, we may be able to simplify it. */
6598 if (((TREE_CODE (arg0) == COMPONENT_REF
6599 && (*lang_hooks.can_use_bit_fields_p) ())
6600 || TREE_CODE (arg0) == BIT_FIELD_REF)
6601 && (code == EQ_EXPR || code == NE_EXPR)
6602 /* Handle the constant case even without -O
6603 to make sure the warnings are given. */
6604 && (optimize || TREE_CODE (arg1) == INTEGER_CST))
6606 t1 = optimize_bit_field_compare (code, type, arg0, arg1);
6610 /* If this is a comparison of complex values and either or both sides
6611 are a COMPLEX_EXPR or COMPLEX_CST, it is best to split up the
6612 comparisons and join them with a TRUTH_ANDIF_EXPR or TRUTH_ORIF_EXPR.
6613 This may prevent needless evaluations. */
6614 if ((code == EQ_EXPR || code == NE_EXPR)
6615 && TREE_CODE (TREE_TYPE (arg0)) == COMPLEX_TYPE
6616 && (TREE_CODE (arg0) == COMPLEX_EXPR
6617 || TREE_CODE (arg1) == COMPLEX_EXPR
6618 || TREE_CODE (arg0) == COMPLEX_CST
6619 || TREE_CODE (arg1) == COMPLEX_CST))
6621 tree subtype = TREE_TYPE (TREE_TYPE (arg0));
6622 tree real0, imag0, real1, imag1;
6624 arg0 = save_expr (arg0);
6625 arg1 = save_expr (arg1);
6626 real0 = fold (build1 (REALPART_EXPR, subtype, arg0));
6627 imag0 = fold (build1 (IMAGPART_EXPR, subtype, arg0));
6628 real1 = fold (build1 (REALPART_EXPR, subtype, arg1));
6629 imag1 = fold (build1 (IMAGPART_EXPR, subtype, arg1));
6631 return fold (build ((code == EQ_EXPR ? TRUTH_ANDIF_EXPR
6634 fold (build (code, type, real0, real1)),
6635 fold (build (code, type, imag0, imag1))));
6638 /* Optimize comparisons of strlen vs zero to a compare of the
6639 first character of the string vs zero. To wit,
6640 strlen(ptr) == 0 => *ptr == 0
6641 strlen(ptr) != 0 => *ptr != 0
6642 Other cases should reduce to one of these two (or a constant)
6643 due to the return value of strlen being unsigned. */
6644 if ((code == EQ_EXPR || code == NE_EXPR)
6645 && integer_zerop (arg1)
6646 && TREE_CODE (arg0) == CALL_EXPR
6647 && TREE_CODE (TREE_OPERAND (arg0, 0)) == ADDR_EXPR)
6649 tree fndecl = TREE_OPERAND (TREE_OPERAND (arg0, 0), 0);
6652 if (TREE_CODE (fndecl) == FUNCTION_DECL
6653 && DECL_BUILT_IN (fndecl)
6654 && DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_MD
6655 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STRLEN
6656 && (arglist = TREE_OPERAND (arg0, 1))
6657 && TREE_CODE (TREE_TYPE (TREE_VALUE (arglist))) == POINTER_TYPE
6658 && ! TREE_CHAIN (arglist))
6659 return fold (build (code, type,
6660 build1 (INDIRECT_REF, char_type_node,
6661 TREE_VALUE(arglist)),
6662 integer_zero_node));
6665 /* From here on, the only cases we handle are when the result is
6666 known to be a constant.
6668 To compute GT, swap the arguments and do LT.
6669 To compute GE, do LT and invert the result.
6670 To compute LE, swap the arguments, do LT and invert the result.
6671 To compute NE, do EQ and invert the result.
6673 Therefore, the code below must handle only EQ and LT. */
6675 if (code == LE_EXPR || code == GT_EXPR)
6677 tem = arg0, arg0 = arg1, arg1 = tem;
6678 code = swap_tree_comparison (code);
6681 /* Note that it is safe to invert for real values here because we
6682 will check below in the one case that it matters. */
6686 if (code == NE_EXPR || code == GE_EXPR)
6689 code = invert_tree_comparison (code);
6692 /* Compute a result for LT or EQ if args permit;
6693 otherwise return T. */
6694 if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
6696 if (code == EQ_EXPR)
6697 t1 = build_int_2 (tree_int_cst_equal (arg0, arg1), 0);
6699 t1 = build_int_2 ((TREE_UNSIGNED (TREE_TYPE (arg0))
6700 ? INT_CST_LT_UNSIGNED (arg0, arg1)
6701 : INT_CST_LT (arg0, arg1)),
6705 #if 0 /* This is no longer useful, but breaks some real code. */
6706 /* Assume a nonexplicit constant cannot equal an explicit one,
6707 since such code would be undefined anyway.
6708 Exception: on sysvr4, using #pragma weak,
6709 a label can come out as 0. */
6710 else if (TREE_CODE (arg1) == INTEGER_CST
6711 && !integer_zerop (arg1)
6712 && TREE_CONSTANT (arg0)
6713 && TREE_CODE (arg0) == ADDR_EXPR
6715 t1 = build_int_2 (0, 0);
6717 /* Two real constants can be compared explicitly. */
6718 else if (TREE_CODE (arg0) == REAL_CST && TREE_CODE (arg1) == REAL_CST)
6720 /* If either operand is a NaN, the result is false with two
6721 exceptions: First, an NE_EXPR is true on NaNs, but that case
6722 is already handled correctly since we will be inverting the
6723 result for NE_EXPR. Second, if we had inverted a LE_EXPR
6724 or a GE_EXPR into a LT_EXPR, we must return true so that it
6725 will be inverted into false. */
6727 if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg0))
6728 || REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
6729 t1 = build_int_2 (invert && code == LT_EXPR, 0);
6731 else if (code == EQ_EXPR)
6732 t1 = build_int_2 (REAL_VALUES_EQUAL (TREE_REAL_CST (arg0),
6733 TREE_REAL_CST (arg1)),
6736 t1 = build_int_2 (REAL_VALUES_LESS (TREE_REAL_CST (arg0),
6737 TREE_REAL_CST (arg1)),
6741 if (t1 == NULL_TREE)
6745 TREE_INT_CST_LOW (t1) ^= 1;
6747 TREE_TYPE (t1) = type;
6748 if (TREE_CODE (type) == BOOLEAN_TYPE)
6749 return (*lang_hooks.truthvalue_conversion) (t1);
6753 /* Pedantic ANSI C says that a conditional expression is never an lvalue,
6754 so all simple results must be passed through pedantic_non_lvalue. */
6755 if (TREE_CODE (arg0) == INTEGER_CST)
6756 return pedantic_non_lvalue
6757 (TREE_OPERAND (t, (integer_zerop (arg0) ? 2 : 1)));
6758 else if (operand_equal_p (arg1, TREE_OPERAND (expr, 2), 0))
6759 return pedantic_omit_one_operand (type, arg1, arg0);
6761 /* If the second operand is zero, invert the comparison and swap
6762 the second and third operands. Likewise if the second operand
6763 is constant and the third is not or if the third operand is
6764 equivalent to the first operand of the comparison. */
6766 if (integer_zerop (arg1)
6767 || (TREE_CONSTANT (arg1) && ! TREE_CONSTANT (TREE_OPERAND (t, 2)))
6768 || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
6769 && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
6770 TREE_OPERAND (t, 2),
6771 TREE_OPERAND (arg0, 1))))
6773 /* See if this can be inverted. If it can't, possibly because
6774 it was a floating-point inequality comparison, don't do
6776 tem = invert_truthvalue (arg0);
6778 if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
6780 t = build (code, type, tem,
6781 TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
6783 /* arg1 should be the first argument of the new T. */
6784 arg1 = TREE_OPERAND (t, 1);
6789 /* If we have A op B ? A : C, we may be able to convert this to a
6790 simpler expression, depending on the operation and the values
6791 of B and C. Signed zeros prevent all of these transformations,
6792 for reasons given above each one. */
6794 if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
6795 && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
6796 arg1, TREE_OPERAND (arg0, 1))
6797 && !HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
6799 tree arg2 = TREE_OPERAND (t, 2);
6800 enum tree_code comp_code = TREE_CODE (arg0);
6804 /* If we have A op 0 ? A : -A, consider applying the following
6807 A == 0? A : -A same as -A
6808 A != 0? A : -A same as A
6809 A >= 0? A : -A same as abs (A)
6810 A > 0? A : -A same as abs (A)
6811 A <= 0? A : -A same as -abs (A)
6812 A < 0? A : -A same as -abs (A)
6814 None of these transformations work for modes with signed
6815 zeros. If A is +/-0, the first two transformations will
6816 change the sign of the result (from +0 to -0, or vice
6817 versa). The last four will fix the sign of the result,
6818 even though the original expressions could be positive or
6819 negative, depending on the sign of A.
6821 Note that all these transformations are correct if A is
6822 NaN, since the two alternatives (A and -A) are also NaNs. */
6823 if ((FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 1)))
6824 ? real_zerop (TREE_OPERAND (arg0, 1))
6825 : integer_zerop (TREE_OPERAND (arg0, 1)))
6826 && TREE_CODE (arg2) == NEGATE_EXPR
6827 && operand_equal_p (TREE_OPERAND (arg2, 0), arg1, 0))
6835 (convert (TREE_TYPE (TREE_OPERAND (t, 1)),
6838 return pedantic_non_lvalue (convert (type, arg1));
6841 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6842 arg1 = convert ((*lang_hooks.types.signed_type)
6843 (TREE_TYPE (arg1)), arg1);
6844 return pedantic_non_lvalue
6845 (convert (type, fold (build1 (ABS_EXPR,
6846 TREE_TYPE (arg1), arg1))));
6849 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6850 arg1 = convert ((lang_hooks.types.signed_type)
6851 (TREE_TYPE (arg1)), arg1);
6852 return pedantic_non_lvalue
6853 (negate_expr (convert (type,
6854 fold (build1 (ABS_EXPR,
6861 /* A != 0 ? A : 0 is simply A, unless A is -0. Likewise
6862 A == 0 ? A : 0 is always 0 unless A is -0. Note that
6863 both transformations are correct when A is NaN: A != 0
6864 is then true, and A == 0 is false. */
6866 if (integer_zerop (TREE_OPERAND (arg0, 1)) && integer_zerop (arg2))
6868 if (comp_code == NE_EXPR)
6869 return pedantic_non_lvalue (convert (type, arg1));
6870 else if (comp_code == EQ_EXPR)
6871 return pedantic_non_lvalue (convert (type, integer_zero_node));
6874 /* Try some transformations of A op B ? A : B.
6876 A == B? A : B same as B
6877 A != B? A : B same as A
6878 A >= B? A : B same as max (A, B)
6879 A > B? A : B same as max (B, A)
6880 A <= B? A : B same as min (A, B)
6881 A < B? A : B same as min (B, A)
6883 As above, these transformations don't work in the presence
6884 of signed zeros. For example, if A and B are zeros of
6885 opposite sign, the first two transformations will change
6886 the sign of the result. In the last four, the original
6887 expressions give different results for (A=+0, B=-0) and
6888 (A=-0, B=+0), but the transformed expressions do not.
6890 The first two transformations are correct if either A or B
6891 is a NaN. In the first transformation, the condition will
6892 be false, and B will indeed be chosen. In the case of the
6893 second transformation, the condition A != B will be true,
6894 and A will be chosen.
6896 The conversions to max() and min() are not correct if B is
6897 a number and A is not. The conditions in the original
6898 expressions will be false, so all four give B. The min()
6899 and max() versions would give a NaN instead. */
6900 if (operand_equal_for_comparison_p (TREE_OPERAND (arg0, 1),
6901 arg2, TREE_OPERAND (arg0, 0)))
6903 tree comp_op0 = TREE_OPERAND (arg0, 0);
6904 tree comp_op1 = TREE_OPERAND (arg0, 1);
6905 tree comp_type = TREE_TYPE (comp_op0);
6907 /* Avoid adding NOP_EXPRs in case this is an lvalue. */
6908 if (TYPE_MAIN_VARIANT (comp_type) == TYPE_MAIN_VARIANT (type))
6914 return pedantic_non_lvalue (convert (type, arg2));
6916 return pedantic_non_lvalue (convert (type, arg1));
6919 /* In C++ a ?: expression can be an lvalue, so put the
6920 operand which will be used if they are equal first
6921 so that we can convert this back to the
6922 corresponding COND_EXPR. */
6923 if (!HONOR_NANS (TYPE_MODE (TREE_TYPE (arg1))))
6924 return pedantic_non_lvalue
6925 (convert (type, fold (build (MIN_EXPR, comp_type,
6926 (comp_code == LE_EXPR
6927 ? comp_op0 : comp_op1),
6928 (comp_code == LE_EXPR
6929 ? comp_op1 : comp_op0)))));
6933 if (!HONOR_NANS (TYPE_MODE (TREE_TYPE (arg1))))
6934 return pedantic_non_lvalue
6935 (convert (type, fold (build (MAX_EXPR, comp_type,
6936 (comp_code == GE_EXPR
6937 ? comp_op0 : comp_op1),
6938 (comp_code == GE_EXPR
6939 ? comp_op1 : comp_op0)))));
6946 /* If this is A op C1 ? A : C2 with C1 and C2 constant integers,
6947 we might still be able to simplify this. For example,
6948 if C1 is one less or one more than C2, this might have started
6949 out as a MIN or MAX and been transformed by this function.
6950 Only good for INTEGER_TYPEs, because we need TYPE_MAX_VALUE. */
6952 if (INTEGRAL_TYPE_P (type)
6953 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
6954 && TREE_CODE (arg2) == INTEGER_CST)
6958 /* We can replace A with C1 in this case. */
6959 arg1 = convert (type, TREE_OPERAND (arg0, 1));
6960 t = build (code, type, TREE_OPERAND (t, 0), arg1,
6961 TREE_OPERAND (t, 2));
6965 /* If C1 is C2 + 1, this is min(A, C2). */
6966 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
6967 && operand_equal_p (TREE_OPERAND (arg0, 1),
6968 const_binop (PLUS_EXPR, arg2,
6969 integer_one_node, 0), 1))
6970 return pedantic_non_lvalue
6971 (fold (build (MIN_EXPR, type, arg1, arg2)));
6975 /* If C1 is C2 - 1, this is min(A, C2). */
6976 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
6977 && operand_equal_p (TREE_OPERAND (arg0, 1),
6978 const_binop (MINUS_EXPR, arg2,
6979 integer_one_node, 0), 1))
6980 return pedantic_non_lvalue
6981 (fold (build (MIN_EXPR, type, arg1, arg2)));
6985 /* If C1 is C2 - 1, this is max(A, C2). */
6986 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
6987 && operand_equal_p (TREE_OPERAND (arg0, 1),
6988 const_binop (MINUS_EXPR, arg2,
6989 integer_one_node, 0), 1))
6990 return pedantic_non_lvalue
6991 (fold (build (MAX_EXPR, type, arg1, arg2)));
6995 /* If C1 is C2 + 1, this is max(A, C2). */
6996 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
6997 && operand_equal_p (TREE_OPERAND (arg0, 1),
6998 const_binop (PLUS_EXPR, arg2,
6999 integer_one_node, 0), 1))
7000 return pedantic_non_lvalue
7001 (fold (build (MAX_EXPR, type, arg1, arg2)));
7010 /* If the second operand is simpler than the third, swap them
7011 since that produces better jump optimization results. */
7012 if ((TREE_CONSTANT (arg1) || DECL_P (arg1)
7013 || TREE_CODE (arg1) == SAVE_EXPR)
7014 && ! (TREE_CONSTANT (TREE_OPERAND (t, 2))
7015 || DECL_P (TREE_OPERAND (t, 2))
7016 || TREE_CODE (TREE_OPERAND (t, 2)) == SAVE_EXPR))
7018 /* See if this can be inverted. If it can't, possibly because
7019 it was a floating-point inequality comparison, don't do
7021 tem = invert_truthvalue (arg0);
7023 if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
7025 t = build (code, type, tem,
7026 TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
7028 /* arg1 should be the first argument of the new T. */
7029 arg1 = TREE_OPERAND (t, 1);
7034 /* Convert A ? 1 : 0 to simply A. */
7035 if (integer_onep (TREE_OPERAND (t, 1))
7036 && integer_zerop (TREE_OPERAND (t, 2))
7037 /* If we try to convert TREE_OPERAND (t, 0) to our type, the
7038 call to fold will try to move the conversion inside
7039 a COND, which will recurse. In that case, the COND_EXPR
7040 is probably the best choice, so leave it alone. */
7041 && type == TREE_TYPE (arg0))
7042 return pedantic_non_lvalue (arg0);
7044 /* Convert A ? 0 : 1 to !A. This prefers the use of NOT_EXPR
7045 over COND_EXPR in cases such as floating point comparisons. */
7046 if (integer_zerop (TREE_OPERAND (t, 1))
7047 && integer_onep (TREE_OPERAND (t, 2))
7048 && truth_value_p (TREE_CODE (arg0)))
7049 return pedantic_non_lvalue (convert (type,
7050 invert_truthvalue (arg0)));
7052 /* Look for expressions of the form A & 2 ? 2 : 0. The result of this
7053 operation is simply A & 2. */
7055 if (integer_zerop (TREE_OPERAND (t, 2))
7056 && TREE_CODE (arg0) == NE_EXPR
7057 && integer_zerop (TREE_OPERAND (arg0, 1))
7058 && integer_pow2p (arg1)
7059 && TREE_CODE (TREE_OPERAND (arg0, 0)) == BIT_AND_EXPR
7060 && operand_equal_p (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1),
7062 return pedantic_non_lvalue (convert (type, TREE_OPERAND (arg0, 0)));
7064 /* Convert A ? B : 0 into A && B if A and B are truth values. */
7065 if (integer_zerop (TREE_OPERAND (t, 2))
7066 && truth_value_p (TREE_CODE (arg0))
7067 && truth_value_p (TREE_CODE (arg1)))
7068 return pedantic_non_lvalue (fold (build (TRUTH_ANDIF_EXPR, type,
7071 /* Convert A ? B : 1 into !A || B if A and B are truth values. */
7072 if (integer_onep (TREE_OPERAND (t, 2))
7073 && truth_value_p (TREE_CODE (arg0))
7074 && truth_value_p (TREE_CODE (arg1)))
7076 /* Only perform transformation if ARG0 is easily inverted. */
7077 tem = invert_truthvalue (arg0);
7078 if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
7079 return pedantic_non_lvalue (fold (build (TRUTH_ORIF_EXPR, type,
7086 /* When pedantic, a compound expression can be neither an lvalue
7087 nor an integer constant expression. */
7088 if (TREE_SIDE_EFFECTS (arg0) || pedantic)
7090 /* Don't let (0, 0) be null pointer constant. */
7091 if (integer_zerop (arg1))
7092 return build1 (NOP_EXPR, type, arg1);
7093 return convert (type, arg1);
7097 return build_complex (type, arg0, arg1);
7101 if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
7103 else if (TREE_CODE (arg0) == COMPLEX_EXPR)
7104 return omit_one_operand (type, TREE_OPERAND (arg0, 0),
7105 TREE_OPERAND (arg0, 1));
7106 else if (TREE_CODE (arg0) == COMPLEX_CST)
7107 return TREE_REALPART (arg0);
7108 else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
7109 return fold (build (TREE_CODE (arg0), type,
7110 fold (build1 (REALPART_EXPR, type,
7111 TREE_OPERAND (arg0, 0))),
7112 fold (build1 (REALPART_EXPR,
7113 type, TREE_OPERAND (arg0, 1)))));
7117 if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
7118 return convert (type, integer_zero_node);
7119 else if (TREE_CODE (arg0) == COMPLEX_EXPR)
7120 return omit_one_operand (type, TREE_OPERAND (arg0, 1),
7121 TREE_OPERAND (arg0, 0));
7122 else if (TREE_CODE (arg0) == COMPLEX_CST)
7123 return TREE_IMAGPART (arg0);
7124 else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
7125 return fold (build (TREE_CODE (arg0), type,
7126 fold (build1 (IMAGPART_EXPR, type,
7127 TREE_OPERAND (arg0, 0))),
7128 fold (build1 (IMAGPART_EXPR, type,
7129 TREE_OPERAND (arg0, 1)))));
7132 /* Pull arithmetic ops out of the CLEANUP_POINT_EXPR where
7134 case CLEANUP_POINT_EXPR:
7135 if (! has_cleanups (arg0))
7136 return TREE_OPERAND (t, 0);
7139 enum tree_code code0 = TREE_CODE (arg0);
7140 int kind0 = TREE_CODE_CLASS (code0);
7141 tree arg00 = TREE_OPERAND (arg0, 0);
7144 if (kind0 == '1' || code0 == TRUTH_NOT_EXPR)
7145 return fold (build1 (code0, type,
7146 fold (build1 (CLEANUP_POINT_EXPR,
7147 TREE_TYPE (arg00), arg00))));
7149 if (kind0 == '<' || kind0 == '2'
7150 || code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR
7151 || code0 == TRUTH_AND_EXPR || code0 == TRUTH_OR_EXPR
7152 || code0 == TRUTH_XOR_EXPR)
7154 arg01 = TREE_OPERAND (arg0, 1);
7156 if (TREE_CONSTANT (arg00)
7157 || ((code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR)
7158 && ! has_cleanups (arg00)))
7159 return fold (build (code0, type, arg00,
7160 fold (build1 (CLEANUP_POINT_EXPR,
7161 TREE_TYPE (arg01), arg01))));
7163 if (TREE_CONSTANT (arg01))
7164 return fold (build (code0, type,
7165 fold (build1 (CLEANUP_POINT_EXPR,
7166 TREE_TYPE (arg00), arg00)),
7174 /* Check for a built-in function. */
7175 if (TREE_CODE (TREE_OPERAND (expr, 0)) == ADDR_EXPR
7176 && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (expr, 0), 0))
7178 && DECL_BUILT_IN (TREE_OPERAND (TREE_OPERAND (expr, 0), 0)))
7180 tree tmp = fold_builtin (expr);
7188 } /* switch (code) */
7191 /* Determine if first argument is a multiple of second argument. Return 0 if
7192 it is not, or we cannot easily determined it to be.
7194 An example of the sort of thing we care about (at this point; this routine
7195 could surely be made more general, and expanded to do what the *_DIV_EXPR's
7196 fold cases do now) is discovering that
7198 SAVE_EXPR (I) * SAVE_EXPR (J * 8)
7204 when we know that the two SAVE_EXPR (J * 8) nodes are the same node.
7206 This code also handles discovering that
7208 SAVE_EXPR (I) * SAVE_EXPR (J * 8)
7210 is a multiple of 8 so we don't have to worry about dealing with a
7213 Note that we *look* inside a SAVE_EXPR only to determine how it was
7214 calculated; it is not safe for fold to do much of anything else with the
7215 internals of a SAVE_EXPR, since it cannot know when it will be evaluated
7216 at run time. For example, the latter example above *cannot* be implemented
7217 as SAVE_EXPR (I) * J or any variant thereof, since the value of J at
7218 evaluation time of the original SAVE_EXPR is not necessarily the same at
7219 the time the new expression is evaluated. The only optimization of this
7220 sort that would be valid is changing
7222 SAVE_EXPR (I) * SAVE_EXPR (SAVE_EXPR (J) * 8)
7226 SAVE_EXPR (I) * SAVE_EXPR (J)
7228 (where the same SAVE_EXPR (J) is used in the original and the
7229 transformed version). */
7232 multiple_of_p (type, top, bottom)
7237 if (operand_equal_p (top, bottom, 0))
7240 if (TREE_CODE (type) != INTEGER_TYPE)
7243 switch (TREE_CODE (top))
7246 return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
7247 || multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
7251 return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
7252 && multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
7255 if (TREE_CODE (TREE_OPERAND (top, 1)) == INTEGER_CST)
7259 op1 = TREE_OPERAND (top, 1);
7260 /* const_binop may not detect overflow correctly,
7261 so check for it explicitly here. */
7262 if (TYPE_PRECISION (TREE_TYPE (size_one_node))
7263 > TREE_INT_CST_LOW (op1)
7264 && TREE_INT_CST_HIGH (op1) == 0
7265 && 0 != (t1 = convert (type,
7266 const_binop (LSHIFT_EXPR, size_one_node,
7268 && ! TREE_OVERFLOW (t1))
7269 return multiple_of_p (type, t1, bottom);
7274 /* Can't handle conversions from non-integral or wider integral type. */
7275 if ((TREE_CODE (TREE_TYPE (TREE_OPERAND (top, 0))) != INTEGER_TYPE)
7276 || (TYPE_PRECISION (type)
7277 < TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (top, 0)))))
7280 /* .. fall through ... */
7283 return multiple_of_p (type, TREE_OPERAND (top, 0), bottom);
7286 if (TREE_CODE (bottom) != INTEGER_CST
7287 || (TREE_UNSIGNED (type)
7288 && (tree_int_cst_sgn (top) < 0
7289 || tree_int_cst_sgn (bottom) < 0)))
7291 return integer_zerop (const_binop (TRUNC_MOD_EXPR,
7299 /* Return true if `t' is known to be non-negative. */
7302 tree_expr_nonnegative_p (t)
7305 switch (TREE_CODE (t))
7311 return tree_int_cst_sgn (t) >= 0;
7312 case TRUNC_DIV_EXPR:
7314 case FLOOR_DIV_EXPR:
7315 case ROUND_DIV_EXPR:
7316 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
7317 && tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7318 case TRUNC_MOD_EXPR:
7320 case FLOOR_MOD_EXPR:
7321 case ROUND_MOD_EXPR:
7322 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
7324 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1))
7325 && tree_expr_nonnegative_p (TREE_OPERAND (t, 2));
7327 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7329 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
7330 && tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7332 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
7333 || tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7335 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7337 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7339 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
7340 case NON_LVALUE_EXPR:
7341 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
7343 return rtl_expr_nonnegative_p (RTL_EXPR_RTL (t));
7346 if (truth_value_p (TREE_CODE (t)))
7347 /* Truth values evaluate to 0 or 1, which is nonnegative. */
7350 /* We don't know sign of `t', so be conservative and return false. */
7355 /* Return true if `r' is known to be non-negative.
7356 Only handles constants at the moment. */
7359 rtl_expr_nonnegative_p (r)
7362 switch (GET_CODE (r))
7365 return INTVAL (r) >= 0;
7368 if (GET_MODE (r) == VOIDmode)
7369 return CONST_DOUBLE_HIGH (r) >= 0;
7377 units = CONST_VECTOR_NUNITS (r);
7379 for (i = 0; i < units; ++i)
7381 elt = CONST_VECTOR_ELT (r, i);
7382 if (!rtl_expr_nonnegative_p (elt))
7391 /* These are always nonnegative. */
7399 #include "gt-fold-const.h"