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