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