* fold-const.c (fold) <PLUS_EXPR>: Guard (-A)+B -> B-A transformation
[gcc/gcc.git] / gcc / fold-const.c
1 /* Fold a constant sub-tree into a single node for C-compiler
2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
3    2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA.  */
21
22 /*@@ This file should be rewritten to use an arbitrary precision
23   @@ representation for "struct tree_int_cst" and "struct tree_real_cst".
24   @@ Perhaps the routines could also be used for bc/dc, and made a lib.
25   @@ The routines that translate from the ap rep should
26   @@ warn if precision et. al. is lost.
27   @@ This would also make life easier when this technology is used
28   @@ for cross-compilers.  */
29
30 /* The entry points in this file are fold, size_int_wide, size_binop
31    and force_fit_type.
32
33    fold takes a tree as argument and returns a simplified tree.
34
35    size_binop takes a tree code for an arithmetic operation
36    and two operands that are trees, and produces a tree for the
37    result, assuming the type comes from `sizetype'.
38
39    size_int takes an integer value, and creates a tree constant
40    with type from `sizetype'.
41
42    force_fit_type takes a constant and prior overflow indicator, and
43    forces the value to fit the type.  It returns an overflow indicator.  */
44
45 #include "config.h"
46 #include "system.h"
47 #include "coretypes.h"
48 #include "tm.h"
49 #include "flags.h"
50 #include "tree.h"
51 #include "real.h"
52 #include "rtl.h"
53 #include "expr.h"
54 #include "tm_p.h"
55 #include "toplev.h"
56 #include "ggc.h"
57 #include "hashtab.h"
58 #include "langhooks.h"
59 #include "md5.h"
60
61 static void encode (HOST_WIDE_INT *, unsigned HOST_WIDE_INT, HOST_WIDE_INT);
62 static void decode (HOST_WIDE_INT *, unsigned HOST_WIDE_INT *, HOST_WIDE_INT *);
63 static bool negate_mathfn_p (enum built_in_function);
64 static bool negate_expr_p (tree);
65 static tree negate_expr (tree);
66 static tree split_tree (tree, enum tree_code, tree *, tree *, tree *, int);
67 static tree associate_trees (tree, tree, enum tree_code, tree);
68 static tree int_const_binop (enum tree_code, tree, tree, int);
69 static tree const_binop (enum tree_code, tree, tree, int);
70 static hashval_t size_htab_hash (const void *);
71 static int size_htab_eq (const void *, const void *);
72 static tree fold_convert_const (enum tree_code, tree, tree);
73 static tree fold_convert (tree, tree);
74 static enum tree_code invert_tree_comparison (enum tree_code);
75 static enum tree_code swap_tree_comparison (enum tree_code);
76 static int comparison_to_compcode (enum tree_code);
77 static enum tree_code compcode_to_comparison (int);
78 static int truth_value_p (enum tree_code);
79 static int operand_equal_for_comparison_p (tree, tree, tree);
80 static int twoval_comparison_p (tree, tree *, tree *, int *);
81 static tree eval_subst (tree, tree, tree, tree, tree);
82 static tree pedantic_omit_one_operand (tree, tree, tree);
83 static tree distribute_bit_expr (enum tree_code, tree, tree, tree);
84 static tree make_bit_field_ref (tree, tree, int, int, int);
85 static tree optimize_bit_field_compare (enum tree_code, tree, tree, tree);
86 static tree decode_field_reference (tree, HOST_WIDE_INT *, HOST_WIDE_INT *,
87                                     enum machine_mode *, int *, int *,
88                                     tree *, tree *);
89 static int all_ones_mask_p (tree, int);
90 static tree sign_bit_p (tree, tree);
91 static int simple_operand_p (tree);
92 static tree range_binop (enum tree_code, tree, tree, int, tree, int);
93 static tree make_range (tree, int *, tree *, tree *);
94 static tree build_range_check (tree, tree, int, tree, tree);
95 static int merge_ranges (int *, tree *, tree *, int, tree, tree, int, tree,
96                          tree);
97 static tree fold_range_test (tree);
98 static tree unextend (tree, int, int, tree);
99 static tree fold_truthop (enum tree_code, tree, tree, tree);
100 static tree optimize_minmax_comparison (tree);
101 static tree extract_muldiv (tree, tree, enum tree_code, tree);
102 static tree extract_muldiv_1 (tree, tree, enum tree_code, tree);
103 static tree strip_compound_expr (tree, tree);
104 static int multiple_of_p (tree, tree, tree);
105 static tree constant_boolean_node (int, tree);
106 static int count_cond (tree, int);
107 static tree fold_binary_op_with_conditional_arg (enum tree_code, tree, tree,
108                                                  tree, int);
109 static bool fold_real_zero_addition_p (tree, tree, int);
110 static tree fold_mathfn_compare (enum built_in_function, enum tree_code,
111                                  tree, tree, tree);
112 static tree fold_inf_compare (enum tree_code, tree, tree, tree);
113 static bool reorder_operands_p (tree, tree);
114 static bool tree_swap_operands_p (tree, tree, bool);
115
116 static tree fold_negate_const (tree, tree);
117 static tree fold_abs_const (tree, tree);
118 static tree fold_relational_const (enum tree_code, 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 static 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             default:
1793               abort ();
1794             }
1795
1796           /* If R is NaN, return zero and show we have an overflow.  */
1797           if (REAL_VALUE_ISNAN (r))
1798             {
1799               overflow = 1;
1800               high = 0;
1801               low = 0;
1802             }
1803
1804           /* See if R is less than the lower bound or greater than the
1805              upper bound.  */
1806
1807           if (! overflow)
1808             {
1809               tree lt = TYPE_MIN_VALUE (type);
1810               REAL_VALUE_TYPE l = real_value_from_int_cst (NULL_TREE, lt);
1811               if (REAL_VALUES_LESS (r, l))
1812                 {
1813                   overflow = 1;
1814                   high = TREE_INT_CST_HIGH (lt);
1815                   low = TREE_INT_CST_LOW (lt);
1816                 }
1817             }
1818
1819           if (! overflow)
1820             {
1821               tree ut = TYPE_MAX_VALUE (type);
1822               if (ut)
1823                 {
1824                   REAL_VALUE_TYPE u = real_value_from_int_cst (NULL_TREE, ut);
1825                   if (REAL_VALUES_LESS (u, r))
1826                     {
1827                       overflow = 1;
1828                       high = TREE_INT_CST_HIGH (ut);
1829                       low = TREE_INT_CST_LOW (ut);
1830                     }
1831                 }
1832             }
1833
1834           if (! overflow)
1835             REAL_VALUE_TO_INT (&low, &high, r);
1836
1837           t = build_int_2 (low, high);
1838           TREE_TYPE (t) = type;
1839           TREE_OVERFLOW (t)
1840             = TREE_OVERFLOW (arg1) | force_fit_type (t, overflow);
1841           TREE_CONSTANT_OVERFLOW (t)
1842             = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1843           return t;
1844         }
1845     }
1846   else if (TREE_CODE (type) == REAL_TYPE)
1847     {
1848       if (TREE_CODE (arg1) == INTEGER_CST)
1849         return build_real_from_int_cst (type, arg1);
1850       if (TREE_CODE (arg1) == REAL_CST)
1851         {
1852           if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
1853             {
1854               /* We make a copy of ARG1 so that we don't modify an
1855                  existing constant tree.  */
1856               t = copy_node (arg1);
1857               TREE_TYPE (t) = type;
1858               return t;
1859             }
1860
1861           t = build_real (type,
1862                           real_value_truncate (TYPE_MODE (type),
1863                                                TREE_REAL_CST (arg1)));
1864
1865           TREE_OVERFLOW (t)
1866             = TREE_OVERFLOW (arg1) | force_fit_type (t, 0);
1867           TREE_CONSTANT_OVERFLOW (t)
1868             = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1869           return t;
1870         }
1871     }
1872   return NULL_TREE;
1873 }
1874
1875 /* Convert expression ARG to type TYPE.  Used by the middle-end for
1876    simple conversions in preference to calling the front-end's convert.  */
1877
1878 static tree
1879 fold_convert (tree type, tree arg)
1880 {
1881   tree orig = TREE_TYPE (arg);
1882   tree tem;
1883
1884   if (type == orig)
1885     return arg;
1886
1887   if (TREE_CODE (arg) == ERROR_MARK
1888       || TREE_CODE (type) == ERROR_MARK
1889       || TREE_CODE (orig) == ERROR_MARK)
1890     return error_mark_node;
1891
1892   if (TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (orig))
1893     return fold (build1 (NOP_EXPR, type, arg));
1894
1895   if (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type))
1896     {
1897       if (TREE_CODE (arg) == INTEGER_CST)
1898         {
1899           tem = fold_convert_const (NOP_EXPR, type, arg);
1900           if (tem != NULL_TREE)
1901             return tem;
1902         }
1903       if (INTEGRAL_TYPE_P (orig) || POINTER_TYPE_P (orig))
1904         return fold (build1 (NOP_EXPR, type, arg));
1905       if (TREE_CODE (orig) == COMPLEX_TYPE)
1906         {
1907           tem = fold (build1 (REALPART_EXPR, TREE_TYPE (orig), arg));
1908           return fold_convert (type, tem);
1909         }
1910       if (TREE_CODE (orig) == VECTOR_TYPE
1911           && GET_MODE_SIZE (TYPE_MODE (type))
1912              == GET_MODE_SIZE (TYPE_MODE (orig)))
1913         return fold (build1 (NOP_EXPR, type, arg));
1914     }
1915   else if (TREE_CODE (type) == REAL_TYPE)
1916     {
1917       if (TREE_CODE (arg) == INTEGER_CST)
1918         {
1919           tem = fold_convert_const (FLOAT_EXPR, type, arg);
1920           if (tem != NULL_TREE)
1921             return tem;
1922         }
1923       else if (TREE_CODE (arg) == REAL_CST)
1924         {
1925           tem = fold_convert_const (NOP_EXPR, type, arg);
1926           if (tem != NULL_TREE)
1927             return tem;
1928         }
1929
1930       if (INTEGRAL_TYPE_P (orig) || POINTER_TYPE_P (orig))
1931         return fold (build1 (FLOAT_EXPR, type, arg));
1932       if (TREE_CODE (orig) == REAL_TYPE)
1933         return fold (build1 (flag_float_store ? CONVERT_EXPR : NOP_EXPR,
1934                              type, arg));
1935       if (TREE_CODE (orig) == COMPLEX_TYPE)
1936         {
1937           tem = fold (build1 (REALPART_EXPR, TREE_TYPE (orig), arg));
1938           return fold_convert (type, tem);
1939         }
1940     }
1941   else if (TREE_CODE (type) == COMPLEX_TYPE)
1942     {
1943       if (INTEGRAL_TYPE_P (orig)
1944           || POINTER_TYPE_P (orig)
1945           || TREE_CODE (orig) == REAL_TYPE)
1946         return build (COMPLEX_EXPR, type,
1947                       fold_convert (TREE_TYPE (type), arg),
1948                       fold_convert (TREE_TYPE (type), integer_zero_node));
1949       if (TREE_CODE (orig) == COMPLEX_TYPE)
1950         {
1951           tree rpart, ipart;
1952
1953           if (TREE_CODE (arg) == COMPLEX_EXPR)
1954             {
1955               rpart = fold_convert (TREE_TYPE (type), TREE_OPERAND (arg, 0));
1956               ipart = fold_convert (TREE_TYPE (type), TREE_OPERAND (arg, 1));
1957               return fold (build (COMPLEX_EXPR, type, rpart, ipart));
1958             }
1959
1960           arg = save_expr (arg);
1961           rpart = fold (build1 (REALPART_EXPR, TREE_TYPE (orig), arg));
1962           ipart = fold (build1 (IMAGPART_EXPR, TREE_TYPE (orig), arg));
1963           rpart = fold_convert (TREE_TYPE (type), rpart);
1964           ipart = fold_convert (TREE_TYPE (type), ipart);
1965           return fold (build (COMPLEX_EXPR, type, rpart, ipart));
1966         }
1967     }
1968   else if (TREE_CODE (type) == VECTOR_TYPE)
1969     {
1970       if ((INTEGRAL_TYPE_P (orig) || POINTER_TYPE_P (orig))
1971           && GET_MODE_SIZE (TYPE_MODE (type))
1972              == GET_MODE_SIZE (TYPE_MODE (orig)))
1973         return fold (build1 (NOP_EXPR, type, arg));
1974       if (TREE_CODE (orig) == VECTOR_TYPE
1975           && GET_MODE_SIZE (TYPE_MODE (type))
1976              == GET_MODE_SIZE (TYPE_MODE (orig)))
1977         return fold (build1 (NOP_EXPR, type, arg));
1978     }
1979   else if (VOID_TYPE_P (type))
1980     return fold (build1 (CONVERT_EXPR, type, arg));
1981   abort ();
1982 }
1983 \f
1984 /* Return an expr equal to X but certainly not valid as an lvalue.  */
1985
1986 tree
1987 non_lvalue (tree x)
1988 {
1989   tree result;
1990
1991   /* These things are certainly not lvalues.  */
1992   if (TREE_CODE (x) == NON_LVALUE_EXPR
1993       || TREE_CODE (x) == INTEGER_CST
1994       || TREE_CODE (x) == REAL_CST
1995       || TREE_CODE (x) == STRING_CST
1996       || TREE_CODE (x) == ADDR_EXPR)
1997     return x;
1998
1999   result = build1 (NON_LVALUE_EXPR, TREE_TYPE (x), x);
2000   TREE_CONSTANT (result) = TREE_CONSTANT (x);
2001   return result;
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.
2138
2139    If ONLY_CONST is nonzero, 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 ONLY_CONST is zero, 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 int
2158 operand_equal_p (tree arg0, tree arg1, int only_const)
2159 {
2160   tree fndecl;
2161
2162   /* If either is ERROR_MARK, they aren't equal.  */
2163   if (TREE_CODE (arg0) == ERROR_MARK || TREE_CODE (arg1) == ERROR_MARK)
2164     return 0;
2165
2166   /* If both types don't have the same signedness, then we can't consider
2167      them equal.  We must check this before the STRIP_NOPS calls
2168      because they may change the signedness of the arguments.  */
2169   if (TYPE_UNSIGNED (TREE_TYPE (arg0)) != TYPE_UNSIGNED (TREE_TYPE (arg1)))
2170     return 0;
2171
2172   STRIP_NOPS (arg0);
2173   STRIP_NOPS (arg1);
2174
2175   if (TREE_CODE (arg0) != TREE_CODE (arg1)
2176       /* This is needed for conversions and for COMPONENT_REF.
2177          Might as well play it safe and always test this.  */
2178       || TREE_CODE (TREE_TYPE (arg0)) == ERROR_MARK
2179       || TREE_CODE (TREE_TYPE (arg1)) == ERROR_MARK
2180       || TYPE_MODE (TREE_TYPE (arg0)) != TYPE_MODE (TREE_TYPE (arg1)))
2181     return 0;
2182
2183   /* If ARG0 and ARG1 are the same SAVE_EXPR, they are necessarily equal.
2184      We don't care about side effects in that case because the SAVE_EXPR
2185      takes care of that for us. In all other cases, two expressions are
2186      equal if they have no side effects.  If we have two identical
2187      expressions with side effects that should be treated the same due
2188      to the only side effects being identical SAVE_EXPR's, that will
2189      be detected in the recursive calls below.  */
2190   if (arg0 == arg1 && ! only_const
2191       && (TREE_CODE (arg0) == SAVE_EXPR
2192           || (! TREE_SIDE_EFFECTS (arg0) && ! TREE_SIDE_EFFECTS (arg1))))
2193     return 1;
2194
2195   /* Next handle constant cases, those for which we can return 1 even
2196      if ONLY_CONST is set.  */
2197   if (TREE_CONSTANT (arg0) && TREE_CONSTANT (arg1))
2198     switch (TREE_CODE (arg0))
2199       {
2200       case INTEGER_CST:
2201         return (! TREE_CONSTANT_OVERFLOW (arg0)
2202                 && ! TREE_CONSTANT_OVERFLOW (arg1)
2203                 && tree_int_cst_equal (arg0, arg1));
2204
2205       case REAL_CST:
2206         return (! TREE_CONSTANT_OVERFLOW (arg0)
2207                 && ! TREE_CONSTANT_OVERFLOW (arg1)
2208                 && REAL_VALUES_IDENTICAL (TREE_REAL_CST (arg0),
2209                                           TREE_REAL_CST (arg1)));
2210
2211       case VECTOR_CST:
2212         {
2213           tree v1, v2;
2214
2215           if (TREE_CONSTANT_OVERFLOW (arg0)
2216               || TREE_CONSTANT_OVERFLOW (arg1))
2217             return 0;
2218
2219           v1 = TREE_VECTOR_CST_ELTS (arg0);
2220           v2 = TREE_VECTOR_CST_ELTS (arg1);
2221           while (v1 && v2)
2222             {
2223               if (!operand_equal_p (TREE_VALUE (v1), TREE_VALUE (v2),
2224                                     only_const))
2225                 return 0;
2226               v1 = TREE_CHAIN (v1);
2227               v2 = TREE_CHAIN (v2);
2228             }
2229
2230           return 1;
2231         }
2232
2233       case COMPLEX_CST:
2234         return (operand_equal_p (TREE_REALPART (arg0), TREE_REALPART (arg1),
2235                                  only_const)
2236                 && operand_equal_p (TREE_IMAGPART (arg0), TREE_IMAGPART (arg1),
2237                                     only_const));
2238
2239       case STRING_CST:
2240         return (TREE_STRING_LENGTH (arg0) == TREE_STRING_LENGTH (arg1)
2241                 && ! memcmp (TREE_STRING_POINTER (arg0),
2242                               TREE_STRING_POINTER (arg1),
2243                               TREE_STRING_LENGTH (arg0)));
2244
2245       case ADDR_EXPR:
2246         return operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0),
2247                                 0);
2248       default:
2249         break;
2250       }
2251
2252   if (only_const)
2253     return 0;
2254
2255   switch (TREE_CODE_CLASS (TREE_CODE (arg0)))
2256     {
2257     case '1':
2258       /* Two conversions are equal only if signedness and modes match.  */
2259       if ((TREE_CODE (arg0) == NOP_EXPR || TREE_CODE (arg0) == CONVERT_EXPR)
2260           && (TYPE_UNSIGNED (TREE_TYPE (arg0))
2261               != TYPE_UNSIGNED (TREE_TYPE (arg1))))
2262         return 0;
2263
2264       return operand_equal_p (TREE_OPERAND (arg0, 0),
2265                               TREE_OPERAND (arg1, 0), 0);
2266
2267     case '<':
2268     case '2':
2269       if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0)
2270           && operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1),
2271                               0))
2272         return 1;
2273
2274       /* For commutative ops, allow the other order.  */
2275       return (commutative_tree_code (TREE_CODE (arg0))
2276               && operand_equal_p (TREE_OPERAND (arg0, 0),
2277                                   TREE_OPERAND (arg1, 1), 0)
2278               && operand_equal_p (TREE_OPERAND (arg0, 1),
2279                                   TREE_OPERAND (arg1, 0), 0));
2280
2281     case 'r':
2282       /* If either of the pointer (or reference) expressions we are
2283          dereferencing contain a side effect, these cannot be equal.  */
2284       if (TREE_SIDE_EFFECTS (arg0)
2285           || TREE_SIDE_EFFECTS (arg1))
2286         return 0;
2287
2288       switch (TREE_CODE (arg0))
2289         {
2290         case INDIRECT_REF:
2291           return operand_equal_p (TREE_OPERAND (arg0, 0),
2292                                   TREE_OPERAND (arg1, 0), 0);
2293
2294         case COMPONENT_REF:
2295         case ARRAY_REF:
2296         case ARRAY_RANGE_REF:
2297           return (operand_equal_p (TREE_OPERAND (arg0, 0),
2298                                    TREE_OPERAND (arg1, 0), 0)
2299                   && operand_equal_p (TREE_OPERAND (arg0, 1),
2300                                       TREE_OPERAND (arg1, 1), 0));
2301
2302         case BIT_FIELD_REF:
2303           return (operand_equal_p (TREE_OPERAND (arg0, 0),
2304                                    TREE_OPERAND (arg1, 0), 0)
2305                   && operand_equal_p (TREE_OPERAND (arg0, 1),
2306                                       TREE_OPERAND (arg1, 1), 0)
2307                   && operand_equal_p (TREE_OPERAND (arg0, 2),
2308                                       TREE_OPERAND (arg1, 2), 0));
2309         default:
2310           return 0;
2311         }
2312
2313     case 'e':
2314       switch (TREE_CODE (arg0))
2315         {
2316         case ADDR_EXPR:
2317         case TRUTH_NOT_EXPR:
2318           return operand_equal_p (TREE_OPERAND (arg0, 0),
2319                                   TREE_OPERAND (arg1, 0), 0);
2320
2321         case RTL_EXPR:
2322           return rtx_equal_p (RTL_EXPR_RTL (arg0), RTL_EXPR_RTL (arg1));
2323
2324         case CALL_EXPR:
2325           /* If the CALL_EXPRs call different functions, then they
2326              clearly can not be equal.  */
2327           if (! operand_equal_p (TREE_OPERAND (arg0, 0),
2328                                  TREE_OPERAND (arg1, 0), 0))
2329             return 0;
2330
2331           /* Only consider const functions equivalent.  */
2332           fndecl = get_callee_fndecl (arg0);
2333           if (fndecl == NULL_TREE
2334               || ! (flags_from_decl_or_type (fndecl) & ECF_CONST))
2335             return 0;
2336
2337           /* Now see if all the arguments are the same.  operand_equal_p
2338              does not handle TREE_LIST, so we walk the operands here
2339              feeding them to operand_equal_p.  */
2340           arg0 = TREE_OPERAND (arg0, 1);
2341           arg1 = TREE_OPERAND (arg1, 1);
2342           while (arg0 && arg1)
2343             {
2344               if (! operand_equal_p (TREE_VALUE (arg0), TREE_VALUE (arg1), 0))
2345                 return 0;
2346
2347               arg0 = TREE_CHAIN (arg0);
2348               arg1 = TREE_CHAIN (arg1);
2349             }
2350
2351           /* If we get here and both argument lists are exhausted
2352              then the CALL_EXPRs are equal.  */
2353           return ! (arg0 || arg1);
2354
2355         default:
2356           return 0;
2357         }
2358
2359     case 'd':
2360         /* Consider __builtin_sqrt equal to sqrt.  */
2361         return TREE_CODE (arg0) == FUNCTION_DECL
2362                && DECL_BUILT_IN (arg0) && DECL_BUILT_IN (arg1)
2363                && DECL_BUILT_IN_CLASS (arg0) == DECL_BUILT_IN_CLASS (arg1)
2364                && DECL_FUNCTION_CODE (arg0) == DECL_FUNCTION_CODE (arg1);
2365
2366     default:
2367       return 0;
2368     }
2369 }
2370 \f
2371 /* Similar to operand_equal_p, but see if ARG0 might have been made by
2372    shorten_compare from ARG1 when ARG1 was being compared with OTHER.
2373
2374    When in doubt, return 0.  */
2375
2376 static int
2377 operand_equal_for_comparison_p (tree arg0, tree arg1, tree other)
2378 {
2379   int unsignedp1, unsignedpo;
2380   tree primarg0, primarg1, primother;
2381   unsigned int correct_width;
2382
2383   if (operand_equal_p (arg0, arg1, 0))
2384     return 1;
2385
2386   if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0))
2387       || ! INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
2388     return 0;
2389
2390   /* Discard any conversions that don't change the modes of ARG0 and ARG1
2391      and see if the inner values are the same.  This removes any
2392      signedness comparison, which doesn't matter here.  */
2393   primarg0 = arg0, primarg1 = arg1;
2394   STRIP_NOPS (primarg0);
2395   STRIP_NOPS (primarg1);
2396   if (operand_equal_p (primarg0, primarg1, 0))
2397     return 1;
2398
2399   /* Duplicate what shorten_compare does to ARG1 and see if that gives the
2400      actual comparison operand, ARG0.
2401
2402      First throw away any conversions to wider types
2403      already present in the operands.  */
2404
2405   primarg1 = get_narrower (arg1, &unsignedp1);
2406   primother = get_narrower (other, &unsignedpo);
2407
2408   correct_width = TYPE_PRECISION (TREE_TYPE (arg1));
2409   if (unsignedp1 == unsignedpo
2410       && TYPE_PRECISION (TREE_TYPE (primarg1)) < correct_width
2411       && TYPE_PRECISION (TREE_TYPE (primother)) < correct_width)
2412     {
2413       tree type = TREE_TYPE (arg0);
2414
2415       /* Make sure shorter operand is extended the right way
2416          to match the longer operand.  */
2417       primarg1 = fold_convert (lang_hooks.types.signed_or_unsigned_type
2418                                (unsignedp1, TREE_TYPE (primarg1)), primarg1);
2419
2420       if (operand_equal_p (arg0, fold_convert (type, primarg1), 0))
2421         return 1;
2422     }
2423
2424   return 0;
2425 }
2426 \f
2427 /* See if ARG is an expression that is either a comparison or is performing
2428    arithmetic on comparisons.  The comparisons must only be comparing
2429    two different values, which will be stored in *CVAL1 and *CVAL2; if
2430    they are nonzero it means that some operands have already been found.
2431    No variables may be used anywhere else in the expression except in the
2432    comparisons.  If SAVE_P is true it means we removed a SAVE_EXPR around
2433    the expression and save_expr needs to be called with CVAL1 and CVAL2.
2434
2435    If this is true, return 1.  Otherwise, return zero.  */
2436
2437 static int
2438 twoval_comparison_p (tree arg, tree *cval1, tree *cval2, int *save_p)
2439 {
2440   enum tree_code code = TREE_CODE (arg);
2441   char class = TREE_CODE_CLASS (code);
2442
2443   /* We can handle some of the 'e' cases here.  */
2444   if (class == 'e' && code == TRUTH_NOT_EXPR)
2445     class = '1';
2446   else if (class == 'e'
2447            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR
2448                || code == COMPOUND_EXPR))
2449     class = '2';
2450
2451   else if (class == 'e' && code == SAVE_EXPR && SAVE_EXPR_RTL (arg) == 0
2452            && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg, 0)))
2453     {
2454       /* If we've already found a CVAL1 or CVAL2, this expression is
2455          two complex to handle.  */
2456       if (*cval1 || *cval2)
2457         return 0;
2458
2459       class = '1';
2460       *save_p = 1;
2461     }
2462
2463   switch (class)
2464     {
2465     case '1':
2466       return twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p);
2467
2468     case '2':
2469       return (twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p)
2470               && twoval_comparison_p (TREE_OPERAND (arg, 1),
2471                                       cval1, cval2, save_p));
2472
2473     case 'c':
2474       return 1;
2475
2476     case 'e':
2477       if (code == COND_EXPR)
2478         return (twoval_comparison_p (TREE_OPERAND (arg, 0),
2479                                      cval1, cval2, save_p)
2480                 && twoval_comparison_p (TREE_OPERAND (arg, 1),
2481                                         cval1, cval2, save_p)
2482                 && twoval_comparison_p (TREE_OPERAND (arg, 2),
2483                                         cval1, cval2, save_p));
2484       return 0;
2485
2486     case '<':
2487       /* First see if we can handle the first operand, then the second.  For
2488          the second operand, we know *CVAL1 can't be zero.  It must be that
2489          one side of the comparison is each of the values; test for the
2490          case where this isn't true by failing if the two operands
2491          are the same.  */
2492
2493       if (operand_equal_p (TREE_OPERAND (arg, 0),
2494                            TREE_OPERAND (arg, 1), 0))
2495         return 0;
2496
2497       if (*cval1 == 0)
2498         *cval1 = TREE_OPERAND (arg, 0);
2499       else if (operand_equal_p (*cval1, TREE_OPERAND (arg, 0), 0))
2500         ;
2501       else if (*cval2 == 0)
2502         *cval2 = TREE_OPERAND (arg, 0);
2503       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 0), 0))
2504         ;
2505       else
2506         return 0;
2507
2508       if (operand_equal_p (*cval1, TREE_OPERAND (arg, 1), 0))
2509         ;
2510       else if (*cval2 == 0)
2511         *cval2 = TREE_OPERAND (arg, 1);
2512       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 1), 0))
2513         ;
2514       else
2515         return 0;
2516
2517       return 1;
2518
2519     default:
2520       return 0;
2521     }
2522 }
2523 \f
2524 /* ARG is a tree that is known to contain just arithmetic operations and
2525    comparisons.  Evaluate the operations in the tree substituting NEW0 for
2526    any occurrence of OLD0 as an operand of a comparison and likewise for
2527    NEW1 and OLD1.  */
2528
2529 static tree
2530 eval_subst (tree arg, tree old0, tree new0, tree old1, tree new1)
2531 {
2532   tree type = TREE_TYPE (arg);
2533   enum tree_code code = TREE_CODE (arg);
2534   char class = TREE_CODE_CLASS (code);
2535
2536   /* We can handle some of the 'e' cases here.  */
2537   if (class == 'e' && code == TRUTH_NOT_EXPR)
2538     class = '1';
2539   else if (class == 'e'
2540            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
2541     class = '2';
2542
2543   switch (class)
2544     {
2545     case '1':
2546       return fold (build1 (code, type,
2547                            eval_subst (TREE_OPERAND (arg, 0),
2548                                        old0, new0, old1, new1)));
2549
2550     case '2':
2551       return fold (build (code, type,
2552                           eval_subst (TREE_OPERAND (arg, 0),
2553                                       old0, new0, old1, new1),
2554                           eval_subst (TREE_OPERAND (arg, 1),
2555                                       old0, new0, old1, new1)));
2556
2557     case 'e':
2558       switch (code)
2559         {
2560         case SAVE_EXPR:
2561           return eval_subst (TREE_OPERAND (arg, 0), old0, new0, old1, new1);
2562
2563         case COMPOUND_EXPR:
2564           return eval_subst (TREE_OPERAND (arg, 1), old0, new0, old1, new1);
2565
2566         case COND_EXPR:
2567           return fold (build (code, type,
2568                               eval_subst (TREE_OPERAND (arg, 0),
2569                                           old0, new0, old1, new1),
2570                               eval_subst (TREE_OPERAND (arg, 1),
2571                                           old0, new0, old1, new1),
2572                               eval_subst (TREE_OPERAND (arg, 2),
2573                                           old0, new0, old1, new1)));
2574         default:
2575           break;
2576         }
2577       /* Fall through - ???  */
2578
2579     case '<':
2580       {
2581         tree arg0 = TREE_OPERAND (arg, 0);
2582         tree arg1 = TREE_OPERAND (arg, 1);
2583
2584         /* We need to check both for exact equality and tree equality.  The
2585            former will be true if the operand has a side-effect.  In that
2586            case, we know the operand occurred exactly once.  */
2587
2588         if (arg0 == old0 || operand_equal_p (arg0, old0, 0))
2589           arg0 = new0;
2590         else if (arg0 == old1 || operand_equal_p (arg0, old1, 0))
2591           arg0 = new1;
2592
2593         if (arg1 == old0 || operand_equal_p (arg1, old0, 0))
2594           arg1 = new0;
2595         else if (arg1 == old1 || operand_equal_p (arg1, old1, 0))
2596           arg1 = new1;
2597
2598         return fold (build (code, type, arg0, arg1));
2599       }
2600
2601     default:
2602       return arg;
2603     }
2604 }
2605 \f
2606 /* Return a tree for the case when the result of an expression is RESULT
2607    converted to TYPE and OMITTED was previously an operand of the expression
2608    but is now not needed (e.g., we folded OMITTED * 0).
2609
2610    If OMITTED has side effects, we must evaluate it.  Otherwise, just do
2611    the conversion of RESULT to TYPE.  */
2612
2613 tree
2614 omit_one_operand (tree type, tree result, tree omitted)
2615 {
2616   tree t = fold_convert (type, result);
2617
2618   if (TREE_SIDE_EFFECTS (omitted))
2619     return build (COMPOUND_EXPR, type, omitted, t);
2620
2621   return non_lvalue (t);
2622 }
2623
2624 /* Similar, but call pedantic_non_lvalue instead of non_lvalue.  */
2625
2626 static tree
2627 pedantic_omit_one_operand (tree type, tree result, tree omitted)
2628 {
2629   tree t = fold_convert (type, result);
2630
2631   if (TREE_SIDE_EFFECTS (omitted))
2632     return build (COMPOUND_EXPR, type, omitted, t);
2633
2634   return pedantic_non_lvalue (t);
2635 }
2636 \f
2637 /* Return a simplified tree node for the truth-negation of ARG.  This
2638    never alters ARG itself.  We assume that ARG is an operation that
2639    returns a truth value (0 or 1).  */
2640
2641 tree
2642 invert_truthvalue (tree arg)
2643 {
2644   tree type = TREE_TYPE (arg);
2645   enum tree_code code = TREE_CODE (arg);
2646
2647   if (code == ERROR_MARK)
2648     return arg;
2649
2650   /* If this is a comparison, we can simply invert it, except for
2651      floating-point non-equality comparisons, in which case we just
2652      enclose a TRUTH_NOT_EXPR around what we have.  */
2653
2654   if (TREE_CODE_CLASS (code) == '<')
2655     {
2656       if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg, 0)))
2657           && !flag_unsafe_math_optimizations
2658           && code != NE_EXPR
2659           && code != EQ_EXPR)
2660         return build1 (TRUTH_NOT_EXPR, type, arg);
2661       else if (code == UNORDERED_EXPR
2662                || code == ORDERED_EXPR
2663                || code == UNEQ_EXPR
2664                || code == UNLT_EXPR
2665                || code == UNLE_EXPR
2666                || code == UNGT_EXPR
2667                || code == UNGE_EXPR)
2668         return build1 (TRUTH_NOT_EXPR, type, arg);
2669       else
2670         return build (invert_tree_comparison (code), type,
2671                       TREE_OPERAND (arg, 0), TREE_OPERAND (arg, 1));
2672     }
2673
2674   switch (code)
2675     {
2676     case INTEGER_CST:
2677       return fold_convert (type, build_int_2 (integer_zerop (arg), 0));
2678
2679     case TRUTH_AND_EXPR:
2680       return build (TRUTH_OR_EXPR, type,
2681                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2682                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2683
2684     case TRUTH_OR_EXPR:
2685       return build (TRUTH_AND_EXPR, type,
2686                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2687                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2688
2689     case TRUTH_XOR_EXPR:
2690       /* Here we can invert either operand.  We invert the first operand
2691          unless the second operand is a TRUTH_NOT_EXPR in which case our
2692          result is the XOR of the first operand with the inside of the
2693          negation of the second operand.  */
2694
2695       if (TREE_CODE (TREE_OPERAND (arg, 1)) == TRUTH_NOT_EXPR)
2696         return build (TRUTH_XOR_EXPR, type, TREE_OPERAND (arg, 0),
2697                       TREE_OPERAND (TREE_OPERAND (arg, 1), 0));
2698       else
2699         return build (TRUTH_XOR_EXPR, type,
2700                       invert_truthvalue (TREE_OPERAND (arg, 0)),
2701                       TREE_OPERAND (arg, 1));
2702
2703     case TRUTH_ANDIF_EXPR:
2704       return build (TRUTH_ORIF_EXPR, type,
2705                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2706                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2707
2708     case TRUTH_ORIF_EXPR:
2709       return build (TRUTH_ANDIF_EXPR, type,
2710                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2711                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2712
2713     case TRUTH_NOT_EXPR:
2714       return TREE_OPERAND (arg, 0);
2715
2716     case COND_EXPR:
2717       return build (COND_EXPR, type, TREE_OPERAND (arg, 0),
2718                     invert_truthvalue (TREE_OPERAND (arg, 1)),
2719                     invert_truthvalue (TREE_OPERAND (arg, 2)));
2720
2721     case COMPOUND_EXPR:
2722       return build (COMPOUND_EXPR, type, TREE_OPERAND (arg, 0),
2723                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2724
2725     case NON_LVALUE_EXPR:
2726       return invert_truthvalue (TREE_OPERAND (arg, 0));
2727
2728     case NOP_EXPR:
2729     case CONVERT_EXPR:
2730     case FLOAT_EXPR:
2731       return build1 (TREE_CODE (arg), type,
2732                      invert_truthvalue (TREE_OPERAND (arg, 0)));
2733
2734     case BIT_AND_EXPR:
2735       if (!integer_onep (TREE_OPERAND (arg, 1)))
2736         break;
2737       return build (EQ_EXPR, type, arg,
2738                     fold_convert (type, integer_zero_node));
2739
2740     case SAVE_EXPR:
2741       return build1 (TRUTH_NOT_EXPR, type, arg);
2742
2743     case CLEANUP_POINT_EXPR:
2744       return build1 (CLEANUP_POINT_EXPR, type,
2745                      invert_truthvalue (TREE_OPERAND (arg, 0)));
2746
2747     default:
2748       break;
2749     }
2750   if (TREE_CODE (TREE_TYPE (arg)) != BOOLEAN_TYPE)
2751     abort ();
2752   return build1 (TRUTH_NOT_EXPR, type, arg);
2753 }
2754
2755 /* Given a bit-wise operation CODE applied to ARG0 and ARG1, see if both
2756    operands are another bit-wise operation with a common input.  If so,
2757    distribute the bit operations to save an operation and possibly two if
2758    constants are involved.  For example, convert
2759         (A | B) & (A | C) into A | (B & C)
2760    Further simplification will occur if B and C are constants.
2761
2762    If this optimization cannot be done, 0 will be returned.  */
2763
2764 static tree
2765 distribute_bit_expr (enum tree_code code, tree type, tree arg0, tree arg1)
2766 {
2767   tree common;
2768   tree left, right;
2769
2770   if (TREE_CODE (arg0) != TREE_CODE (arg1)
2771       || TREE_CODE (arg0) == code
2772       || (TREE_CODE (arg0) != BIT_AND_EXPR
2773           && TREE_CODE (arg0) != BIT_IOR_EXPR))
2774     return 0;
2775
2776   if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0))
2777     {
2778       common = TREE_OPERAND (arg0, 0);
2779       left = TREE_OPERAND (arg0, 1);
2780       right = TREE_OPERAND (arg1, 1);
2781     }
2782   else if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 1), 0))
2783     {
2784       common = TREE_OPERAND (arg0, 0);
2785       left = TREE_OPERAND (arg0, 1);
2786       right = TREE_OPERAND (arg1, 0);
2787     }
2788   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 0), 0))
2789     {
2790       common = TREE_OPERAND (arg0, 1);
2791       left = TREE_OPERAND (arg0, 0);
2792       right = TREE_OPERAND (arg1, 1);
2793     }
2794   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1), 0))
2795     {
2796       common = TREE_OPERAND (arg0, 1);
2797       left = TREE_OPERAND (arg0, 0);
2798       right = TREE_OPERAND (arg1, 0);
2799     }
2800   else
2801     return 0;
2802
2803   return fold (build (TREE_CODE (arg0), type, common,
2804                       fold (build (code, type, left, right))));
2805 }
2806 \f
2807 /* Return a BIT_FIELD_REF of type TYPE to refer to BITSIZE bits of INNER
2808    starting at BITPOS.  The field is unsigned if UNSIGNEDP is nonzero.  */
2809
2810 static tree
2811 make_bit_field_ref (tree inner, tree type, int bitsize, int bitpos,
2812                     int unsignedp)
2813 {
2814   tree result = build (BIT_FIELD_REF, type, inner,
2815                        size_int (bitsize), bitsize_int (bitpos));
2816
2817   BIT_FIELD_REF_UNSIGNED (result) = unsignedp;
2818
2819   return result;
2820 }
2821
2822 /* Optimize a bit-field compare.
2823
2824    There are two cases:  First is a compare against a constant and the
2825    second is a comparison of two items where the fields are at the same
2826    bit position relative to the start of a chunk (byte, halfword, word)
2827    large enough to contain it.  In these cases we can avoid the shift
2828    implicit in bitfield extractions.
2829
2830    For constants, we emit a compare of the shifted constant with the
2831    BIT_AND_EXPR of a mask and a byte, halfword, or word of the operand being
2832    compared.  For two fields at the same position, we do the ANDs with the
2833    similar mask and compare the result of the ANDs.
2834
2835    CODE is the comparison code, known to be either NE_EXPR or EQ_EXPR.
2836    COMPARE_TYPE is the type of the comparison, and LHS and RHS
2837    are the left and right operands of the comparison, respectively.
2838
2839    If the optimization described above can be done, we return the resulting
2840    tree.  Otherwise we return zero.  */
2841
2842 static tree
2843 optimize_bit_field_compare (enum tree_code code, tree compare_type,
2844                             tree lhs, tree rhs)
2845 {
2846   HOST_WIDE_INT lbitpos, lbitsize, rbitpos, rbitsize, nbitpos, nbitsize;
2847   tree type = TREE_TYPE (lhs);
2848   tree signed_type, unsigned_type;
2849   int const_p = TREE_CODE (rhs) == INTEGER_CST;
2850   enum machine_mode lmode, rmode, nmode;
2851   int lunsignedp, runsignedp;
2852   int lvolatilep = 0, rvolatilep = 0;
2853   tree linner, rinner = NULL_TREE;
2854   tree mask;
2855   tree offset;
2856
2857   /* Get all the information about the extractions being done.  If the bit size
2858      if the same as the size of the underlying object, we aren't doing an
2859      extraction at all and so can do nothing.  We also don't want to
2860      do anything if the inner expression is a PLACEHOLDER_EXPR since we
2861      then will no longer be able to replace it.  */
2862   linner = get_inner_reference (lhs, &lbitsize, &lbitpos, &offset, &lmode,
2863                                 &lunsignedp, &lvolatilep);
2864   if (linner == lhs || lbitsize == GET_MODE_BITSIZE (lmode) || lbitsize < 0
2865       || offset != 0 || TREE_CODE (linner) == PLACEHOLDER_EXPR)
2866     return 0;
2867
2868  if (!const_p)
2869    {
2870      /* If this is not a constant, we can only do something if bit positions,
2871         sizes, and signedness are the same.  */
2872      rinner = get_inner_reference (rhs, &rbitsize, &rbitpos, &offset, &rmode,
2873                                    &runsignedp, &rvolatilep);
2874
2875      if (rinner == rhs || lbitpos != rbitpos || lbitsize != rbitsize
2876          || lunsignedp != runsignedp || offset != 0
2877          || TREE_CODE (rinner) == PLACEHOLDER_EXPR)
2878        return 0;
2879    }
2880
2881   /* See if we can find a mode to refer to this field.  We should be able to,
2882      but fail if we can't.  */
2883   nmode = get_best_mode (lbitsize, lbitpos,
2884                          const_p ? TYPE_ALIGN (TREE_TYPE (linner))
2885                          : MIN (TYPE_ALIGN (TREE_TYPE (linner)),
2886                                 TYPE_ALIGN (TREE_TYPE (rinner))),
2887                          word_mode, lvolatilep || rvolatilep);
2888   if (nmode == VOIDmode)
2889     return 0;
2890
2891   /* Set signed and unsigned types of the precision of this mode for the
2892      shifts below.  */
2893   signed_type = lang_hooks.types.type_for_mode (nmode, 0);
2894   unsigned_type = lang_hooks.types.type_for_mode (nmode, 1);
2895
2896   /* Compute the bit position and size for the new reference and our offset
2897      within it. If the new reference is the same size as the original, we
2898      won't optimize anything, so return zero.  */
2899   nbitsize = GET_MODE_BITSIZE (nmode);
2900   nbitpos = lbitpos & ~ (nbitsize - 1);
2901   lbitpos -= nbitpos;
2902   if (nbitsize == lbitsize)
2903     return 0;
2904
2905   if (BYTES_BIG_ENDIAN)
2906     lbitpos = nbitsize - lbitsize - lbitpos;
2907
2908   /* Make the mask to be used against the extracted field.  */
2909   mask = build_int_2 (~0, ~0);
2910   TREE_TYPE (mask) = unsigned_type;
2911   force_fit_type (mask, 0);
2912   mask = fold_convert (unsigned_type, mask);
2913   mask = const_binop (LSHIFT_EXPR, mask, size_int (nbitsize - lbitsize), 0);
2914   mask = const_binop (RSHIFT_EXPR, mask,
2915                       size_int (nbitsize - lbitsize - lbitpos), 0);
2916
2917   if (! const_p)
2918     /* If not comparing with constant, just rework the comparison
2919        and return.  */
2920     return build (code, compare_type,
2921                   build (BIT_AND_EXPR, unsigned_type,
2922                          make_bit_field_ref (linner, unsigned_type,
2923                                              nbitsize, nbitpos, 1),
2924                          mask),
2925                   build (BIT_AND_EXPR, unsigned_type,
2926                          make_bit_field_ref (rinner, unsigned_type,
2927                                              nbitsize, nbitpos, 1),
2928                          mask));
2929
2930   /* Otherwise, we are handling the constant case. See if the constant is too
2931      big for the field.  Warn and return a tree of for 0 (false) if so.  We do
2932      this not only for its own sake, but to avoid having to test for this
2933      error case below.  If we didn't, we might generate wrong code.
2934
2935      For unsigned fields, the constant shifted right by the field length should
2936      be all zero.  For signed fields, the high-order bits should agree with
2937      the sign bit.  */
2938
2939   if (lunsignedp)
2940     {
2941       if (! integer_zerop (const_binop (RSHIFT_EXPR,
2942                                         fold_convert (unsigned_type, rhs),
2943                                         size_int (lbitsize), 0)))
2944         {
2945           warning ("comparison is always %d due to width of bit-field",
2946                    code == NE_EXPR);
2947           return fold_convert (compare_type,
2948                                (code == NE_EXPR
2949                                 ? integer_one_node : integer_zero_node));
2950         }
2951     }
2952   else
2953     {
2954       tree tem = const_binop (RSHIFT_EXPR, fold_convert (signed_type, rhs),
2955                               size_int (lbitsize - 1), 0);
2956       if (! integer_zerop (tem) && ! integer_all_onesp (tem))
2957         {
2958           warning ("comparison is always %d due to width of bit-field",
2959                    code == NE_EXPR);
2960           return fold_convert (compare_type,
2961                                (code == NE_EXPR
2962                                 ? integer_one_node : integer_zero_node));
2963         }
2964     }
2965
2966   /* Single-bit compares should always be against zero.  */
2967   if (lbitsize == 1 && ! integer_zerop (rhs))
2968     {
2969       code = code == EQ_EXPR ? NE_EXPR : EQ_EXPR;
2970       rhs = fold_convert (type, integer_zero_node);
2971     }
2972
2973   /* Make a new bitfield reference, shift the constant over the
2974      appropriate number of bits and mask it with the computed mask
2975      (in case this was a signed field).  If we changed it, make a new one.  */
2976   lhs = make_bit_field_ref (linner, unsigned_type, nbitsize, nbitpos, 1);
2977   if (lvolatilep)
2978     {
2979       TREE_SIDE_EFFECTS (lhs) = 1;
2980       TREE_THIS_VOLATILE (lhs) = 1;
2981     }
2982
2983   rhs = fold (const_binop (BIT_AND_EXPR,
2984                            const_binop (LSHIFT_EXPR,
2985                                         fold_convert (unsigned_type, rhs),
2986                                         size_int (lbitpos), 0),
2987                            mask, 0));
2988
2989   return build (code, compare_type,
2990                 build (BIT_AND_EXPR, unsigned_type, lhs, mask),
2991                 rhs);
2992 }
2993 \f
2994 /* Subroutine for fold_truthop: decode a field reference.
2995
2996    If EXP is a comparison reference, we return the innermost reference.
2997
2998    *PBITSIZE is set to the number of bits in the reference, *PBITPOS is
2999    set to the starting bit number.
3000
3001    If the innermost field can be completely contained in a mode-sized
3002    unit, *PMODE is set to that mode.  Otherwise, it is set to VOIDmode.
3003
3004    *PVOLATILEP is set to 1 if the any expression encountered is volatile;
3005    otherwise it is not changed.
3006
3007    *PUNSIGNEDP is set to the signedness of the field.
3008
3009    *PMASK is set to the mask used.  This is either contained in a
3010    BIT_AND_EXPR or derived from the width of the field.
3011
3012    *PAND_MASK is set to the mask found in a BIT_AND_EXPR, if any.
3013
3014    Return 0 if this is not a component reference or is one that we can't
3015    do anything with.  */
3016
3017 static tree
3018 decode_field_reference (tree exp, HOST_WIDE_INT *pbitsize,
3019                         HOST_WIDE_INT *pbitpos, enum machine_mode *pmode,
3020                         int *punsignedp, int *pvolatilep,
3021                         tree *pmask, tree *pand_mask)
3022 {
3023   tree outer_type = 0;
3024   tree and_mask = 0;
3025   tree mask, inner, offset;
3026   tree unsigned_type;
3027   unsigned int precision;
3028
3029   /* All the optimizations using this function assume integer fields.
3030      There are problems with FP fields since the type_for_size call
3031      below can fail for, e.g., XFmode.  */
3032   if (! INTEGRAL_TYPE_P (TREE_TYPE (exp)))
3033     return 0;
3034
3035   /* We are interested in the bare arrangement of bits, so strip everything
3036      that doesn't affect the machine mode.  However, record the type of the
3037      outermost expression if it may matter below.  */
3038   if (TREE_CODE (exp) == NOP_EXPR
3039       || TREE_CODE (exp) == CONVERT_EXPR
3040       || TREE_CODE (exp) == NON_LVALUE_EXPR)
3041     outer_type = TREE_TYPE (exp);
3042   STRIP_NOPS (exp);
3043
3044   if (TREE_CODE (exp) == BIT_AND_EXPR)
3045     {
3046       and_mask = TREE_OPERAND (exp, 1);
3047       exp = TREE_OPERAND (exp, 0);
3048       STRIP_NOPS (exp); STRIP_NOPS (and_mask);
3049       if (TREE_CODE (and_mask) != INTEGER_CST)
3050         return 0;
3051     }
3052
3053   inner = get_inner_reference (exp, pbitsize, pbitpos, &offset, pmode,
3054                                punsignedp, pvolatilep);
3055   if ((inner == exp && and_mask == 0)
3056       || *pbitsize < 0 || offset != 0
3057       || TREE_CODE (inner) == PLACEHOLDER_EXPR)
3058     return 0;
3059
3060   /* If the number of bits in the reference is the same as the bitsize of
3061      the outer type, then the outer type gives the signedness. Otherwise
3062      (in case of a small bitfield) the signedness is unchanged.  */
3063   if (outer_type && *pbitsize == tree_low_cst (TYPE_SIZE (outer_type), 1))
3064     *punsignedp = TYPE_UNSIGNED (outer_type);
3065
3066   /* Compute the mask to access the bitfield.  */
3067   unsigned_type = lang_hooks.types.type_for_size (*pbitsize, 1);
3068   precision = TYPE_PRECISION (unsigned_type);
3069
3070   mask = build_int_2 (~0, ~0);
3071   TREE_TYPE (mask) = unsigned_type;
3072   force_fit_type (mask, 0);
3073   mask = const_binop (LSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
3074   mask = const_binop (RSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
3075
3076   /* Merge it with the mask we found in the BIT_AND_EXPR, if any.  */
3077   if (and_mask != 0)
3078     mask = fold (build (BIT_AND_EXPR, unsigned_type,
3079                         fold_convert (unsigned_type, and_mask), mask));
3080
3081   *pmask = mask;
3082   *pand_mask = and_mask;
3083   return inner;
3084 }
3085
3086 /* Return nonzero if MASK represents a mask of SIZE ones in the low-order
3087    bit positions.  */
3088
3089 static int
3090 all_ones_mask_p (tree mask, int size)
3091 {
3092   tree type = TREE_TYPE (mask);
3093   unsigned int precision = TYPE_PRECISION (type);
3094   tree tmask;
3095
3096   tmask = build_int_2 (~0, ~0);
3097   TREE_TYPE (tmask) = lang_hooks.types.signed_type (type);
3098   force_fit_type (tmask, 0);
3099   return
3100     tree_int_cst_equal (mask,
3101                         const_binop (RSHIFT_EXPR,
3102                                      const_binop (LSHIFT_EXPR, tmask,
3103                                                   size_int (precision - size),
3104                                                   0),
3105                                      size_int (precision - size), 0));
3106 }
3107
3108 /* Subroutine for fold: determine if VAL is the INTEGER_CONST that
3109    represents the sign bit of EXP's type.  If EXP represents a sign
3110    or zero extension, also test VAL against the unextended type.
3111    The return value is the (sub)expression whose sign bit is VAL,
3112    or NULL_TREE otherwise.  */
3113
3114 static tree
3115 sign_bit_p (tree exp, tree val)
3116 {
3117   unsigned HOST_WIDE_INT mask_lo, lo;
3118   HOST_WIDE_INT mask_hi, hi;
3119   int width;
3120   tree t;
3121
3122   /* Tree EXP must have an integral type.  */
3123   t = TREE_TYPE (exp);
3124   if (! INTEGRAL_TYPE_P (t))
3125     return NULL_TREE;
3126
3127   /* Tree VAL must be an integer constant.  */
3128   if (TREE_CODE (val) != INTEGER_CST
3129       || TREE_CONSTANT_OVERFLOW (val))
3130     return NULL_TREE;
3131
3132   width = TYPE_PRECISION (t);
3133   if (width > HOST_BITS_PER_WIDE_INT)
3134     {
3135       hi = (unsigned HOST_WIDE_INT) 1 << (width - HOST_BITS_PER_WIDE_INT - 1);
3136       lo = 0;
3137
3138       mask_hi = ((unsigned HOST_WIDE_INT) -1
3139                  >> (2 * HOST_BITS_PER_WIDE_INT - width));
3140       mask_lo = -1;
3141     }
3142   else
3143     {
3144       hi = 0;
3145       lo = (unsigned HOST_WIDE_INT) 1 << (width - 1);
3146
3147       mask_hi = 0;
3148       mask_lo = ((unsigned HOST_WIDE_INT) -1
3149                  >> (HOST_BITS_PER_WIDE_INT - width));
3150     }
3151
3152   /* We mask off those bits beyond TREE_TYPE (exp) so that we can
3153      treat VAL as if it were unsigned.  */
3154   if ((TREE_INT_CST_HIGH (val) & mask_hi) == hi
3155       && (TREE_INT_CST_LOW (val) & mask_lo) == lo)
3156     return exp;
3157
3158   /* Handle extension from a narrower type.  */
3159   if (TREE_CODE (exp) == NOP_EXPR
3160       && TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (exp, 0))) < width)
3161     return sign_bit_p (TREE_OPERAND (exp, 0), val);
3162
3163   return NULL_TREE;
3164 }
3165
3166 /* Subroutine for fold_truthop: determine if an operand is simple enough
3167    to be evaluated unconditionally.  */
3168
3169 static int
3170 simple_operand_p (tree exp)
3171 {
3172   /* Strip any conversions that don't change the machine mode.  */
3173   while ((TREE_CODE (exp) == NOP_EXPR
3174           || TREE_CODE (exp) == CONVERT_EXPR)
3175          && (TYPE_MODE (TREE_TYPE (exp))
3176              == TYPE_MODE (TREE_TYPE (TREE_OPERAND (exp, 0)))))
3177     exp = TREE_OPERAND (exp, 0);
3178
3179   return (TREE_CODE_CLASS (TREE_CODE (exp)) == 'c'
3180           || (DECL_P (exp)
3181               && ! TREE_ADDRESSABLE (exp)
3182               && ! TREE_THIS_VOLATILE (exp)
3183               && ! DECL_NONLOCAL (exp)
3184               /* Don't regard global variables as simple.  They may be
3185                  allocated in ways unknown to the compiler (shared memory,
3186                  #pragma weak, etc).  */
3187               && ! TREE_PUBLIC (exp)
3188               && ! DECL_EXTERNAL (exp)
3189               /* Loading a static variable is unduly expensive, but global
3190                  registers aren't expensive.  */
3191               && (! TREE_STATIC (exp) || DECL_REGISTER (exp))));
3192 }
3193 \f
3194 /* The following functions are subroutines to fold_range_test and allow it to
3195    try to change a logical combination of comparisons into a range test.
3196
3197    For example, both
3198         X == 2 || X == 3 || X == 4 || X == 5
3199    and
3200         X >= 2 && X <= 5
3201    are converted to
3202         (unsigned) (X - 2) <= 3
3203
3204    We describe each set of comparisons as being either inside or outside
3205    a range, using a variable named like IN_P, and then describe the
3206    range with a lower and upper bound.  If one of the bounds is omitted,
3207    it represents either the highest or lowest value of the type.
3208
3209    In the comments below, we represent a range by two numbers in brackets
3210    preceded by a "+" to designate being inside that range, or a "-" to
3211    designate being outside that range, so the condition can be inverted by
3212    flipping the prefix.  An omitted bound is represented by a "-".  For
3213    example, "- [-, 10]" means being outside the range starting at the lowest
3214    possible value and ending at 10, in other words, being greater than 10.
3215    The range "+ [-, -]" is always true and hence the range "- [-, -]" is
3216    always false.
3217
3218    We set up things so that the missing bounds are handled in a consistent
3219    manner so neither a missing bound nor "true" and "false" need to be
3220    handled using a special case.  */
3221
3222 /* Return the result of applying CODE to ARG0 and ARG1, but handle the case
3223    of ARG0 and/or ARG1 being omitted, meaning an unlimited range. UPPER0_P
3224    and UPPER1_P are nonzero if the respective argument is an upper bound
3225    and zero for a lower.  TYPE, if nonzero, is the type of the result; it
3226    must be specified for a comparison.  ARG1 will be converted to ARG0's
3227    type if both are specified.  */
3228
3229 static tree
3230 range_binop (enum tree_code code, tree type, tree arg0, int upper0_p,
3231              tree arg1, int upper1_p)
3232 {
3233   tree tem;
3234   int result;
3235   int sgn0, sgn1;
3236
3237   /* If neither arg represents infinity, do the normal operation.
3238      Else, if not a comparison, return infinity.  Else handle the special
3239      comparison rules. Note that most of the cases below won't occur, but
3240      are handled for consistency.  */
3241
3242   if (arg0 != 0 && arg1 != 0)
3243     {
3244       tem = fold (build (code, type != 0 ? type : TREE_TYPE (arg0),
3245                          arg0, fold_convert (TREE_TYPE (arg0), arg1)));
3246       STRIP_NOPS (tem);
3247       return TREE_CODE (tem) == INTEGER_CST ? tem : 0;
3248     }
3249
3250   if (TREE_CODE_CLASS (code) != '<')
3251     return 0;
3252
3253   /* Set SGN[01] to -1 if ARG[01] is a lower bound, 1 for upper, and 0
3254      for neither.  In real maths, we cannot assume open ended ranges are
3255      the same. But, this is computer arithmetic, where numbers are finite.
3256      We can therefore make the transformation of any unbounded range with
3257      the value Z, Z being greater than any representable number. This permits
3258      us to treat unbounded ranges as equal.  */
3259   sgn0 = arg0 != 0 ? 0 : (upper0_p ? 1 : -1);
3260   sgn1 = arg1 != 0 ? 0 : (upper1_p ? 1 : -1);
3261   switch (code)
3262     {
3263     case EQ_EXPR:
3264       result = sgn0 == sgn1;
3265       break;
3266     case NE_EXPR:
3267       result = sgn0 != sgn1;
3268       break;
3269     case LT_EXPR:
3270       result = sgn0 < sgn1;
3271       break;
3272     case LE_EXPR:
3273       result = sgn0 <= sgn1;
3274       break;
3275     case GT_EXPR:
3276       result = sgn0 > sgn1;
3277       break;
3278     case GE_EXPR:
3279       result = sgn0 >= sgn1;
3280       break;
3281     default:
3282       abort ();
3283     }
3284
3285   return fold_convert (type, result ? integer_one_node : integer_zero_node);
3286 }
3287 \f
3288 /* Given EXP, a logical expression, set the range it is testing into
3289    variables denoted by PIN_P, PLOW, and PHIGH.  Return the expression
3290    actually being tested.  *PLOW and *PHIGH will be made of the same type
3291    as the returned expression.  If EXP is not a comparison, we will most
3292    likely not be returning a useful value and range.  */
3293
3294 static tree
3295 make_range (tree exp, int *pin_p, tree *plow, tree *phigh)
3296 {
3297   enum tree_code code;
3298   tree arg0 = NULL_TREE, arg1 = NULL_TREE, type = NULL_TREE;
3299   tree orig_type = NULL_TREE;
3300   int in_p, n_in_p;
3301   tree low, high, n_low, n_high;
3302
3303   /* Start with simply saying "EXP != 0" and then look at the code of EXP
3304      and see if we can refine the range.  Some of the cases below may not
3305      happen, but it doesn't seem worth worrying about this.  We "continue"
3306      the outer loop when we've changed something; otherwise we "break"
3307      the switch, which will "break" the while.  */
3308
3309   in_p = 0;
3310   low = high = fold_convert (TREE_TYPE (exp), integer_zero_node);
3311
3312   while (1)
3313     {
3314       code = TREE_CODE (exp);
3315
3316       if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
3317         {
3318           if (first_rtl_op (code) > 0)
3319             arg0 = TREE_OPERAND (exp, 0);
3320           if (TREE_CODE_CLASS (code) == '<'
3321               || TREE_CODE_CLASS (code) == '1'
3322               || TREE_CODE_CLASS (code) == '2')
3323             type = TREE_TYPE (arg0);
3324           if (TREE_CODE_CLASS (code) == '2'
3325               || TREE_CODE_CLASS (code) == '<'
3326               || (TREE_CODE_CLASS (code) == 'e'
3327                   && TREE_CODE_LENGTH (code) > 1))
3328             arg1 = TREE_OPERAND (exp, 1);
3329         }
3330
3331       /* Set ORIG_TYPE as soon as TYPE is non-null so that we do not
3332          lose a cast by accident.  */
3333       if (type != NULL_TREE && orig_type == NULL_TREE)
3334         orig_type = type;
3335
3336       switch (code)
3337         {
3338         case TRUTH_NOT_EXPR:
3339           in_p = ! in_p, exp = arg0;
3340           continue;
3341
3342         case EQ_EXPR: case NE_EXPR:
3343         case LT_EXPR: case LE_EXPR: case GE_EXPR: case GT_EXPR:
3344           /* We can only do something if the range is testing for zero
3345              and if the second operand is an integer constant.  Note that
3346              saying something is "in" the range we make is done by
3347              complementing IN_P since it will set in the initial case of
3348              being not equal to zero; "out" is leaving it alone.  */
3349           if (low == 0 || high == 0
3350               || ! integer_zerop (low) || ! integer_zerop (high)
3351               || TREE_CODE (arg1) != INTEGER_CST)
3352             break;
3353
3354           switch (code)
3355             {
3356             case NE_EXPR:  /* - [c, c]  */
3357               low = high = arg1;
3358               break;
3359             case EQ_EXPR:  /* + [c, c]  */
3360               in_p = ! in_p, low = high = arg1;
3361               break;
3362             case GT_EXPR:  /* - [-, c] */
3363               low = 0, high = arg1;
3364               break;
3365             case GE_EXPR:  /* + [c, -] */
3366               in_p = ! in_p, low = arg1, high = 0;
3367               break;
3368             case LT_EXPR:  /* - [c, -] */
3369               low = arg1, high = 0;
3370               break;
3371             case LE_EXPR:  /* + [-, c] */
3372               in_p = ! in_p, low = 0, high = arg1;
3373               break;
3374             default:
3375               abort ();
3376             }
3377
3378           exp = arg0;
3379
3380           /* If this is an unsigned comparison, we also know that EXP is
3381              greater than or equal to zero.  We base the range tests we make
3382              on that fact, so we record it here so we can parse existing
3383              range tests.  */
3384           if (TYPE_UNSIGNED (type) && (low == 0 || high == 0))
3385             {
3386               if (! merge_ranges (&n_in_p, &n_low, &n_high, in_p, low, high,
3387                                   1, fold_convert (type, integer_zero_node),
3388                                   NULL_TREE))
3389                 break;
3390
3391               in_p = n_in_p, low = n_low, high = n_high;
3392
3393               /* If the high bound is missing, but we have a nonzero low
3394                  bound, reverse the range so it goes from zero to the low bound
3395                  minus 1.  */
3396               if (high == 0 && low && ! integer_zerop (low))
3397                 {
3398                   in_p = ! in_p;
3399                   high = range_binop (MINUS_EXPR, NULL_TREE, low, 0,
3400                                       integer_one_node, 0);
3401                   low = fold_convert (type, integer_zero_node);
3402                 }
3403             }
3404           continue;
3405
3406         case NEGATE_EXPR:
3407           /* (-x) IN [a,b] -> x in [-b, -a]  */
3408           n_low = range_binop (MINUS_EXPR, type,
3409                                fold_convert (type, integer_zero_node),
3410                                0, high, 1);
3411           n_high = range_binop (MINUS_EXPR, type,
3412                                 fold_convert (type, integer_zero_node),
3413                                 0, low, 0);
3414           low = n_low, high = n_high;
3415           exp = arg0;
3416           continue;
3417
3418         case BIT_NOT_EXPR:
3419           /* ~ X -> -X - 1  */
3420           exp = build (MINUS_EXPR, type, negate_expr (arg0),
3421                        fold_convert (type, integer_one_node));
3422           continue;
3423
3424         case PLUS_EXPR:  case MINUS_EXPR:
3425           if (TREE_CODE (arg1) != INTEGER_CST)
3426             break;
3427
3428           /* If EXP is signed, any overflow in the computation is undefined,
3429              so we don't worry about it so long as our computations on
3430              the bounds don't overflow.  For unsigned, overflow is defined
3431              and this is exactly the right thing.  */
3432           n_low = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
3433                                type, low, 0, arg1, 0);
3434           n_high = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
3435                                 type, high, 1, arg1, 0);
3436           if ((n_low != 0 && TREE_OVERFLOW (n_low))
3437               || (n_high != 0 && TREE_OVERFLOW (n_high)))
3438             break;
3439
3440           /* Check for an unsigned range which has wrapped around the maximum
3441              value thus making n_high < n_low, and normalize it.  */
3442           if (n_low && n_high && tree_int_cst_lt (n_high, n_low))
3443             {
3444               low = range_binop (PLUS_EXPR, type, n_high, 0,
3445                                  integer_one_node, 0);
3446               high = range_binop (MINUS_EXPR, type, n_low, 0,
3447                                   integer_one_node, 0);
3448
3449               /* If the range is of the form +/- [ x+1, x ], we won't
3450                  be able to normalize it.  But then, it represents the
3451                  whole range or the empty set, so make it
3452                  +/- [ -, - ].  */
3453               if (tree_int_cst_equal (n_low, low)
3454                   && tree_int_cst_equal (n_high, high))
3455                 low = high = 0;
3456               else
3457                 in_p = ! in_p;
3458             }
3459           else
3460             low = n_low, high = n_high;
3461
3462           exp = arg0;
3463           continue;
3464
3465         case NOP_EXPR:  case NON_LVALUE_EXPR:  case CONVERT_EXPR:
3466           if (TYPE_PRECISION (type) > TYPE_PRECISION (orig_type))
3467             break;
3468
3469           if (! INTEGRAL_TYPE_P (type)
3470               || (low != 0 && ! int_fits_type_p (low, type))
3471               || (high != 0 && ! int_fits_type_p (high, type)))
3472             break;
3473
3474           n_low = low, n_high = high;
3475
3476           if (n_low != 0)
3477             n_low = fold_convert (type, n_low);
3478
3479           if (n_high != 0)
3480             n_high = fold_convert (type, n_high);
3481
3482           /* If we're converting from an unsigned to a signed type,
3483              we will be doing the comparison as unsigned.  The tests above
3484              have already verified that LOW and HIGH are both positive.
3485
3486              So we have to make sure that the original unsigned value will
3487              be interpreted as positive.  */
3488           if (TYPE_UNSIGNED (type) && ! TYPE_UNSIGNED (TREE_TYPE (exp)))
3489             {
3490               tree equiv_type = lang_hooks.types.type_for_mode
3491                 (TYPE_MODE (type), 1);
3492               tree high_positive;
3493
3494               /* A range without an upper bound is, naturally, unbounded.
3495                  Since convert would have cropped a very large value, use
3496                  the max value for the destination type.  */
3497               high_positive
3498                 = TYPE_MAX_VALUE (equiv_type) ? TYPE_MAX_VALUE (equiv_type)
3499                   : TYPE_MAX_VALUE (type);
3500
3501               if (TYPE_PRECISION (type) == TYPE_PRECISION (TREE_TYPE (exp)))
3502                 high_positive = fold (build (RSHIFT_EXPR, type,
3503                                              fold_convert (type,
3504                                                            high_positive),
3505                                              fold_convert (type,
3506                                                            integer_one_node)));
3507
3508               /* If the low bound is specified, "and" the range with the
3509                  range for which the original unsigned value will be
3510                  positive.  */
3511               if (low != 0)
3512                 {
3513                   if (! merge_ranges (&n_in_p, &n_low, &n_high,
3514                                       1, n_low, n_high, 1,
3515                                       fold_convert (type, integer_zero_node),
3516                                       high_positive))
3517                     break;
3518
3519                   in_p = (n_in_p == in_p);
3520                 }
3521               else
3522                 {
3523                   /* Otherwise, "or" the range with the range of the input
3524                      that will be interpreted as negative.  */
3525                   if (! merge_ranges (&n_in_p, &n_low, &n_high,
3526                                       0, n_low, n_high, 1,
3527                                       fold_convert (type, integer_zero_node),
3528                                       high_positive))
3529                     break;
3530
3531                   in_p = (in_p != n_in_p);
3532                 }
3533             }
3534
3535           exp = arg0;
3536           low = n_low, high = n_high;
3537           continue;
3538
3539         default:
3540           break;
3541         }
3542
3543       break;
3544     }
3545
3546   /* If EXP is a constant, we can evaluate whether this is true or false.  */
3547   if (TREE_CODE (exp) == INTEGER_CST)
3548     {
3549       in_p = in_p == (integer_onep (range_binop (GE_EXPR, integer_type_node,
3550                                                  exp, 0, low, 0))
3551                       && integer_onep (range_binop (LE_EXPR, integer_type_node,
3552                                                     exp, 1, high, 1)));
3553       low = high = 0;
3554       exp = 0;
3555     }
3556
3557   *pin_p = in_p, *plow = low, *phigh = high;
3558   return exp;
3559 }
3560 \f
3561 /* Given a range, LOW, HIGH, and IN_P, an expression, EXP, and a result
3562    type, TYPE, return an expression to test if EXP is in (or out of, depending
3563    on IN_P) the range.  */
3564
3565 static tree
3566 build_range_check (tree type, tree exp, int in_p, tree low, tree high)
3567 {
3568   tree etype = TREE_TYPE (exp);
3569   tree value;
3570
3571   if (! in_p
3572       && (0 != (value = build_range_check (type, exp, 1, low, high))))
3573     return invert_truthvalue (value);
3574
3575   if (low == 0 && high == 0)
3576     return fold_convert (type, integer_one_node);
3577
3578   if (low == 0)
3579     return fold (build (LE_EXPR, type, exp, high));
3580
3581   if (high == 0)
3582     return fold (build (GE_EXPR, type, exp, low));
3583
3584   if (operand_equal_p (low, high, 0))
3585     return fold (build (EQ_EXPR, type, exp, low));
3586
3587   if (integer_zerop (low))
3588     {
3589       if (! TYPE_UNSIGNED (etype))
3590         {
3591           etype = lang_hooks.types.unsigned_type (etype);
3592           high = fold_convert (etype, high);
3593           exp = fold_convert (etype, exp);
3594         }
3595       return build_range_check (type, exp, 1, 0, high);
3596     }
3597
3598   /* Optimize (c>=1) && (c<=127) into (signed char)c > 0.  */
3599   if (integer_onep (low) && TREE_CODE (high) == INTEGER_CST)
3600     {
3601       unsigned HOST_WIDE_INT lo;
3602       HOST_WIDE_INT hi;
3603       int prec;
3604
3605       prec = TYPE_PRECISION (etype);
3606       if (prec <= HOST_BITS_PER_WIDE_INT)
3607         {
3608           hi = 0;
3609           lo = ((unsigned HOST_WIDE_INT) 1 << (prec - 1)) - 1;
3610         }
3611       else
3612         {
3613           hi = ((HOST_WIDE_INT) 1 << (prec - HOST_BITS_PER_WIDE_INT - 1)) - 1;
3614           lo = (unsigned HOST_WIDE_INT) -1;
3615         }
3616
3617       if (TREE_INT_CST_HIGH (high) == hi && TREE_INT_CST_LOW (high) == lo)
3618         {
3619           if (TYPE_UNSIGNED (etype))
3620             {
3621               etype = lang_hooks.types.signed_type (etype);
3622               exp = fold_convert (etype, exp);
3623             }
3624           return fold (build (GT_EXPR, type, exp,
3625                               fold_convert (etype, integer_zero_node)));
3626         }
3627     }
3628
3629   if (0 != (value = const_binop (MINUS_EXPR, high, low, 0))
3630       && ! TREE_OVERFLOW (value))
3631     return build_range_check (type,
3632                               fold (build (MINUS_EXPR, etype, exp, low)),
3633                               1, fold_convert (etype, integer_zero_node),
3634                               value);
3635
3636   return 0;
3637 }
3638 \f
3639 /* Given two ranges, see if we can merge them into one.  Return 1 if we
3640    can, 0 if we can't.  Set the output range into the specified parameters.  */
3641
3642 static int
3643 merge_ranges (int *pin_p, tree *plow, tree *phigh, int in0_p, tree low0,
3644               tree high0, int in1_p, tree low1, tree high1)
3645 {
3646   int no_overlap;
3647   int subset;
3648   int temp;
3649   tree tem;
3650   int in_p;
3651   tree low, high;
3652   int lowequal = ((low0 == 0 && low1 == 0)
3653                   || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3654                                                 low0, 0, low1, 0)));
3655   int highequal = ((high0 == 0 && high1 == 0)
3656                    || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3657                                                  high0, 1, high1, 1)));
3658
3659   /* Make range 0 be the range that starts first, or ends last if they
3660      start at the same value.  Swap them if it isn't.  */
3661   if (integer_onep (range_binop (GT_EXPR, integer_type_node,
3662                                  low0, 0, low1, 0))
3663       || (lowequal
3664           && integer_onep (range_binop (GT_EXPR, integer_type_node,
3665                                         high1, 1, high0, 1))))
3666     {
3667       temp = in0_p, in0_p = in1_p, in1_p = temp;
3668       tem = low0, low0 = low1, low1 = tem;
3669       tem = high0, high0 = high1, high1 = tem;
3670     }
3671
3672   /* Now flag two cases, whether the ranges are disjoint or whether the
3673      second range is totally subsumed in the first.  Note that the tests
3674      below are simplified by the ones above.  */
3675   no_overlap = integer_onep (range_binop (LT_EXPR, integer_type_node,
3676                                           high0, 1, low1, 0));
3677   subset = integer_onep (range_binop (LE_EXPR, integer_type_node,
3678                                       high1, 1, high0, 1));
3679
3680   /* We now have four cases, depending on whether we are including or
3681      excluding the two ranges.  */
3682   if (in0_p && in1_p)
3683     {
3684       /* If they don't overlap, the result is false.  If the second range
3685          is a subset it is the result.  Otherwise, the range is from the start
3686          of the second to the end of the first.  */
3687       if (no_overlap)
3688         in_p = 0, low = high = 0;
3689       else if (subset)
3690         in_p = 1, low = low1, high = high1;
3691       else
3692         in_p = 1, low = low1, high = high0;
3693     }
3694
3695   else if (in0_p && ! in1_p)
3696     {
3697       /* If they don't overlap, the result is the first range.  If they are
3698          equal, the result is false.  If the second range is a subset of the
3699          first, and the ranges begin at the same place, we go from just after
3700          the end of the first range to the end of the second.  If the second
3701          range is not a subset of the first, or if it is a subset and both
3702          ranges end at the same place, the range starts at the start of the
3703          first range and ends just before the second range.
3704          Otherwise, we can't describe this as a single range.  */
3705       if (no_overlap)
3706         in_p = 1, low = low0, high = high0;
3707       else if (lowequal && highequal)
3708         in_p = 0, low = high = 0;
3709       else if (subset && lowequal)
3710         {
3711           in_p = 1, high = high0;
3712           low = range_binop (PLUS_EXPR, NULL_TREE, high1, 0,
3713                              integer_one_node, 0);
3714         }
3715       else if (! subset || highequal)
3716         {
3717           in_p = 1, low = low0;
3718           high = range_binop (MINUS_EXPR, NULL_TREE, low1, 0,
3719                               integer_one_node, 0);
3720         }
3721       else
3722         return 0;
3723     }
3724
3725   else if (! in0_p && in1_p)
3726     {
3727       /* If they don't overlap, the result is the second range.  If the second
3728          is a subset of the first, the result is false.  Otherwise,
3729          the range starts just after the first range and ends at the
3730          end of the second.  */
3731       if (no_overlap)
3732         in_p = 1, low = low1, high = high1;
3733       else if (subset || highequal)
3734         in_p = 0, low = high = 0;
3735       else
3736         {
3737           in_p = 1, high = high1;
3738           low = range_binop (PLUS_EXPR, NULL_TREE, high0, 1,
3739                              integer_one_node, 0);
3740         }
3741     }
3742
3743   else
3744     {
3745       /* The case where we are excluding both ranges.  Here the complex case
3746          is if they don't overlap.  In that case, the only time we have a
3747          range is if they are adjacent.  If the second is a subset of the
3748          first, the result is the first.  Otherwise, the range to exclude
3749          starts at the beginning of the first range and ends at the end of the
3750          second.  */
3751       if (no_overlap)
3752         {
3753           if (integer_onep (range_binop (EQ_EXPR, integer_type_node,
3754                                          range_binop (PLUS_EXPR, NULL_TREE,
3755                                                       high0, 1,
3756                                                       integer_one_node, 1),
3757                                          1, low1, 0)))
3758             in_p = 0, low = low0, high = high1;
3759           else
3760             return 0;
3761         }
3762       else if (subset)
3763         in_p = 0, low = low0, high = high0;
3764       else
3765         in_p = 0, low = low0, high = high1;
3766     }
3767
3768   *pin_p = in_p, *plow = low, *phigh = high;
3769   return 1;
3770 }
3771 \f
3772 #ifndef RANGE_TEST_NON_SHORT_CIRCUIT
3773 #define RANGE_TEST_NON_SHORT_CIRCUIT (BRANCH_COST >= 2)
3774 #endif
3775
3776 /* EXP is some logical combination of boolean tests.  See if we can
3777    merge it into some range test.  Return the new tree if so.  */
3778
3779 static tree
3780 fold_range_test (tree exp)
3781 {
3782   int or_op = (TREE_CODE (exp) == TRUTH_ORIF_EXPR
3783                || TREE_CODE (exp) == TRUTH_OR_EXPR);
3784   int in0_p, in1_p, in_p;
3785   tree low0, low1, low, high0, high1, high;
3786   tree lhs = make_range (TREE_OPERAND (exp, 0), &in0_p, &low0, &high0);
3787   tree rhs = make_range (TREE_OPERAND (exp, 1), &in1_p, &low1, &high1);
3788   tree tem;
3789
3790   /* If this is an OR operation, invert both sides; we will invert
3791      again at the end.  */
3792   if (or_op)
3793     in0_p = ! in0_p, in1_p = ! in1_p;
3794
3795   /* If both expressions are the same, if we can merge the ranges, and we
3796      can build the range test, return it or it inverted.  If one of the
3797      ranges is always true or always false, consider it to be the same
3798      expression as the other.  */
3799   if ((lhs == 0 || rhs == 0 || operand_equal_p (lhs, rhs, 0))
3800       && merge_ranges (&in_p, &low, &high, in0_p, low0, high0,
3801                        in1_p, low1, high1)
3802       && 0 != (tem = (build_range_check (TREE_TYPE (exp),
3803                                          lhs != 0 ? lhs
3804                                          : rhs != 0 ? rhs : integer_zero_node,
3805                                          in_p, low, high))))
3806     return or_op ? invert_truthvalue (tem) : tem;
3807
3808   /* On machines where the branch cost is expensive, if this is a
3809      short-circuited branch and the underlying object on both sides
3810      is the same, make a non-short-circuit operation.  */
3811   else if (RANGE_TEST_NON_SHORT_CIRCUIT
3812            && lhs != 0 && rhs != 0
3813            && (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3814                || TREE_CODE (exp) == TRUTH_ORIF_EXPR)
3815            && operand_equal_p (lhs, rhs, 0))
3816     {
3817       /* If simple enough, just rewrite.  Otherwise, make a SAVE_EXPR
3818          unless we are at top level or LHS contains a PLACEHOLDER_EXPR, in
3819          which cases we can't do this.  */
3820       if (simple_operand_p (lhs))
3821         return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3822                       ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3823                       TREE_TYPE (exp), TREE_OPERAND (exp, 0),
3824                       TREE_OPERAND (exp, 1));
3825
3826       else if (lang_hooks.decls.global_bindings_p () == 0
3827                && ! CONTAINS_PLACEHOLDER_P (lhs))
3828         {
3829           tree common = save_expr (lhs);
3830
3831           if (0 != (lhs = build_range_check (TREE_TYPE (exp), common,
3832                                              or_op ? ! in0_p : in0_p,
3833                                              low0, high0))
3834               && (0 != (rhs = build_range_check (TREE_TYPE (exp), common,
3835                                                  or_op ? ! in1_p : in1_p,
3836                                                  low1, high1))))
3837             return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3838                           ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3839                           TREE_TYPE (exp), lhs, rhs);
3840         }
3841     }
3842
3843   return 0;
3844 }
3845 \f
3846 /* Subroutine for fold_truthop: C is an INTEGER_CST interpreted as a P
3847    bit value.  Arrange things so the extra bits will be set to zero if and
3848    only if C is signed-extended to its full width.  If MASK is nonzero,
3849    it is an INTEGER_CST that should be AND'ed with the extra bits.  */
3850
3851 static tree
3852 unextend (tree c, int p, int unsignedp, tree mask)
3853 {
3854   tree type = TREE_TYPE (c);
3855   int modesize = GET_MODE_BITSIZE (TYPE_MODE (type));
3856   tree temp;
3857
3858   if (p == modesize || unsignedp)
3859     return c;
3860
3861   /* We work by getting just the sign bit into the low-order bit, then
3862      into the high-order bit, then sign-extend.  We then XOR that value
3863      with C.  */
3864   temp = const_binop (RSHIFT_EXPR, c, size_int (p - 1), 0);
3865   temp = const_binop (BIT_AND_EXPR, temp, size_int (1), 0);
3866
3867   /* We must use a signed type in order to get an arithmetic right shift.
3868      However, we must also avoid introducing accidental overflows, so that
3869      a subsequent call to integer_zerop will work.  Hence we must
3870      do the type conversion here.  At this point, the constant is either
3871      zero or one, and the conversion to a signed type can never overflow.
3872      We could get an overflow if this conversion is done anywhere else.  */
3873   if (TYPE_UNSIGNED (type))
3874     temp = fold_convert (lang_hooks.types.signed_type (type), temp);
3875
3876   temp = const_binop (LSHIFT_EXPR, temp, size_int (modesize - 1), 0);
3877   temp = const_binop (RSHIFT_EXPR, temp, size_int (modesize - p - 1), 0);
3878   if (mask != 0)
3879     temp = const_binop (BIT_AND_EXPR, temp,
3880                         fold_convert (TREE_TYPE (c), mask), 0);
3881   /* If necessary, convert the type back to match the type of C.  */
3882   if (TYPE_UNSIGNED (type))
3883     temp = fold_convert (type, temp);
3884
3885   return fold_convert (type, const_binop (BIT_XOR_EXPR, c, temp, 0));
3886 }
3887 \f
3888 /* Find ways of folding logical expressions of LHS and RHS:
3889    Try to merge two comparisons to the same innermost item.
3890    Look for range tests like "ch >= '0' && ch <= '9'".
3891    Look for combinations of simple terms on machines with expensive branches
3892    and evaluate the RHS unconditionally.
3893
3894    For example, if we have p->a == 2 && p->b == 4 and we can make an
3895    object large enough to span both A and B, we can do this with a comparison
3896    against the object ANDed with the a mask.
3897
3898    If we have p->a == q->a && p->b == q->b, we may be able to use bit masking
3899    operations to do this with one comparison.
3900
3901    We check for both normal comparisons and the BIT_AND_EXPRs made this by
3902    function and the one above.
3903
3904    CODE is the logical operation being done.  It can be TRUTH_ANDIF_EXPR,
3905    TRUTH_AND_EXPR, TRUTH_ORIF_EXPR, or TRUTH_OR_EXPR.
3906
3907    TRUTH_TYPE is the type of the logical operand and LHS and RHS are its
3908    two operands.
3909
3910    We return the simplified tree or 0 if no optimization is possible.  */
3911
3912 static tree
3913 fold_truthop (enum tree_code code, tree truth_type, tree lhs, tree rhs)
3914 {
3915   /* If this is the "or" of two comparisons, we can do something if
3916      the comparisons are NE_EXPR.  If this is the "and", we can do something
3917      if the comparisons are EQ_EXPR.  I.e.,
3918         (a->b == 2 && a->c == 4) can become (a->new == NEW).
3919
3920      WANTED_CODE is this operation code.  For single bit fields, we can
3921      convert EQ_EXPR to NE_EXPR so we need not reject the "wrong"
3922      comparison for one-bit fields.  */
3923
3924   enum tree_code wanted_code;
3925   enum tree_code lcode, rcode;
3926   tree ll_arg, lr_arg, rl_arg, rr_arg;
3927   tree ll_inner, lr_inner, rl_inner, rr_inner;
3928   HOST_WIDE_INT ll_bitsize, ll_bitpos, lr_bitsize, lr_bitpos;
3929   HOST_WIDE_INT rl_bitsize, rl_bitpos, rr_bitsize, rr_bitpos;
3930   HOST_WIDE_INT xll_bitpos, xlr_bitpos, xrl_bitpos, xrr_bitpos;
3931   HOST_WIDE_INT lnbitsize, lnbitpos, rnbitsize, rnbitpos;
3932   int ll_unsignedp, lr_unsignedp, rl_unsignedp, rr_unsignedp;
3933   enum machine_mode ll_mode, lr_mode, rl_mode, rr_mode;
3934   enum machine_mode lnmode, rnmode;
3935   tree ll_mask, lr_mask, rl_mask, rr_mask;
3936   tree ll_and_mask, lr_and_mask, rl_and_mask, rr_and_mask;
3937   tree l_const, r_const;
3938   tree lntype, rntype, result;
3939   int first_bit, end_bit;
3940   int volatilep;
3941
3942   /* Start by getting the comparison codes.  Fail if anything is volatile.
3943      If one operand is a BIT_AND_EXPR with the constant one, treat it as if
3944      it were surrounded with a NE_EXPR.  */
3945
3946   if (TREE_SIDE_EFFECTS (lhs) || TREE_SIDE_EFFECTS (rhs))
3947     return 0;
3948
3949   lcode = TREE_CODE (lhs);
3950   rcode = TREE_CODE (rhs);
3951
3952   if (lcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (lhs, 1)))
3953     lcode = NE_EXPR, lhs = build (NE_EXPR, truth_type, lhs, integer_zero_node);
3954
3955   if (rcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (rhs, 1)))
3956     rcode = NE_EXPR, rhs = build (NE_EXPR, truth_type, rhs, integer_zero_node);
3957
3958   if (TREE_CODE_CLASS (lcode) != '<' || TREE_CODE_CLASS (rcode) != '<')
3959     return 0;
3960
3961   code = ((code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR)
3962           ? TRUTH_AND_EXPR : TRUTH_OR_EXPR);
3963
3964   ll_arg = TREE_OPERAND (lhs, 0);
3965   lr_arg = TREE_OPERAND (lhs, 1);
3966   rl_arg = TREE_OPERAND (rhs, 0);
3967   rr_arg = TREE_OPERAND (rhs, 1);
3968
3969   /* Simplify (x<y) && (x==y) into (x<=y) and related optimizations.  */
3970   if (simple_operand_p (ll_arg)
3971       && simple_operand_p (lr_arg)
3972       && !FLOAT_TYPE_P (TREE_TYPE (ll_arg)))
3973     {
3974       int compcode;
3975
3976       if (operand_equal_p (ll_arg, rl_arg, 0)
3977           && operand_equal_p (lr_arg, rr_arg, 0))
3978         {
3979           int lcompcode, rcompcode;
3980
3981           lcompcode = comparison_to_compcode (lcode);
3982           rcompcode = comparison_to_compcode (rcode);
3983           compcode = (code == TRUTH_AND_EXPR)
3984                      ? lcompcode & rcompcode
3985                      : lcompcode | rcompcode;
3986         }
3987       else if (operand_equal_p (ll_arg, rr_arg, 0)
3988                && operand_equal_p (lr_arg, rl_arg, 0))
3989         {
3990           int lcompcode, rcompcode;
3991
3992           rcode = swap_tree_comparison (rcode);
3993           lcompcode = comparison_to_compcode (lcode);
3994           rcompcode = comparison_to_compcode (rcode);
3995           compcode = (code == TRUTH_AND_EXPR)
3996                      ? lcompcode & rcompcode