OSDN Git Service

682ae00a08cf45602f833c1831133fb537055b1b
[pf3gnuchains/gcc-fork.git] / gcc / fold-const.c
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, 1999,
3    2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
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
10 version.
11
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
15 for more details.
16
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, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA.  */
21
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.  */
29
30 /* The entry points in this file are fold, size_int_wide, size_binop
31    and force_fit_type.
32
33    fold takes a tree as argument and returns a simplified tree.
34
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'.
38
39    size_int takes an integer value, and creates a tree constant
40    with type from `sizetype'.
41
42    force_fit_type takes a constant, an overflowable flag and prior
43    overflow indicators.  It forces the value to fit the type and sets
44    TREE_OVERFLOW and TREE_CONSTANT_OVERFLOW as appropriate.  */
45
46 #include "config.h"
47 #include "system.h"
48 #include "coretypes.h"
49 #include "tm.h"
50 #include "flags.h"
51 #include "tree.h"
52 #include "real.h"
53 #include "rtl.h"
54 #include "expr.h"
55 #include "tm_p.h"
56 #include "toplev.h"
57 #include "ggc.h"
58 #include "hashtab.h"
59 #include "langhooks.h"
60 #include "md5.h"
61
62 /* The following constants represent a bit based encoding of GCC's
63    comparison operators.  This encoding simplifies transformations
64    on relational comparison operators, such as AND and OR.  */
65 enum comparison_code {
66   COMPCODE_FALSE = 0,
67   COMPCODE_LT = 1,
68   COMPCODE_EQ = 2,
69   COMPCODE_LE = 3,
70   COMPCODE_GT = 4,
71   COMPCODE_LTGT = 5,
72   COMPCODE_GE = 6,
73   COMPCODE_ORD = 7,
74   COMPCODE_UNORD = 8,
75   COMPCODE_UNLT = 9,
76   COMPCODE_UNEQ = 10,
77   COMPCODE_UNLE = 11,
78   COMPCODE_UNGT = 12,
79   COMPCODE_NE = 13,
80   COMPCODE_UNGE = 14,
81   COMPCODE_TRUE = 15
82 };
83
84 static void encode (HOST_WIDE_INT *, unsigned HOST_WIDE_INT, HOST_WIDE_INT);
85 static void decode (HOST_WIDE_INT *, unsigned HOST_WIDE_INT *, HOST_WIDE_INT *);
86 static bool negate_mathfn_p (enum built_in_function);
87 static bool negate_expr_p (tree);
88 static tree negate_expr (tree);
89 static tree split_tree (tree, enum tree_code, tree *, tree *, tree *, int);
90 static tree associate_trees (tree, tree, enum tree_code, tree);
91 static tree const_binop (enum tree_code, tree, tree, int);
92 static enum comparison_code comparison_to_compcode (enum tree_code);
93 static enum tree_code compcode_to_comparison (enum comparison_code);
94 static tree combine_comparisons (enum tree_code, enum tree_code,
95                                  enum tree_code, tree, tree, tree);
96 static int truth_value_p (enum tree_code);
97 static int operand_equal_for_comparison_p (tree, tree, tree);
98 static int twoval_comparison_p (tree, tree *, tree *, int *);
99 static tree eval_subst (tree, tree, tree, tree, tree);
100 static tree pedantic_omit_one_operand (tree, tree, tree);
101 static tree distribute_bit_expr (enum tree_code, tree, tree, tree);
102 static tree make_bit_field_ref (tree, tree, int, int, int);
103 static tree optimize_bit_field_compare (enum tree_code, tree, tree, tree);
104 static tree decode_field_reference (tree, HOST_WIDE_INT *, HOST_WIDE_INT *,
105                                     enum machine_mode *, int *, int *,
106                                     tree *, tree *);
107 static int all_ones_mask_p (tree, int);
108 static tree sign_bit_p (tree, tree);
109 static int simple_operand_p (tree);
110 static tree range_binop (enum tree_code, tree, tree, int, tree, int);
111 static tree make_range (tree, int *, tree *, tree *);
112 static tree build_range_check (tree, tree, int, tree, tree);
113 static int merge_ranges (int *, tree *, tree *, int, tree, tree, int, tree,
114                          tree);
115 static tree fold_range_test (enum tree_code, tree, tree, tree);
116 static tree fold_cond_expr_with_comparison (tree, tree, tree, tree);
117 static tree unextend (tree, int, int, tree);
118 static tree fold_truthop (enum tree_code, tree, tree, tree);
119 static tree optimize_minmax_comparison (enum tree_code, tree, tree, tree);
120 static tree extract_muldiv (tree, tree, enum tree_code, tree);
121 static tree extract_muldiv_1 (tree, tree, enum tree_code, tree);
122 static int multiple_of_p (tree, tree, tree);
123 static tree fold_binary_op_with_conditional_arg (enum tree_code, tree,
124                                                  tree, tree,
125                                                  tree, tree, int);
126 static bool fold_real_zero_addition_p (tree, tree, int);
127 static tree fold_mathfn_compare (enum built_in_function, enum tree_code,
128                                  tree, tree, tree);
129 static tree fold_inf_compare (enum tree_code, tree, tree, tree);
130 static tree fold_div_compare (enum tree_code, tree, tree, tree);
131 static bool reorder_operands_p (tree, tree);
132 static tree fold_negate_const (tree, tree);
133 static tree fold_not_const (tree, tree);
134 static tree fold_relational_const (enum tree_code, tree, tree, tree);
135 static bool tree_expr_nonzero_p (tree);
136
137 /* We know that A1 + B1 = SUM1, using 2's complement arithmetic and ignoring
138    overflow.  Suppose A, B and SUM have the same respective signs as A1, B1,
139    and SUM1.  Then this yields nonzero if overflow occurred during the
140    addition.
141
142    Overflow occurs if A and B have the same sign, but A and SUM differ in
143    sign.  Use `^' to test whether signs differ, and `< 0' to isolate the
144    sign.  */
145 #define OVERFLOW_SUM_SIGN(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)
146 \f
147 /* To do constant folding on INTEGER_CST nodes requires two-word arithmetic.
148    We do that by representing the two-word integer in 4 words, with only
149    HOST_BITS_PER_WIDE_INT / 2 bits stored in each word, as a positive
150    number.  The value of the word is LOWPART + HIGHPART * BASE.  */
151
152 #define LOWPART(x) \
153   ((x) & (((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)) - 1))
154 #define HIGHPART(x) \
155   ((unsigned HOST_WIDE_INT) (x) >> HOST_BITS_PER_WIDE_INT / 2)
156 #define BASE ((unsigned HOST_WIDE_INT) 1 << HOST_BITS_PER_WIDE_INT / 2)
157
158 /* Unpack a two-word integer into 4 words.
159    LOW and HI are the integer, as two `HOST_WIDE_INT' pieces.
160    WORDS points to the array of HOST_WIDE_INTs.  */
161
162 static void
163 encode (HOST_WIDE_INT *words, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
164 {
165   words[0] = LOWPART (low);
166   words[1] = HIGHPART (low);
167   words[2] = LOWPART (hi);
168   words[3] = HIGHPART (hi);
169 }
170
171 /* Pack an array of 4 words into a two-word integer.
172    WORDS points to the array of words.
173    The integer is stored into *LOW and *HI as two `HOST_WIDE_INT' pieces.  */
174
175 static void
176 decode (HOST_WIDE_INT *words, unsigned HOST_WIDE_INT *low,
177         HOST_WIDE_INT *hi)
178 {
179   *low = words[0] + words[1] * BASE;
180   *hi = words[2] + words[3] * BASE;
181 }
182 \f
183 /* T is an INT_CST node.  OVERFLOWABLE indicates if we are interested
184    in overflow of the value, when >0 we are only interested in signed
185    overflow, for <0 we are interested in any overflow.  OVERFLOWED
186    indicates whether overflow has already occurred.  CONST_OVERFLOWED
187    indicates whether constant overflow has already occurred.  We force
188    T's value to be within range of T's type (by setting to 0 or 1 all
189    the bits outside the type's range).  We set TREE_OVERFLOWED if,
190         OVERFLOWED is nonzero,
191         or OVERFLOWABLE is >0 and signed overflow occurs
192         or OVERFLOWABLE is <0 and any overflow occurs
193    We set TREE_CONSTANT_OVERFLOWED if,
194         CONST_OVERFLOWED is nonzero
195         or we set TREE_OVERFLOWED.
196   We return either the original T, or a copy.  */
197
198 tree
199 force_fit_type (tree t, int overflowable,
200                 bool overflowed, bool overflowed_const)
201 {
202   unsigned HOST_WIDE_INT low;
203   HOST_WIDE_INT high;
204   unsigned int prec;
205   int sign_extended_type;
206
207   gcc_assert (TREE_CODE (t) == INTEGER_CST);
208
209   low = TREE_INT_CST_LOW (t);
210   high = TREE_INT_CST_HIGH (t);
211
212   if (POINTER_TYPE_P (TREE_TYPE (t))
213       || TREE_CODE (TREE_TYPE (t)) == OFFSET_TYPE)
214     prec = POINTER_SIZE;
215   else
216     prec = TYPE_PRECISION (TREE_TYPE (t));
217   /* Size types *are* sign extended.  */
218   sign_extended_type = (!TYPE_UNSIGNED (TREE_TYPE (t))
219                         || (TREE_CODE (TREE_TYPE (t)) == INTEGER_TYPE
220                             && TYPE_IS_SIZETYPE (TREE_TYPE (t))));
221
222   /* First clear all bits that are beyond the type's precision.  */
223
224   if (prec >= 2 * HOST_BITS_PER_WIDE_INT)
225     ;
226   else if (prec > HOST_BITS_PER_WIDE_INT)
227     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
228   else
229     {
230       high = 0;
231       if (prec < HOST_BITS_PER_WIDE_INT)
232         low &= ~((HOST_WIDE_INT) (-1) << prec);
233     }
234
235   if (!sign_extended_type)
236     /* No sign extension */;
237   else if (prec >= 2 * HOST_BITS_PER_WIDE_INT)
238     /* Correct width already.  */;
239   else if (prec > HOST_BITS_PER_WIDE_INT)
240     {
241       /* Sign extend top half? */
242       if (high & ((unsigned HOST_WIDE_INT)1
243                   << (prec - HOST_BITS_PER_WIDE_INT - 1)))
244         high |= (HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT);
245     }
246   else if (prec == HOST_BITS_PER_WIDE_INT)
247     {
248       if ((HOST_WIDE_INT)low < 0)
249         high = -1;
250     }
251   else
252     {
253       /* Sign extend bottom half? */
254       if (low & ((unsigned HOST_WIDE_INT)1 << (prec - 1)))
255         {
256           high = -1;
257           low |= (HOST_WIDE_INT)(-1) << prec;
258         }
259     }
260
261   /* If the value changed, return a new node.  */
262   if (overflowed || overflowed_const
263       || low != TREE_INT_CST_LOW (t) || high != TREE_INT_CST_HIGH (t))
264     {
265       t = build_int_cst_wide (TREE_TYPE (t), low, high);
266
267       if (overflowed
268           || overflowable < 0
269           || (overflowable > 0 && sign_extended_type))
270         {
271           t = copy_node (t);
272           TREE_OVERFLOW (t) = 1;
273           TREE_CONSTANT_OVERFLOW (t) = 1;
274         }
275       else if (overflowed_const)
276         {
277           t = copy_node (t);
278           TREE_CONSTANT_OVERFLOW (t) = 1;
279         }
280     }
281
282   return t;
283 }
284 \f
285 /* Add two doubleword integers with doubleword result.
286    Each argument is given as two `HOST_WIDE_INT' pieces.
287    One argument is L1 and H1; the other, L2 and H2.
288    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
289
290 int
291 add_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
292             unsigned HOST_WIDE_INT l2, HOST_WIDE_INT h2,
293             unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv)
294 {
295   unsigned HOST_WIDE_INT l;
296   HOST_WIDE_INT h;
297
298   l = l1 + l2;
299   h = h1 + h2 + (l < l1);
300
301   *lv = l;
302   *hv = h;
303   return OVERFLOW_SUM_SIGN (h1, h2, h);
304 }
305
306 /* Negate a doubleword integer with doubleword result.
307    Return nonzero if the operation overflows, assuming it's signed.
308    The argument is given as two `HOST_WIDE_INT' pieces in L1 and H1.
309    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
310
311 int
312 neg_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
313             unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv)
314 {
315   if (l1 == 0)
316     {
317       *lv = 0;
318       *hv = - h1;
319       return (*hv & h1) < 0;
320     }
321   else
322     {
323       *lv = -l1;
324       *hv = ~h1;
325       return 0;
326     }
327 }
328 \f
329 /* Multiply two doubleword integers with doubleword result.
330    Return nonzero if the operation overflows, assuming it's signed.
331    Each argument is given as two `HOST_WIDE_INT' pieces.
332    One argument is L1 and H1; the other, L2 and H2.
333    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
334
335 int
336 mul_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
337             unsigned HOST_WIDE_INT l2, HOST_WIDE_INT h2,
338             unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv)
339 {
340   HOST_WIDE_INT arg1[4];
341   HOST_WIDE_INT arg2[4];
342   HOST_WIDE_INT prod[4 * 2];
343   unsigned HOST_WIDE_INT carry;
344   int i, j, k;
345   unsigned HOST_WIDE_INT toplow, neglow;
346   HOST_WIDE_INT tophigh, neghigh;
347
348   encode (arg1, l1, h1);
349   encode (arg2, l2, h2);
350
351   memset (prod, 0, sizeof prod);
352
353   for (i = 0; i < 4; i++)
354     {
355       carry = 0;
356       for (j = 0; j < 4; j++)
357         {
358           k = i + j;
359           /* This product is <= 0xFFFE0001, the sum <= 0xFFFF0000.  */
360           carry += arg1[i] * arg2[j];
361           /* Since prod[p] < 0xFFFF, this sum <= 0xFFFFFFFF.  */
362           carry += prod[k];
363           prod[k] = LOWPART (carry);
364           carry = HIGHPART (carry);
365         }
366       prod[i + 4] = carry;
367     }
368
369   decode (prod, lv, hv);        /* This ignores prod[4] through prod[4*2-1] */
370
371   /* Check for overflow by calculating the top half of the answer in full;
372      it should agree with the low half's sign bit.  */
373   decode (prod + 4, &toplow, &tophigh);
374   if (h1 < 0)
375     {
376       neg_double (l2, h2, &neglow, &neghigh);
377       add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
378     }
379   if (h2 < 0)
380     {
381       neg_double (l1, h1, &neglow, &neghigh);
382       add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
383     }
384   return (*hv < 0 ? ~(toplow & tophigh) : toplow | tophigh) != 0;
385 }
386 \f
387 /* Shift the doubleword integer in L1, H1 left by COUNT places
388    keeping only PREC bits of result.
389    Shift right if COUNT is negative.
390    ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
391    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
392
393 void
394 lshift_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
395                HOST_WIDE_INT count, unsigned int prec,
396                unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv, int arith)
397 {
398   unsigned HOST_WIDE_INT signmask;
399
400   if (count < 0)
401     {
402       rshift_double (l1, h1, -count, prec, lv, hv, arith);
403       return;
404     }
405
406   if (SHIFT_COUNT_TRUNCATED)
407     count %= prec;
408
409   if (count >= 2 * HOST_BITS_PER_WIDE_INT)
410     {
411       /* Shifting by the host word size is undefined according to the
412          ANSI standard, so we must handle this as a special case.  */
413       *hv = 0;
414       *lv = 0;
415     }
416   else if (count >= HOST_BITS_PER_WIDE_INT)
417     {
418       *hv = l1 << (count - HOST_BITS_PER_WIDE_INT);
419       *lv = 0;
420     }
421   else
422     {
423       *hv = (((unsigned HOST_WIDE_INT) h1 << count)
424              | (l1 >> (HOST_BITS_PER_WIDE_INT - count - 1) >> 1));
425       *lv = l1 << count;
426     }
427
428   /* Sign extend all bits that are beyond the precision.  */
429
430   signmask = -((prec > HOST_BITS_PER_WIDE_INT
431                 ? ((unsigned HOST_WIDE_INT) *hv
432                    >> (prec - HOST_BITS_PER_WIDE_INT - 1))
433                 : (*lv >> (prec - 1))) & 1);
434
435   if (prec >= 2 * HOST_BITS_PER_WIDE_INT)
436     ;
437   else if (prec >= HOST_BITS_PER_WIDE_INT)
438     {
439       *hv &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
440       *hv |= signmask << (prec - HOST_BITS_PER_WIDE_INT);
441     }
442   else
443     {
444       *hv = signmask;
445       *lv &= ~((unsigned HOST_WIDE_INT) (-1) << prec);
446       *lv |= signmask << prec;
447     }
448 }
449
450 /* Shift the doubleword integer in L1, H1 right by COUNT places
451    keeping only PREC bits of result.  COUNT must be positive.
452    ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
453    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
454
455 void
456 rshift_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
457                HOST_WIDE_INT count, unsigned int prec,
458                unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv,
459                int arith)
460 {
461   unsigned HOST_WIDE_INT signmask;
462
463   signmask = (arith
464               ? -((unsigned HOST_WIDE_INT) h1 >> (HOST_BITS_PER_WIDE_INT - 1))
465               : 0);
466
467   if (SHIFT_COUNT_TRUNCATED)
468     count %= prec;
469
470   if (count >= 2 * HOST_BITS_PER_WIDE_INT)
471     {
472       /* Shifting by the host word size is undefined according to the
473          ANSI standard, so we must handle this as a special case.  */
474       *hv = 0;
475       *lv = 0;
476     }
477   else if (count >= HOST_BITS_PER_WIDE_INT)
478     {
479       *hv = 0;
480       *lv = (unsigned HOST_WIDE_INT) h1 >> (count - HOST_BITS_PER_WIDE_INT);
481     }
482   else
483     {
484       *hv = (unsigned HOST_WIDE_INT) h1 >> count;
485       *lv = ((l1 >> count)
486              | ((unsigned HOST_WIDE_INT) h1 << (HOST_BITS_PER_WIDE_INT - count - 1) << 1));
487     }
488
489   /* Zero / sign extend all bits that are beyond the precision.  */
490
491   if (count >= (HOST_WIDE_INT)prec)
492     {
493       *hv = signmask;
494       *lv = signmask;
495     }
496   else if ((prec - count) >= 2 * HOST_BITS_PER_WIDE_INT)
497     ;
498   else if ((prec - count) >= HOST_BITS_PER_WIDE_INT)
499     {
500       *hv &= ~((HOST_WIDE_INT) (-1) << (prec - count - HOST_BITS_PER_WIDE_INT));
501       *hv |= signmask << (prec - count - HOST_BITS_PER_WIDE_INT);
502     }
503   else
504     {
505       *hv = signmask;
506       *lv &= ~((unsigned HOST_WIDE_INT) (-1) << (prec - count));
507       *lv |= signmask << (prec - count);
508     }
509 }
510 \f
511 /* Rotate the doubleword integer in L1, H1 left by COUNT places
512    keeping only PREC bits of result.
513    Rotate right if COUNT is negative.
514    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
515
516 void
517 lrotate_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
518                 HOST_WIDE_INT count, unsigned int prec,
519                 unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv)
520 {
521   unsigned HOST_WIDE_INT s1l, s2l;
522   HOST_WIDE_INT s1h, s2h;
523
524   count %= prec;
525   if (count < 0)
526     count += prec;
527
528   lshift_double (l1, h1, count, prec, &s1l, &s1h, 0);
529   rshift_double (l1, h1, prec - count, prec, &s2l, &s2h, 0);
530   *lv = s1l | s2l;
531   *hv = s1h | s2h;
532 }
533
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.  */
537
538 void
539 rrotate_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
540                 HOST_WIDE_INT count, unsigned int prec,
541                 unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv)
542 {
543   unsigned HOST_WIDE_INT s1l, s2l;
544   HOST_WIDE_INT s1h, s2h;
545
546   count %= prec;
547   if (count < 0)
548     count += prec;
549
550   rshift_double (l1, h1, count, prec, &s1l, &s1h, 0);
551   lshift_double (l1, h1, prec - count, prec, &s2l, &s2h, 0);
552   *lv = s1l | s2l;
553   *hv = s1h | s2h;
554 }
555 \f
556 /* Divide doubleword integer LNUM, HNUM by doubleword integer LDEN, HDEN
557    for a quotient (stored in *LQUO, *HQUO) and remainder (in *LREM, *HREM).
558    CODE is a tree code for a kind of division, one of
559    TRUNC_DIV_EXPR, FLOOR_DIV_EXPR, CEIL_DIV_EXPR, ROUND_DIV_EXPR
560    or EXACT_DIV_EXPR
561    It controls how the quotient is rounded to an integer.
562    Return nonzero if the operation overflows.
563    UNS nonzero says do unsigned division.  */
564
565 int
566 div_and_round_double (enum tree_code code, int uns,
567                       unsigned HOST_WIDE_INT lnum_orig, /* num == numerator == dividend */
568                       HOST_WIDE_INT hnum_orig,
569                       unsigned HOST_WIDE_INT lden_orig, /* den == denominator == divisor */
570                       HOST_WIDE_INT hden_orig,
571                       unsigned HOST_WIDE_INT *lquo,
572                       HOST_WIDE_INT *hquo, unsigned HOST_WIDE_INT *lrem,
573                       HOST_WIDE_INT *hrem)
574 {
575   int quo_neg = 0;
576   HOST_WIDE_INT num[4 + 1];     /* extra element for scaling.  */
577   HOST_WIDE_INT den[4], quo[4];
578   int i, j;
579   unsigned HOST_WIDE_INT work;
580   unsigned HOST_WIDE_INT carry = 0;
581   unsigned HOST_WIDE_INT lnum = lnum_orig;
582   HOST_WIDE_INT hnum = hnum_orig;
583   unsigned HOST_WIDE_INT lden = lden_orig;
584   HOST_WIDE_INT hden = hden_orig;
585   int overflow = 0;
586
587   if (hden == 0 && lden == 0)
588     overflow = 1, lden = 1;
589
590   /* Calculate quotient sign and convert operands to unsigned.  */
591   if (!uns)
592     {
593       if (hnum < 0)
594         {
595           quo_neg = ~ quo_neg;
596           /* (minimum integer) / (-1) is the only overflow case.  */
597           if (neg_double (lnum, hnum, &lnum, &hnum)
598               && ((HOST_WIDE_INT) lden & hden) == -1)
599             overflow = 1;
600         }
601       if (hden < 0)
602         {
603           quo_neg = ~ quo_neg;
604           neg_double (lden, hden, &lden, &hden);
605         }
606     }
607
608   if (hnum == 0 && hden == 0)
609     {                           /* single precision */
610       *hquo = *hrem = 0;
611       /* This unsigned division rounds toward zero.  */
612       *lquo = lnum / lden;
613       goto finish_up;
614     }
615
616   if (hnum == 0)
617     {                           /* trivial case: dividend < divisor */
618       /* hden != 0 already checked.  */
619       *hquo = *lquo = 0;
620       *hrem = hnum;
621       *lrem = lnum;
622       goto finish_up;
623     }
624
625   memset (quo, 0, sizeof quo);
626
627   memset (num, 0, sizeof num);  /* to zero 9th element */
628   memset (den, 0, sizeof den);
629
630   encode (num, lnum, hnum);
631   encode (den, lden, hden);
632
633   /* Special code for when the divisor < BASE.  */
634   if (hden == 0 && lden < (unsigned HOST_WIDE_INT) BASE)
635     {
636       /* hnum != 0 already checked.  */
637       for (i = 4 - 1; i >= 0; i--)
638         {
639           work = num[i] + carry * BASE;
640           quo[i] = work / lden;
641           carry = work % lden;
642         }
643     }
644   else
645     {
646       /* Full double precision division,
647          with thanks to Don Knuth's "Seminumerical Algorithms".  */
648       int num_hi_sig, den_hi_sig;
649       unsigned HOST_WIDE_INT quo_est, scale;
650
651       /* Find the highest nonzero divisor digit.  */
652       for (i = 4 - 1;; i--)
653         if (den[i] != 0)
654           {
655             den_hi_sig = i;
656             break;
657           }
658
659       /* Insure that the first digit of the divisor is at least BASE/2.
660          This is required by the quotient digit estimation algorithm.  */
661
662       scale = BASE / (den[den_hi_sig] + 1);
663       if (scale > 1)
664         {               /* scale divisor and dividend */
665           carry = 0;
666           for (i = 0; i <= 4 - 1; i++)
667             {
668               work = (num[i] * scale) + carry;
669               num[i] = LOWPART (work);
670               carry = HIGHPART (work);
671             }
672
673           num[4] = carry;
674           carry = 0;
675           for (i = 0; i <= 4 - 1; i++)
676             {
677               work = (den[i] * scale) + carry;
678               den[i] = LOWPART (work);
679               carry = HIGHPART (work);
680               if (den[i] != 0) den_hi_sig = i;
681             }
682         }
683
684       num_hi_sig = 4;
685
686       /* Main loop */
687       for (i = num_hi_sig - den_hi_sig - 1; i >= 0; i--)
688         {
689           /* Guess the next quotient digit, quo_est, by dividing the first
690              two remaining dividend digits by the high order quotient digit.
691              quo_est is never low and is at most 2 high.  */
692           unsigned HOST_WIDE_INT tmp;
693
694           num_hi_sig = i + den_hi_sig + 1;
695           work = num[num_hi_sig] * BASE + num[num_hi_sig - 1];
696           if (num[num_hi_sig] != den[den_hi_sig])
697             quo_est = work / den[den_hi_sig];
698           else
699             quo_est = BASE - 1;
700
701           /* Refine quo_est so it's usually correct, and at most one high.  */
702           tmp = work - quo_est * den[den_hi_sig];
703           if (tmp < BASE
704               && (den[den_hi_sig - 1] * quo_est
705                   > (tmp * BASE + num[num_hi_sig - 2])))
706             quo_est--;
707
708           /* Try QUO_EST as the quotient digit, by multiplying the
709              divisor by QUO_EST and subtracting from the remaining dividend.
710              Keep in mind that QUO_EST is the I - 1st digit.  */
711
712           carry = 0;
713           for (j = 0; j <= den_hi_sig; j++)
714             {
715               work = quo_est * den[j] + carry;
716               carry = HIGHPART (work);
717               work = num[i + j] - LOWPART (work);
718               num[i + j] = LOWPART (work);
719               carry += HIGHPART (work) != 0;
720             }
721
722           /* If quo_est was high by one, then num[i] went negative and
723              we need to correct things.  */
724           if (num[num_hi_sig] < (HOST_WIDE_INT) carry)
725             {
726               quo_est--;
727               carry = 0;                /* add divisor back in */
728               for (j = 0; j <= den_hi_sig; j++)
729                 {
730                   work = num[i + j] + den[j] + carry;
731                   carry = HIGHPART (work);
732                   num[i + j] = LOWPART (work);
733                 }
734
735               num [num_hi_sig] += carry;
736             }
737
738           /* Store the quotient digit.  */
739           quo[i] = quo_est;
740         }
741     }
742
743   decode (quo, lquo, hquo);
744
745  finish_up:
746   /* If result is negative, make it so.  */
747   if (quo_neg)
748     neg_double (*lquo, *hquo, lquo, hquo);
749
750   /* Compute trial remainder:  rem = num - (quo * den)  */
751   mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
752   neg_double (*lrem, *hrem, lrem, hrem);
753   add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
754
755   switch (code)
756     {
757     case TRUNC_DIV_EXPR:
758     case TRUNC_MOD_EXPR:        /* round toward zero */
759     case EXACT_DIV_EXPR:        /* for this one, it shouldn't matter */
760       return overflow;
761
762     case FLOOR_DIV_EXPR:
763     case FLOOR_MOD_EXPR:        /* round toward negative infinity */
764       if (quo_neg && (*lrem != 0 || *hrem != 0))   /* ratio < 0 && rem != 0 */
765         {
766           /* quo = quo - 1;  */
767           add_double (*lquo, *hquo, (HOST_WIDE_INT) -1, (HOST_WIDE_INT)  -1,
768                       lquo, hquo);
769         }
770       else
771         return overflow;
772       break;
773
774     case CEIL_DIV_EXPR:
775     case CEIL_MOD_EXPR:         /* round toward positive infinity */
776       if (!quo_neg && (*lrem != 0 || *hrem != 0))  /* ratio > 0 && rem != 0 */
777         {
778           add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
779                       lquo, hquo);
780         }
781       else
782         return overflow;
783       break;
784
785     case ROUND_DIV_EXPR:
786     case ROUND_MOD_EXPR:        /* round to closest integer */
787       {
788         unsigned HOST_WIDE_INT labs_rem = *lrem;
789         HOST_WIDE_INT habs_rem = *hrem;
790         unsigned HOST_WIDE_INT labs_den = lden, ltwice;
791         HOST_WIDE_INT habs_den = hden, htwice;
792
793         /* Get absolute values.  */
794         if (*hrem < 0)
795           neg_double (*lrem, *hrem, &labs_rem, &habs_rem);
796         if (hden < 0)
797           neg_double (lden, hden, &labs_den, &habs_den);
798
799         /* If (2 * abs (lrem) >= abs (lden)) */
800         mul_double ((HOST_WIDE_INT) 2, (HOST_WIDE_INT) 0,
801                     labs_rem, habs_rem, &ltwice, &htwice);
802
803         if (((unsigned HOST_WIDE_INT) habs_den
804              < (unsigned HOST_WIDE_INT) htwice)
805             || (((unsigned HOST_WIDE_INT) habs_den
806                  == (unsigned HOST_WIDE_INT) htwice)
807                 && (labs_den < ltwice)))
808           {
809             if (*hquo < 0)
810               /* quo = quo - 1;  */
811               add_double (*lquo, *hquo,
812                           (HOST_WIDE_INT) -1, (HOST_WIDE_INT) -1, lquo, hquo);
813             else
814               /* quo = quo + 1; */
815               add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
816                           lquo, hquo);
817           }
818         else
819           return overflow;
820       }
821       break;
822
823     default:
824       gcc_unreachable ();
825     }
826
827   /* Compute true remainder:  rem = num - (quo * den)  */
828   mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
829   neg_double (*lrem, *hrem, lrem, hrem);
830   add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
831   return overflow;
832 }
833
834 /* If ARG2 divides ARG1 with zero remainder, carries out the division
835    of type CODE and returns the quotient.
836    Otherwise returns NULL_TREE.  */
837
838 static tree
839 div_if_zero_remainder (enum tree_code code, tree arg1, tree arg2)
840 {
841   unsigned HOST_WIDE_INT int1l, int2l;
842   HOST_WIDE_INT int1h, int2h;
843   unsigned HOST_WIDE_INT quol, reml;
844   HOST_WIDE_INT quoh, remh;
845   tree type = TREE_TYPE (arg1);
846   int uns = TYPE_UNSIGNED (type);
847
848   int1l = TREE_INT_CST_LOW (arg1);
849   int1h = TREE_INT_CST_HIGH (arg1);
850   int2l = TREE_INT_CST_LOW (arg2);
851   int2h = TREE_INT_CST_HIGH (arg2);
852
853   div_and_round_double (code, uns, int1l, int1h, int2l, int2h,
854                         &quol, &quoh, &reml, &remh);
855   if (remh != 0 || reml != 0)
856     return NULL_TREE;
857
858   return build_int_cst_wide (type, quol, quoh);
859 }
860 \f
861 /* Return true if built-in mathematical function specified by CODE
862    preserves the sign of it argument, i.e. -f(x) == f(-x).  */
863
864 static bool
865 negate_mathfn_p (enum built_in_function code)
866 {
867   switch (code)
868     {
869     case BUILT_IN_ASIN:
870     case BUILT_IN_ASINF:
871     case BUILT_IN_ASINL:
872     case BUILT_IN_ATAN:
873     case BUILT_IN_ATANF:
874     case BUILT_IN_ATANL:
875     case BUILT_IN_SIN:
876     case BUILT_IN_SINF:
877     case BUILT_IN_SINL:
878     case BUILT_IN_TAN:
879     case BUILT_IN_TANF:
880     case BUILT_IN_TANL:
881       return true;
882
883     default:
884       break;
885     }
886   return false;
887 }
888
889 /* Check whether we may negate an integer constant T without causing
890    overflow.  */
891
892 bool
893 may_negate_without_overflow_p (tree t)
894 {
895   unsigned HOST_WIDE_INT val;
896   unsigned int prec;
897   tree type;
898
899   gcc_assert (TREE_CODE (t) == INTEGER_CST);
900
901   type = TREE_TYPE (t);
902   if (TYPE_UNSIGNED (type))
903     return false;
904
905   prec = TYPE_PRECISION (type);
906   if (prec > HOST_BITS_PER_WIDE_INT)
907     {
908       if (TREE_INT_CST_LOW (t) != 0)
909         return true;
910       prec -= HOST_BITS_PER_WIDE_INT;
911       val = TREE_INT_CST_HIGH (t);
912     }
913   else
914     val = TREE_INT_CST_LOW (t);
915   if (prec < HOST_BITS_PER_WIDE_INT)
916     val &= ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
917   return val != ((unsigned HOST_WIDE_INT) 1 << (prec - 1));
918 }
919
920 /* Determine whether an expression T can be cheaply negated using
921    the function negate_expr.  */
922
923 static bool
924 negate_expr_p (tree t)
925 {
926   tree type;
927
928   if (t == 0)
929     return false;
930
931   type = TREE_TYPE (t);
932
933   STRIP_SIGN_NOPS (t);
934   switch (TREE_CODE (t))
935     {
936     case INTEGER_CST:
937       if (TYPE_UNSIGNED (type) || ! flag_trapv)
938         return true;
939
940       /* Check that -CST will not overflow type.  */
941       return may_negate_without_overflow_p (t);
942
943     case REAL_CST:
944     case NEGATE_EXPR:
945       return true;
946
947     case COMPLEX_CST:
948       return negate_expr_p (TREE_REALPART (t))
949              && negate_expr_p (TREE_IMAGPART (t));
950
951     case PLUS_EXPR:
952       if (FLOAT_TYPE_P (type) && !flag_unsafe_math_optimizations)
953         return false;
954       /* -(A + B) -> (-B) - A.  */
955       if (negate_expr_p (TREE_OPERAND (t, 1))
956           && reorder_operands_p (TREE_OPERAND (t, 0),
957                                  TREE_OPERAND (t, 1)))
958         return true;
959       /* -(A + B) -> (-A) - B.  */
960       return negate_expr_p (TREE_OPERAND (t, 0));
961
962     case MINUS_EXPR:
963       /* We can't turn -(A-B) into B-A when we honor signed zeros.  */
964       return (! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations)
965              && reorder_operands_p (TREE_OPERAND (t, 0),
966                                     TREE_OPERAND (t, 1));
967
968     case MULT_EXPR:
969       if (TYPE_UNSIGNED (TREE_TYPE (t)))
970         break;
971
972       /* Fall through.  */
973
974     case RDIV_EXPR:
975       if (! HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (TREE_TYPE (t))))
976         return negate_expr_p (TREE_OPERAND (t, 1))
977                || negate_expr_p (TREE_OPERAND (t, 0));
978       break;
979
980     case NOP_EXPR:
981       /* Negate -((double)float) as (double)(-float).  */
982       if (TREE_CODE (type) == REAL_TYPE)
983         {
984           tree tem = strip_float_extensions (t);
985           if (tem != t)
986             return negate_expr_p (tem);
987         }
988       break;
989
990     case CALL_EXPR:
991       /* Negate -f(x) as f(-x).  */
992       if (negate_mathfn_p (builtin_mathfn_code (t)))
993         return negate_expr_p (TREE_VALUE (TREE_OPERAND (t, 1)));
994       break;
995
996     case RSHIFT_EXPR:
997       /* Optimize -((int)x >> 31) into (unsigned)x >> 31.  */
998       if (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST)
999         {
1000           tree op1 = TREE_OPERAND (t, 1);
1001           if (TREE_INT_CST_HIGH (op1) == 0
1002               && (unsigned HOST_WIDE_INT) (TYPE_PRECISION (type) - 1)
1003                  == TREE_INT_CST_LOW (op1))
1004             return true;
1005         }
1006       break;
1007
1008     default:
1009       break;
1010     }
1011   return false;
1012 }
1013
1014 /* Given T, an expression, return the negation of T.  Allow for T to be
1015    null, in which case return null.  */
1016
1017 static tree
1018 negate_expr (tree t)
1019 {
1020   tree type;
1021   tree tem;
1022
1023   if (t == 0)
1024     return 0;
1025
1026   type = TREE_TYPE (t);
1027   STRIP_SIGN_NOPS (t);
1028
1029   switch (TREE_CODE (t))
1030     {
1031     case INTEGER_CST:
1032       tem = fold_negate_const (t, type);
1033       if (! TREE_OVERFLOW (tem)
1034           || TYPE_UNSIGNED (type)
1035           || ! flag_trapv)
1036         return tem;
1037       break;
1038
1039     case REAL_CST:
1040       tem = fold_negate_const (t, type);
1041       /* Two's complement FP formats, such as c4x, may overflow.  */
1042       if (! TREE_OVERFLOW (tem) || ! flag_trapping_math)
1043         return fold_convert (type, tem);
1044       break;
1045
1046     case COMPLEX_CST:
1047       {
1048         tree rpart = negate_expr (TREE_REALPART (t));
1049         tree ipart = negate_expr (TREE_IMAGPART (t));
1050
1051         if ((TREE_CODE (rpart) == REAL_CST
1052              && TREE_CODE (ipart) == REAL_CST)
1053             || (TREE_CODE (rpart) == INTEGER_CST
1054                 && TREE_CODE (ipart) == INTEGER_CST))
1055           return build_complex (type, rpart, ipart);
1056       }
1057       break;
1058
1059     case NEGATE_EXPR:
1060       return fold_convert (type, TREE_OPERAND (t, 0));
1061
1062     case PLUS_EXPR:
1063       if (! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations)
1064         {
1065           /* -(A + B) -> (-B) - A.  */
1066           if (negate_expr_p (TREE_OPERAND (t, 1))
1067               && reorder_operands_p (TREE_OPERAND (t, 0),
1068                                      TREE_OPERAND (t, 1)))
1069             {
1070               tem = negate_expr (TREE_OPERAND (t, 1));
1071               tem = fold_build2 (MINUS_EXPR, TREE_TYPE (t),
1072                                  tem, TREE_OPERAND (t, 0));
1073               return fold_convert (type, tem);
1074             }
1075
1076           /* -(A + B) -> (-A) - B.  */
1077           if (negate_expr_p (TREE_OPERAND (t, 0)))
1078             {
1079               tem = negate_expr (TREE_OPERAND (t, 0));
1080               tem = fold_build2 (MINUS_EXPR, TREE_TYPE (t),
1081                                  tem, TREE_OPERAND (t, 1));
1082               return fold_convert (type, tem);
1083             }
1084         }
1085       break;
1086
1087     case MINUS_EXPR:
1088       /* - (A - B) -> B - A  */
1089       if ((! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations)
1090           && reorder_operands_p (TREE_OPERAND (t, 0), TREE_OPERAND (t, 1)))
1091         return fold_convert (type,
1092                              fold_build2 (MINUS_EXPR, TREE_TYPE (t),
1093                                           TREE_OPERAND (t, 1),
1094                                           TREE_OPERAND (t, 0)));
1095       break;
1096
1097     case MULT_EXPR:
1098       if (TYPE_UNSIGNED (TREE_TYPE (t)))
1099         break;
1100
1101       /* Fall through.  */
1102
1103     case RDIV_EXPR:
1104       if (! HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (TREE_TYPE (t))))
1105         {
1106           tem = TREE_OPERAND (t, 1);
1107           if (negate_expr_p (tem))
1108             return fold_convert (type,
1109                                  fold_build2 (TREE_CODE (t), TREE_TYPE (t),
1110                                               TREE_OPERAND (t, 0),
1111                                               negate_expr (tem)));
1112           tem = TREE_OPERAND (t, 0);
1113           if (negate_expr_p (tem))
1114             return fold_convert (type,
1115                                  fold_build2 (TREE_CODE (t), TREE_TYPE (t),
1116                                               negate_expr (tem),
1117                                               TREE_OPERAND (t, 1)));
1118         }
1119       break;
1120
1121     case NOP_EXPR:
1122       /* Convert -((double)float) into (double)(-float).  */
1123       if (TREE_CODE (type) == REAL_TYPE)
1124         {
1125           tem = strip_float_extensions (t);
1126           if (tem != t && negate_expr_p (tem))
1127             return fold_convert (type, negate_expr (tem));
1128         }
1129       break;
1130
1131     case CALL_EXPR:
1132       /* Negate -f(x) as f(-x).  */
1133       if (negate_mathfn_p (builtin_mathfn_code (t))
1134           && negate_expr_p (TREE_VALUE (TREE_OPERAND (t, 1))))
1135         {
1136           tree fndecl, arg, arglist;
1137
1138           fndecl = get_callee_fndecl (t);
1139           arg = negate_expr (TREE_VALUE (TREE_OPERAND (t, 1)));
1140           arglist = build_tree_list (NULL_TREE, arg);
1141           return build_function_call_expr (fndecl, arglist);
1142         }
1143       break;
1144
1145     case RSHIFT_EXPR:
1146       /* Optimize -((int)x >> 31) into (unsigned)x >> 31.  */
1147       if (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST)
1148         {
1149           tree op1 = TREE_OPERAND (t, 1);
1150           if (TREE_INT_CST_HIGH (op1) == 0
1151               && (unsigned HOST_WIDE_INT) (TYPE_PRECISION (type) - 1)
1152                  == TREE_INT_CST_LOW (op1))
1153             {
1154               tree ntype = TYPE_UNSIGNED (type)
1155                            ? lang_hooks.types.signed_type (type)
1156                            : lang_hooks.types.unsigned_type (type);
1157               tree temp = fold_convert (ntype, TREE_OPERAND (t, 0));
1158               temp = fold_build2 (RSHIFT_EXPR, ntype, temp, op1);
1159               return fold_convert (type, temp);
1160             }
1161         }
1162       break;
1163
1164     default:
1165       break;
1166     }
1167
1168   tem = fold_build1 (NEGATE_EXPR, TREE_TYPE (t), t);
1169   return fold_convert (type, tem);
1170 }
1171 \f
1172 /* Split a tree IN into a constant, literal and variable parts that could be
1173    combined with CODE to make IN.  "constant" means an expression with
1174    TREE_CONSTANT but that isn't an actual constant.  CODE must be a
1175    commutative arithmetic operation.  Store the constant part into *CONP,
1176    the literal in *LITP and return the variable part.  If a part isn't
1177    present, set it to null.  If the tree does not decompose in this way,
1178    return the entire tree as the variable part and the other parts as null.
1179
1180    If CODE is PLUS_EXPR we also split trees that use MINUS_EXPR.  In that
1181    case, we negate an operand that was subtracted.  Except if it is a
1182    literal for which we use *MINUS_LITP instead.
1183
1184    If NEGATE_P is true, we are negating all of IN, again except a literal
1185    for which we use *MINUS_LITP instead.
1186
1187    If IN is itself a literal or constant, return it as appropriate.
1188
1189    Note that we do not guarantee that any of the three values will be the
1190    same type as IN, but they will have the same signedness and mode.  */
1191
1192 static tree
1193 split_tree (tree in, enum tree_code code, tree *conp, tree *litp,
1194             tree *minus_litp, int negate_p)
1195 {
1196   tree var = 0;
1197
1198   *conp = 0;
1199   *litp = 0;
1200   *minus_litp = 0;
1201
1202   /* Strip any conversions that don't change the machine mode or signedness.  */
1203   STRIP_SIGN_NOPS (in);
1204
1205   if (TREE_CODE (in) == INTEGER_CST || TREE_CODE (in) == REAL_CST)
1206     *litp = in;
1207   else if (TREE_CODE (in) == code
1208            || (! FLOAT_TYPE_P (TREE_TYPE (in))
1209                /* We can associate addition and subtraction together (even
1210                   though the C standard doesn't say so) for integers because
1211                   the value is not affected.  For reals, the value might be
1212                   affected, so we can't.  */
1213                && ((code == PLUS_EXPR && TREE_CODE (in) == MINUS_EXPR)
1214                    || (code == MINUS_EXPR && TREE_CODE (in) == PLUS_EXPR))))
1215     {
1216       tree op0 = TREE_OPERAND (in, 0);
1217       tree op1 = TREE_OPERAND (in, 1);
1218       int neg1_p = TREE_CODE (in) == MINUS_EXPR;
1219       int neg_litp_p = 0, neg_conp_p = 0, neg_var_p = 0;
1220
1221       /* First see if either of the operands is a literal, then a constant.  */
1222       if (TREE_CODE (op0) == INTEGER_CST || TREE_CODE (op0) == REAL_CST)
1223         *litp = op0, op0 = 0;
1224       else if (TREE_CODE (op1) == INTEGER_CST || TREE_CODE (op1) == REAL_CST)
1225         *litp = op1, neg_litp_p = neg1_p, op1 = 0;
1226
1227       if (op0 != 0 && TREE_CONSTANT (op0))
1228         *conp = op0, op0 = 0;
1229       else if (op1 != 0 && TREE_CONSTANT (op1))
1230         *conp = op1, neg_conp_p = neg1_p, op1 = 0;
1231
1232       /* If we haven't dealt with either operand, this is not a case we can
1233          decompose.  Otherwise, VAR is either of the ones remaining, if any.  */
1234       if (op0 != 0 && op1 != 0)
1235         var = in;
1236       else if (op0 != 0)
1237         var = op0;
1238       else
1239         var = op1, neg_var_p = neg1_p;
1240
1241       /* Now do any needed negations.  */
1242       if (neg_litp_p)
1243         *minus_litp = *litp, *litp = 0;
1244       if (neg_conp_p)
1245         *conp = negate_expr (*conp);
1246       if (neg_var_p)
1247         var = negate_expr (var);
1248     }
1249   else if (TREE_CONSTANT (in))
1250     *conp = in;
1251   else
1252     var = in;
1253
1254   if (negate_p)
1255     {
1256       if (*litp)
1257         *minus_litp = *litp, *litp = 0;
1258       else if (*minus_litp)
1259         *litp = *minus_litp, *minus_litp = 0;
1260       *conp = negate_expr (*conp);
1261       var = negate_expr (var);
1262     }
1263
1264   return var;
1265 }
1266
1267 /* Re-associate trees split by the above function.  T1 and T2 are either
1268    expressions to associate or null.  Return the new expression, if any.  If
1269    we build an operation, do it in TYPE and with CODE.  */
1270
1271 static tree
1272 associate_trees (tree t1, tree t2, enum tree_code code, tree type)
1273 {
1274   if (t1 == 0)
1275     return t2;
1276   else if (t2 == 0)
1277     return t1;
1278
1279   /* If either input is CODE, a PLUS_EXPR, or a MINUS_EXPR, don't
1280      try to fold this since we will have infinite recursion.  But do
1281      deal with any NEGATE_EXPRs.  */
1282   if (TREE_CODE (t1) == code || TREE_CODE (t2) == code
1283       || TREE_CODE (t1) == MINUS_EXPR || TREE_CODE (t2) == MINUS_EXPR)
1284     {
1285       if (code == PLUS_EXPR)
1286         {
1287           if (TREE_CODE (t1) == NEGATE_EXPR)
1288             return build2 (MINUS_EXPR, type, fold_convert (type, t2),
1289                            fold_convert (type, TREE_OPERAND (t1, 0)));
1290           else if (TREE_CODE (t2) == NEGATE_EXPR)
1291             return build2 (MINUS_EXPR, type, fold_convert (type, t1),
1292                            fold_convert (type, TREE_OPERAND (t2, 0)));
1293           else if (integer_zerop (t2))
1294             return fold_convert (type, t1);
1295         }
1296       else if (code == MINUS_EXPR)
1297         {
1298           if (integer_zerop (t2))
1299             return fold_convert (type, t1);
1300         }
1301
1302       return build2 (code, type, fold_convert (type, t1),
1303                      fold_convert (type, t2));
1304     }
1305
1306   return fold_build2 (code, type, fold_convert (type, t1),
1307                       fold_convert (type, t2));
1308 }
1309 \f
1310 /* Combine two integer constants ARG1 and ARG2 under operation CODE
1311    to produce a new constant.
1312
1313    If NOTRUNC is nonzero, do not truncate the result to fit the data type.  */
1314
1315 tree
1316 int_const_binop (enum tree_code code, tree arg1, tree arg2, int notrunc)
1317 {
1318   unsigned HOST_WIDE_INT int1l, int2l;
1319   HOST_WIDE_INT int1h, int2h;
1320   unsigned HOST_WIDE_INT low;
1321   HOST_WIDE_INT hi;
1322   unsigned HOST_WIDE_INT garbagel;
1323   HOST_WIDE_INT garbageh;
1324   tree t;
1325   tree type = TREE_TYPE (arg1);
1326   int uns = TYPE_UNSIGNED (type);
1327   int is_sizetype
1328     = (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type));
1329   int overflow = 0;
1330
1331   int1l = TREE_INT_CST_LOW (arg1);
1332   int1h = TREE_INT_CST_HIGH (arg1);
1333   int2l = TREE_INT_CST_LOW (arg2);
1334   int2h = TREE_INT_CST_HIGH (arg2);
1335
1336   switch (code)
1337     {
1338     case BIT_IOR_EXPR:
1339       low = int1l | int2l, hi = int1h | int2h;
1340       break;
1341
1342     case BIT_XOR_EXPR:
1343       low = int1l ^ int2l, hi = int1h ^ int2h;
1344       break;
1345
1346     case BIT_AND_EXPR:
1347       low = int1l & int2l, hi = int1h & int2h;
1348       break;
1349
1350     case RSHIFT_EXPR:
1351       int2l = -int2l;
1352     case LSHIFT_EXPR:
1353       /* It's unclear from the C standard whether shifts can overflow.
1354          The following code ignores overflow; perhaps a C standard
1355          interpretation ruling is needed.  */
1356       lshift_double (int1l, int1h, int2l, TYPE_PRECISION (type),
1357                      &low, &hi, !uns);
1358       break;
1359
1360     case RROTATE_EXPR:
1361       int2l = - int2l;
1362     case LROTATE_EXPR:
1363       lrotate_double (int1l, int1h, int2l, TYPE_PRECISION (type),
1364                       &low, &hi);
1365       break;
1366
1367     case PLUS_EXPR:
1368       overflow = add_double (int1l, int1h, int2l, int2h, &low, &hi);
1369       break;
1370
1371     case MINUS_EXPR:
1372       neg_double (int2l, int2h, &low, &hi);
1373       add_double (int1l, int1h, low, hi, &low, &hi);
1374       overflow = OVERFLOW_SUM_SIGN (hi, int2h, int1h);
1375       break;
1376
1377     case MULT_EXPR:
1378       overflow = mul_double (int1l, int1h, int2l, int2h, &low, &hi);
1379       break;
1380
1381     case TRUNC_DIV_EXPR:
1382     case FLOOR_DIV_EXPR: case CEIL_DIV_EXPR:
1383     case EXACT_DIV_EXPR:
1384       /* This is a shortcut for a common special case.  */
1385       if (int2h == 0 && (HOST_WIDE_INT) int2l > 0
1386           && ! TREE_CONSTANT_OVERFLOW (arg1)
1387           && ! TREE_CONSTANT_OVERFLOW (arg2)
1388           && int1h == 0 && (HOST_WIDE_INT) int1l >= 0)
1389         {
1390           if (code == CEIL_DIV_EXPR)
1391             int1l += int2l - 1;
1392
1393           low = int1l / int2l, hi = 0;
1394           break;
1395         }
1396
1397       /* ... fall through ...  */
1398
1399     case ROUND_DIV_EXPR:
1400       if (int2h == 0 && int2l == 1)
1401         {
1402           low = int1l, hi = int1h;
1403           break;
1404         }
1405       if (int1l == int2l && int1h == int2h
1406           && ! (int1l == 0 && int1h == 0))
1407         {
1408           low = 1, hi = 0;
1409           break;
1410         }
1411       overflow = div_and_round_double (code, uns, int1l, int1h, int2l, int2h,
1412                                        &low, &hi, &garbagel, &garbageh);
1413       break;
1414
1415     case TRUNC_MOD_EXPR:
1416     case FLOOR_MOD_EXPR: case CEIL_MOD_EXPR:
1417       /* This is a shortcut for a common special case.  */
1418       if (int2h == 0 && (HOST_WIDE_INT) int2l > 0
1419           && ! TREE_CONSTANT_OVERFLOW (arg1)
1420           && ! TREE_CONSTANT_OVERFLOW (arg2)
1421           && int1h == 0 && (HOST_WIDE_INT) int1l >= 0)
1422         {
1423           if (code == CEIL_MOD_EXPR)
1424             int1l += int2l - 1;
1425           low = int1l % int2l, hi = 0;
1426           break;
1427         }
1428
1429       /* ... fall through ...  */
1430
1431     case ROUND_MOD_EXPR:
1432       overflow = div_and_round_double (code, uns,
1433                                        int1l, int1h, int2l, int2h,
1434                                        &garbagel, &garbageh, &low, &hi);
1435       break;
1436
1437     case MIN_EXPR:
1438     case MAX_EXPR:
1439       if (uns)
1440         low = (((unsigned HOST_WIDE_INT) int1h
1441                 < (unsigned HOST_WIDE_INT) int2h)
1442                || (((unsigned HOST_WIDE_INT) int1h
1443                     == (unsigned HOST_WIDE_INT) int2h)
1444                    && int1l < int2l));
1445       else
1446         low = (int1h < int2h
1447                || (int1h == int2h && int1l < int2l));
1448
1449       if (low == (code == MIN_EXPR))
1450         low = int1l, hi = int1h;
1451       else
1452         low = int2l, hi = int2h;
1453       break;
1454
1455     default:
1456       gcc_unreachable ();
1457     }
1458
1459   t = build_int_cst_wide (TREE_TYPE (arg1), low, hi);
1460
1461   if (notrunc)
1462     {
1463       /* Propagate overflow flags ourselves.  */
1464       if (((!uns || is_sizetype) && overflow)
1465           | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2))
1466         {
1467           t = copy_node (t);
1468           TREE_OVERFLOW (t) = 1;
1469           TREE_CONSTANT_OVERFLOW (t) = 1;
1470         }
1471       else if (TREE_CONSTANT_OVERFLOW (arg1) | TREE_CONSTANT_OVERFLOW (arg2))
1472         {
1473           t = copy_node (t);
1474           TREE_CONSTANT_OVERFLOW (t) = 1;
1475         }
1476     }
1477   else
1478     t = force_fit_type (t, 1,
1479                         ((!uns || is_sizetype) && overflow)
1480                         | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2),
1481                         TREE_CONSTANT_OVERFLOW (arg1)
1482                         | TREE_CONSTANT_OVERFLOW (arg2));
1483
1484   return t;
1485 }
1486
1487 /* Combine two constants ARG1 and ARG2 under operation CODE to produce a new
1488    constant.  We assume ARG1 and ARG2 have the same data type, or at least
1489    are the same kind of constant and the same machine mode.
1490
1491    If NOTRUNC is nonzero, do not truncate the result to fit the data type.  */
1492
1493 static tree
1494 const_binop (enum tree_code code, tree arg1, tree arg2, int notrunc)
1495 {
1496   STRIP_NOPS (arg1);
1497   STRIP_NOPS (arg2);
1498
1499   if (TREE_CODE (arg1) == INTEGER_CST)
1500     return int_const_binop (code, arg1, arg2, notrunc);
1501
1502   if (TREE_CODE (arg1) == REAL_CST)
1503     {
1504       enum machine_mode mode;
1505       REAL_VALUE_TYPE d1;
1506       REAL_VALUE_TYPE d2;
1507       REAL_VALUE_TYPE value;
1508       REAL_VALUE_TYPE result;
1509       bool inexact;
1510       tree t, type;
1511
1512       d1 = TREE_REAL_CST (arg1);
1513       d2 = TREE_REAL_CST (arg2);
1514
1515       type = TREE_TYPE (arg1);
1516       mode = TYPE_MODE (type);
1517
1518       /* Don't perform operation if we honor signaling NaNs and
1519          either operand is a NaN.  */
1520       if (HONOR_SNANS (mode)
1521           && (REAL_VALUE_ISNAN (d1) || REAL_VALUE_ISNAN (d2)))
1522         return NULL_TREE;
1523
1524       /* Don't perform operation if it would raise a division
1525          by zero exception.  */
1526       if (code == RDIV_EXPR
1527           && REAL_VALUES_EQUAL (d2, dconst0)
1528           && (flag_trapping_math || ! MODE_HAS_INFINITIES (mode)))
1529         return NULL_TREE;
1530
1531       /* If either operand is a NaN, just return it.  Otherwise, set up
1532          for floating-point trap; we return an overflow.  */
1533       if (REAL_VALUE_ISNAN (d1))
1534         return arg1;
1535       else if (REAL_VALUE_ISNAN (d2))
1536         return arg2;
1537
1538       inexact = real_arithmetic (&value, code, &d1, &d2);
1539       real_convert (&result, mode, &value);
1540
1541       /* Don't constant fold this floating point operation if the
1542          result may dependent upon the run-time rounding mode and
1543          flag_rounding_math is set, or if GCC's software emulation
1544          is unable to accurately represent the result.  */
1545       
1546       if ((flag_rounding_math
1547            || (REAL_MODE_FORMAT_COMPOSITE_P (mode)
1548                && !flag_unsafe_math_optimizations))
1549           && (inexact || !real_identical (&result, &value)))
1550         return NULL_TREE;
1551
1552       t = build_real (type, result);
1553
1554       TREE_OVERFLOW (t) = TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2);
1555       TREE_CONSTANT_OVERFLOW (t)
1556         = TREE_OVERFLOW (t)
1557           | TREE_CONSTANT_OVERFLOW (arg1)
1558           | TREE_CONSTANT_OVERFLOW (arg2);
1559       return t;
1560     }
1561   if (TREE_CODE (arg1) == COMPLEX_CST)
1562     {
1563       tree type = TREE_TYPE (arg1);
1564       tree r1 = TREE_REALPART (arg1);
1565       tree i1 = TREE_IMAGPART (arg1);
1566       tree r2 = TREE_REALPART (arg2);
1567       tree i2 = TREE_IMAGPART (arg2);
1568       tree t;
1569
1570       switch (code)
1571         {
1572         case PLUS_EXPR:
1573           t = build_complex (type,
1574                              const_binop (PLUS_EXPR, r1, r2, notrunc),
1575                              const_binop (PLUS_EXPR, i1, i2, notrunc));
1576           break;
1577
1578         case MINUS_EXPR:
1579           t = build_complex (type,
1580                              const_binop (MINUS_EXPR, r1, r2, notrunc),
1581                              const_binop (MINUS_EXPR, i1, i2, notrunc));
1582           break;
1583
1584         case MULT_EXPR:
1585           t = build_complex (type,
1586                              const_binop (MINUS_EXPR,
1587                                           const_binop (MULT_EXPR,
1588                                                        r1, r2, notrunc),
1589                                           const_binop (MULT_EXPR,
1590                                                        i1, i2, notrunc),
1591                                           notrunc),
1592                              const_binop (PLUS_EXPR,
1593                                           const_binop (MULT_EXPR,
1594                                                        r1, i2, notrunc),
1595                                           const_binop (MULT_EXPR,
1596                                                        i1, r2, notrunc),
1597                                           notrunc));
1598           break;
1599
1600         case RDIV_EXPR:
1601           {
1602             tree t1, t2, real, imag;
1603             tree magsquared
1604               = const_binop (PLUS_EXPR,
1605                              const_binop (MULT_EXPR, r2, r2, notrunc),
1606                              const_binop (MULT_EXPR, i2, i2, notrunc),
1607                              notrunc);
1608
1609             t1 = const_binop (PLUS_EXPR,
1610                               const_binop (MULT_EXPR, r1, r2, notrunc),
1611                               const_binop (MULT_EXPR, i1, i2, notrunc),
1612                               notrunc);
1613             t2 = const_binop (MINUS_EXPR,
1614                               const_binop (MULT_EXPR, i1, r2, notrunc),
1615                               const_binop (MULT_EXPR, r1, i2, notrunc),
1616                               notrunc);
1617
1618             if (INTEGRAL_TYPE_P (TREE_TYPE (r1)))
1619               {
1620                 real = const_binop (TRUNC_DIV_EXPR, t1, magsquared, notrunc);
1621                 imag = const_binop (TRUNC_DIV_EXPR, t2, magsquared, notrunc);
1622               }
1623             else
1624               {
1625                 real = const_binop (RDIV_EXPR, t1, magsquared, notrunc);
1626                 imag = const_binop (RDIV_EXPR, t2, magsquared, notrunc);
1627                 if (!real || !imag)
1628                   return NULL_TREE;
1629               }
1630
1631             t = build_complex (type, real, imag);
1632           }
1633           break;
1634
1635         default:
1636           gcc_unreachable ();
1637         }
1638       return t;
1639     }
1640   return 0;
1641 }
1642
1643 /* Create a size type INT_CST node with NUMBER sign extended.  KIND
1644    indicates which particular sizetype to create.  */
1645
1646 tree
1647 size_int_kind (HOST_WIDE_INT number, enum size_type_kind kind)
1648 {
1649   return build_int_cst (sizetype_tab[(int) kind], number);
1650 }
1651 \f
1652 /* Combine operands OP1 and OP2 with arithmetic operation CODE.  CODE
1653    is a tree code.  The type of the result is taken from the operands.
1654    Both must be the same type integer type and it must be a size type.
1655    If the operands are constant, so is the result.  */
1656
1657 tree
1658 size_binop (enum tree_code code, tree arg0, tree arg1)
1659 {
1660   tree type = TREE_TYPE (arg0);
1661
1662   gcc_assert (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type)
1663               && type == TREE_TYPE (arg1));
1664
1665   /* Handle the special case of two integer constants faster.  */
1666   if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
1667     {
1668       /* And some specific cases even faster than that.  */
1669       if (code == PLUS_EXPR && integer_zerop (arg0))
1670         return arg1;
1671       else if ((code == MINUS_EXPR || code == PLUS_EXPR)
1672                && integer_zerop (arg1))
1673         return arg0;
1674       else if (code == MULT_EXPR && integer_onep (arg0))
1675         return arg1;
1676
1677       /* Handle general case of two integer constants.  */
1678       return int_const_binop (code, arg0, arg1, 0);
1679     }
1680
1681   if (arg0 == error_mark_node || arg1 == error_mark_node)
1682     return error_mark_node;
1683
1684   return fold_build2 (code, type, arg0, arg1);
1685 }
1686
1687 /* Given two values, either both of sizetype or both of bitsizetype,
1688    compute the difference between the two values.  Return the value
1689    in signed type corresponding to the type of the operands.  */
1690
1691 tree
1692 size_diffop (tree arg0, tree arg1)
1693 {
1694   tree type = TREE_TYPE (arg0);
1695   tree ctype;
1696
1697   gcc_assert (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type)
1698               && type == TREE_TYPE (arg1));
1699
1700   /* If the type is already signed, just do the simple thing.  */
1701   if (!TYPE_UNSIGNED (type))
1702     return size_binop (MINUS_EXPR, arg0, arg1);
1703
1704   ctype = type == bitsizetype ? sbitsizetype : ssizetype;
1705
1706   /* If either operand is not a constant, do the conversions to the signed
1707      type and subtract.  The hardware will do the right thing with any
1708      overflow in the subtraction.  */
1709   if (TREE_CODE (arg0) != INTEGER_CST || TREE_CODE (arg1) != INTEGER_CST)
1710     return size_binop (MINUS_EXPR, fold_convert (ctype, arg0),
1711                        fold_convert (ctype, arg1));
1712
1713   /* If ARG0 is larger than ARG1, subtract and return the result in CTYPE.
1714      Otherwise, subtract the other way, convert to CTYPE (we know that can't
1715      overflow) and negate (which can't either).  Special-case a result
1716      of zero while we're here.  */
1717   if (tree_int_cst_equal (arg0, arg1))
1718     return fold_convert (ctype, integer_zero_node);
1719   else if (tree_int_cst_lt (arg1, arg0))
1720     return fold_convert (ctype, size_binop (MINUS_EXPR, arg0, arg1));
1721   else
1722     return size_binop (MINUS_EXPR, fold_convert (ctype, integer_zero_node),
1723                        fold_convert (ctype, size_binop (MINUS_EXPR,
1724                                                         arg1, arg0)));
1725 }
1726 \f
1727 /* A subroutine of fold_convert_const handling conversions of an
1728    INTEGER_CST to another integer type.  */
1729
1730 static tree
1731 fold_convert_const_int_from_int (tree type, tree arg1)
1732 {
1733   tree t;
1734
1735   /* Given an integer constant, make new constant with new type,
1736      appropriately sign-extended or truncated.  */
1737   t = build_int_cst_wide (type, TREE_INT_CST_LOW (arg1),
1738                           TREE_INT_CST_HIGH (arg1));
1739
1740   t = force_fit_type (t,
1741                       /* Don't set the overflow when
1742                          converting a pointer  */
1743                       !POINTER_TYPE_P (TREE_TYPE (arg1)),
1744                       (TREE_INT_CST_HIGH (arg1) < 0
1745                        && (TYPE_UNSIGNED (type)
1746                            < TYPE_UNSIGNED (TREE_TYPE (arg1))))
1747                       | TREE_OVERFLOW (arg1),
1748                       TREE_CONSTANT_OVERFLOW (arg1));
1749
1750   return t;
1751 }
1752
1753 /* A subroutine of fold_convert_const handling conversions a REAL_CST
1754    to an integer type.  */
1755
1756 static tree
1757 fold_convert_const_int_from_real (enum tree_code code, tree type, tree arg1)
1758 {
1759   int overflow = 0;
1760   tree t;
1761
1762   /* The following code implements the floating point to integer
1763      conversion rules required by the Java Language Specification,
1764      that IEEE NaNs are mapped to zero and values that overflow
1765      the target precision saturate, i.e. values greater than
1766      INT_MAX are mapped to INT_MAX, and values less than INT_MIN
1767      are mapped to INT_MIN.  These semantics are allowed by the
1768      C and C++ standards that simply state that the behavior of
1769      FP-to-integer conversion is unspecified upon overflow.  */
1770
1771   HOST_WIDE_INT high, low;
1772   REAL_VALUE_TYPE r;
1773   REAL_VALUE_TYPE x = TREE_REAL_CST (arg1);
1774
1775   switch (code)
1776     {
1777     case FIX_TRUNC_EXPR:
1778       real_trunc (&r, VOIDmode, &x);
1779       break;
1780
1781     case FIX_CEIL_EXPR:
1782       real_ceil (&r, VOIDmode, &x);
1783       break;
1784
1785     case FIX_FLOOR_EXPR:
1786       real_floor (&r, VOIDmode, &x);
1787       break;
1788
1789     case FIX_ROUND_EXPR:
1790       real_round (&r, VOIDmode, &x);
1791       break;
1792
1793     default:
1794       gcc_unreachable ();
1795     }
1796
1797   /* If R is NaN, return zero and show we have an overflow.  */
1798   if (REAL_VALUE_ISNAN (r))
1799     {
1800       overflow = 1;
1801       high = 0;
1802       low = 0;
1803     }
1804
1805   /* See if R is less than the lower bound or greater than the
1806      upper bound.  */
1807
1808   if (! overflow)
1809     {
1810       tree lt = TYPE_MIN_VALUE (type);
1811       REAL_VALUE_TYPE l = real_value_from_int_cst (NULL_TREE, lt);
1812       if (REAL_VALUES_LESS (r, l))
1813         {
1814           overflow = 1;
1815           high = TREE_INT_CST_HIGH (lt);
1816           low = TREE_INT_CST_LOW (lt);
1817         }
1818     }
1819
1820   if (! overflow)
1821     {
1822       tree ut = TYPE_MAX_VALUE (type);
1823       if (ut)
1824         {
1825           REAL_VALUE_TYPE u = real_value_from_int_cst (NULL_TREE, ut);
1826           if (REAL_VALUES_LESS (u, r))
1827             {
1828               overflow = 1;
1829               high = TREE_INT_CST_HIGH (ut);
1830               low = TREE_INT_CST_LOW (ut);
1831             }
1832         }
1833     }
1834
1835   if (! overflow)
1836     REAL_VALUE_TO_INT (&low, &high, r);
1837
1838   t = build_int_cst_wide (type, low, high);
1839
1840   t = force_fit_type (t, -1, overflow | TREE_OVERFLOW (arg1),
1841                       TREE_CONSTANT_OVERFLOW (arg1));
1842   return t;
1843 }
1844
1845 /* A subroutine of fold_convert_const handling conversions a REAL_CST
1846    to another floating point type.  */
1847
1848 static tree
1849 fold_convert_const_real_from_real (tree type, tree arg1)
1850 {
1851   REAL_VALUE_TYPE value;
1852   tree t;
1853
1854   real_convert (&value, TYPE_MODE (type), &TREE_REAL_CST (arg1));
1855   t = build_real (type, value);
1856
1857   TREE_OVERFLOW (t) = TREE_OVERFLOW (arg1);
1858   TREE_CONSTANT_OVERFLOW (t)
1859     = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1860   return t;
1861 }
1862
1863 /* Attempt to fold type conversion operation CODE of expression ARG1 to
1864    type TYPE.  If no simplification can be done return NULL_TREE.  */
1865
1866 static tree
1867 fold_convert_const (enum tree_code code, tree type, tree arg1)
1868 {
1869   if (TREE_TYPE (arg1) == type)
1870     return arg1;
1871
1872   if (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type))
1873     {
1874       if (TREE_CODE (arg1) == INTEGER_CST)
1875         return fold_convert_const_int_from_int (type, arg1);
1876       else if (TREE_CODE (arg1) == REAL_CST)
1877         return fold_convert_const_int_from_real (code, type, arg1);
1878     }
1879   else if (TREE_CODE (type) == REAL_TYPE)
1880     {
1881       if (TREE_CODE (arg1) == INTEGER_CST)
1882         return build_real_from_int_cst (type, arg1);
1883       if (TREE_CODE (arg1) == REAL_CST)
1884         return fold_convert_const_real_from_real (type, arg1);
1885     }
1886   return NULL_TREE;
1887 }
1888
1889 /* Construct a vector of zero elements of vector type TYPE.  */
1890
1891 static tree
1892 build_zero_vector (tree type)
1893 {
1894   tree elem, list;
1895   int i, units;
1896
1897   elem = fold_convert_const (NOP_EXPR, TREE_TYPE (type), integer_zero_node);
1898   units = TYPE_VECTOR_SUBPARTS (type);
1899   
1900   list = NULL_TREE;
1901   for (i = 0; i < units; i++)
1902     list = tree_cons (NULL_TREE, elem, list);
1903   return build_vector (type, list);
1904 }
1905
1906 /* Convert expression ARG to type TYPE.  Used by the middle-end for
1907    simple conversions in preference to calling the front-end's convert.  */
1908
1909 tree
1910 fold_convert (tree type, tree arg)
1911 {
1912   tree orig = TREE_TYPE (arg);
1913   tree tem;
1914
1915   if (type == orig)
1916     return arg;
1917
1918   if (TREE_CODE (arg) == ERROR_MARK
1919       || TREE_CODE (type) == ERROR_MARK
1920       || TREE_CODE (orig) == ERROR_MARK)
1921     return error_mark_node;
1922
1923   if (TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (orig)
1924       || lang_hooks.types_compatible_p (TYPE_MAIN_VARIANT (type),
1925                                         TYPE_MAIN_VARIANT (orig)))
1926     return fold_build1 (NOP_EXPR, type, arg);
1927
1928   switch (TREE_CODE (type))
1929     {
1930     case INTEGER_TYPE: case CHAR_TYPE: case ENUMERAL_TYPE: case BOOLEAN_TYPE:
1931     case POINTER_TYPE: case REFERENCE_TYPE:
1932     case OFFSET_TYPE:
1933       if (TREE_CODE (arg) == INTEGER_CST)
1934         {
1935           tem = fold_convert_const (NOP_EXPR, type, arg);
1936           if (tem != NULL_TREE)
1937             return tem;
1938         }
1939       if (INTEGRAL_TYPE_P (orig) || POINTER_TYPE_P (orig)
1940           || TREE_CODE (orig) == OFFSET_TYPE)
1941         return fold_build1 (NOP_EXPR, type, arg);
1942       if (TREE_CODE (orig) == COMPLEX_TYPE)
1943         {
1944           tem = fold_build1 (REALPART_EXPR, TREE_TYPE (orig), arg);
1945           return fold_convert (type, tem);
1946         }
1947       gcc_assert (TREE_CODE (orig) == VECTOR_TYPE
1948                   && tree_int_cst_equal (TYPE_SIZE (type), TYPE_SIZE (orig)));
1949       return fold_build1 (NOP_EXPR, type, arg);
1950
1951     case REAL_TYPE:
1952       if (TREE_CODE (arg) == INTEGER_CST)
1953         {
1954           tem = fold_convert_const (FLOAT_EXPR, type, arg);
1955           if (tem != NULL_TREE)
1956             return tem;
1957         }
1958       else if (TREE_CODE (arg) == REAL_CST)
1959         {
1960           tem = fold_convert_const (NOP_EXPR, type, arg);
1961           if (tem != NULL_TREE)
1962             return tem;
1963         }
1964
1965       switch (TREE_CODE (orig))
1966         {
1967         case INTEGER_TYPE: case CHAR_TYPE:
1968         case BOOLEAN_TYPE: case ENUMERAL_TYPE:
1969         case POINTER_TYPE: case REFERENCE_TYPE:
1970           return fold_build1 (FLOAT_EXPR, type, arg);
1971
1972         case REAL_TYPE:
1973           return fold_build1 (flag_float_store ? CONVERT_EXPR : NOP_EXPR,
1974                               type, arg);
1975
1976         case COMPLEX_TYPE:
1977           tem = fold_build1 (REALPART_EXPR, TREE_TYPE (orig), arg);
1978           return fold_convert (type, tem);
1979
1980         default:
1981           gcc_unreachable ();
1982         }
1983
1984     case COMPLEX_TYPE:
1985       switch (TREE_CODE (orig))
1986         {
1987         case INTEGER_TYPE: case CHAR_TYPE:
1988         case BOOLEAN_TYPE: case ENUMERAL_TYPE:
1989         case POINTER_TYPE: case REFERENCE_TYPE:
1990         case REAL_TYPE:
1991           return build2 (COMPLEX_EXPR, type,
1992                          fold_convert (TREE_TYPE (type), arg),
1993                          fold_convert (TREE_TYPE (type), integer_zero_node));
1994         case COMPLEX_TYPE:
1995           {
1996             tree rpart, ipart;
1997
1998             if (TREE_CODE (arg) == COMPLEX_EXPR)
1999               {
2000                 rpart = fold_convert (TREE_TYPE (type), TREE_OPERAND (arg, 0));
2001                 ipart = fold_convert (TREE_TYPE (type), TREE_OPERAND (arg, 1));
2002                 return fold_build2 (COMPLEX_EXPR, type, rpart, ipart);
2003               }
2004
2005             arg = save_expr (arg);
2006             rpart = fold_build1 (REALPART_EXPR, TREE_TYPE (orig), arg);
2007             ipart = fold_build1 (IMAGPART_EXPR, TREE_TYPE (orig), arg);
2008             rpart = fold_convert (TREE_TYPE (type), rpart);
2009             ipart = fold_convert (TREE_TYPE (type), ipart);
2010             return fold_build2 (COMPLEX_EXPR, type, rpart, ipart);
2011           }
2012
2013         default:
2014           gcc_unreachable ();
2015         }
2016
2017     case VECTOR_TYPE:
2018       if (integer_zerop (arg))
2019         return build_zero_vector (type);
2020       gcc_assert (tree_int_cst_equal (TYPE_SIZE (type), TYPE_SIZE (orig)));
2021       gcc_assert (INTEGRAL_TYPE_P (orig) || POINTER_TYPE_P (orig)
2022                   || TREE_CODE (orig) == VECTOR_TYPE);
2023       return fold_build1 (NOP_EXPR, type, arg);
2024
2025     case VOID_TYPE:
2026       return fold_build1 (CONVERT_EXPR, type, fold_ignored_result (arg));
2027
2028     default:
2029       gcc_unreachable ();
2030     }
2031 }
2032 \f
2033 /* Return false if expr can be assumed not to be an value, true
2034    otherwise.  */
2035
2036 static bool
2037 maybe_lvalue_p (tree x)
2038 {
2039   /* We only need to wrap lvalue tree codes.  */
2040   switch (TREE_CODE (x))
2041   {
2042   case VAR_DECL:
2043   case PARM_DECL:
2044   case RESULT_DECL:
2045   case LABEL_DECL:
2046   case FUNCTION_DECL:
2047   case SSA_NAME:
2048
2049   case COMPONENT_REF:
2050   case INDIRECT_REF:
2051   case ALIGN_INDIRECT_REF:
2052   case MISALIGNED_INDIRECT_REF:
2053   case ARRAY_REF:
2054   case ARRAY_RANGE_REF:
2055   case BIT_FIELD_REF:
2056   case OBJ_TYPE_REF:
2057
2058   case REALPART_EXPR:
2059   case IMAGPART_EXPR:
2060   case PREINCREMENT_EXPR:
2061   case PREDECREMENT_EXPR:
2062   case SAVE_EXPR:
2063   case TRY_CATCH_EXPR:
2064   case WITH_CLEANUP_EXPR:
2065   case COMPOUND_EXPR:
2066   case MODIFY_EXPR:
2067   case TARGET_EXPR:
2068   case COND_EXPR:
2069   case BIND_EXPR:
2070   case MIN_EXPR:
2071   case MAX_EXPR:
2072     break;
2073
2074   default:
2075     /* Assume the worst for front-end tree codes.  */
2076     if ((int)TREE_CODE (x) >= NUM_TREE_CODES)
2077       break;
2078     return false;
2079   }
2080
2081   return true;
2082 }
2083
2084 /* Return an expr equal to X but certainly not valid as an lvalue.  */
2085
2086 tree
2087 non_lvalue (tree x)
2088 {
2089   /* While we are in GIMPLE, NON_LVALUE_EXPR doesn't mean anything to
2090      us.  */
2091   if (in_gimple_form)
2092     return x;
2093
2094   if (! maybe_lvalue_p (x))
2095     return x;
2096   return build1 (NON_LVALUE_EXPR, TREE_TYPE (x), x);
2097 }
2098
2099 /* Nonzero means lvalues are limited to those valid in pedantic ANSI C.
2100    Zero means allow extended lvalues.  */
2101
2102 int pedantic_lvalues;
2103
2104 /* When pedantic, return an expr equal to X but certainly not valid as a
2105    pedantic lvalue.  Otherwise, return X.  */
2106
2107 static tree
2108 pedantic_non_lvalue (tree x)
2109 {
2110   if (pedantic_lvalues)
2111     return non_lvalue (x);
2112   else
2113     return x;
2114 }
2115 \f
2116 /* Given a tree comparison code, return the code that is the logical inverse
2117    of the given code.  It is not safe to do this for floating-point
2118    comparisons, except for NE_EXPR and EQ_EXPR, so we receive a machine mode
2119    as well: if reversing the comparison is unsafe, return ERROR_MARK.  */
2120
2121 enum tree_code
2122 invert_tree_comparison (enum tree_code code, bool honor_nans)
2123 {
2124   if (honor_nans && flag_trapping_math)
2125     return ERROR_MARK;
2126
2127   switch (code)
2128     {
2129     case EQ_EXPR:
2130       return NE_EXPR;
2131     case NE_EXPR:
2132       return EQ_EXPR;
2133     case GT_EXPR:
2134       return honor_nans ? UNLE_EXPR : LE_EXPR;
2135     case GE_EXPR:
2136       return honor_nans ? UNLT_EXPR : LT_EXPR;
2137     case LT_EXPR:
2138       return honor_nans ? UNGE_EXPR : GE_EXPR;
2139     case LE_EXPR:
2140       return honor_nans ? UNGT_EXPR : GT_EXPR;
2141     case LTGT_EXPR:
2142       return UNEQ_EXPR;
2143     case UNEQ_EXPR:
2144       return LTGT_EXPR;
2145     case UNGT_EXPR:
2146       return LE_EXPR;
2147     case UNGE_EXPR:
2148       return LT_EXPR;
2149     case UNLT_EXPR:
2150       return GE_EXPR;
2151     case UNLE_EXPR:
2152       return GT_EXPR;
2153     case ORDERED_EXPR:
2154       return UNORDERED_EXPR;
2155     case UNORDERED_EXPR:
2156       return ORDERED_EXPR;
2157     default:
2158       gcc_unreachable ();
2159     }
2160 }
2161
2162 /* Similar, but return the comparison that results if the operands are
2163    swapped.  This is safe for floating-point.  */
2164
2165 enum tree_code
2166 swap_tree_comparison (enum tree_code code)
2167 {
2168   switch (code)
2169     {
2170     case EQ_EXPR:
2171     case NE_EXPR:
2172     case ORDERED_EXPR:
2173     case UNORDERED_EXPR:
2174     case LTGT_EXPR:
2175     case UNEQ_EXPR:
2176       return code;
2177     case GT_EXPR:
2178       return LT_EXPR;
2179     case GE_EXPR:
2180       return LE_EXPR;
2181     case LT_EXPR:
2182       return GT_EXPR;
2183     case LE_EXPR:
2184       return GE_EXPR;
2185     case UNGT_EXPR:
2186       return UNLT_EXPR;
2187     case UNGE_EXPR:
2188       return UNLE_EXPR;
2189     case UNLT_EXPR:
2190       return UNGT_EXPR;
2191     case UNLE_EXPR:
2192       return UNGE_EXPR;
2193     default:
2194       gcc_unreachable ();
2195     }
2196 }
2197
2198
2199 /* Convert a comparison tree code from an enum tree_code representation
2200    into a compcode bit-based encoding.  This function is the inverse of
2201    compcode_to_comparison.  */
2202
2203 static enum comparison_code
2204 comparison_to_compcode (enum tree_code code)
2205 {
2206   switch (code)
2207     {
2208     case LT_EXPR:
2209       return COMPCODE_LT;
2210     case EQ_EXPR:
2211       return COMPCODE_EQ;
2212     case LE_EXPR:
2213       return COMPCODE_LE;
2214     case GT_EXPR:
2215       return COMPCODE_GT;
2216     case NE_EXPR:
2217       return COMPCODE_NE;
2218     case GE_EXPR:
2219       return COMPCODE_GE;
2220     case ORDERED_EXPR:
2221       return COMPCODE_ORD;
2222     case UNORDERED_EXPR:
2223       return COMPCODE_UNORD;
2224     case UNLT_EXPR:
2225       return COMPCODE_UNLT;
2226     case UNEQ_EXPR:
2227       return COMPCODE_UNEQ;
2228     case UNLE_EXPR:
2229       return COMPCODE_UNLE;
2230     case UNGT_EXPR:
2231       return COMPCODE_UNGT;
2232     case LTGT_EXPR:
2233       return COMPCODE_LTGT;
2234     case UNGE_EXPR:
2235       return COMPCODE_UNGE;
2236     default:
2237       gcc_unreachable ();
2238     }
2239 }
2240
2241 /* Convert a compcode bit-based encoding of a comparison operator back
2242    to GCC's enum tree_code representation.  This function is the
2243    inverse of comparison_to_compcode.  */
2244
2245 static enum tree_code
2246 compcode_to_comparison (enum comparison_code code)
2247 {
2248   switch (code)
2249     {
2250     case COMPCODE_LT:
2251       return LT_EXPR;
2252     case COMPCODE_EQ:
2253       return EQ_EXPR;
2254     case COMPCODE_LE:
2255       return LE_EXPR;
2256     case COMPCODE_GT:
2257       return GT_EXPR;
2258     case COMPCODE_NE:
2259       return NE_EXPR;
2260     case COMPCODE_GE:
2261       return GE_EXPR;
2262     case COMPCODE_ORD:
2263       return ORDERED_EXPR;
2264     case COMPCODE_UNORD:
2265       return UNORDERED_EXPR;
2266     case COMPCODE_UNLT:
2267       return UNLT_EXPR;
2268     case COMPCODE_UNEQ:
2269       return UNEQ_EXPR;
2270     case COMPCODE_UNLE:
2271       return UNLE_EXPR;
2272     case COMPCODE_UNGT:
2273       return UNGT_EXPR;
2274     case COMPCODE_LTGT:
2275       return LTGT_EXPR;
2276     case COMPCODE_UNGE:
2277       return UNGE_EXPR;
2278     default:
2279       gcc_unreachable ();
2280     }
2281 }
2282
2283 /* Return a tree for the comparison which is the combination of
2284    doing the AND or OR (depending on CODE) of the two operations LCODE
2285    and RCODE on the identical operands LL_ARG and LR_ARG.  Take into account
2286    the possibility of trapping if the mode has NaNs, and return NULL_TREE
2287    if this makes the transformation invalid.  */
2288
2289 tree
2290 combine_comparisons (enum tree_code code, enum tree_code lcode,
2291                      enum tree_code rcode, tree truth_type,
2292                      tree ll_arg, tree lr_arg)
2293 {
2294   bool honor_nans = HONOR_NANS (TYPE_MODE (TREE_TYPE (ll_arg)));
2295   enum comparison_code lcompcode = comparison_to_compcode (lcode);
2296   enum comparison_code rcompcode = comparison_to_compcode (rcode);
2297   enum comparison_code compcode;
2298
2299   switch (code)
2300     {
2301     case TRUTH_AND_EXPR: case TRUTH_ANDIF_EXPR:
2302       compcode = lcompcode & rcompcode;
2303       break;
2304
2305     case TRUTH_OR_EXPR: case TRUTH_ORIF_EXPR:
2306       compcode = lcompcode | rcompcode;
2307       break;
2308
2309     default:
2310       return NULL_TREE;
2311     }
2312
2313   if (!honor_nans)
2314     {
2315       /* Eliminate unordered comparisons, as well as LTGT and ORD
2316          which are not used unless the mode has NaNs.  */
2317       compcode &= ~COMPCODE_UNORD;
2318       if (compcode == COMPCODE_LTGT)
2319         compcode = COMPCODE_NE;
2320       else if (compcode == COMPCODE_ORD)
2321         compcode = COMPCODE_TRUE;
2322     }
2323    else if (flag_trapping_math)
2324      {
2325         /* Check that the original operation and the optimized ones will trap
2326            under the same condition.  */
2327         bool ltrap = (lcompcode & COMPCODE_UNORD) == 0
2328                      && (lcompcode != COMPCODE_EQ)
2329                      && (lcompcode != COMPCODE_ORD);
2330         bool rtrap = (rcompcode & COMPCODE_UNORD) == 0
2331                      && (rcompcode != COMPCODE_EQ)
2332                      && (rcompcode != COMPCODE_ORD);
2333         bool trap = (compcode & COMPCODE_UNORD) == 0
2334                     && (compcode != COMPCODE_EQ)
2335                     && (compcode != COMPCODE_ORD);
2336
2337         /* In a short-circuited boolean expression the LHS might be
2338            such that the RHS, if evaluated, will never trap.  For
2339            example, in ORD (x, y) && (x < y), we evaluate the RHS only
2340            if neither x nor y is NaN.  (This is a mixed blessing: for
2341            example, the expression above will never trap, hence
2342            optimizing it to x < y would be invalid).  */
2343         if ((code == TRUTH_ORIF_EXPR && (lcompcode & COMPCODE_UNORD))
2344             || (code == TRUTH_ANDIF_EXPR && !(lcompcode & COMPCODE_UNORD)))
2345           rtrap = false;
2346
2347         /* If the comparison was short-circuited, and only the RHS
2348            trapped, we may now generate a spurious trap.  */
2349         if (rtrap && !ltrap
2350             && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
2351           return NULL_TREE;
2352
2353         /* If we changed the conditions that cause a trap, we lose.  */
2354         if ((ltrap || rtrap) != trap)
2355           return NULL_TREE;
2356       }
2357
2358   if (compcode == COMPCODE_TRUE)
2359     return constant_boolean_node (true, truth_type);
2360   else if (compcode == COMPCODE_FALSE)
2361     return constant_boolean_node (false, truth_type);
2362   else
2363     return fold_build2 (compcode_to_comparison (compcode),
2364                         truth_type, ll_arg, lr_arg);
2365 }
2366
2367 /* Return nonzero if CODE is a tree code that represents a truth value.  */
2368
2369 static int
2370 truth_value_p (enum tree_code code)
2371 {
2372   return (TREE_CODE_CLASS (code) == tcc_comparison
2373           || code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR
2374           || code == TRUTH_OR_EXPR || code == TRUTH_ORIF_EXPR
2375           || code == TRUTH_XOR_EXPR || code == TRUTH_NOT_EXPR);
2376 }
2377 \f
2378 /* Return nonzero if two operands (typically of the same tree node)
2379    are necessarily equal.  If either argument has side-effects this
2380    function returns zero.  FLAGS modifies behavior as follows:
2381
2382    If OEP_ONLY_CONST is set, only return nonzero for constants.
2383    This function tests whether the operands are indistinguishable;
2384    it does not test whether they are equal using C's == operation.
2385    The distinction is important for IEEE floating point, because
2386    (1) -0.0 and 0.0 are distinguishable, but -0.0==0.0, and
2387    (2) two NaNs may be indistinguishable, but NaN!=NaN.
2388
2389    If OEP_ONLY_CONST is unset, a VAR_DECL is considered equal to itself
2390    even though it may hold multiple values during a function.
2391    This is because a GCC tree node guarantees that nothing else is
2392    executed between the evaluation of its "operands" (which may often
2393    be evaluated in arbitrary order).  Hence if the operands themselves
2394    don't side-effect, the VAR_DECLs, PARM_DECLs etc... must hold the
2395    same value in each operand/subexpression.  Hence leaving OEP_ONLY_CONST
2396    unset means assuming isochronic (or instantaneous) tree equivalence.
2397    Unless comparing arbitrary expression trees, such as from different
2398    statements, this flag can usually be left unset.
2399
2400    If OEP_PURE_SAME is set, then pure functions with identical arguments
2401    are considered the same.  It is used when the caller has other ways
2402    to ensure that global memory is unchanged in between.  */
2403
2404 int
2405 operand_equal_p (tree arg0, tree arg1, unsigned int flags)
2406 {
2407   /* If either is ERROR_MARK, they aren't equal.  */
2408   if (TREE_CODE (arg0) == ERROR_MARK || TREE_CODE (arg1) == ERROR_MARK)
2409     return 0;
2410
2411   /* If both types don't have the same signedness, then we can't consider
2412      them equal.  We must check this before the STRIP_NOPS calls
2413      because they may change the signedness of the arguments.  */
2414   if (TYPE_UNSIGNED (TREE_TYPE (arg0)) != TYPE_UNSIGNED (TREE_TYPE (arg1)))
2415     return 0;
2416
2417   STRIP_NOPS (arg0);
2418   STRIP_NOPS (arg1);
2419
2420   if (TREE_CODE (arg0) != TREE_CODE (arg1)
2421       /* This is needed for conversions and for COMPONENT_REF.
2422          Might as well play it safe and always test this.  */
2423       || TREE_CODE (TREE_TYPE (arg0)) == ERROR_MARK
2424       || TREE_CODE (TREE_TYPE (arg1)) == ERROR_MARK
2425       || TYPE_MODE (TREE_TYPE (arg0)) != TYPE_MODE (TREE_TYPE (arg1)))
2426     return 0;
2427
2428   /* If ARG0 and ARG1 are the same SAVE_EXPR, they are necessarily equal.
2429      We don't care about side effects in that case because the SAVE_EXPR
2430      takes care of that for us. In all other cases, two expressions are
2431      equal if they have no side effects.  If we have two identical
2432      expressions with side effects that should be treated the same due
2433      to the only side effects being identical SAVE_EXPR's, that will
2434      be detected in the recursive calls below.  */
2435   if (arg0 == arg1 && ! (flags & OEP_ONLY_CONST)
2436       && (TREE_CODE (arg0) == SAVE_EXPR
2437           || (! TREE_SIDE_EFFECTS (arg0) && ! TREE_SIDE_EFFECTS (arg1))))
2438     return 1;
2439
2440   /* Next handle constant cases, those for which we can return 1 even
2441      if ONLY_CONST is set.  */
2442   if (TREE_CONSTANT (arg0) && TREE_CONSTANT (arg1))
2443     switch (TREE_CODE (arg0))
2444       {
2445       case INTEGER_CST:
2446         return (! TREE_CONSTANT_OVERFLOW (arg0)
2447                 && ! TREE_CONSTANT_OVERFLOW (arg1)
2448                 && tree_int_cst_equal (arg0, arg1));
2449
2450       case REAL_CST:
2451         return (! TREE_CONSTANT_OVERFLOW (arg0)
2452                 && ! TREE_CONSTANT_OVERFLOW (arg1)
2453                 && REAL_VALUES_IDENTICAL (TREE_REAL_CST (arg0),
2454                                           TREE_REAL_CST (arg1)));
2455
2456       case VECTOR_CST:
2457         {
2458           tree v1, v2;
2459
2460           if (TREE_CONSTANT_OVERFLOW (arg0)
2461               || TREE_CONSTANT_OVERFLOW (arg1))
2462             return 0;
2463
2464           v1 = TREE_VECTOR_CST_ELTS (arg0);
2465           v2 = TREE_VECTOR_CST_ELTS (arg1);
2466           while (v1 && v2)
2467             {
2468               if (!operand_equal_p (TREE_VALUE (v1), TREE_VALUE (v2),
2469                                     flags))
2470                 return 0;
2471               v1 = TREE_CHAIN (v1);
2472               v2 = TREE_CHAIN (v2);
2473             }
2474
2475           return v1 == v2;
2476         }
2477
2478       case COMPLEX_CST:
2479         return (operand_equal_p (TREE_REALPART (arg0), TREE_REALPART (arg1),
2480                                  flags)
2481                 && operand_equal_p (TREE_IMAGPART (arg0), TREE_IMAGPART (arg1),
2482                                     flags));
2483
2484       case STRING_CST:
2485         return (TREE_STRING_LENGTH (arg0) == TREE_STRING_LENGTH (arg1)
2486                 && ! memcmp (TREE_STRING_POINTER (arg0),
2487                               TREE_STRING_POINTER (arg1),
2488                               TREE_STRING_LENGTH (arg0)));
2489
2490       case ADDR_EXPR:
2491         return operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0),
2492                                 0);
2493       default:
2494         break;
2495       }
2496
2497   if (flags & OEP_ONLY_CONST)
2498     return 0;
2499
2500 /* Define macros to test an operand from arg0 and arg1 for equality and a
2501    variant that allows null and views null as being different from any
2502    non-null value.  In the latter case, if either is null, the both
2503    must be; otherwise, do the normal comparison.  */
2504 #define OP_SAME(N) operand_equal_p (TREE_OPERAND (arg0, N),     \
2505                                     TREE_OPERAND (arg1, N), flags)
2506
2507 #define OP_SAME_WITH_NULL(N)                            \
2508   ((!TREE_OPERAND (arg0, N) || !TREE_OPERAND (arg1, N)) \
2509    ? TREE_OPERAND (arg0, N) == TREE_OPERAND (arg1, N) : OP_SAME (N))
2510
2511   switch (TREE_CODE_CLASS (TREE_CODE (arg0)))
2512     {
2513     case tcc_unary:
2514       /* Two conversions are equal only if signedness and modes match.  */
2515       switch (TREE_CODE (arg0))
2516         {
2517         case NOP_EXPR:
2518         case CONVERT_EXPR:
2519         case FIX_CEIL_EXPR:
2520         case FIX_TRUNC_EXPR:
2521         case FIX_FLOOR_EXPR:
2522         case FIX_ROUND_EXPR:
2523           if (TYPE_UNSIGNED (TREE_TYPE (arg0))
2524               != TYPE_UNSIGNED (TREE_TYPE (arg1)))
2525             return 0;
2526           break;
2527         default:
2528           break;
2529         }
2530
2531       return OP_SAME (0);
2532
2533
2534     case tcc_comparison:
2535     case tcc_binary:
2536       if (OP_SAME (0) && OP_SAME (1))
2537         return 1;
2538
2539       /* For commutative ops, allow the other order.  */
2540       return (commutative_tree_code (TREE_CODE (arg0))
2541               && operand_equal_p (TREE_OPERAND (arg0, 0),
2542                                   TREE_OPERAND (arg1, 1), flags)
2543               && operand_equal_p (TREE_OPERAND (arg0, 1),
2544                                   TREE_OPERAND (arg1, 0), flags));
2545
2546     case tcc_reference:
2547       /* If either of the pointer (or reference) expressions we are
2548          dereferencing contain a side effect, these cannot be equal.  */
2549       if (TREE_SIDE_EFFECTS (arg0)
2550           || TREE_SIDE_EFFECTS (arg1))
2551         return 0;
2552
2553       switch (TREE_CODE (arg0))
2554         {
2555         case INDIRECT_REF:
2556         case ALIGN_INDIRECT_REF:
2557         case MISALIGNED_INDIRECT_REF:
2558         case REALPART_EXPR:
2559         case IMAGPART_EXPR:
2560           return OP_SAME (0);
2561
2562         case ARRAY_REF:
2563         case ARRAY_RANGE_REF:
2564           /* Operands 2 and 3 may be null.  */
2565           return (OP_SAME (0)
2566                   && OP_SAME (1)
2567                   && OP_SAME_WITH_NULL (2)
2568                   && OP_SAME_WITH_NULL (3));
2569
2570         case COMPONENT_REF:
2571           /* Handle operand 2 the same as for ARRAY_REF.  */
2572           return OP_SAME (0) && OP_SAME (1) && OP_SAME_WITH_NULL (2);
2573
2574         case BIT_FIELD_REF:
2575           return OP_SAME (0) && OP_SAME (1) && OP_SAME (2);
2576
2577         default:
2578           return 0;
2579         }
2580
2581     case tcc_expression:
2582       switch (TREE_CODE (arg0))
2583         {
2584         case ADDR_EXPR:
2585         case TRUTH_NOT_EXPR:
2586           return OP_SAME (0);
2587
2588         case TRUTH_ANDIF_EXPR:
2589         case TRUTH_ORIF_EXPR:
2590           return OP_SAME (0) && OP_SAME (1);
2591
2592         case TRUTH_AND_EXPR:
2593         case TRUTH_OR_EXPR:
2594         case TRUTH_XOR_EXPR:
2595           if (OP_SAME (0) && OP_SAME (1))
2596             return 1;
2597
2598           /* Otherwise take into account this is a commutative operation.  */
2599           return (operand_equal_p (TREE_OPERAND (arg0, 0),
2600                                    TREE_OPERAND (arg1, 1), flags)
2601                   && operand_equal_p (TREE_OPERAND (arg0, 1),
2602                                       TREE_OPERAND (arg1, 0), flags));
2603
2604         case CALL_EXPR:
2605           /* If the CALL_EXPRs call different functions, then they
2606              clearly can not be equal.  */
2607           if (!OP_SAME (0))
2608             return 0;
2609
2610           {
2611             unsigned int cef = call_expr_flags (arg0);
2612             if (flags & OEP_PURE_SAME)
2613               cef &= ECF_CONST | ECF_PURE;
2614             else
2615               cef &= ECF_CONST;
2616             if (!cef)
2617               return 0;
2618           }
2619
2620           /* Now see if all the arguments are the same.  operand_equal_p
2621              does not handle TREE_LIST, so we walk the operands here
2622              feeding them to operand_equal_p.  */
2623           arg0 = TREE_OPERAND (arg0, 1);
2624           arg1 = TREE_OPERAND (arg1, 1);
2625           while (arg0 && arg1)
2626             {
2627               if (! operand_equal_p (TREE_VALUE (arg0), TREE_VALUE (arg1),
2628                                      flags))
2629                 return 0;
2630
2631               arg0 = TREE_CHAIN (arg0);
2632               arg1 = TREE_CHAIN (arg1);
2633             }
2634
2635           /* If we get here and both argument lists are exhausted
2636              then the CALL_EXPRs are equal.  */
2637           return ! (arg0 || arg1);
2638
2639         default:
2640           return 0;
2641         }
2642
2643     case tcc_declaration:
2644       /* Consider __builtin_sqrt equal to sqrt.  */
2645       return (TREE_CODE (arg0) == FUNCTION_DECL
2646               && DECL_BUILT_IN (arg0) && DECL_BUILT_IN (arg1)
2647               && DECL_BUILT_IN_CLASS (arg0) == DECL_BUILT_IN_CLASS (arg1)
2648               && DECL_FUNCTION_CODE (arg0) == DECL_FUNCTION_CODE (arg1));
2649
2650     default:
2651       return 0;
2652     }
2653
2654 #undef OP_SAME
2655 #undef OP_SAME_WITH_NULL
2656 }
2657 \f
2658 /* Similar to operand_equal_p, but see if ARG0 might have been made by
2659    shorten_compare from ARG1 when ARG1 was being compared with OTHER.
2660
2661    When in doubt, return 0.  */
2662
2663 static int
2664 operand_equal_for_comparison_p (tree arg0, tree arg1, tree other)
2665 {
2666   int unsignedp1, unsignedpo;
2667   tree primarg0, primarg1, primother;
2668   unsigned int correct_width;
2669
2670   if (operand_equal_p (arg0, arg1, 0))
2671     return 1;
2672
2673   if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0))
2674       || ! INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
2675     return 0;
2676
2677   /* Discard any conversions that don't change the modes of ARG0 and ARG1
2678      and see if the inner values are the same.  This removes any
2679      signedness comparison, which doesn't matter here.  */
2680   primarg0 = arg0, primarg1 = arg1;
2681   STRIP_NOPS (primarg0);
2682   STRIP_NOPS (primarg1);
2683   if (operand_equal_p (primarg0, primarg1, 0))
2684     return 1;
2685
2686   /* Duplicate what shorten_compare does to ARG1 and see if that gives the
2687      actual comparison operand, ARG0.
2688
2689      First throw away any conversions to wider types
2690      already present in the operands.  */
2691
2692   primarg1 = get_narrower (arg1, &unsignedp1);
2693   primother = get_narrower (other, &unsignedpo);
2694
2695   correct_width = TYPE_PRECISION (TREE_TYPE (arg1));
2696   if (unsignedp1 == unsignedpo
2697       && TYPE_PRECISION (TREE_TYPE (primarg1)) < correct_width
2698       && TYPE_PRECISION (TREE_TYPE (primother)) < correct_width)
2699     {
2700       tree type = TREE_TYPE (arg0);
2701
2702       /* Make sure shorter operand is extended the right way
2703          to match the longer operand.  */
2704       primarg1 = fold_convert (lang_hooks.types.signed_or_unsigned_type
2705                                (unsignedp1, TREE_TYPE (primarg1)), primarg1);
2706
2707       if (operand_equal_p (arg0, fold_convert (type, primarg1), 0))
2708         return 1;
2709     }
2710
2711   return 0;
2712 }
2713 \f
2714 /* See if ARG is an expression that is either a comparison or is performing
2715    arithmetic on comparisons.  The comparisons must only be comparing
2716    two different values, which will be stored in *CVAL1 and *CVAL2; if
2717    they are nonzero it means that some operands have already been found.
2718    No variables may be used anywhere else in the expression except in the
2719    comparisons.  If SAVE_P is true it means we removed a SAVE_EXPR around
2720    the expression and save_expr needs to be called with CVAL1 and CVAL2.
2721
2722    If this is true, return 1.  Otherwise, return zero.  */
2723
2724 static int
2725 twoval_comparison_p (tree arg, tree *cval1, tree *cval2, int *save_p)
2726 {
2727   enum tree_code code = TREE_CODE (arg);
2728   enum tree_code_class class = TREE_CODE_CLASS (code);
2729
2730   /* We can handle some of the tcc_expression cases here.  */
2731   if (class == tcc_expression && code == TRUTH_NOT_EXPR)
2732     class = tcc_unary;
2733   else if (class == tcc_expression
2734            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR
2735                || code == COMPOUND_EXPR))
2736     class = tcc_binary;
2737
2738   else if (class == tcc_expression && code == SAVE_EXPR
2739            && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg, 0)))
2740     {
2741       /* If we've already found a CVAL1 or CVAL2, this expression is
2742          two complex to handle.  */
2743       if (*cval1 || *cval2)
2744         return 0;
2745
2746       class = tcc_unary;
2747       *save_p = 1;
2748     }
2749
2750   switch (class)
2751     {
2752     case tcc_unary:
2753       return twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p);
2754
2755     case tcc_binary:
2756       return (twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p)
2757               && twoval_comparison_p (TREE_OPERAND (arg, 1),
2758                                       cval1, cval2, save_p));
2759
2760     case tcc_constant:
2761       return 1;
2762
2763     case tcc_expression:
2764       if (code == COND_EXPR)
2765         return (twoval_comparison_p (TREE_OPERAND (arg, 0),
2766                                      cval1, cval2, save_p)
2767                 && twoval_comparison_p (TREE_OPERAND (arg, 1),
2768                                         cval1, cval2, save_p)
2769                 && twoval_comparison_p (TREE_OPERAND (arg, 2),
2770                                         cval1, cval2, save_p));
2771       return 0;
2772
2773     case tcc_comparison:
2774       /* First see if we can handle the first operand, then the second.  For
2775          the second operand, we know *CVAL1 can't be zero.  It must be that
2776          one side of the comparison is each of the values; test for the
2777          case where this isn't true by failing if the two operands
2778          are the same.  */
2779
2780       if (operand_equal_p (TREE_OPERAND (arg, 0),
2781                            TREE_OPERAND (arg, 1), 0))
2782         return 0;
2783
2784       if (*cval1 == 0)
2785         *cval1 = TREE_OPERAND (arg, 0);
2786       else if (operand_equal_p (*cval1, TREE_OPERAND (arg, 0), 0))
2787         ;
2788       else if (*cval2 == 0)
2789         *cval2 = TREE_OPERAND (arg, 0);
2790       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 0), 0))
2791         ;
2792       else
2793         return 0;
2794
2795       if (operand_equal_p (*cval1, TREE_OPERAND (arg, 1), 0))
2796         ;
2797       else if (*cval2 == 0)
2798         *cval2 = TREE_OPERAND (arg, 1);
2799       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 1), 0))
2800         ;
2801       else
2802         return 0;
2803
2804       return 1;
2805
2806     default:
2807       return 0;
2808     }
2809 }
2810 \f
2811 /* ARG is a tree that is known to contain just arithmetic operations and
2812    comparisons.  Evaluate the operations in the tree substituting NEW0 for
2813    any occurrence of OLD0 as an operand of a comparison and likewise for
2814    NEW1 and OLD1.  */
2815
2816 static tree
2817 eval_subst (tree arg, tree old0, tree new0, tree old1, tree new1)
2818 {
2819   tree type = TREE_TYPE (arg);
2820   enum tree_code code = TREE_CODE (arg);
2821   enum tree_code_class class = TREE_CODE_CLASS (code);
2822
2823   /* We can handle some of the tcc_expression cases here.  */
2824   if (class == tcc_expression && code == TRUTH_NOT_EXPR)
2825     class = tcc_unary;
2826   else if (class == tcc_expression
2827            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
2828     class = tcc_binary;
2829
2830   switch (class)
2831     {
2832     case tcc_unary:
2833       return fold_build1 (code, type,
2834                           eval_subst (TREE_OPERAND (arg, 0),
2835                                       old0, new0, old1, new1));
2836
2837     case tcc_binary:
2838       return fold_build2 (code, type,
2839                           eval_subst (TREE_OPERAND (arg, 0),
2840                                       old0, new0, old1, new1),
2841                           eval_subst (TREE_OPERAND (arg, 1),
2842                                       old0, new0, old1, new1));
2843
2844     case tcc_expression:
2845       switch (code)
2846         {
2847         case SAVE_EXPR:
2848           return eval_subst (TREE_OPERAND (arg, 0), old0, new0, old1, new1);
2849
2850         case COMPOUND_EXPR:
2851           return eval_subst (TREE_OPERAND (arg, 1), old0, new0, old1, new1);
2852
2853         case COND_EXPR:
2854           return fold_build3 (code, type,
2855                               eval_subst (TREE_OPERAND (arg, 0),
2856                                           old0, new0, old1, new1),
2857                               eval_subst (TREE_OPERAND (arg, 1),
2858                                           old0, new0, old1, new1),
2859                               eval_subst (TREE_OPERAND (arg, 2),
2860                                           old0, new0, old1, new1));
2861         default:
2862           break;
2863         }
2864       /* Fall through - ???  */
2865
2866     case tcc_comparison:
2867       {
2868         tree arg0 = TREE_OPERAND (arg, 0);
2869         tree arg1 = TREE_OPERAND (arg, 1);
2870
2871         /* We need to check both for exact equality and tree equality.  The
2872            former will be true if the operand has a side-effect.  In that
2873            case, we know the operand occurred exactly once.  */
2874
2875         if (arg0 == old0 || operand_equal_p (arg0, old0, 0))
2876           arg0 = new0;
2877         else if (arg0 == old1 || operand_equal_p (arg0, old1, 0))
2878           arg0 = new1;
2879
2880         if (arg1 == old0 || operand_equal_p (arg1, old0, 0))
2881           arg1 = new0;
2882         else if (arg1 == old1 || operand_equal_p (arg1, old1, 0))
2883           arg1 = new1;
2884
2885         return fold_build2 (code, type, arg0, arg1);
2886       }
2887
2888     default:
2889       return arg;
2890     }
2891 }
2892 \f
2893 /* Return a tree for the case when the result of an expression is RESULT
2894    converted to TYPE and OMITTED was previously an operand of the expression
2895    but is now not needed (e.g., we folded OMITTED * 0).
2896
2897    If OMITTED has side effects, we must evaluate it.  Otherwise, just do
2898    the conversion of RESULT to TYPE.  */
2899
2900 tree
2901 omit_one_operand (tree type, tree result, tree omitted)
2902 {
2903   tree t = fold_convert (type, result);
2904
2905   if (TREE_SIDE_EFFECTS (omitted))
2906     return build2 (COMPOUND_EXPR, type, fold_ignored_result (omitted), t);
2907
2908   return non_lvalue (t);
2909 }
2910
2911 /* Similar, but call pedantic_non_lvalue instead of non_lvalue.  */
2912
2913 static tree
2914 pedantic_omit_one_operand (tree type, tree result, tree omitted)
2915 {
2916   tree t = fold_convert (type, result);
2917
2918   if (TREE_SIDE_EFFECTS (omitted))
2919     return build2 (COMPOUND_EXPR, type, fold_ignored_result (omitted), t);
2920
2921   return pedantic_non_lvalue (t);
2922 }
2923
2924 /* Return a tree for the case when the result of an expression is RESULT
2925    converted to TYPE and OMITTED1 and OMITTED2 were previously operands
2926    of the expression but are now not needed.
2927
2928    If OMITTED1 or OMITTED2 has side effects, they must be evaluated.
2929    If both OMITTED1 and OMITTED2 have side effects, OMITTED1 is
2930    evaluated before OMITTED2.  Otherwise, if neither has side effects,
2931    just do the conversion of RESULT to TYPE.  */
2932
2933 tree
2934 omit_two_operands (tree type, tree result, tree omitted1, tree omitted2)
2935 {
2936   tree t = fold_convert (type, result);
2937
2938   if (TREE_SIDE_EFFECTS (omitted2))
2939     t = build2 (COMPOUND_EXPR, type, omitted2, t);
2940   if (TREE_SIDE_EFFECTS (omitted1))
2941     t = build2 (COMPOUND_EXPR, type, omitted1, t);
2942
2943   return TREE_CODE (t) != COMPOUND_EXPR ? non_lvalue (t) : t;
2944 }
2945
2946 \f
2947 /* Return a simplified tree node for the truth-negation of ARG.  This
2948    never alters ARG itself.  We assume that ARG is an operation that
2949    returns a truth value (0 or 1).
2950
2951    FIXME: one would think we would fold the result, but it causes
2952    problems with the dominator optimizer.  */
2953 tree
2954 invert_truthvalue (tree arg)
2955 {
2956   tree type = TREE_TYPE (arg);
2957   enum tree_code code = TREE_CODE (arg);
2958
2959   if (code == ERROR_MARK)
2960     return arg;
2961
2962   /* If this is a comparison, we can simply invert it, except for
2963      floating-point non-equality comparisons, in which case we just
2964      enclose a TRUTH_NOT_EXPR around what we have.  */
2965
2966   if (TREE_CODE_CLASS (code) == tcc_comparison)
2967     {
2968       tree op_type = TREE_TYPE (TREE_OPERAND (arg, 0));
2969       if (FLOAT_TYPE_P (op_type)
2970           && flag_trapping_math
2971           && code != ORDERED_EXPR && code != UNORDERED_EXPR
2972           && code != NE_EXPR && code != EQ_EXPR)
2973         return build1 (TRUTH_NOT_EXPR, type, arg);
2974       else
2975         {
2976           code = invert_tree_comparison (code,
2977                                          HONOR_NANS (TYPE_MODE (op_type)));
2978           if (code == ERROR_MARK)
2979             return build1 (TRUTH_NOT_EXPR, type, arg);
2980           else
2981             return build2 (code, type,
2982                            TREE_OPERAND (arg, 0), TREE_OPERAND (arg, 1));
2983         }
2984     }
2985
2986   switch (code)
2987     {
2988     case INTEGER_CST:
2989       return constant_boolean_node (integer_zerop (arg), type);
2990
2991     case TRUTH_AND_EXPR:
2992       return build2 (TRUTH_OR_EXPR, type,
2993                      invert_truthvalue (TREE_OPERAND (arg, 0)),
2994                      invert_truthvalue (TREE_OPERAND (arg, 1)));
2995
2996     case TRUTH_OR_EXPR:
2997       return build2 (TRUTH_AND_EXPR, type,
2998                      invert_truthvalue (TREE_OPERAND (arg, 0)),
2999                      invert_truthvalue (TREE_OPERAND (arg, 1)));
3000
3001     case TRUTH_XOR_EXPR:
3002       /* Here we can invert either operand.  We invert the first operand
3003          unless the second operand is a TRUTH_NOT_EXPR in which case our
3004          result is the XOR of the first operand with the inside of the
3005          negation of the second operand.  */
3006
3007       if (TREE_CODE (TREE_OPERAND (arg, 1)) == TRUTH_NOT_EXPR)
3008         return build2 (TRUTH_XOR_EXPR, type, TREE_OPERAND (arg, 0),
3009                        TREE_OPERAND (TREE_OPERAND (arg, 1), 0));
3010       else
3011         return build2 (TRUTH_XOR_EXPR, type,
3012                        invert_truthvalue (TREE_OPERAND (arg, 0)),
3013                        TREE_OPERAND (arg, 1));
3014
3015     case TRUTH_ANDIF_EXPR:
3016       return build2 (TRUTH_ORIF_EXPR, type,
3017                      invert_truthvalue (TREE_OPERAND (arg, 0)),
3018                      invert_truthvalue (TREE_OPERAND (arg, 1)));
3019
3020     case TRUTH_ORIF_EXPR:
3021       return build2 (TRUTH_ANDIF_EXPR, type,
3022                      invert_truthvalue (TREE_OPERAND (arg, 0)),
3023                      invert_truthvalue (TREE_OPERAND (arg, 1)));
3024
3025     case TRUTH_NOT_EXPR:
3026       return TREE_OPERAND (arg, 0);
3027
3028     case COND_EXPR:
3029       return build3 (COND_EXPR, type, TREE_OPERAND (arg, 0),
3030                      invert_truthvalue (TREE_OPERAND (arg, 1)),
3031                      invert_truthvalue (TREE_OPERAND (arg, 2)));
3032
3033     case COMPOUND_EXPR:
3034       return build2 (COMPOUND_EXPR, type, TREE_OPERAND (arg, 0),
3035                      invert_truthvalue (TREE_OPERAND (arg, 1)));
3036
3037     case NON_LVALUE_EXPR:
3038       return invert_truthvalue (TREE_OPERAND (arg, 0));
3039
3040     case NOP_EXPR:
3041       if (TREE_CODE (TREE_TYPE (arg)) == BOOLEAN_TYPE)
3042         break;
3043
3044     case CONVERT_EXPR:
3045     case FLOAT_EXPR:
3046       return build1 (TREE_CODE (arg), type,
3047                      invert_truthvalue (TREE_OPERAND (arg, 0)));
3048
3049     case BIT_AND_EXPR:
3050       if (!integer_onep (TREE_OPERAND (arg, 1)))
3051         break;
3052       return build2 (EQ_EXPR, type, arg,
3053                      fold_convert (type, integer_zero_node));
3054
3055     case SAVE_EXPR:
3056       return build1 (TRUTH_NOT_EXPR, type, arg);
3057
3058     case CLEANUP_POINT_EXPR:
3059       return build1 (CLEANUP_POINT_EXPR, type,
3060                      invert_truthvalue (TREE_OPERAND (arg, 0)));
3061
3062     default:
3063       break;
3064     }
3065   gcc_assert (TREE_CODE (TREE_TYPE (arg)) == BOOLEAN_TYPE);
3066   return build1 (TRUTH_NOT_EXPR, type, arg);
3067 }
3068
3069 /* Given a bit-wise operation CODE applied to ARG0 and ARG1, see if both
3070    operands are another bit-wise operation with a common input.  If so,
3071    distribute the bit operations to save an operation and possibly two if
3072    constants are involved.  For example, convert
3073         (A | B) & (A | C) into A | (B & C)
3074    Further simplification will occur if B and C are constants.
3075
3076    If this optimization cannot be done, 0 will be returned.  */
3077
3078 static tree
3079 distribute_bit_expr (enum tree_code code, tree type, tree arg0, tree arg1)
3080 {
3081   tree common;
3082   tree left, right;
3083
3084   if (TREE_CODE (arg0) != TREE_CODE (arg1)
3085       || TREE_CODE (arg0) == code
3086       || (TREE_CODE (arg0) != BIT_AND_EXPR
3087           && TREE_CODE (arg0) != BIT_IOR_EXPR))
3088     return 0;
3089
3090   if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0))
3091     {
3092       common = TREE_OPERAND (arg0, 0);
3093       left = TREE_OPERAND (arg0, 1);
3094       right = TREE_OPERAND (arg1, 1);
3095     }
3096   else if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 1), 0))
3097     {
3098       common = TREE_OPERAND (arg0, 0);
3099       left = TREE_OPERAND (arg0, 1);
3100       right = TREE_OPERAND (arg1, 0);
3101     }
3102   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 0), 0))
3103     {
3104       common = TREE_OPERAND (arg0, 1);
3105       left = TREE_OPERAND (arg0, 0);
3106       right = TREE_OPERAND (arg1, 1);
3107     }
3108   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1), 0))
3109     {
3110       common = TREE_OPERAND (arg0, 1);
3111       left = TREE_OPERAND (arg0, 0);
3112       right = TREE_OPERAND (arg1, 0);
3113     }
3114   else
3115     return 0;
3116
3117   return fold_build2 (TREE_CODE (arg0), type, common,
3118                       fold_build2 (code, type, left, right));
3119 }
3120
3121 /* Knowing that ARG0 and ARG1 are both RDIV_EXPRs, simplify a binary operation
3122    with code CODE.  This optimization is unsafe.  */
3123 static tree
3124 distribute_real_division (enum tree_code code, tree type, tree arg0, tree arg1)
3125 {
3126   bool mul0 = TREE_CODE (arg0) == MULT_EXPR;
3127   bool mul1 = TREE_CODE (arg1) == MULT_EXPR;
3128
3129   /* (A / C) +- (B / C) -> (A +- B) / C.  */
3130   if (mul0 == mul1
3131       && operand_equal_p (TREE_OPERAND (arg0, 1),
3132                        TREE_OPERAND (arg1, 1), 0))
3133     return fold_build2 (mul0 ? MULT_EXPR : RDIV_EXPR, type,
3134                         fold_build2 (code, type,
3135                                      TREE_OPERAND (arg0, 0),
3136                                      TREE_OPERAND (arg1, 0)),
3137                         TREE_OPERAND (arg0, 1));
3138
3139   /* (A / C1) +- (A / C2) -> A * (1 / C1 +- 1 / C2).  */
3140   if (operand_equal_p (TREE_OPERAND (arg0, 0),
3141                        TREE_OPERAND (arg1, 0), 0)
3142       && TREE_CODE (TREE_OPERAND (arg0, 1)) == REAL_CST
3143       && TREE_CODE (TREE_OPERAND (arg1, 1)) == REAL_CST)
3144     {
3145       REAL_VALUE_TYPE r0, r1;
3146       r0 = TREE_REAL_CST (TREE_OPERAND (arg0, 1));
3147       r1 = TREE_REAL_CST (TREE_OPERAND (arg1, 1));
3148       if (!mul0)
3149         real_arithmetic (&r0, RDIV_EXPR, &dconst1, &r0);
3150       if (!mul1)
3151         real_arithmetic (&r1, RDIV_EXPR, &dconst1, &r1);
3152       real_arithmetic (&r0, code, &r0, &r1);
3153       return fold_build2 (MULT_EXPR, type,
3154                           TREE_OPERAND (arg0, 0),
3155                           build_real (type, r0));
3156     }
3157
3158   return NULL_TREE;
3159 }
3160 \f
3161 /* Return a BIT_FIELD_REF of type TYPE to refer to BITSIZE bits of INNER
3162    starting at BITPOS.  The field is unsigned if UNSIGNEDP is nonzero.  */
3163
3164 static tree
3165 make_bit_field_ref (tree inner, tree type, int bitsize, int bitpos,
3166                     int unsignedp)
3167 {
3168   tree result;
3169
3170   if (bitpos == 0)
3171     {
3172       tree size = TYPE_SIZE (TREE_TYPE (inner));
3173       if ((INTEGRAL_TYPE_P (TREE_TYPE (inner))
3174            || POINTER_TYPE_P (TREE_TYPE (inner)))
3175           && host_integerp (size, 0) 
3176           && tree_low_cst (size, 0) == bitsize)
3177         return fold_convert (type, inner);
3178     }
3179
3180   result = build3 (BIT_FIELD_REF, type, inner,
3181                    size_int (bitsize), bitsize_int (bitpos));
3182
3183   BIT_FIELD_REF_UNSIGNED (result) = unsignedp;
3184
3185   return result;
3186 }
3187
3188 /* Optimize a bit-field compare.
3189
3190    There are two cases:  First is a compare against a constant and the
3191    second is a comparison of two items where the fields are at the same
3192    bit position relative to the start of a chunk (byte, halfword, word)
3193    large enough to contain it.  In these cases we can avoid the shift
3194    implicit in bitfield extractions.
3195
3196    For constants, we emit a compare of the shifted constant with the
3197    BIT_AND_EXPR of a mask and a byte, halfword, or word of the operand being
3198    compared.  For two fields at the same position, we do the ANDs with the
3199    similar mask and compare the result of the ANDs.
3200
3201    CODE is the comparison code, known to be either NE_EXPR or EQ_EXPR.
3202    COMPARE_TYPE is the type of the comparison, and LHS and RHS
3203    are the left and right operands of the comparison, respectively.
3204
3205    If the optimization described above can be done, we return the resulting
3206    tree.  Otherwise we return zero.  */
3207
3208 static tree
3209 optimize_bit_field_compare (enum tree_code code, tree compare_type,
3210                             tree lhs, tree rhs)
3211 {
3212   HOST_WIDE_INT lbitpos, lbitsize, rbitpos, rbitsize, nbitpos, nbitsize;
3213   tree type = TREE_TYPE (lhs);
3214   tree signed_type, unsigned_type;
3215   int const_p = TREE_CODE (rhs) == INTEGER_CST;
3216   enum machine_mode lmode, rmode, nmode;
3217   int lunsignedp, runsignedp;
3218   int lvolatilep = 0, rvolatilep = 0;
3219   tree linner, rinner = NULL_TREE;
3220   tree mask;
3221   tree offset;
3222
3223   /* Get all the information about the extractions being done.  If the bit size
3224      if the same as the size of the underlying object, we aren't doing an
3225      extraction at all and so can do nothing.  We also don't want to
3226      do anything if the inner expression is a PLACEHOLDER_EXPR since we
3227      then will no longer be able to replace it.  */
3228   linner = get_inner_reference (lhs, &lbitsize, &lbitpos, &offset, &lmode,
3229                                 &lunsignedp, &lvolatilep, false);
3230   if (linner == lhs || lbitsize == GET_MODE_BITSIZE (lmode) || lbitsize < 0
3231       || offset != 0 || TREE_CODE (linner) == PLACEHOLDER_EXPR)
3232     return 0;
3233
3234  if (!const_p)
3235    {
3236      /* If this is not a constant, we can only do something if bit positions,
3237         sizes, and signedness are the same.  */
3238      rinner = get_inner_reference (rhs, &rbitsize, &rbitpos, &offset, &rmode,
3239                                    &runsignedp, &rvolatilep, false);
3240
3241      if (rinner == rhs || lbitpos != rbitpos || lbitsize != rbitsize
3242          || lunsignedp != runsignedp || offset != 0
3243          || TREE_CODE (rinner) == PLACEHOLDER_EXPR)
3244        return 0;
3245    }
3246
3247   /* See if we can find a mode to refer to this field.  We should be able to,
3248      but fail if we can't.  */
3249   nmode = get_best_mode (lbitsize, lbitpos,
3250                          const_p ? TYPE_ALIGN (TREE_TYPE (linner))
3251                          : MIN (TYPE_ALIGN (TREE_TYPE (linner)),
3252                                 TYPE_ALIGN (TREE_TYPE (rinner))),
3253                          word_mode, lvolatilep || rvolatilep);
3254   if (nmode == VOIDmode)
3255     return 0;
3256
3257   /* Set signed and unsigned types of the precision of this mode for the
3258      shifts below.  */
3259   signed_type = lang_hooks.types.type_for_mode (nmode, 0);
3260   unsigned_type = lang_hooks.types.type_for_mode (nmode, 1);
3261
3262   /* Compute the bit position and size for the new reference and our offset
3263      within it. If the new reference is the same size as the original, we
3264      won't optimize anything, so return zero.  */
3265   nbitsize = GET_MODE_BITSIZE (nmode);
3266   nbitpos = lbitpos & ~ (nbitsize - 1);
3267   lbitpos -= nbitpos;
3268   if (nbitsize == lbitsize)
3269     return 0;
3270
3271   if (BYTES_BIG_ENDIAN)
3272     lbitpos = nbitsize - lbitsize - lbitpos;
3273
3274   /* Make the mask to be used against the extracted field.  */
3275   mask = build_int_cst (unsigned_type, -1);
3276   mask = force_fit_type (mask, 0, false, false);
3277   mask = fold_convert (unsigned_type, mask);
3278   mask = const_binop (LSHIFT_EXPR, mask, size_int (nbitsize - lbitsize), 0);
3279   mask = const_binop (RSHIFT_EXPR, mask,
3280                       size_int (nbitsize - lbitsize - lbitpos), 0);
3281
3282   if (! const_p)
3283     /* If not comparing with constant, just rework the comparison
3284        and return.  */
3285     return build2 (code, compare_type,
3286                    build2 (BIT_AND_EXPR, unsigned_type,
3287                            make_bit_field_ref (linner, unsigned_type,
3288                                                nbitsize, nbitpos, 1),
3289                            mask),
3290                    build2 (BIT_AND_EXPR, unsigned_type,
3291                            make_bit_field_ref (rinner, unsigned_type,
3292                                                nbitsize, nbitpos, 1),
3293                            mask));
3294
3295   /* Otherwise, we are handling the constant case. See if the constant is too
3296      big for the field.  Warn and return a tree of for 0 (false) if so.  We do
3297      this not only for its own sake, but to avoid having to test for this
3298      error case below.  If we didn't, we might generate wrong code.
3299
3300      For unsigned fields, the constant shifted right by the field length should
3301      be all zero.  For signed fields, the high-order bits should agree with
3302      the sign bit.  */
3303
3304   if (lunsignedp)
3305     {
3306       if (! integer_zerop (const_binop (RSHIFT_EXPR,
3307                                         fold_convert (unsigned_type, rhs),
3308                                         size_int (lbitsize), 0)))
3309         {
3310           warning (0, "comparison is always %d due to width of bit-field",
3311                    code == NE_EXPR);
3312           return constant_boolean_node (code == NE_EXPR, compare_type);
3313         }
3314     }
3315   else
3316     {
3317       tree tem = const_binop (RSHIFT_EXPR, fold_convert (signed_type, rhs),
3318                               size_int (lbitsize - 1), 0);
3319       if (! integer_zerop (tem) && ! integer_all_onesp (tem))
3320         {
3321           warning (0, "comparison is always %d due to width of bit-field",
3322                    code == NE_EXPR);
3323           return constant_boolean_node (code == NE_EXPR, compare_type);
3324         }
3325     }
3326
3327   /* Single-bit compares should always be against zero.  */
3328   if (lbitsize == 1 && ! integer_zerop (rhs))
3329     {
3330       code = code == EQ_EXPR ? NE_EXPR : EQ_EXPR;
3331       rhs = fold_convert (type, integer_zero_node);
3332     }
3333
3334   /* Make a new bitfield reference, shift the constant over the
3335      appropriate number of bits and mask it with the computed mask
3336      (in case this was a signed field).  If we changed it, make a new one.  */
3337   lhs = make_bit_field_ref (linner, unsigned_type, nbitsize, nbitpos, 1);
3338   if (lvolatilep)
3339     {
3340       TREE_SIDE_EFFECTS (lhs) = 1;
3341       TREE_THIS_VOLATILE (lhs) = 1;
3342     }
3343
3344   rhs = fold (const_binop (BIT_AND_EXPR,
3345                            const_binop (LSHIFT_EXPR,
3346                                         fold_convert (unsigned_type, rhs),
3347                                         size_int (lbitpos), 0),
3348                            mask, 0));
3349
3350   return build2 (code, compare_type,
3351                  build2 (BIT_AND_EXPR, unsigned_type, lhs, mask),
3352                  rhs);
3353 }
3354 \f
3355 /* Subroutine for fold_truthop: decode a field reference.
3356
3357    If EXP is a comparison reference, we return the innermost reference.
3358
3359    *PBITSIZE is set to the number of bits in the reference, *PBITPOS is
3360    set to the starting bit number.
3361
3362    If the innermost field can be completely contained in a mode-sized
3363    unit, *PMODE is set to that mode.  Otherwise, it is set to VOIDmode.
3364
3365    *PVOLATILEP is set to 1 if the any expression encountered is volatile;
3366    otherwise it is not changed.
3367
3368    *PUNSIGNEDP is set to the signedness of the field.
3369
3370    *PMASK is set to the mask used.  This is either contained in a
3371    BIT_AND_EXPR or derived from the width of the field.
3372
3373    *PAND_MASK is set to the mask found in a BIT_AND_EXPR, if any.
3374
3375    Return 0 if this is not a component reference or is one that we can't
3376    do anything with.  */
3377
3378 static tree
3379 decode_field_reference (tree exp, HOST_WIDE_INT *pbitsize,
3380                         HOST_WIDE_INT *pbitpos, enum machine_mode *pmode,
3381                         int *punsignedp, int *pvolatilep,
3382                         tree *pmask, tree *pand_mask)
3383 {
3384   tree outer_type = 0;
3385   tree and_mask = 0;
3386   tree mask, inner, offset;
3387   tree unsigned_type;
3388   unsigned int precision;
3389
3390   /* All the optimizations using this function assume integer fields.
3391      There are problems with FP fields since the type_for_size call
3392      below can fail for, e.g., XFmode.  */
3393   if (! INTEGRAL_TYPE_P (TREE_TYPE (exp)))
3394     return 0;
3395
3396   /* We are interested in the bare arrangement of bits, so strip everything
3397      that doesn't affect the machine mode.  However, record the type of the
3398      outermost expression if it may matter below.  */
3399   if (TREE_CODE (exp) == NOP_EXPR
3400       || TREE_CODE (exp) == CONVERT_EXPR
3401       || TREE_CODE (exp) == NON_LVALUE_EXPR)
3402     outer_type = TREE_TYPE (exp);
3403   STRIP_NOPS (exp);
3404
3405   if (TREE_CODE (exp) == BIT_AND_EXPR)
3406     {
3407       and_mask = TREE_OPERAND (exp, 1);
3408       exp = TREE_OPERAND (exp, 0);
3409       STRIP_NOPS (exp); STRIP_NOPS (and_mask);
3410       if (TREE_CODE (and_mask) != INTEGER_CST)
3411         return 0;
3412     }
3413
3414   inner = get_inner_reference (exp, pbitsize, pbitpos, &offset, pmode,
3415                                punsignedp, pvolatilep, false);
3416   if ((inner == exp && and_mask == 0)
3417       || *pbitsize < 0 || offset != 0
3418       || TREE_CODE (inner) == PLACEHOLDER_EXPR)
3419     return 0;
3420
3421   /* If the number of bits in the reference is the same as the bitsize of
3422      the outer type, then the outer type gives the signedness. Otherwise
3423      (in case of a small bitfield) the signedness is unchanged.  */
3424   if (outer_type && *pbitsize == TYPE_PRECISION (outer_type))
3425     *punsignedp = TYPE_UNSIGNED (outer_type);
3426
3427   /* Compute the mask to access the bitfield.  */
3428   unsigned_type = lang_hooks.types.type_for_size (*pbitsize, 1);
3429   precision = TYPE_PRECISION (unsigned_type);
3430
3431   mask = build_int_cst (unsigned_type, -1);
3432   mask = force_fit_type (mask, 0, false, false);
3433
3434   mask = const_binop (LSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
3435   mask = const_binop (RSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
3436
3437   /* Merge it with the mask we found in the BIT_AND_EXPR, if any.  */
3438   if (and_mask != 0)
3439     mask = fold_build2 (BIT_AND_EXPR, unsigned_type,
3440                         fold_convert (unsigned_type, and_mask), mask);
3441
3442   *pmask = mask;
3443   *pand_mask = and_mask;
3444   return inner;
3445 }
3446
3447 /* Return nonzero if MASK represents a mask of SIZE ones in the low-order
3448    bit positions.  */
3449
3450 static int
3451 all_ones_mask_p (tree mask, int size)
3452 {
3453   tree type = TREE_TYPE (mask);
3454   unsigned int precision = TYPE_PRECISION (type);
3455   tree tmask;
3456
3457   tmask = build_int_cst (lang_hooks.types.signed_type (type), -1);
3458   tmask = force_fit_type (tmask, 0, false, false);
3459
3460   return
3461     tree_int_cst_equal (mask,
3462                         const_binop (RSHIFT_EXPR,
3463                                      const_binop (LSHIFT_EXPR, tmask,
3464                                                   size_int (precision - size),
3465                                                   0),
3466                                      size_int (precision - size), 0));
3467 }
3468
3469 /* Subroutine for fold: determine if VAL is the INTEGER_CONST that
3470    represents the sign bit of EXP's type.  If EXP represents a sign
3471    or zero extension, also test VAL against the unextended type.
3472    The return value is the (sub)expression whose sign bit is VAL,
3473    or NULL_TREE otherwise.  */
3474
3475 static tree
3476 sign_bit_p (tree exp, tree val)
3477 {
3478   unsigned HOST_WIDE_INT mask_lo, lo;
3479   HOST_WIDE_INT mask_hi, hi;
3480   int width;
3481   tree t;
3482
3483   /* Tree EXP must have an integral type.  */
3484   t = TREE_TYPE (exp);
3485   if (! INTEGRAL_TYPE_P (t))
3486     return NULL_TREE;
3487
3488   /* Tree VAL must be an integer constant.  */
3489   if (TREE_CODE (val) != INTEGER_CST
3490       || TREE_CONSTANT_OVERFLOW (val))
3491     return NULL_TREE;
3492
3493   width = TYPE_PRECISION (t);
3494   if (width > HOST_BITS_PER_WIDE_INT)
3495     {
3496       hi = (unsigned HOST_WIDE_INT) 1 << (width - HOST_BITS_PER_WIDE_INT - 1);
3497       lo = 0;
3498
3499       mask_hi = ((unsigned HOST_WIDE_INT) -1
3500                  >> (2 * HOST_BITS_PER_WIDE_INT - width));
3501       mask_lo = -1;
3502     }
3503   else
3504     {
3505       hi = 0;
3506       lo = (unsigned HOST_WIDE_INT) 1 << (width - 1);
3507
3508       mask_hi = 0;
3509       mask_lo = ((unsigned HOST_WIDE_INT) -1
3510                  >> (HOST_BITS_PER_WIDE_INT - width));
3511     }
3512
3513   /* We mask off those bits beyond TREE_TYPE (exp) so that we can
3514      treat VAL as if it were unsigned.  */
3515   if ((TREE_INT_CST_HIGH (val) & mask_hi) == hi
3516       && (TREE_INT_CST_LOW (val) & mask_lo) == lo)
3517     return exp;
3518
3519   /* Handle extension from a narrower type.  */
3520   if (TREE_CODE (exp) == NOP_EXPR
3521       && TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (exp, 0))) < width)
3522     return sign_bit_p (TREE_OPERAND (exp, 0), val);
3523
3524   return NULL_TREE;
3525 }
3526
3527 /* Subroutine for fold_truthop: determine if an operand is simple enough
3528    to be evaluated unconditionally.  */
3529
3530 static int
3531 simple_operand_p (tree exp)
3532 {
3533   /* Strip any conversions that don't change the machine mode.  */
3534   STRIP_NOPS (exp);
3535
3536   return (CONSTANT_CLASS_P (exp)
3537           || TREE_CODE (exp) == SSA_NAME
3538           || (DECL_P (exp)
3539               && ! TREE_ADDRESSABLE (exp)
3540               && ! TREE_THIS_VOLATILE (exp)
3541               && ! DECL_NONLOCAL (exp)
3542               /* Don't regard global variables as simple.  They may be
3543                  allocated in ways unknown to the compiler (shared memory,
3544                  #pragma weak, etc).  */
3545               && ! TREE_PUBLIC (exp)
3546               && ! DECL_EXTERNAL (exp)
3547               /* Loading a static variable is unduly expensive, but global
3548                  registers aren't expensive.  */
3549               && (! TREE_STATIC (exp) || DECL_REGISTER (exp))));
3550 }
3551 \f
3552 /* The following functions are subroutines to fold_range_test and allow it to
3553    try to change a logical combination of comparisons into a range test.
3554
3555    For example, both
3556         X == 2 || X == 3 || X == 4 || X == 5
3557    and
3558         X >= 2 && X <= 5
3559    are converted to
3560         (unsigned) (X - 2) <= 3
3561
3562    We describe each set of comparisons as being either inside or outside
3563    a range, using a variable named like IN_P, and then describe the
3564    range with a lower and upper bound.  If one of the bounds is omitted,
3565    it represents either the highest or lowest value of the type.
3566
3567    In the comments below, we represent a range by two numbers in brackets
3568    preceded by a "+" to designate being inside that range, or a "-" to
3569    designate being outside that range, so the condition can be inverted by
3570    flipping the prefix.  An omitted bound is represented by a "-".  For
3571    example, "- [-, 10]" means being outside the range starting at the lowest
3572    possible value and ending at 10, in other words, being greater than 10.
3573    The range "+ [-, -]" is always true and hence the range "- [-, -]" is
3574    always false.
3575
3576    We set up things so that the missing bounds are handled in a consistent
3577    manner so neither a missing bound nor "true" and "false" need to be
3578    handled using a special case.  */
3579
3580 /* Return the result of applying CODE to ARG0 and ARG1, but handle the case
3581    of ARG0 and/or ARG1 being omitted, meaning an unlimited range. UPPER0_P
3582    and UPPER1_P are nonzero if the respective argument is an upper bound
3583    and zero for a lower.  TYPE, if nonzero, is the type of the result; it
3584    must be specified for a comparison.  ARG1 will be converted to ARG0's
3585    type if both are specified.  */
3586
3587 static tree
3588 range_binop (enum tree_code code, tree type, tree arg0, int upper0_p,
3589              tree arg1, int upper1_p)
3590 {
3591   tree tem;
3592   int result;
3593   int sgn0, sgn1;
3594
3595   /* If neither arg represents infinity, do the normal operation.
3596      Else, if not a comparison, return infinity.  Else handle the special
3597      comparison rules. Note that most of the cases below won't occur, but
3598      are handled for consistency.  */
3599
3600   if (arg0 != 0 && arg1 != 0)
3601     {
3602       tem = fold_build2 (code, type != 0 ? type : TREE_TYPE (arg0),
3603                          arg0, fold_convert (TREE_TYPE (arg0), arg1));
3604       STRIP_NOPS (tem);
3605       return TREE_CODE (tem) == INTEGER_CST ? tem : 0;
3606     }
3607
3608   if (TREE_CODE_CLASS (code) != tcc_comparison)
3609     return 0;
3610
3611   /* Set SGN[01] to -1 if ARG[01] is a lower bound, 1 for upper, and 0
3612      for neither.  In real maths, we cannot assume open ended ranges are
3613      the same. But, this is computer arithmetic, where numbers are finite.
3614      We can therefore make the transformation of any unbounded range with
3615      the value Z, Z being greater than any representable number. This permits
3616      us to treat unbounded ranges as equal.  */
3617   sgn0 = arg0 != 0 ? 0 : (upper0_p ? 1 : -1);
3618   sgn1 = arg1 != 0 ? 0 : (upper1_p ? 1 : -1);
3619   switch (code)
3620     {
3621     case EQ_EXPR:
3622       result = sgn0 == sgn1;
3623       break;
3624     case NE_EXPR:
3625       result = sgn0 != sgn1;
3626       break;
3627     case LT_EXPR:
3628       result = sgn0 < sgn1;
3629       break;
3630     case LE_EXPR:
3631       result = sgn0 <= sgn1;
3632       break;
3633     case GT_EXPR:
3634       result = sgn0 > sgn1;
3635       break;
3636     case GE_EXPR:
3637       result = sgn0 >= sgn1;
3638       break;
3639     default:
3640       gcc_unreachable ();
3641     }
3642
3643   return constant_boolean_node (result, type);
3644 }
3645 \f
3646 /* Given EXP, a logical expression, set the range it is testing into
3647    variables denoted by PIN_P, PLOW, and PHIGH.  Return the expression
3648    actually being tested.  *PLOW and *PHIGH will be made of the same type
3649    as the returned expression.  If EXP is not a comparison, we will most
3650    likely not be returning a useful value and range.  */
3651
3652 static tree
3653 make_range (tree exp, int *pin_p, tree *plow, tree *phigh)
3654 {
3655   enum tree_code code;
3656   tree arg0 = NULL_TREE, arg1 = NULL_TREE;
3657   tree exp_type = NULL_TREE, arg0_type = NULL_TREE;
3658   int in_p, n_in_p;
3659   tree low, high, n_low, n_high;
3660
3661   /* Start with simply saying "EXP != 0" and then look at the code of EXP
3662      and see if we can refine the range.  Some of the cases below may not
3663      happen, but it doesn't seem worth worrying about this.  We "continue"
3664      the outer loop when we've changed something; otherwise we "break"
3665      the switch, which will "break" the while.  */
3666
3667   in_p = 0;
3668   low = high = fold_convert (TREE_TYPE (exp), integer_zero_node);
3669
3670   while (1)
3671     {
3672       code = TREE_CODE (exp);
3673       exp_type = TREE_TYPE (exp);
3674
3675       if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
3676         {
3677           if (TREE_CODE_LENGTH (code) > 0)
3678             arg0 = TREE_OPERAND (exp, 0);
3679           if (TREE_CODE_CLASS (code) == tcc_comparison
3680               || TREE_CODE_CLASS (code) == tcc_unary
3681               || TREE_CODE_CLASS (code) == tcc_binary)
3682             arg0_type = TREE_TYPE (arg0);
3683           if (TREE_CODE_CLASS (code) == tcc_binary
3684               || TREE_CODE_CLASS (code) == tcc_comparison
3685               || (TREE_CODE_CLASS (code) == tcc_expression
3686                   && TREE_CODE_LENGTH (code) > 1))
3687             arg1 = TREE_OPERAND (exp, 1);
3688         }
3689
3690       switch (code)
3691         {
3692         case TRUTH_NOT_EXPR:
3693           in_p = ! in_p, exp = arg0;
3694           continue;
3695
3696         case EQ_EXPR: case NE_EXPR:
3697         case LT_EXPR: case LE_EXPR: case GE_EXPR: case GT_EXPR:
3698           /* We can only do something if the range is testing for zero
3699              and if the second operand is an integer constant.  Note that
3700              saying something is "in" the range we make is done by
3701              complementing IN_P since it will set in the initial case of
3702              being not equal to zero; "out" is leaving it alone.  */
3703           if (low == 0 || high == 0
3704               || ! integer_zerop (low) || ! integer_zerop (high)
3705               || TREE_CODE (arg1) != INTEGER_CST)
3706             break;
3707
3708           switch (code)
3709             {
3710             case NE_EXPR:  /* - [c, c]  */
3711               low = high = arg1;
3712               break;
3713             case EQ_EXPR:  /* + [c, c]  */
3714               in_p = ! in_p, low = high = arg1;
3715               break;
3716             case GT_EXPR:  /* - [-, c] */
3717               low = 0, high = arg1;
3718               break;
3719             case GE_EXPR:  /* + [c, -] */
3720               in_p = ! in_p, low = arg1, high = 0;
3721               break;
3722             case LT_EXPR:  /* - [c, -] */
3723               low = arg1, high = 0;
3724               break;
3725             case LE_EXPR:  /* + [-, c] */
3726               in_p = ! in_p, low = 0, high = arg1;
3727               break;
3728             default:
3729               gcc_unreachable ();
3730             }
3731
3732           /* If this is an unsigned comparison, we also know that EXP is
3733              greater than or equal to zero.  We base the range tests we make
3734              on that fact, so we record it here so we can parse existing
3735              range tests.  We test arg0_type since often the return type
3736              of, e.g. EQ_EXPR, is boolean.  */
3737           if (TYPE_UNSIGNED (arg0_type) && (low == 0 || high == 0))
3738             {
3739               if (! merge_ranges (&n_in_p, &n_low, &n_high,
3740                                   in_p, low, high, 1,
3741                                   fold_convert (arg0_type, integer_zero_node),
3742                                   NULL_TREE))
3743                 break;
3744
3745               in_p = n_in_p, low = n_low, high = n_high;
3746
3747               /* If the high bound is missing, but we have a nonzero low
3748                  bound, reverse the range so it goes from zero to the low bound
3749                  minus 1.  */
3750               if (high == 0 && low && ! integer_zerop (low))
3751                 {
3752                   in_p = ! in_p;
3753                   high = range_binop (MINUS_EXPR, NULL_TREE, low, 0,
3754                                       integer_one_node, 0);
3755                   low = fold_convert (arg0_type, integer_zero_node);
3756                 }
3757             }
3758
3759           exp = arg0;
3760           continue;
3761
3762         case NEGATE_EXPR:
3763           /* (-x) IN [a,b] -> x in [-b, -a]  */
3764           n_low = range_binop (MINUS_EXPR, exp_type,
3765                                fold_convert (exp_type, integer_zero_node),
3766                                0, high, 1);
3767           n_high = range_binop (MINUS_EXPR, exp_type,
3768                                 fold_convert (exp_type, integer_zero_node),
3769                                 0, low, 0);
3770           low = n_low, high = n_high;
3771           exp = arg0;
3772           continue;
3773
3774         case BIT_NOT_EXPR:
3775           /* ~ X -> -X - 1  */
3776           exp = build2 (MINUS_EXPR, exp_type, negate_expr (arg0),
3777                         fold_convert (exp_type, integer_one_node));
3778           continue;
3779
3780         case PLUS_EXPR:  case MINUS_EXPR:
3781           if (TREE_CODE (arg1) != INTEGER_CST)
3782             break;
3783
3784           /* If EXP is signed, any overflow in the computation is undefined,
3785              so we don't worry about it so long as our computations on
3786              the bounds don't overflow.  For unsigned, overflow is defined
3787              and this is exactly the right thing.  */
3788           n_low = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
3789                                arg0_type, low, 0, arg1, 0);
3790           n_high = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
3791                                 arg0_type, high, 1, arg1, 0);
3792           if ((n_low != 0 && TREE_OVERFLOW (n_low))
3793               || (n_high != 0 && TREE_OVERFLOW (n_high)))
3794             break;
3795
3796           /* Check for an unsigned range which has wrapped around the maximum
3797              value thus making n_high < n_low, and normalize it.  */
3798           if (n_low && n_high && tree_int_cst_lt (n_high, n_low))
3799             {
3800               low = range_binop (PLUS_EXPR, arg0_type, n_high, 0,
3801                                  integer_one_node, 0);
3802               high = range_binop (MINUS_EXPR, arg0_type, n_low, 0,
3803                                   integer_one_node, 0);
3804
3805               /* If the range is of the form +/- [ x+1, x ], we won't
3806                  be able to normalize it.  But then, it represents the
3807                  whole range or the empty set, so make it
3808                  +/- [ -, - ].  */
3809               if (tree_int_cst_equal (n_low, low)
3810                   && tree_int_cst_equal (n_high, high))
3811                 low = high = 0;
3812               else
3813                 in_p = ! in_p;
3814             }
3815           else
3816             low = n_low, high = n_high;
3817
3818           exp = arg0;
3819           continue;
3820
3821         case NOP_EXPR:  case NON_LVALUE_EXPR:  case CONVERT_EXPR:
3822           if (TYPE_PRECISION (arg0_type) > TYPE_PRECISION (exp_type))
3823             break;
3824
3825           if (! INTEGRAL_TYPE_P (arg0_type)
3826               || (low != 0 && ! int_fits_type_p (low, arg0_type))
3827               || (high != 0 && ! int_fits_type_p (high, arg0_type)))
3828             break;
3829
3830           n_low = low, n_high = high;
3831
3832           if (n_low != 0)
3833             n_low = fold_convert (arg0_type, n_low);
3834
3835           if (n_high != 0)
3836             n_high = fold_convert (arg0_type, n_high);
3837
3838
3839           /* If we're converting arg0 from an unsigned type, to exp,
3840              a signed type,  we will be doing the comparison as unsigned.
3841              The tests above have already verified that LOW and HIGH
3842              are both positive.
3843
3844              So we have to ensure that we will handle large unsigned
3845              values the same way that the current signed bounds treat
3846              negative values.  */
3847
3848           if (!TYPE_UNSIGNED (exp_type) && TYPE_UNSIGNED (arg0_type))
3849             {
3850               tree high_positive;
3851               tree equiv_type = lang_hooks.types.type_for_mode
3852                 (TYPE_MODE (arg0_type), 1);
3853
3854               /* A range without an upper bound is, naturally, unbounded.
3855                  Since convert would have cropped a very large value, use
3856                  the max value for the destination type.  */
3857               high_positive
3858                 = TYPE_MAX_VALUE (equiv_type) ? TYPE_MAX_VALUE (equiv_type)
3859                 : TYPE_MAX_VALUE (arg0_type);
3860
3861               if (TYPE_PRECISION (exp_type) == TYPE_PRECISION (arg0_type))
3862                 high_positive = fold_build2 (RSHIFT_EXPR, arg0_type,
3863                                              fold_convert (arg0_type,
3864                                                            high_positive),
3865                                              fold_convert (arg0_type,
3866                                                            integer_one_node));
3867
3868               /* If the low bound is specified, "and" the range with the
3869                  range for which the original unsigned value will be
3870                  positive.  */
3871               if (low != 0)
3872                 {
3873                   if (! merge_ranges (&n_in_p, &n_low, &n_high,
3874                                       1, n_low, n_high, 1,
3875                                       fold_convert (arg0_type,
3876                                                     integer_zero_node),
3877                                       high_positive))
3878                     break;
3879
3880                   in_p = (n_in_p == in_p);
3881                 }
3882               else
3883                 {
3884                   /* Otherwise, "or" the range with the range of the input
3885                      that will be interpreted as negative.  */
3886                   if (! merge_ranges (&n_in_p, &n_low, &n_high,
3887                                       0, n_low, n_high, 1,
3888                                       fold_convert (arg0_type,
3889                                                     integer_zero_node),
3890                                       high_positive))
3891                     break;
3892
3893                   in_p = (in_p != n_in_p);
3894                 }
3895             }
3896
3897           exp = arg0;
3898           low = n_low, high = n_high;
3899           continue;
3900
3901         default:
3902           break;
3903         }
3904
3905       break;
3906     }
3907
3908   /* If EXP is a constant, we can evaluate whether this is true or false.  */
3909   if (TREE_CODE (exp) == INTEGER_CST)
3910     {
3911       in_p = in_p == (integer_onep (range_binop (GE_EXPR, integer_type_node,
3912                                                  exp, 0, low, 0))
3913                       && integer_onep (range_binop (LE_EXPR, integer_type_node,
3914                                                     exp, 1, high, 1)));
3915       low = high = 0;
3916       exp = 0;
3917     }
3918
3919   *pin_p = in_p, *plow = low, *phigh = high;
3920   return exp;
3921 }
3922 \f
3923 /* Given a range, LOW, HIGH, and IN_P, an expression, EXP, and a result
3924    type, TYPE, return an expression to test if EXP is in (or out of, depending
3925    on IN_P) the range.  Return 0 if the test couldn't be created.  */
3926
3927 static tree
3928 build_range_check (tree type, tree exp, int in_p, tree low, tree high)
3929 {
3930   tree etype = TREE_TYPE (exp);
3931   tree value;
3932
3933   if (! in_p)
3934     {
3935       value = build_range_check (type, exp, 1, low, high);
3936       if (value != 0)
3937         return invert_truthvalue (value);
3938
3939       return 0;
3940     }
3941
3942   if (low == 0 && high == 0)
3943     return fold_convert (type, integer_one_node);
3944
3945   if (low == 0)
3946     return fold_build2 (LE_EXPR, type, exp, high);
3947
3948   if (high == 0)
3949     return fold_build2 (GE_EXPR, type, exp, low);
3950
3951   if (operand_equal_p (low, high, 0))
3952     return fold_build2 (EQ_EXPR, type, exp, low);
3953
3954   if (integer_zerop (low))
3955     {
3956       if (! TYPE_UNSIGNED (etype))
3957         {
3958           etype = lang_hooks.types.unsigned_type (etype);
3959           high = fold_convert (etype, high);
3960           exp = fold_convert (etype, exp);
3961         }
3962       return build_range_check (type, exp, 1, 0, high);
3963     }
3964
3965   /* Optimize (c>=1) && (c<=127) into (signed char)c > 0.  */
3966   if (integer_onep (low) && TREE_CODE (high) == INTEGER_CST)
3967     {
3968       unsigned HOST_WIDE_INT lo;
3969       HOST_WIDE_INT hi;
3970       int prec;
3971
3972       prec = TYPE_PRECISION (etype);
3973       if (prec <= HOST_BITS_PER_WIDE_INT)
3974         {
3975           hi = 0;
3976           lo = ((unsigned HOST_WIDE_INT) 1 << (prec - 1)) - 1;
3977         }
3978       else
3979         {
3980           hi = ((HOST_WIDE_INT) 1 << (prec - HOST_BITS_PER_WIDE_INT - 1)) - 1;
3981           lo = (unsigned HOST_WIDE_INT) -1;
3982         }
3983
3984       if (TREE_INT_CST_HIGH (high) == hi && TREE_INT_CST_LOW (high) == lo)
3985         {
3986           if (TYPE_UNSIGNED (etype))
3987             {
3988               etype = lang_hooks.types.signed_type (etype);
3989               exp = fold_convert (etype, exp);
3990             }
3991           return fold_build2 (GT_EXPR, type, exp,
3992                               fold_convert (etype, integer_zero_node));
3993         }
3994     }
3995
3996   value = const_binop (MINUS_EXPR, high, low, 0);
3997   if (value != 0 && TREE_OVERFLOW (value) && ! TYPE_UNSIGNED (etype))
3998     {
3999       tree utype, minv, maxv;
4000
4001       /* Check if (unsigned) INT_MAX + 1 == (unsigned) INT_MIN
4002          for the type in question, as we rely on this here.  */
4003       switch (TREE_CODE (etype))
4004         {
4005         case INTEGER_TYPE:
4006         case ENUMERAL_TYPE:
4007         case CHAR_TYPE:
4008           utype = lang_hooks.types.unsigned_type (etype);
4009           maxv = fold_convert (utype, TYPE_MAX_VALUE (etype));
4010           maxv = range_binop (PLUS_EXPR, NULL_TREE, maxv, 1,
4011                               integer_one_node, 1);
4012           minv = fold_convert (utype, TYPE_MIN_VALUE (etype));
4013           if (integer_zerop (range_binop (NE_EXPR, integer_type_node,
4014                                           minv, 1, maxv, 1)))
4015             {
4016               etype = utype;
4017               high = fold_convert (etype, high);
4018               low = fold_convert (etype, low);
4019               exp = fold_convert (etype, exp);
4020               value = const_binop (MINUS_EXPR, high, low, 0);
4021             }
4022           break;
4023         default:
4024           break;
4025         }
4026     }
4027
4028   if (value != 0 && ! TREE_OVERFLOW (value))
4029     return build_range_check (type,
4030                               fold_build2 (MINUS_EXPR, etype, exp, low),
4031                               1, fold_convert (etype, integer_zero_node),
4032                               value);
4033
4034   return 0;
4035 }
4036 \f
4037 /* Given two ranges, see if we can merge them into one.  Return 1 if we
4038    can, 0 if we can't.  Set the output range into the specified parameters.  */
4039
4040 static int
4041 merge_ranges (int *pin_p, tree *plow, tree *phigh, int in0_p, tree low0,
4042               tree high0, int in1_p, tree low1, tree high1)
4043 {
4044   int no_overlap;