OSDN Git Service

2010-04-15 Richard Guenther <rguenther@suse.de>
[pf3gnuchains/gcc-fork.git] / gcc / fold-const.c
1 /* Fold a constant sub-tree into a single node for C-compiler
2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
3    2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4    Free Software Foundation, Inc.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
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_double.
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_double takes a constant, an overflowable flag and a
43    prior overflow indicator.  It forces the value to fit the type and
44    sets TREE_OVERFLOW.
45
46    Note: Since the folders get called on non-gimple code as well as
47    gimple code, we need to handle GIMPLE tuples as well as their
48    corresponding tree equivalents.  */
49
50 #include "config.h"
51 #include "system.h"
52 #include "coretypes.h"
53 #include "tm.h"
54 #include "flags.h"
55 #include "tree.h"
56 #include "real.h"
57 #include "fixed-value.h"
58 #include "rtl.h"
59 #include "expr.h"
60 #include "tm_p.h"
61 #include "target.h"
62 #include "toplev.h"
63 #include "intl.h"
64 #include "ggc.h"
65 #include "hashtab.h"
66 #include "langhooks.h"
67 #include "md5.h"
68 #include "gimple.h"
69
70 /* Nonzero if we are folding constants inside an initializer; zero
71    otherwise.  */
72 int folding_initializer = 0;
73
74 /* The following constants represent a bit based encoding of GCC's
75    comparison operators.  This encoding simplifies transformations
76    on relational comparison operators, such as AND and OR.  */
77 enum comparison_code {
78   COMPCODE_FALSE = 0,
79   COMPCODE_LT = 1,
80   COMPCODE_EQ = 2,
81   COMPCODE_LE = 3,
82   COMPCODE_GT = 4,
83   COMPCODE_LTGT = 5,
84   COMPCODE_GE = 6,
85   COMPCODE_ORD = 7,
86   COMPCODE_UNORD = 8,
87   COMPCODE_UNLT = 9,
88   COMPCODE_UNEQ = 10,
89   COMPCODE_UNLE = 11,
90   COMPCODE_UNGT = 12,
91   COMPCODE_NE = 13,
92   COMPCODE_UNGE = 14,
93   COMPCODE_TRUE = 15
94 };
95
96 static bool negate_mathfn_p (enum built_in_function);
97 static bool negate_expr_p (tree);
98 static tree negate_expr (tree);
99 static tree split_tree (tree, enum tree_code, tree *, tree *, tree *, int);
100 static tree associate_trees (location_t, tree, tree, enum tree_code, tree);
101 static tree const_binop (enum tree_code, tree, tree, int);
102 static enum comparison_code comparison_to_compcode (enum tree_code);
103 static enum tree_code compcode_to_comparison (enum comparison_code);
104 static int operand_equal_for_comparison_p (tree, tree, tree);
105 static int twoval_comparison_p (tree, tree *, tree *, int *);
106 static tree eval_subst (location_t, tree, tree, tree, tree, tree);
107 static tree pedantic_omit_one_operand_loc (location_t, tree, tree, tree);
108 static tree distribute_bit_expr (location_t, enum tree_code, tree, tree, tree);
109 static tree make_bit_field_ref (location_t, tree, tree,
110                                 HOST_WIDE_INT, HOST_WIDE_INT, int);
111 static tree optimize_bit_field_compare (location_t, enum tree_code,
112                                         tree, tree, tree);
113 static tree decode_field_reference (location_t, tree, HOST_WIDE_INT *,
114                                     HOST_WIDE_INT *,
115                                     enum machine_mode *, int *, int *,
116                                     tree *, tree *);
117 static int all_ones_mask_p (const_tree, int);
118 static tree sign_bit_p (tree, const_tree);
119 static int simple_operand_p (const_tree);
120 static tree range_binop (enum tree_code, tree, tree, int, tree, int);
121 static tree range_predecessor (tree);
122 static tree range_successor (tree);
123 extern tree make_range (tree, int *, tree *, tree *, bool *);
124 extern bool merge_ranges (int *, tree *, tree *, int, tree, tree, int,
125                           tree, tree);
126 static tree fold_range_test (location_t, enum tree_code, tree, tree, tree);
127 static tree fold_cond_expr_with_comparison (location_t, tree, tree, tree, tree);
128 static tree unextend (tree, int, int, tree);
129 static tree fold_truthop (location_t, enum tree_code, tree, tree, tree);
130 static tree optimize_minmax_comparison (location_t, enum tree_code,
131                                         tree, tree, tree);
132 static tree extract_muldiv (tree, tree, enum tree_code, tree, bool *);
133 static tree extract_muldiv_1 (tree, tree, enum tree_code, tree, bool *);
134 static tree fold_binary_op_with_conditional_arg (location_t,
135                                                  enum tree_code, tree,
136                                                  tree, tree,
137                                                  tree, tree, int);
138 static tree fold_mathfn_compare (location_t,
139                                  enum built_in_function, enum tree_code,
140                                  tree, tree, tree);
141 static tree fold_inf_compare (location_t, enum tree_code, tree, tree, tree);
142 static tree fold_div_compare (location_t, enum tree_code, tree, tree, tree);
143 static bool reorder_operands_p (const_tree, const_tree);
144 static tree fold_negate_const (tree, tree);
145 static tree fold_not_const (tree, tree);
146 static tree fold_relational_const (enum tree_code, tree, tree, tree);
147 static tree fold_convert_const (enum tree_code, tree, tree);
148
149
150 /* We know that A1 + B1 = SUM1, using 2's complement arithmetic and ignoring
151    overflow.  Suppose A, B and SUM have the same respective signs as A1, B1,
152    and SUM1.  Then this yields nonzero if overflow occurred during the
153    addition.
154
155    Overflow occurs if A and B have the same sign, but A and SUM differ in
156    sign.  Use `^' to test whether signs differ, and `< 0' to isolate the
157    sign.  */
158 #define OVERFLOW_SUM_SIGN(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)
159 \f
160 /* If ARG2 divides ARG1 with zero remainder, carries out the division
161    of type CODE and returns the quotient.
162    Otherwise returns NULL_TREE.  */
163
164 tree
165 div_if_zero_remainder (enum tree_code code, const_tree arg1, const_tree arg2)
166 {
167   double_int quo, rem;
168   int uns;
169
170   /* The sign of the division is according to operand two, that
171      does the correct thing for POINTER_PLUS_EXPR where we want
172      a signed division.  */
173   uns = TYPE_UNSIGNED (TREE_TYPE (arg2));
174   if (TREE_CODE (TREE_TYPE (arg2)) == INTEGER_TYPE
175       && TYPE_IS_SIZETYPE (TREE_TYPE (arg2)))
176     uns = false;
177
178   quo = double_int_divmod (tree_to_double_int (arg1),
179                            tree_to_double_int (arg2),
180                            uns, code, &rem);
181
182   if (double_int_zero_p (rem))
183     return build_int_cst_wide (TREE_TYPE (arg1), quo.low, quo.high);
184
185   return NULL_TREE; 
186 }
187 \f
188 /* This is nonzero if we should defer warnings about undefined
189    overflow.  This facility exists because these warnings are a
190    special case.  The code to estimate loop iterations does not want
191    to issue any warnings, since it works with expressions which do not
192    occur in user code.  Various bits of cleanup code call fold(), but
193    only use the result if it has certain characteristics (e.g., is a
194    constant); that code only wants to issue a warning if the result is
195    used.  */
196
197 static int fold_deferring_overflow_warnings;
198
199 /* If a warning about undefined overflow is deferred, this is the
200    warning.  Note that this may cause us to turn two warnings into
201    one, but that is fine since it is sufficient to only give one
202    warning per expression.  */
203
204 static const char* fold_deferred_overflow_warning;
205
206 /* If a warning about undefined overflow is deferred, this is the
207    level at which the warning should be emitted.  */
208
209 static enum warn_strict_overflow_code fold_deferred_overflow_code;
210
211 /* Start deferring overflow warnings.  We could use a stack here to
212    permit nested calls, but at present it is not necessary.  */
213
214 void
215 fold_defer_overflow_warnings (void)
216 {
217   ++fold_deferring_overflow_warnings;
218 }
219
220 /* Stop deferring overflow warnings.  If there is a pending warning,
221    and ISSUE is true, then issue the warning if appropriate.  STMT is
222    the statement with which the warning should be associated (used for
223    location information); STMT may be NULL.  CODE is the level of the
224    warning--a warn_strict_overflow_code value.  This function will use
225    the smaller of CODE and the deferred code when deciding whether to
226    issue the warning.  CODE may be zero to mean to always use the
227    deferred code.  */
228
229 void
230 fold_undefer_overflow_warnings (bool issue, const_gimple stmt, int code)
231 {
232   const char *warnmsg;
233   location_t locus;
234
235   gcc_assert (fold_deferring_overflow_warnings > 0);
236   --fold_deferring_overflow_warnings;
237   if (fold_deferring_overflow_warnings > 0)
238     {
239       if (fold_deferred_overflow_warning != NULL
240           && code != 0
241           && code < (int) fold_deferred_overflow_code)
242         fold_deferred_overflow_code = (enum warn_strict_overflow_code) code;
243       return;
244     }
245
246   warnmsg = fold_deferred_overflow_warning;
247   fold_deferred_overflow_warning = NULL;
248
249   if (!issue || warnmsg == NULL)
250     return;
251
252   if (gimple_no_warning_p (stmt))
253     return;
254
255   /* Use the smallest code level when deciding to issue the
256      warning.  */
257   if (code == 0 || code > (int) fold_deferred_overflow_code)
258     code = fold_deferred_overflow_code;
259
260   if (!issue_strict_overflow_warning (code))
261     return;
262
263   if (stmt == NULL)
264     locus = input_location;
265   else
266     locus = gimple_location (stmt);
267   warning_at (locus, OPT_Wstrict_overflow, "%s", warnmsg);
268 }
269
270 /* Stop deferring overflow warnings, ignoring any deferred
271    warnings.  */
272
273 void
274 fold_undefer_and_ignore_overflow_warnings (void)
275 {
276   fold_undefer_overflow_warnings (false, NULL, 0);
277 }
278
279 /* Whether we are deferring overflow warnings.  */
280
281 bool
282 fold_deferring_overflow_warnings_p (void)
283 {
284   return fold_deferring_overflow_warnings > 0;
285 }
286
287 /* This is called when we fold something based on the fact that signed
288    overflow is undefined.  */
289
290 static void
291 fold_overflow_warning (const char* gmsgid, enum warn_strict_overflow_code wc)
292 {
293   if (fold_deferring_overflow_warnings > 0)
294     {
295       if (fold_deferred_overflow_warning == NULL
296           || wc < fold_deferred_overflow_code)
297         {
298           fold_deferred_overflow_warning = gmsgid;
299           fold_deferred_overflow_code = wc;
300         }
301     }
302   else if (issue_strict_overflow_warning (wc))
303     warning (OPT_Wstrict_overflow, gmsgid);
304 }
305 \f
306 /* Return true if the built-in mathematical function specified by CODE
307    is odd, i.e. -f(x) == f(-x).  */
308
309 static bool
310 negate_mathfn_p (enum built_in_function code)
311 {
312   switch (code)
313     {
314     CASE_FLT_FN (BUILT_IN_ASIN):
315     CASE_FLT_FN (BUILT_IN_ASINH):
316     CASE_FLT_FN (BUILT_IN_ATAN):
317     CASE_FLT_FN (BUILT_IN_ATANH):
318     CASE_FLT_FN (BUILT_IN_CASIN):
319     CASE_FLT_FN (BUILT_IN_CASINH):
320     CASE_FLT_FN (BUILT_IN_CATAN):
321     CASE_FLT_FN (BUILT_IN_CATANH):
322     CASE_FLT_FN (BUILT_IN_CBRT):
323     CASE_FLT_FN (BUILT_IN_CPROJ):
324     CASE_FLT_FN (BUILT_IN_CSIN):
325     CASE_FLT_FN (BUILT_IN_CSINH):
326     CASE_FLT_FN (BUILT_IN_CTAN):
327     CASE_FLT_FN (BUILT_IN_CTANH):
328     CASE_FLT_FN (BUILT_IN_ERF):
329     CASE_FLT_FN (BUILT_IN_LLROUND):
330     CASE_FLT_FN (BUILT_IN_LROUND):
331     CASE_FLT_FN (BUILT_IN_ROUND):
332     CASE_FLT_FN (BUILT_IN_SIN):
333     CASE_FLT_FN (BUILT_IN_SINH):
334     CASE_FLT_FN (BUILT_IN_TAN):
335     CASE_FLT_FN (BUILT_IN_TANH):
336     CASE_FLT_FN (BUILT_IN_TRUNC):
337       return true;
338
339     CASE_FLT_FN (BUILT_IN_LLRINT):
340     CASE_FLT_FN (BUILT_IN_LRINT):
341     CASE_FLT_FN (BUILT_IN_NEARBYINT):
342     CASE_FLT_FN (BUILT_IN_RINT):
343       return !flag_rounding_math;
344
345     default:
346       break;
347     }
348   return false;
349 }
350
351 /* Check whether we may negate an integer constant T without causing
352    overflow.  */
353
354 bool
355 may_negate_without_overflow_p (const_tree t)
356 {
357   unsigned HOST_WIDE_INT val;
358   unsigned int prec;
359   tree type;
360
361   gcc_assert (TREE_CODE (t) == INTEGER_CST);
362
363   type = TREE_TYPE (t);
364   if (TYPE_UNSIGNED (type))
365     return false;
366
367   prec = TYPE_PRECISION (type);
368   if (prec > HOST_BITS_PER_WIDE_INT)
369     {
370       if (TREE_INT_CST_LOW (t) != 0)
371         return true;
372       prec -= HOST_BITS_PER_WIDE_INT;
373       val = TREE_INT_CST_HIGH (t);
374     }
375   else
376     val = TREE_INT_CST_LOW (t);
377   if (prec < HOST_BITS_PER_WIDE_INT)
378     val &= ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
379   return val != ((unsigned HOST_WIDE_INT) 1 << (prec - 1));
380 }
381
382 /* Determine whether an expression T can be cheaply negated using
383    the function negate_expr without introducing undefined overflow.  */
384
385 static bool
386 negate_expr_p (tree t)
387 {
388   tree type;
389
390   if (t == 0)
391     return false;
392
393   type = TREE_TYPE (t);
394
395   STRIP_SIGN_NOPS (t);
396   switch (TREE_CODE (t))
397     {
398     case INTEGER_CST:
399       if (TYPE_OVERFLOW_WRAPS (type))
400         return true;
401
402       /* Check that -CST will not overflow type.  */
403       return may_negate_without_overflow_p (t);
404     case BIT_NOT_EXPR:
405       return (INTEGRAL_TYPE_P (type)
406               && TYPE_OVERFLOW_WRAPS (type));
407
408     case FIXED_CST:
409     case NEGATE_EXPR:
410       return true;
411
412     case REAL_CST:
413       /* We want to canonicalize to positive real constants.  Pretend
414          that only negative ones can be easily negated.  */
415       return REAL_VALUE_NEGATIVE (TREE_REAL_CST (t));
416
417     case COMPLEX_CST:
418       return negate_expr_p (TREE_REALPART (t))
419              && negate_expr_p (TREE_IMAGPART (t));
420
421     case COMPLEX_EXPR:
422       return negate_expr_p (TREE_OPERAND (t, 0))
423              && negate_expr_p (TREE_OPERAND (t, 1));
424
425     case CONJ_EXPR:
426       return negate_expr_p (TREE_OPERAND (t, 0));
427
428     case PLUS_EXPR:
429       if (HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (type))
430           || HONOR_SIGNED_ZEROS (TYPE_MODE (type)))
431         return false;
432       /* -(A + B) -> (-B) - A.  */
433       if (negate_expr_p (TREE_OPERAND (t, 1))
434           && reorder_operands_p (TREE_OPERAND (t, 0),
435                                  TREE_OPERAND (t, 1)))
436         return true;
437       /* -(A + B) -> (-A) - B.  */
438       return negate_expr_p (TREE_OPERAND (t, 0));
439
440     case MINUS_EXPR:
441       /* We can't turn -(A-B) into B-A when we honor signed zeros.  */
442       return !HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (type))
443              && !HONOR_SIGNED_ZEROS (TYPE_MODE (type))
444              && reorder_operands_p (TREE_OPERAND (t, 0),
445                                     TREE_OPERAND (t, 1));
446
447     case MULT_EXPR:
448       if (TYPE_UNSIGNED (TREE_TYPE (t)))
449         break;
450
451       /* Fall through.  */
452
453     case RDIV_EXPR:
454       if (! HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (TREE_TYPE (t))))
455         return negate_expr_p (TREE_OPERAND (t, 1))
456                || negate_expr_p (TREE_OPERAND (t, 0));
457       break;
458
459     case TRUNC_DIV_EXPR:
460     case ROUND_DIV_EXPR:
461     case FLOOR_DIV_EXPR:
462     case CEIL_DIV_EXPR:
463     case EXACT_DIV_EXPR:
464       /* In general we can't negate A / B, because if A is INT_MIN and
465          B is 1, we may turn this into INT_MIN / -1 which is undefined
466          and actually traps on some architectures.  But if overflow is
467          undefined, we can negate, because - (INT_MIN / 1) is an
468          overflow.  */
469       if (INTEGRAL_TYPE_P (TREE_TYPE (t))
470           && !TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (t)))
471         break;
472       return negate_expr_p (TREE_OPERAND (t, 1))
473              || negate_expr_p (TREE_OPERAND (t, 0));
474
475     case NOP_EXPR:
476       /* Negate -((double)float) as (double)(-float).  */
477       if (TREE_CODE (type) == REAL_TYPE)
478         {
479           tree tem = strip_float_extensions (t);
480           if (tem != t)
481             return negate_expr_p (tem);
482         }
483       break;
484
485     case CALL_EXPR:
486       /* Negate -f(x) as f(-x).  */
487       if (negate_mathfn_p (builtin_mathfn_code (t)))
488         return negate_expr_p (CALL_EXPR_ARG (t, 0));
489       break;
490
491     case RSHIFT_EXPR:
492       /* Optimize -((int)x >> 31) into (unsigned)x >> 31.  */
493       if (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST)
494         {
495           tree op1 = TREE_OPERAND (t, 1);
496           if (TREE_INT_CST_HIGH (op1) == 0
497               && (unsigned HOST_WIDE_INT) (TYPE_PRECISION (type) - 1)
498                  == TREE_INT_CST_LOW (op1))
499             return true;
500         }
501       break;
502
503     default:
504       break;
505     }
506   return false;
507 }
508
509 /* Given T, an expression, return a folded tree for -T or NULL_TREE, if no
510    simplification is possible.
511    If negate_expr_p would return true for T, NULL_TREE will never be
512    returned.  */
513
514 static tree
515 fold_negate_expr (location_t loc, tree t)
516 {
517   tree type = TREE_TYPE (t);
518   tree tem;
519
520   switch (TREE_CODE (t))
521     {
522     /* Convert - (~A) to A + 1.  */
523     case BIT_NOT_EXPR:
524       if (INTEGRAL_TYPE_P (type))
525         return fold_build2_loc (loc, PLUS_EXPR, type, TREE_OPERAND (t, 0),
526                             build_int_cst (type, 1));
527       break;
528
529     case INTEGER_CST:
530       tem = fold_negate_const (t, type);
531       if (TREE_OVERFLOW (tem) == TREE_OVERFLOW (t)
532           || !TYPE_OVERFLOW_TRAPS (type))
533         return tem;
534       break;
535
536     case REAL_CST:
537       tem = fold_negate_const (t, type);
538       /* Two's complement FP formats, such as c4x, may overflow.  */
539       if (!TREE_OVERFLOW (tem) || !flag_trapping_math)
540         return tem;
541       break;
542
543     case FIXED_CST:
544       tem = fold_negate_const (t, type);
545       return tem;
546
547     case COMPLEX_CST:
548       {
549         tree rpart = negate_expr (TREE_REALPART (t));
550         tree ipart = negate_expr (TREE_IMAGPART (t));
551
552         if ((TREE_CODE (rpart) == REAL_CST
553              && TREE_CODE (ipart) == REAL_CST)
554             || (TREE_CODE (rpart) == INTEGER_CST
555                 && TREE_CODE (ipart) == INTEGER_CST))
556           return build_complex (type, rpart, ipart);
557       }
558       break;
559
560     case COMPLEX_EXPR:
561       if (negate_expr_p (t))
562         return fold_build2_loc (loc, COMPLEX_EXPR, type,
563                             fold_negate_expr (loc, TREE_OPERAND (t, 0)),
564                             fold_negate_expr (loc, TREE_OPERAND (t, 1)));
565       break;
566
567     case CONJ_EXPR:
568       if (negate_expr_p (t))
569         return fold_build1_loc (loc, CONJ_EXPR, type,
570                             fold_negate_expr (loc, TREE_OPERAND (t, 0)));
571       break;
572
573     case NEGATE_EXPR:
574       return TREE_OPERAND (t, 0);
575
576     case PLUS_EXPR:
577       if (!HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (type))
578           && !HONOR_SIGNED_ZEROS (TYPE_MODE (type)))
579         {
580           /* -(A + B) -> (-B) - A.  */
581           if (negate_expr_p (TREE_OPERAND (t, 1))
582               && reorder_operands_p (TREE_OPERAND (t, 0),
583                                      TREE_OPERAND (t, 1)))
584             {
585               tem = negate_expr (TREE_OPERAND (t, 1));
586               return fold_build2_loc (loc, MINUS_EXPR, type,
587                                   tem, TREE_OPERAND (t, 0));
588             }
589
590           /* -(A + B) -> (-A) - B.  */
591           if (negate_expr_p (TREE_OPERAND (t, 0)))
592             {
593               tem = negate_expr (TREE_OPERAND (t, 0));
594               return fold_build2_loc (loc, MINUS_EXPR, type,
595                                   tem, TREE_OPERAND (t, 1));
596             }
597         }
598       break;
599
600     case MINUS_EXPR:
601       /* - (A - B) -> B - A  */
602       if (!HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (type))
603           && !HONOR_SIGNED_ZEROS (TYPE_MODE (type))
604           && reorder_operands_p (TREE_OPERAND (t, 0), TREE_OPERAND (t, 1)))
605         return fold_build2_loc (loc, MINUS_EXPR, type,
606                             TREE_OPERAND (t, 1), TREE_OPERAND (t, 0));
607       break;
608
609     case MULT_EXPR:
610       if (TYPE_UNSIGNED (type))
611         break;
612
613       /* Fall through.  */
614
615     case RDIV_EXPR:
616       if (! HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (type)))
617         {
618           tem = TREE_OPERAND (t, 1);
619           if (negate_expr_p (tem))
620             return fold_build2_loc (loc, TREE_CODE (t), type,
621                                 TREE_OPERAND (t, 0), negate_expr (tem));
622           tem = TREE_OPERAND (t, 0);
623           if (negate_expr_p (tem))
624             return fold_build2_loc (loc, TREE_CODE (t), type,
625                                 negate_expr (tem), TREE_OPERAND (t, 1));
626         }
627       break;
628
629     case TRUNC_DIV_EXPR:
630     case ROUND_DIV_EXPR:
631     case FLOOR_DIV_EXPR:
632     case CEIL_DIV_EXPR:
633     case EXACT_DIV_EXPR:
634       /* In general we can't negate A / B, because if A is INT_MIN and
635          B is 1, we may turn this into INT_MIN / -1 which is undefined
636          and actually traps on some architectures.  But if overflow is
637          undefined, we can negate, because - (INT_MIN / 1) is an
638          overflow.  */
639       if (!INTEGRAL_TYPE_P (type) || TYPE_OVERFLOW_UNDEFINED (type))
640         {
641           const char * const warnmsg = G_("assuming signed overflow does not "
642                                           "occur when negating a division");
643           tem = TREE_OPERAND (t, 1);
644           if (negate_expr_p (tem))
645             {
646               if (INTEGRAL_TYPE_P (type)
647                   && (TREE_CODE (tem) != INTEGER_CST
648                       || integer_onep (tem)))
649                 fold_overflow_warning (warnmsg, WARN_STRICT_OVERFLOW_MISC);
650               return fold_build2_loc (loc, TREE_CODE (t), type,
651                                   TREE_OPERAND (t, 0), negate_expr (tem));
652             }
653           tem = TREE_OPERAND (t, 0);
654           if (negate_expr_p (tem))
655             {
656               if (INTEGRAL_TYPE_P (type)
657                   && (TREE_CODE (tem) != INTEGER_CST
658                       || tree_int_cst_equal (tem, TYPE_MIN_VALUE (type))))
659                 fold_overflow_warning (warnmsg, WARN_STRICT_OVERFLOW_MISC);
660               return fold_build2_loc (loc, TREE_CODE (t), type,
661                                   negate_expr (tem), TREE_OPERAND (t, 1));
662             }
663         }
664       break;
665
666     case NOP_EXPR:
667       /* Convert -((double)float) into (double)(-float).  */
668       if (TREE_CODE (type) == REAL_TYPE)
669         {
670           tem = strip_float_extensions (t);
671           if (tem != t && negate_expr_p (tem))
672             return fold_convert_loc (loc, type, negate_expr (tem));
673         }
674       break;
675
676     case CALL_EXPR:
677       /* Negate -f(x) as f(-x).  */
678       if (negate_mathfn_p (builtin_mathfn_code (t))
679           && negate_expr_p (CALL_EXPR_ARG (t, 0)))
680         {
681           tree fndecl, arg;
682
683           fndecl = get_callee_fndecl (t);
684           arg = negate_expr (CALL_EXPR_ARG (t, 0));
685           return build_call_expr_loc (loc, fndecl, 1, arg);
686         }
687       break;
688
689     case RSHIFT_EXPR:
690       /* Optimize -((int)x >> 31) into (unsigned)x >> 31.  */
691       if (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST)
692         {
693           tree op1 = TREE_OPERAND (t, 1);
694           if (TREE_INT_CST_HIGH (op1) == 0
695               && (unsigned HOST_WIDE_INT) (TYPE_PRECISION (type) - 1)
696                  == TREE_INT_CST_LOW (op1))
697             {
698               tree ntype = TYPE_UNSIGNED (type)
699                            ? signed_type_for (type)
700                            : unsigned_type_for (type);
701               tree temp = fold_convert_loc (loc, ntype, TREE_OPERAND (t, 0));
702               temp = fold_build2_loc (loc, RSHIFT_EXPR, ntype, temp, op1);
703               return fold_convert_loc (loc, type, temp);
704             }
705         }
706       break;
707
708     default:
709       break;
710     }
711
712   return NULL_TREE;
713 }
714
715 /* Like fold_negate_expr, but return a NEGATE_EXPR tree, if T can not be
716    negated in a simpler way.  Also allow for T to be NULL_TREE, in which case
717    return NULL_TREE. */
718
719 static tree
720 negate_expr (tree t)
721 {
722   tree type, tem;
723   location_t loc;
724
725   if (t == NULL_TREE)
726     return NULL_TREE;
727
728   loc = EXPR_LOCATION (t);
729   type = TREE_TYPE (t);
730   STRIP_SIGN_NOPS (t);
731
732   tem = fold_negate_expr (loc, t);
733   if (!tem)
734     {
735       tem = build1 (NEGATE_EXPR, TREE_TYPE (t), t);
736       SET_EXPR_LOCATION (tem, loc);
737     }
738   return fold_convert_loc (loc, type, tem);
739 }
740 \f
741 /* Split a tree IN into a constant, literal and variable parts that could be
742    combined with CODE to make IN.  "constant" means an expression with
743    TREE_CONSTANT but that isn't an actual constant.  CODE must be a
744    commutative arithmetic operation.  Store the constant part into *CONP,
745    the literal in *LITP and return the variable part.  If a part isn't
746    present, set it to null.  If the tree does not decompose in this way,
747    return the entire tree as the variable part and the other parts as null.
748
749    If CODE is PLUS_EXPR we also split trees that use MINUS_EXPR.  In that
750    case, we negate an operand that was subtracted.  Except if it is a
751    literal for which we use *MINUS_LITP instead.
752
753    If NEGATE_P is true, we are negating all of IN, again except a literal
754    for which we use *MINUS_LITP instead.
755
756    If IN is itself a literal or constant, return it as appropriate.
757
758    Note that we do not guarantee that any of the three values will be the
759    same type as IN, but they will have the same signedness and mode.  */
760
761 static tree
762 split_tree (tree in, enum tree_code code, tree *conp, tree *litp,
763             tree *minus_litp, int negate_p)
764 {
765   tree var = 0;
766
767   *conp = 0;
768   *litp = 0;
769   *minus_litp = 0;
770
771   /* Strip any conversions that don't change the machine mode or signedness.  */
772   STRIP_SIGN_NOPS (in);
773
774   if (TREE_CODE (in) == INTEGER_CST || TREE_CODE (in) == REAL_CST
775       || TREE_CODE (in) == FIXED_CST)
776     *litp = in;
777   else if (TREE_CODE (in) == code
778            || ((! FLOAT_TYPE_P (TREE_TYPE (in)) || flag_associative_math)
779                && ! SAT_FIXED_POINT_TYPE_P (TREE_TYPE (in))
780                /* We can associate addition and subtraction together (even
781                   though the C standard doesn't say so) for integers because
782                   the value is not affected.  For reals, the value might be
783                   affected, so we can't.  */
784                && ((code == PLUS_EXPR && TREE_CODE (in) == MINUS_EXPR)
785                    || (code == MINUS_EXPR && TREE_CODE (in) == PLUS_EXPR))))
786     {
787       tree op0 = TREE_OPERAND (in, 0);
788       tree op1 = TREE_OPERAND (in, 1);
789       int neg1_p = TREE_CODE (in) == MINUS_EXPR;
790       int neg_litp_p = 0, neg_conp_p = 0, neg_var_p = 0;
791
792       /* First see if either of the operands is a literal, then a constant.  */
793       if (TREE_CODE (op0) == INTEGER_CST || TREE_CODE (op0) == REAL_CST
794           || TREE_CODE (op0) == FIXED_CST)
795         *litp = op0, op0 = 0;
796       else if (TREE_CODE (op1) == INTEGER_CST || TREE_CODE (op1) == REAL_CST
797                || TREE_CODE (op1) == FIXED_CST)
798         *litp = op1, neg_litp_p = neg1_p, op1 = 0;
799
800       if (op0 != 0 && TREE_CONSTANT (op0))
801         *conp = op0, op0 = 0;
802       else if (op1 != 0 && TREE_CONSTANT (op1))
803         *conp = op1, neg_conp_p = neg1_p, op1 = 0;
804
805       /* If we haven't dealt with either operand, this is not a case we can
806          decompose.  Otherwise, VAR is either of the ones remaining, if any.  */
807       if (op0 != 0 && op1 != 0)
808         var = in;
809       else if (op0 != 0)
810         var = op0;
811       else
812         var = op1, neg_var_p = neg1_p;
813
814       /* Now do any needed negations.  */
815       if (neg_litp_p)
816         *minus_litp = *litp, *litp = 0;
817       if (neg_conp_p)
818         *conp = negate_expr (*conp);
819       if (neg_var_p)
820         var = negate_expr (var);
821     }
822   else if (TREE_CONSTANT (in))
823     *conp = in;
824   else
825     var = in;
826
827   if (negate_p)
828     {
829       if (*litp)
830         *minus_litp = *litp, *litp = 0;
831       else if (*minus_litp)
832         *litp = *minus_litp, *minus_litp = 0;
833       *conp = negate_expr (*conp);
834       var = negate_expr (var);
835     }
836
837   return var;
838 }
839
840 /* Re-associate trees split by the above function.  T1 and T2 are
841    either expressions to associate or null.  Return the new
842    expression, if any.  LOC is the location of the new expression.  If
843    we build an operation, do it in TYPE and with CODE.  */
844
845 static tree
846 associate_trees (location_t loc, tree t1, tree t2, enum tree_code code, tree type)
847 {
848   tree tem;
849
850   if (t1 == 0)
851     return t2;
852   else if (t2 == 0)
853     return t1;
854
855   /* If either input is CODE, a PLUS_EXPR, or a MINUS_EXPR, don't
856      try to fold this since we will have infinite recursion.  But do
857      deal with any NEGATE_EXPRs.  */
858   if (TREE_CODE (t1) == code || TREE_CODE (t2) == code
859       || TREE_CODE (t1) == MINUS_EXPR || TREE_CODE (t2) == MINUS_EXPR)
860     {
861       if (code == PLUS_EXPR)
862         {
863           if (TREE_CODE (t1) == NEGATE_EXPR)
864             tem = build2 (MINUS_EXPR, type, fold_convert_loc (loc, type, t2),
865                           fold_convert_loc (loc, type, TREE_OPERAND (t1, 0)));
866           else if (TREE_CODE (t2) == NEGATE_EXPR)
867             tem = build2 (MINUS_EXPR, type, fold_convert_loc (loc, type, t1),
868                           fold_convert_loc (loc, type, TREE_OPERAND (t2, 0)));
869           else if (integer_zerop (t2))
870             return fold_convert_loc (loc, type, t1);
871         }
872       else if (code == MINUS_EXPR)
873         {
874           if (integer_zerop (t2))
875             return fold_convert_loc (loc, type, t1);
876         }
877
878       tem = build2 (code, type, fold_convert_loc (loc, type, t1),
879                     fold_convert_loc (loc, type, t2));
880       goto associate_trees_exit;
881     }
882
883   return fold_build2_loc (loc, code, type, fold_convert_loc (loc, type, t1),
884                       fold_convert_loc (loc, type, t2));
885  associate_trees_exit:
886   protected_set_expr_location (tem, loc);
887   return tem;
888 }
889 \f
890 /* Check whether TYPE1 and TYPE2 are equivalent integer types, suitable
891    for use in int_const_binop, size_binop and size_diffop.  */
892
893 static bool
894 int_binop_types_match_p (enum tree_code code, const_tree type1, const_tree type2)
895 {
896   if (TREE_CODE (type1) != INTEGER_TYPE && !POINTER_TYPE_P (type1))
897     return false;
898   if (TREE_CODE (type2) != INTEGER_TYPE && !POINTER_TYPE_P (type2))
899     return false;
900
901   switch (code)
902     {
903     case LSHIFT_EXPR:
904     case RSHIFT_EXPR:
905     case LROTATE_EXPR:
906     case RROTATE_EXPR:
907       return true;
908
909     default:
910       break;
911     }
912
913   return TYPE_UNSIGNED (type1) == TYPE_UNSIGNED (type2)
914          && TYPE_PRECISION (type1) == TYPE_PRECISION (type2)
915          && TYPE_MODE (type1) == TYPE_MODE (type2);
916 }
917
918
919 /* Combine two integer constants ARG1 and ARG2 under operation CODE
920    to produce a new constant.  Return NULL_TREE if we don't know how
921    to evaluate CODE at compile-time.
922
923    If NOTRUNC is nonzero, do not truncate the result to fit the data type.  */
924
925 tree
926 int_const_binop (enum tree_code code, const_tree arg1, const_tree arg2, int notrunc)
927 {
928   unsigned HOST_WIDE_INT int1l, int2l;
929   HOST_WIDE_INT int1h, int2h;
930   unsigned HOST_WIDE_INT low;
931   HOST_WIDE_INT hi;
932   unsigned HOST_WIDE_INT garbagel;
933   HOST_WIDE_INT garbageh;
934   tree t;
935   tree type = TREE_TYPE (arg1);
936   int uns = TYPE_UNSIGNED (type);
937   int is_sizetype
938     = (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type));
939   int overflow = 0;
940
941   int1l = TREE_INT_CST_LOW (arg1);
942   int1h = TREE_INT_CST_HIGH (arg1);
943   int2l = TREE_INT_CST_LOW (arg2);
944   int2h = TREE_INT_CST_HIGH (arg2);
945
946   switch (code)
947     {
948     case BIT_IOR_EXPR:
949       low = int1l | int2l, hi = int1h | int2h;
950       break;
951
952     case BIT_XOR_EXPR:
953       low = int1l ^ int2l, hi = int1h ^ int2h;
954       break;
955
956     case BIT_AND_EXPR:
957       low = int1l & int2l, hi = int1h & int2h;
958       break;
959
960     case RSHIFT_EXPR:
961       int2l = -int2l;
962     case LSHIFT_EXPR:
963       /* It's unclear from the C standard whether shifts can overflow.
964          The following code ignores overflow; perhaps a C standard
965          interpretation ruling is needed.  */
966       lshift_double (int1l, int1h, int2l, TYPE_PRECISION (type),
967                      &low, &hi, !uns);
968       break;
969
970     case RROTATE_EXPR:
971       int2l = - int2l;
972     case LROTATE_EXPR:
973       lrotate_double (int1l, int1h, int2l, TYPE_PRECISION (type),
974                       &low, &hi);
975       break;
976
977     case PLUS_EXPR:
978       overflow = add_double (int1l, int1h, int2l, int2h, &low, &hi);
979       break;
980
981     case MINUS_EXPR:
982       neg_double (int2l, int2h, &low, &hi);
983       add_double (int1l, int1h, low, hi, &low, &hi);
984       overflow = OVERFLOW_SUM_SIGN (hi, int2h, int1h);
985       break;
986
987     case MULT_EXPR:
988       overflow = mul_double (int1l, int1h, int2l, int2h, &low, &hi);
989       break;
990
991     case TRUNC_DIV_EXPR:
992     case FLOOR_DIV_EXPR: case CEIL_DIV_EXPR:
993     case EXACT_DIV_EXPR:
994       /* This is a shortcut for a common special case.  */
995       if (int2h == 0 && (HOST_WIDE_INT) int2l > 0
996           && !TREE_OVERFLOW (arg1)
997           && !TREE_OVERFLOW (arg2)
998           && int1h == 0 && (HOST_WIDE_INT) int1l >= 0)
999         {
1000           if (code == CEIL_DIV_EXPR)
1001             int1l += int2l - 1;
1002
1003           low = int1l / int2l, hi = 0;
1004           break;
1005         }
1006
1007       /* ... fall through ...  */
1008
1009     case ROUND_DIV_EXPR:
1010       if (int2h == 0 && int2l == 0)
1011         return NULL_TREE;
1012       if (int2h == 0 && int2l == 1)
1013         {
1014           low = int1l, hi = int1h;
1015           break;
1016         }
1017       if (int1l == int2l && int1h == int2h
1018           && ! (int1l == 0 && int1h == 0))
1019         {
1020           low = 1, hi = 0;
1021           break;
1022         }
1023       overflow = div_and_round_double (code, uns, int1l, int1h, int2l, int2h,
1024                                        &low, &hi, &garbagel, &garbageh);
1025       break;
1026
1027     case TRUNC_MOD_EXPR:
1028     case FLOOR_MOD_EXPR: case CEIL_MOD_EXPR:
1029       /* This is a shortcut for a common special case.  */
1030       if (int2h == 0 && (HOST_WIDE_INT) int2l > 0
1031           && !TREE_OVERFLOW (arg1)
1032           && !TREE_OVERFLOW (arg2)
1033           && int1h == 0 && (HOST_WIDE_INT) int1l >= 0)
1034         {
1035           if (code == CEIL_MOD_EXPR)
1036             int1l += int2l - 1;
1037           low = int1l % int2l, hi = 0;
1038           break;
1039         }
1040
1041       /* ... fall through ...  */
1042
1043     case ROUND_MOD_EXPR:
1044       if (int2h == 0 && int2l == 0)
1045         return NULL_TREE;
1046       overflow = div_and_round_double (code, uns,
1047                                        int1l, int1h, int2l, int2h,
1048                                        &garbagel, &garbageh, &low, &hi);
1049       break;
1050
1051     case MIN_EXPR:
1052     case MAX_EXPR:
1053       if (uns)
1054         low = (((unsigned HOST_WIDE_INT) int1h
1055                 < (unsigned HOST_WIDE_INT) int2h)
1056                || (((unsigned HOST_WIDE_INT) int1h
1057                     == (unsigned HOST_WIDE_INT) int2h)
1058                    && int1l < int2l));
1059       else
1060         low = (int1h < int2h
1061                || (int1h == int2h && int1l < int2l));
1062
1063       if (low == (code == MIN_EXPR))
1064         low = int1l, hi = int1h;
1065       else
1066         low = int2l, hi = int2h;
1067       break;
1068
1069     default:
1070       return NULL_TREE;
1071     }
1072
1073   if (notrunc)
1074     {
1075       t = build_int_cst_wide (TREE_TYPE (arg1), low, hi);
1076
1077       /* Propagate overflow flags ourselves.  */
1078       if (((!uns || is_sizetype) && overflow)
1079           | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2))
1080         {
1081           t = copy_node (t);
1082           TREE_OVERFLOW (t) = 1;
1083         }
1084     }
1085   else
1086     t = force_fit_type_double (TREE_TYPE (arg1), low, hi, 1,
1087                                ((!uns || is_sizetype) && overflow)
1088                                | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2));
1089
1090   return t;
1091 }
1092
1093 /* Combine two constants ARG1 and ARG2 under operation CODE to produce a new
1094    constant.  We assume ARG1 and ARG2 have the same data type, or at least
1095    are the same kind of constant and the same machine mode.  Return zero if
1096    combining the constants is not allowed in the current operating mode.
1097
1098    If NOTRUNC is nonzero, do not truncate the result to fit the data type.  */
1099
1100 static tree
1101 const_binop (enum tree_code code, tree arg1, tree arg2, int notrunc)
1102 {
1103   /* Sanity check for the recursive cases.  */
1104   if (!arg1 || !arg2)
1105     return NULL_TREE;
1106
1107   STRIP_NOPS (arg1);
1108   STRIP_NOPS (arg2);
1109
1110   if (TREE_CODE (arg1) == INTEGER_CST)
1111     return int_const_binop (code, arg1, arg2, notrunc);
1112
1113   if (TREE_CODE (arg1) == REAL_CST)
1114     {
1115       enum machine_mode mode;
1116       REAL_VALUE_TYPE d1;
1117       REAL_VALUE_TYPE d2;
1118       REAL_VALUE_TYPE value;
1119       REAL_VALUE_TYPE result;
1120       bool inexact;
1121       tree t, type;
1122
1123       /* The following codes are handled by real_arithmetic.  */
1124       switch (code)
1125         {
1126         case PLUS_EXPR:
1127         case MINUS_EXPR:
1128         case MULT_EXPR:
1129         case RDIV_EXPR:
1130         case MIN_EXPR:
1131         case MAX_EXPR:
1132           break;
1133
1134         default:
1135           return NULL_TREE;
1136         }
1137
1138       d1 = TREE_REAL_CST (arg1);
1139       d2 = TREE_REAL_CST (arg2);
1140
1141       type = TREE_TYPE (arg1);
1142       mode = TYPE_MODE (type);
1143
1144       /* Don't perform operation if we honor signaling NaNs and
1145          either operand is a NaN.  */
1146       if (HONOR_SNANS (mode)
1147           && (REAL_VALUE_ISNAN (d1) || REAL_VALUE_ISNAN (d2)))
1148         return NULL_TREE;
1149
1150       /* Don't perform operation if it would raise a division
1151          by zero exception.  */
1152       if (code == RDIV_EXPR
1153           && REAL_VALUES_EQUAL (d2, dconst0)
1154           && (flag_trapping_math || ! MODE_HAS_INFINITIES (mode)))
1155         return NULL_TREE;
1156
1157       /* If either operand is a NaN, just return it.  Otherwise, set up
1158          for floating-point trap; we return an overflow.  */
1159       if (REAL_VALUE_ISNAN (d1))
1160         return arg1;
1161       else if (REAL_VALUE_ISNAN (d2))
1162         return arg2;
1163
1164       inexact = real_arithmetic (&value, code, &d1, &d2);
1165       real_convert (&result, mode, &value);
1166
1167       /* Don't constant fold this floating point operation if
1168          the result has overflowed and flag_trapping_math.  */
1169       if (flag_trapping_math
1170           && MODE_HAS_INFINITIES (mode)
1171           && REAL_VALUE_ISINF (result)
1172           && !REAL_VALUE_ISINF (d1)
1173           && !REAL_VALUE_ISINF (d2))
1174         return NULL_TREE;
1175
1176       /* Don't constant fold this floating point operation if the
1177          result may dependent upon the run-time rounding mode and
1178          flag_rounding_math is set, or if GCC's software emulation
1179          is unable to accurately represent the result.  */
1180       if ((flag_rounding_math
1181            || (MODE_COMPOSITE_P (mode) && !flag_unsafe_math_optimizations))
1182           && (inexact || !real_identical (&result, &value)))
1183         return NULL_TREE;
1184
1185       t = build_real (type, result);
1186
1187       TREE_OVERFLOW (t) = TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2);
1188       return t;
1189     }
1190
1191   if (TREE_CODE (arg1) == FIXED_CST)
1192     {
1193       FIXED_VALUE_TYPE f1;
1194       FIXED_VALUE_TYPE f2;
1195       FIXED_VALUE_TYPE result;
1196       tree t, type;
1197       int sat_p;
1198       bool overflow_p;
1199
1200       /* The following codes are handled by fixed_arithmetic.  */
1201       switch (code)
1202         {
1203         case PLUS_EXPR:
1204         case MINUS_EXPR:
1205         case MULT_EXPR:
1206         case TRUNC_DIV_EXPR:
1207           f2 = TREE_FIXED_CST (arg2);
1208           break;
1209
1210         case LSHIFT_EXPR:
1211         case RSHIFT_EXPR:
1212           f2.data.high = TREE_INT_CST_HIGH (arg2);
1213           f2.data.low = TREE_INT_CST_LOW (arg2);
1214           f2.mode = SImode;
1215           break;
1216
1217         default:
1218           return NULL_TREE;
1219         }
1220
1221       f1 = TREE_FIXED_CST (arg1);
1222       type = TREE_TYPE (arg1);
1223       sat_p = TYPE_SATURATING (type);
1224       overflow_p = fixed_arithmetic (&result, code, &f1, &f2, sat_p);
1225       t = build_fixed (type, result);
1226       /* Propagate overflow flags.  */
1227       if (overflow_p | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2))
1228         TREE_OVERFLOW (t) = 1;
1229       return t;
1230     }
1231
1232   if (TREE_CODE (arg1) == COMPLEX_CST)
1233     {
1234       tree type = TREE_TYPE (arg1);
1235       tree r1 = TREE_REALPART (arg1);
1236       tree i1 = TREE_IMAGPART (arg1);
1237       tree r2 = TREE_REALPART (arg2);
1238       tree i2 = TREE_IMAGPART (arg2);
1239       tree real, imag;
1240
1241       switch (code)
1242         {
1243         case PLUS_EXPR:
1244         case MINUS_EXPR:
1245           real = const_binop (code, r1, r2, notrunc);
1246           imag = const_binop (code, i1, i2, notrunc);
1247           break;
1248
1249         case MULT_EXPR:
1250           if (COMPLEX_FLOAT_TYPE_P (type))
1251             return do_mpc_arg2 (arg1, arg2, type,
1252                                 /* do_nonfinite= */ folding_initializer,
1253                                 mpc_mul);
1254
1255           real = const_binop (MINUS_EXPR,
1256                               const_binop (MULT_EXPR, r1, r2, notrunc),
1257                               const_binop (MULT_EXPR, i1, i2, notrunc),
1258                               notrunc);
1259           imag = const_binop (PLUS_EXPR,
1260                               const_binop (MULT_EXPR, r1, i2, notrunc),
1261                               const_binop (MULT_EXPR, i1, r2, notrunc),
1262                               notrunc);
1263           break;
1264
1265         case RDIV_EXPR:
1266           if (COMPLEX_FLOAT_TYPE_P (type))
1267             return do_mpc_arg2 (arg1, arg2, type,
1268                                 /* do_nonfinite= */ folding_initializer,
1269                                 mpc_div);
1270           /* Fallthru ... */
1271         case TRUNC_DIV_EXPR:
1272         case CEIL_DIV_EXPR:
1273         case FLOOR_DIV_EXPR:
1274         case ROUND_DIV_EXPR:
1275           if (flag_complex_method == 0)
1276           {
1277             /* Keep this algorithm in sync with
1278                tree-complex.c:expand_complex_div_straight().
1279
1280                Expand complex division to scalars, straightforward algorithm.
1281                a / b = ((ar*br + ai*bi)/t) + i((ai*br - ar*bi)/t)
1282                t = br*br + bi*bi
1283             */
1284             tree magsquared
1285               = const_binop (PLUS_EXPR,
1286                              const_binop (MULT_EXPR, r2, r2, notrunc),
1287                              const_binop (MULT_EXPR, i2, i2, notrunc),
1288                              notrunc);
1289             tree t1
1290               = const_binop (PLUS_EXPR,
1291                              const_binop (MULT_EXPR, r1, r2, notrunc),
1292                              const_binop (MULT_EXPR, i1, i2, notrunc),
1293                              notrunc);
1294             tree t2
1295               = const_binop (MINUS_EXPR,
1296                              const_binop (MULT_EXPR, i1, r2, notrunc),
1297                              const_binop (MULT_EXPR, r1, i2, notrunc),
1298                              notrunc);
1299
1300             real = const_binop (code, t1, magsquared, notrunc);
1301             imag = const_binop (code, t2, magsquared, notrunc);
1302           }
1303           else
1304           {
1305             /* Keep this algorithm in sync with
1306                tree-complex.c:expand_complex_div_wide().
1307
1308                Expand complex division to scalars, modified algorithm to minimize
1309                overflow with wide input ranges.  */
1310             tree compare = fold_build2 (LT_EXPR, boolean_type_node,
1311                                         fold_abs_const (r2, TREE_TYPE (type)),
1312                                         fold_abs_const (i2, TREE_TYPE (type)));
1313
1314             if (integer_nonzerop (compare))
1315               {
1316                 /* In the TRUE branch, we compute
1317                    ratio = br/bi;
1318                    div = (br * ratio) + bi;
1319                    tr = (ar * ratio) + ai;
1320                    ti = (ai * ratio) - ar;
1321                    tr = tr / div;
1322                    ti = ti / div;  */
1323                 tree ratio = const_binop (code, r2, i2, notrunc);
1324                 tree div = const_binop (PLUS_EXPR, i2,
1325                                         const_binop (MULT_EXPR, r2, ratio,
1326                                                      notrunc),
1327                                         notrunc);
1328                 real = const_binop (MULT_EXPR, r1, ratio, notrunc);
1329                 real = const_binop (PLUS_EXPR, real, i1, notrunc);
1330                 real = const_binop (code, real, div, notrunc);
1331
1332                 imag = const_binop (MULT_EXPR, i1, ratio, notrunc);
1333                 imag = const_binop (MINUS_EXPR, imag, r1, notrunc);
1334                 imag = const_binop (code, imag, div, notrunc);
1335               }
1336             else
1337               {
1338                 /* In the FALSE branch, we compute
1339                    ratio = d/c;
1340                    divisor = (d * ratio) + c;
1341                    tr = (b * ratio) + a;
1342                    ti = b - (a * ratio);
1343                    tr = tr / div;
1344                    ti = ti / div;  */
1345                 tree ratio = const_binop (code, i2, r2, notrunc);
1346                 tree div = const_binop (PLUS_EXPR, r2,
1347                                         const_binop (MULT_EXPR, i2, ratio,
1348                                                      notrunc),
1349                                         notrunc);
1350
1351                 real = const_binop (MULT_EXPR, i1, ratio, notrunc);
1352                 real = const_binop (PLUS_EXPR, real, r1, notrunc);
1353                 real = const_binop (code, real, div, notrunc);
1354
1355                 imag = const_binop (MULT_EXPR, r1, ratio, notrunc);
1356                 imag = const_binop (MINUS_EXPR, i1, imag, notrunc);
1357                 imag = const_binop (code, imag, div, notrunc);
1358               }
1359           }
1360           break;
1361
1362         default:
1363           return NULL_TREE;
1364         }
1365
1366       if (real && imag)
1367         return build_complex (type, real, imag);
1368     }
1369
1370   if (TREE_CODE (arg1) == VECTOR_CST)
1371     {
1372       tree type = TREE_TYPE(arg1);
1373       int count = TYPE_VECTOR_SUBPARTS (type), i;
1374       tree elements1, elements2, list = NULL_TREE;
1375
1376       if(TREE_CODE(arg2) != VECTOR_CST)
1377         return NULL_TREE;
1378
1379       elements1 = TREE_VECTOR_CST_ELTS (arg1);
1380       elements2 = TREE_VECTOR_CST_ELTS (arg2);
1381
1382       for (i = 0; i < count; i++)
1383         {
1384           tree elem1, elem2, elem;
1385
1386           /* The trailing elements can be empty and should be treated as 0 */
1387           if(!elements1)
1388             elem1 = fold_convert_const (NOP_EXPR, TREE_TYPE (type), integer_zero_node);
1389           else
1390             {
1391               elem1 = TREE_VALUE(elements1);
1392               elements1 = TREE_CHAIN (elements1);
1393             }
1394
1395           if(!elements2)
1396             elem2 = fold_convert_const (NOP_EXPR, TREE_TYPE (type), integer_zero_node);
1397           else
1398             {
1399               elem2 = TREE_VALUE(elements2);
1400               elements2 = TREE_CHAIN (elements2);
1401             }
1402
1403           elem = const_binop (code, elem1, elem2, notrunc);
1404
1405           /* It is possible that const_binop cannot handle the given
1406             code and return NULL_TREE */
1407           if(elem == NULL_TREE)
1408             return NULL_TREE;
1409
1410           list = tree_cons (NULL_TREE, elem, list);
1411         }
1412       return build_vector(type, nreverse(list));
1413     }
1414   return NULL_TREE;
1415 }
1416
1417 /* Create a size type INT_CST node with NUMBER sign extended.  KIND
1418    indicates which particular sizetype to create.  */
1419
1420 tree
1421 size_int_kind (HOST_WIDE_INT number, enum size_type_kind kind)
1422 {
1423   return build_int_cst (sizetype_tab[(int) kind], number);
1424 }
1425 \f
1426 /* Combine operands OP1 and OP2 with arithmetic operation CODE.  CODE
1427    is a tree code.  The type of the result is taken from the operands.
1428    Both must be equivalent integer types, ala int_binop_types_match_p.
1429    If the operands are constant, so is the result.  */
1430
1431 tree
1432 size_binop_loc (location_t loc, enum tree_code code, tree arg0, tree arg1)
1433 {
1434   tree type = TREE_TYPE (arg0);
1435
1436   if (arg0 == error_mark_node || arg1 == error_mark_node)
1437     return error_mark_node;
1438
1439   gcc_assert (int_binop_types_match_p (code, TREE_TYPE (arg0),
1440                                        TREE_TYPE (arg1)));
1441
1442   /* Handle the special case of two integer constants faster.  */
1443   if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
1444     {
1445       /* And some specific cases even faster than that.  */
1446       if (code == PLUS_EXPR)
1447         {
1448           if (integer_zerop (arg0) && !TREE_OVERFLOW (arg0))
1449             return arg1;
1450           if (integer_zerop (arg1) && !TREE_OVERFLOW (arg1))
1451             return arg0;
1452         }
1453       else if (code == MINUS_EXPR)
1454         {
1455           if (integer_zerop (arg1) && !TREE_OVERFLOW (arg1))
1456             return arg0;
1457         }
1458       else if (code == MULT_EXPR)
1459         {
1460           if (integer_onep (arg0) && !TREE_OVERFLOW (arg0))
1461             return arg1;
1462         }
1463
1464       /* Handle general case of two integer constants.  */
1465       return int_const_binop (code, arg0, arg1, 0);
1466     }
1467
1468   return fold_build2_loc (loc, code, type, arg0, arg1);
1469 }
1470
1471 /* Given two values, either both of sizetype or both of bitsizetype,
1472    compute the difference between the two values.  Return the value
1473    in signed type corresponding to the type of the operands.  */
1474
1475 tree
1476 size_diffop_loc (location_t loc, tree arg0, tree arg1)
1477 {
1478   tree type = TREE_TYPE (arg0);
1479   tree ctype;
1480
1481   gcc_assert (int_binop_types_match_p (MINUS_EXPR, TREE_TYPE (arg0),
1482                                        TREE_TYPE (arg1)));
1483
1484   /* If the type is already signed, just do the simple thing.  */
1485   if (!TYPE_UNSIGNED (type))
1486     return size_binop_loc (loc, MINUS_EXPR, arg0, arg1);
1487
1488   if (type == sizetype)
1489     ctype = ssizetype;
1490   else if (type == bitsizetype)
1491     ctype = sbitsizetype;
1492   else
1493     ctype = signed_type_for (type);
1494
1495   /* If either operand is not a constant, do the conversions to the signed
1496      type and subtract.  The hardware will do the right thing with any
1497      overflow in the subtraction.  */
1498   if (TREE_CODE (arg0) != INTEGER_CST || TREE_CODE (arg1) != INTEGER_CST)
1499     return size_binop_loc (loc, MINUS_EXPR,
1500                            fold_convert_loc (loc, ctype, arg0),
1501                            fold_convert_loc (loc, ctype, arg1));
1502
1503   /* If ARG0 is larger than ARG1, subtract and return the result in CTYPE.
1504      Otherwise, subtract the other way, convert to CTYPE (we know that can't
1505      overflow) and negate (which can't either).  Special-case a result
1506      of zero while we're here.  */
1507   if (tree_int_cst_equal (arg0, arg1))
1508     return build_int_cst (ctype, 0);
1509   else if (tree_int_cst_lt (arg1, arg0))
1510     return fold_convert_loc (loc, ctype,
1511                              size_binop_loc (loc, MINUS_EXPR, arg0, arg1));
1512   else
1513     return size_binop_loc (loc, MINUS_EXPR, build_int_cst (ctype, 0),
1514                            fold_convert_loc (loc, ctype,
1515                                              size_binop_loc (loc,
1516                                                              MINUS_EXPR,
1517                                                              arg1, arg0)));
1518 }
1519 \f
1520 /* A subroutine of fold_convert_const handling conversions of an
1521    INTEGER_CST to another integer type.  */
1522
1523 static tree
1524 fold_convert_const_int_from_int (tree type, const_tree arg1)
1525 {
1526   tree t;
1527
1528   /* Given an integer constant, make new constant with new type,
1529      appropriately sign-extended or truncated.  */
1530   t = force_fit_type_double (type, TREE_INT_CST_LOW (arg1),
1531                              TREE_INT_CST_HIGH (arg1),
1532                              !POINTER_TYPE_P (TREE_TYPE (arg1)),
1533                              (TREE_INT_CST_HIGH (arg1) < 0
1534                               && (TYPE_UNSIGNED (type)
1535                                   < TYPE_UNSIGNED (TREE_TYPE (arg1))))
1536                              | TREE_OVERFLOW (arg1));
1537
1538   return t;
1539 }
1540
1541 /* A subroutine of fold_convert_const handling conversions a REAL_CST
1542    to an integer type.  */
1543
1544 static tree
1545 fold_convert_const_int_from_real (enum tree_code code, tree type, const_tree arg1)
1546 {
1547   int overflow = 0;
1548   tree t;
1549
1550   /* The following code implements the floating point to integer
1551      conversion rules required by the Java Language Specification,
1552      that IEEE NaNs are mapped to zero and values that overflow
1553      the target precision saturate, i.e. values greater than
1554      INT_MAX are mapped to INT_MAX, and values less than INT_MIN
1555      are mapped to INT_MIN.  These semantics are allowed by the
1556      C and C++ standards that simply state that the behavior of
1557      FP-to-integer conversion is unspecified upon overflow.  */
1558
1559   double_int val;
1560   REAL_VALUE_TYPE r;
1561   REAL_VALUE_TYPE x = TREE_REAL_CST (arg1);
1562
1563   switch (code)
1564     {
1565     case FIX_TRUNC_EXPR:
1566       real_trunc (&r, VOIDmode, &x);
1567       break;
1568
1569     default:
1570       gcc_unreachable ();
1571     }
1572
1573   /* If R is NaN, return zero and show we have an overflow.  */
1574   if (REAL_VALUE_ISNAN (r))
1575     {
1576       overflow = 1;
1577       val = double_int_zero;
1578     }
1579
1580   /* See if R is less than the lower bound or greater than the
1581      upper bound.  */
1582
1583   if (! overflow)
1584     {
1585       tree lt = TYPE_MIN_VALUE (type);
1586       REAL_VALUE_TYPE l = real_value_from_int_cst (NULL_TREE, lt);
1587       if (REAL_VALUES_LESS (r, l))
1588         {
1589           overflow = 1;
1590           val = tree_to_double_int (lt);
1591         }
1592     }
1593
1594   if (! overflow)
1595     {
1596       tree ut = TYPE_MAX_VALUE (type);
1597       if (ut)
1598         {
1599           REAL_VALUE_TYPE u = real_value_from_int_cst (NULL_TREE, ut);
1600           if (REAL_VALUES_LESS (u, r))
1601             {
1602               overflow = 1;
1603               val = tree_to_double_int (ut);
1604             }
1605         }
1606     }
1607
1608   if (! overflow)
1609     real_to_integer2 ((HOST_WIDE_INT *) &val.low, &val.high, &r);
1610
1611   t = force_fit_type_double (type, val.low, val.high, -1,
1612                              overflow | TREE_OVERFLOW (arg1));
1613   return t;
1614 }
1615
1616 /* A subroutine of fold_convert_const handling conversions of a
1617    FIXED_CST to an integer type.  */
1618
1619 static tree
1620 fold_convert_const_int_from_fixed (tree type, const_tree arg1)
1621 {
1622   tree t;
1623   double_int temp, temp_trunc;
1624   unsigned int mode;
1625
1626   /* Right shift FIXED_CST to temp by fbit.  */
1627   temp = TREE_FIXED_CST (arg1).data;
1628   mode = TREE_FIXED_CST (arg1).mode;
1629   if (GET_MODE_FBIT (mode) < 2 * HOST_BITS_PER_WIDE_INT)
1630     {
1631       temp = double_int_rshift (temp, GET_MODE_FBIT (mode),
1632                                 HOST_BITS_PER_DOUBLE_INT,
1633                                 SIGNED_FIXED_POINT_MODE_P (mode));
1634
1635       /* Left shift temp to temp_trunc by fbit.  */
1636       temp_trunc = double_int_lshift (temp, GET_MODE_FBIT (mode),
1637                                       HOST_BITS_PER_DOUBLE_INT,
1638                                       SIGNED_FIXED_POINT_MODE_P (mode));
1639     }
1640   else
1641     {
1642       temp = double_int_zero;
1643       temp_trunc = double_int_zero;
1644     }
1645
1646   /* If FIXED_CST is negative, we need to round the value toward 0.
1647      By checking if the fractional bits are not zero to add 1 to temp.  */
1648   if (SIGNED_FIXED_POINT_MODE_P (mode)
1649       && double_int_negative_p (temp_trunc)
1650       && !double_int_equal_p (TREE_FIXED_CST (arg1).data, temp_trunc))
1651     temp = double_int_add (temp, double_int_one);
1652
1653   /* Given a fixed-point constant, make new constant with new type,
1654      appropriately sign-extended or truncated.  */
1655   t = force_fit_type_double (type, temp.low, temp.high, -1,
1656                              (double_int_negative_p (temp)
1657                               && (TYPE_UNSIGNED (type)
1658                                   < TYPE_UNSIGNED (TREE_TYPE (arg1))))
1659                              | TREE_OVERFLOW (arg1));
1660
1661   return t;
1662 }
1663
1664 /* A subroutine of fold_convert_const handling conversions a REAL_CST
1665    to another floating point type.  */
1666
1667 static tree
1668 fold_convert_const_real_from_real (tree type, const_tree arg1)
1669 {
1670   REAL_VALUE_TYPE value;
1671   tree t;
1672
1673   real_convert (&value, TYPE_MODE (type), &TREE_REAL_CST (arg1));
1674   t = build_real (type, value);
1675
1676   /* If converting an infinity or NAN to a representation that doesn't
1677      have one, set the overflow bit so that we can produce some kind of
1678      error message at the appropriate point if necessary.  It's not the
1679      most user-friendly message, but it's better than nothing.  */
1680   if (REAL_VALUE_ISINF (TREE_REAL_CST (arg1))
1681       && !MODE_HAS_INFINITIES (TYPE_MODE (type)))
1682     TREE_OVERFLOW (t) = 1;
1683   else if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg1))
1684            && !MODE_HAS_NANS (TYPE_MODE (type)))
1685     TREE_OVERFLOW (t) = 1;
1686   /* Regular overflow, conversion produced an infinity in a mode that
1687      can't represent them.  */
1688   else if (!MODE_HAS_INFINITIES (TYPE_MODE (type))
1689            && REAL_VALUE_ISINF (value)
1690            && !REAL_VALUE_ISINF (TREE_REAL_CST (arg1)))
1691     TREE_OVERFLOW (t) = 1;
1692   else
1693     TREE_OVERFLOW (t) = TREE_OVERFLOW (arg1);
1694   return t;
1695 }
1696
1697 /* A subroutine of fold_convert_const handling conversions a FIXED_CST
1698    to a floating point type.  */
1699
1700 static tree
1701 fold_convert_const_real_from_fixed (tree type, const_tree arg1)
1702 {
1703   REAL_VALUE_TYPE value;
1704   tree t;
1705
1706   real_convert_from_fixed (&value, TYPE_MODE (type), &TREE_FIXED_CST (arg1));
1707   t = build_real (type, value);
1708
1709   TREE_OVERFLOW (t) = TREE_OVERFLOW (arg1);
1710   return t;
1711 }
1712
1713 /* A subroutine of fold_convert_const handling conversions a FIXED_CST
1714    to another fixed-point type.  */
1715
1716 static tree
1717 fold_convert_const_fixed_from_fixed (tree type, const_tree arg1)
1718 {
1719   FIXED_VALUE_TYPE value;
1720   tree t;
1721   bool overflow_p;
1722
1723   overflow_p = fixed_convert (&value, TYPE_MODE (type), &TREE_FIXED_CST (arg1),
1724                               TYPE_SATURATING (type));
1725   t = build_fixed (type, value);
1726
1727   /* Propagate overflow flags.  */
1728   if (overflow_p | TREE_OVERFLOW (arg1))
1729     TREE_OVERFLOW (t) = 1;
1730   return t;
1731 }
1732
1733 /* A subroutine of fold_convert_const handling conversions an INTEGER_CST
1734    to a fixed-point type.  */
1735
1736 static tree
1737 fold_convert_const_fixed_from_int (tree type, const_tree arg1)
1738 {
1739   FIXED_VALUE_TYPE value;
1740   tree t;
1741   bool overflow_p;
1742
1743   overflow_p = fixed_convert_from_int (&value, TYPE_MODE (type),
1744                                        TREE_INT_CST (arg1),
1745                                        TYPE_UNSIGNED (TREE_TYPE (arg1)),
1746                                        TYPE_SATURATING (type));
1747   t = build_fixed (type, value);
1748
1749   /* Propagate overflow flags.  */
1750   if (overflow_p | TREE_OVERFLOW (arg1))
1751     TREE_OVERFLOW (t) = 1;
1752   return t;
1753 }
1754
1755 /* A subroutine of fold_convert_const handling conversions a REAL_CST
1756    to a fixed-point type.  */
1757
1758 static tree
1759 fold_convert_const_fixed_from_real (tree type, const_tree arg1)
1760 {
1761   FIXED_VALUE_TYPE value;
1762   tree t;
1763   bool overflow_p;
1764
1765   overflow_p = fixed_convert_from_real (&value, TYPE_MODE (type),
1766                                         &TREE_REAL_CST (arg1),
1767                                         TYPE_SATURATING (type));
1768   t = build_fixed (type, value);
1769
1770   /* Propagate overflow flags.  */
1771   if (overflow_p | TREE_OVERFLOW (arg1))
1772     TREE_OVERFLOW (t) = 1;
1773   return t;
1774 }
1775
1776 /* Attempt to fold type conversion operation CODE of expression ARG1 to
1777    type TYPE.  If no simplification can be done return NULL_TREE.  */
1778
1779 static tree
1780 fold_convert_const (enum tree_code code, tree type, tree arg1)
1781 {
1782   if (TREE_TYPE (arg1) == type)
1783     return arg1;
1784
1785   if (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type)
1786       || TREE_CODE (type) == OFFSET_TYPE)
1787     {
1788       if (TREE_CODE (arg1) == INTEGER_CST)
1789         return fold_convert_const_int_from_int (type, arg1);
1790       else if (TREE_CODE (arg1) == REAL_CST)
1791         return fold_convert_const_int_from_real (code, type, arg1);
1792       else if (TREE_CODE (arg1) == FIXED_CST)
1793         return fold_convert_const_int_from_fixed (type, arg1);
1794     }
1795   else if (TREE_CODE (type) == REAL_TYPE)
1796     {
1797       if (TREE_CODE (arg1) == INTEGER_CST)
1798         return build_real_from_int_cst (type, arg1);
1799       else if (TREE_CODE (arg1) == REAL_CST)
1800         return fold_convert_const_real_from_real (type, arg1);
1801       else if (TREE_CODE (arg1) == FIXED_CST)
1802         return fold_convert_const_real_from_fixed (type, arg1);
1803     }
1804   else if (TREE_CODE (type) == FIXED_POINT_TYPE)
1805     {
1806       if (TREE_CODE (arg1) == FIXED_CST)
1807         return fold_convert_const_fixed_from_fixed (type, arg1);
1808       else if (TREE_CODE (arg1) == INTEGER_CST)
1809         return fold_convert_const_fixed_from_int (type, arg1);
1810       else if (TREE_CODE (arg1) == REAL_CST)
1811         return fold_convert_const_fixed_from_real (type, arg1);
1812     }
1813   return NULL_TREE;
1814 }
1815
1816 /* Construct a vector of zero elements of vector type TYPE.  */
1817
1818 static tree
1819 build_zero_vector (tree type)
1820 {
1821   tree elem, list;
1822   int i, units;
1823
1824   elem = fold_convert_const (NOP_EXPR, TREE_TYPE (type), integer_zero_node);
1825   units = TYPE_VECTOR_SUBPARTS (type);
1826
1827   list = NULL_TREE;
1828   for (i = 0; i < units; i++)
1829     list = tree_cons (NULL_TREE, elem, list);
1830   return build_vector (type, list);
1831 }
1832
1833 /* Returns true, if ARG is convertible to TYPE using a NOP_EXPR.  */
1834
1835 bool
1836 fold_convertible_p (const_tree type, const_tree arg)
1837 {
1838   tree orig = TREE_TYPE (arg);
1839
1840   if (type == orig)
1841     return true;
1842
1843   if (TREE_CODE (arg) == ERROR_MARK
1844       || TREE_CODE (type) == ERROR_MARK
1845       || TREE_CODE (orig) == ERROR_MARK)
1846     return false;
1847
1848   if (TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (orig))
1849     return true;
1850
1851   switch (TREE_CODE (type))
1852     {
1853     case INTEGER_TYPE: case ENUMERAL_TYPE: case BOOLEAN_TYPE:
1854     case POINTER_TYPE: case REFERENCE_TYPE:
1855     case OFFSET_TYPE:
1856       if (INTEGRAL_TYPE_P (orig) || POINTER_TYPE_P (orig)
1857           || TREE_CODE (orig) == OFFSET_TYPE)
1858         return true;
1859       return (TREE_CODE (orig) == VECTOR_TYPE
1860               && tree_int_cst_equal (TYPE_SIZE (type), TYPE_SIZE (orig)));
1861
1862     case REAL_TYPE:
1863     case FIXED_POINT_TYPE:
1864     case COMPLEX_TYPE:
1865     case VECTOR_TYPE:
1866     case VOID_TYPE:
1867       return TREE_CODE (type) == TREE_CODE (orig);
1868
1869     default:
1870       return false;
1871     }
1872 }
1873
1874 /* Convert expression ARG to type TYPE.  Used by the middle-end for
1875    simple conversions in preference to calling the front-end's convert.  */
1876
1877 tree
1878 fold_convert_loc (location_t loc, tree type, tree arg)
1879 {
1880   tree orig = TREE_TYPE (arg);
1881   tree tem;
1882
1883   if (type == orig)
1884     return arg;
1885
1886   if (TREE_CODE (arg) == ERROR_MARK
1887       || TREE_CODE (type) == ERROR_MARK
1888       || TREE_CODE (orig) == ERROR_MARK)
1889     return error_mark_node;
1890
1891   if (TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (orig))
1892     return fold_build1_loc (loc, NOP_EXPR, type, arg);
1893
1894   switch (TREE_CODE (type))
1895     {
1896     case POINTER_TYPE:
1897     case REFERENCE_TYPE:
1898       /* Handle conversions between pointers to different address spaces.  */
1899       if (POINTER_TYPE_P (orig)
1900           && (TYPE_ADDR_SPACE (TREE_TYPE (type))
1901               != TYPE_ADDR_SPACE (TREE_TYPE (orig))))
1902         return fold_build1_loc (loc, ADDR_SPACE_CONVERT_EXPR, type, arg);
1903       /* fall through */
1904
1905     case INTEGER_TYPE: case ENUMERAL_TYPE: case BOOLEAN_TYPE:
1906     case OFFSET_TYPE:
1907       if (TREE_CODE (arg) == INTEGER_CST)
1908         {
1909           tem = fold_convert_const (NOP_EXPR, type, arg);
1910           if (tem != NULL_TREE)
1911             return tem;
1912         }
1913       if (INTEGRAL_TYPE_P (orig) || POINTER_TYPE_P (orig)
1914           || TREE_CODE (orig) == OFFSET_TYPE)
1915         return fold_build1_loc (loc, NOP_EXPR, type, arg);
1916       if (TREE_CODE (orig) == COMPLEX_TYPE)
1917         return fold_convert_loc (loc, type,
1918                              fold_build1_loc (loc, REALPART_EXPR,
1919                                           TREE_TYPE (orig), arg));
1920       gcc_assert (TREE_CODE (orig) == VECTOR_TYPE
1921                   && tree_int_cst_equal (TYPE_SIZE (type), TYPE_SIZE (orig)));
1922       return fold_build1_loc (loc, NOP_EXPR, type, arg);
1923
1924     case REAL_TYPE:
1925       if (TREE_CODE (arg) == INTEGER_CST)
1926         {
1927           tem = fold_convert_const (FLOAT_EXPR, type, arg);
1928           if (tem != NULL_TREE)
1929             return tem;
1930         }
1931       else if (TREE_CODE (arg) == REAL_CST)
1932         {
1933           tem = fold_convert_const (NOP_EXPR, type, arg);
1934           if (tem != NULL_TREE)
1935             return tem;
1936         }
1937       else if (TREE_CODE (arg) == FIXED_CST)
1938         {
1939           tem = fold_convert_const (FIXED_CONVERT_EXPR, type, arg);
1940           if (tem != NULL_TREE)
1941             return tem;
1942         }
1943
1944       switch (TREE_CODE (orig))
1945         {
1946         case INTEGER_TYPE:
1947         case BOOLEAN_TYPE: case ENUMERAL_TYPE:
1948         case POINTER_TYPE: case REFERENCE_TYPE:
1949           return fold_build1_loc (loc, FLOAT_EXPR, type, arg);
1950
1951         case REAL_TYPE:
1952           return fold_build1_loc (loc, NOP_EXPR, type, arg);
1953
1954         case FIXED_POINT_TYPE:
1955           return fold_build1_loc (loc, FIXED_CONVERT_EXPR, type, arg);
1956
1957         case COMPLEX_TYPE:
1958           tem = fold_build1_loc (loc, REALPART_EXPR, TREE_TYPE (orig), arg);
1959           return fold_convert_loc (loc, type, tem);
1960
1961         default:
1962           gcc_unreachable ();
1963         }
1964
1965     case FIXED_POINT_TYPE:
1966       if (TREE_CODE (arg) == FIXED_CST || TREE_CODE (arg) == INTEGER_CST
1967           || TREE_CODE (arg) == REAL_CST)
1968         {
1969           tem = fold_convert_const (FIXED_CONVERT_EXPR, type, arg);
1970           if (tem != NULL_TREE)
1971             goto fold_convert_exit;
1972         }
1973
1974       switch (TREE_CODE (orig))
1975         {
1976         case FIXED_POINT_TYPE:
1977         case INTEGER_TYPE:
1978         case ENUMERAL_TYPE:
1979         case BOOLEAN_TYPE:
1980         case REAL_TYPE:
1981           return fold_build1_loc (loc, FIXED_CONVERT_EXPR, type, arg);
1982
1983         case COMPLEX_TYPE:
1984           tem = fold_build1_loc (loc, REALPART_EXPR, TREE_TYPE (orig), arg);
1985           return fold_convert_loc (loc, type, tem);
1986
1987         default:
1988           gcc_unreachable ();
1989         }
1990
1991     case COMPLEX_TYPE:
1992       switch (TREE_CODE (orig))
1993         {
1994         case INTEGER_TYPE:
1995         case BOOLEAN_TYPE: case ENUMERAL_TYPE:
1996         case POINTER_TYPE: case REFERENCE_TYPE:
1997         case REAL_TYPE:
1998         case FIXED_POINT_TYPE:
1999           return fold_build2_loc (loc, COMPLEX_EXPR, type,
2000                               fold_convert_loc (loc, TREE_TYPE (type), arg),
2001                               fold_convert_loc (loc, TREE_TYPE (type),
2002                                             integer_zero_node));
2003         case COMPLEX_TYPE:
2004           {
2005             tree rpart, ipart;
2006
2007             if (TREE_CODE (arg) == COMPLEX_EXPR)
2008               {
2009                 rpart = fold_convert_loc (loc, TREE_TYPE (type),
2010                                       TREE_OPERAND (arg, 0));
2011                 ipart = fold_convert_loc (loc, TREE_TYPE (type),
2012                                       TREE_OPERAND (arg, 1));
2013                 return fold_build2_loc (loc, COMPLEX_EXPR, type, rpart, ipart);
2014               }
2015
2016             arg = save_expr (arg);
2017             rpart = fold_build1_loc (loc, REALPART_EXPR, TREE_TYPE (orig), arg);
2018             ipart = fold_build1_loc (loc, IMAGPART_EXPR, TREE_TYPE (orig), arg);
2019             rpart = fold_convert_loc (loc, TREE_TYPE (type), rpart);
2020             ipart = fold_convert_loc (loc, TREE_TYPE (type), ipart);
2021             return fold_build2_loc (loc, COMPLEX_EXPR, type, rpart, ipart);
2022           }
2023
2024         default:
2025           gcc_unreachable ();
2026         }
2027
2028     case VECTOR_TYPE:
2029       if (integer_zerop (arg))
2030         return build_zero_vector (type);
2031       gcc_assert (tree_int_cst_equal (TYPE_SIZE (type), TYPE_SIZE (orig)));
2032       gcc_assert (INTEGRAL_TYPE_P (orig) || POINTER_TYPE_P (orig)
2033                   || TREE_CODE (orig) == VECTOR_TYPE);
2034       return fold_build1_loc (loc, VIEW_CONVERT_EXPR, type, arg);
2035
2036     case VOID_TYPE:
2037       tem = fold_ignored_result (arg);
2038       if (TREE_CODE (tem) == MODIFY_EXPR)
2039         goto fold_convert_exit;
2040       return fold_build1_loc (loc, NOP_EXPR, type, tem);
2041
2042     default:
2043       gcc_unreachable ();
2044     }
2045  fold_convert_exit:
2046   protected_set_expr_location (tem, loc);
2047   return tem;
2048 }
2049 \f
2050 /* Return false if expr can be assumed not to be an lvalue, true
2051    otherwise.  */
2052
2053 static bool
2054 maybe_lvalue_p (const_tree x)
2055 {
2056   /* We only need to wrap lvalue tree codes.  */
2057   switch (TREE_CODE (x))
2058   {
2059   case VAR_DECL:
2060   case PARM_DECL:
2061   case RESULT_DECL:
2062   case LABEL_DECL:
2063   case FUNCTION_DECL:
2064   case SSA_NAME:
2065
2066   case COMPONENT_REF:
2067   case INDIRECT_REF:
2068   case ALIGN_INDIRECT_REF:
2069   case MISALIGNED_INDIRECT_REF:
2070   case ARRAY_REF:
2071   case ARRAY_RANGE_REF:
2072   case BIT_FIELD_REF:
2073   case OBJ_TYPE_REF:
2074
2075   case REALPART_EXPR:
2076   case IMAGPART_EXPR:
2077   case PREINCREMENT_EXPR:
2078   case PREDECREMENT_EXPR:
2079   case SAVE_EXPR:
2080   case TRY_CATCH_EXPR:
2081   case WITH_CLEANUP_EXPR:
2082   case COMPOUND_EXPR:
2083   case MODIFY_EXPR:
2084   case TARGET_EXPR:
2085   case COND_EXPR:
2086   case BIND_EXPR:
2087     break;
2088
2089   default:
2090     /* Assume the worst for front-end tree codes.  */
2091     if ((int)TREE_CODE (x) >= NUM_TREE_CODES)
2092       break;
2093     return false;
2094   }
2095
2096   return true;
2097 }
2098
2099 /* Return an expr equal to X but certainly not valid as an lvalue.  */
2100
2101 tree
2102 non_lvalue_loc (location_t loc, tree x)
2103 {
2104   /* While we are in GIMPLE, NON_LVALUE_EXPR doesn't mean anything to
2105      us.  */
2106   if (in_gimple_form)
2107     return x;
2108
2109   if (! maybe_lvalue_p (x))
2110     return x;
2111   x = build1 (NON_LVALUE_EXPR, TREE_TYPE (x), x);
2112   SET_EXPR_LOCATION (x, loc);
2113   return x;
2114 }
2115
2116 /* Nonzero means lvalues are limited to those valid in pedantic ANSI C.
2117    Zero means allow extended lvalues.  */
2118
2119 int pedantic_lvalues;
2120
2121 /* When pedantic, return an expr equal to X but certainly not valid as a
2122    pedantic lvalue.  Otherwise, return X.  */
2123
2124 static tree
2125 pedantic_non_lvalue_loc (location_t loc, tree x)
2126 {
2127   if (pedantic_lvalues)
2128     return non_lvalue_loc (loc, x);
2129   protected_set_expr_location (x, loc);
2130   return x;
2131 }
2132 \f
2133 /* Given a tree comparison code, return the code that is the logical inverse
2134    of the given code.  It is not safe to do this for floating-point
2135    comparisons, except for NE_EXPR and EQ_EXPR, so we receive a machine mode
2136    as well: if reversing the comparison is unsafe, return ERROR_MARK.  */
2137
2138 enum tree_code
2139 invert_tree_comparison (enum tree_code code, bool honor_nans)
2140 {
2141   if (honor_nans && flag_trapping_math)
2142     return ERROR_MARK;
2143
2144   switch (code)
2145     {
2146     case EQ_EXPR:
2147       return NE_EXPR;
2148     case NE_EXPR:
2149       return EQ_EXPR;
2150     case GT_EXPR:
2151       return honor_nans ? UNLE_EXPR : LE_EXPR;
2152     case GE_EXPR:
2153       return honor_nans ? UNLT_EXPR : LT_EXPR;
2154     case LT_EXPR:
2155       return honor_nans ? UNGE_EXPR : GE_EXPR;
2156     case LE_EXPR:
2157       return honor_nans ? UNGT_EXPR : GT_EXPR;
2158     case LTGT_EXPR:
2159       return UNEQ_EXPR;
2160     case UNEQ_EXPR:
2161       return LTGT_EXPR;
2162     case UNGT_EXPR:
2163       return LE_EXPR;
2164     case UNGE_EXPR:
2165       return LT_EXPR;
2166     case UNLT_EXPR:
2167       return GE_EXPR;
2168     case UNLE_EXPR:
2169       return GT_EXPR;
2170     case ORDERED_EXPR:
2171       return UNORDERED_EXPR;
2172     case UNORDERED_EXPR:
2173       return ORDERED_EXPR;
2174     default:
2175       gcc_unreachable ();
2176     }
2177 }
2178
2179 /* Similar, but return the comparison that results if the operands are
2180    swapped.  This is safe for floating-point.  */
2181
2182 enum tree_code
2183 swap_tree_comparison (enum tree_code code)
2184 {
2185   switch (code)
2186     {
2187     case EQ_EXPR:
2188     case NE_EXPR:
2189     case ORDERED_EXPR:
2190     case UNORDERED_EXPR:
2191     case LTGT_EXPR:
2192     case UNEQ_EXPR:
2193       return code;
2194     case GT_EXPR:
2195       return LT_EXPR;
2196     case GE_EXPR:
2197       return LE_EXPR;
2198     case LT_EXPR:
2199       return GT_EXPR;
2200     case LE_EXPR:
2201       return GE_EXPR;
2202     case UNGT_EXPR:
2203       return UNLT_EXPR;
2204     case UNGE_EXPR:
2205       return UNLE_EXPR;
2206     case UNLT_EXPR:
2207       return UNGT_EXPR;
2208     case UNLE_EXPR:
2209       return UNGE_EXPR;
2210     default:
2211       gcc_unreachable ();
2212     }
2213 }
2214
2215
2216 /* Convert a comparison tree code from an enum tree_code representation
2217    into a compcode bit-based encoding.  This function is the inverse of
2218    compcode_to_comparison.  */
2219
2220 static enum comparison_code
2221 comparison_to_compcode (enum tree_code code)
2222 {
2223   switch (code)
2224     {
2225     case LT_EXPR:
2226       return COMPCODE_LT;
2227     case EQ_EXPR:
2228       return COMPCODE_EQ;
2229     case LE_EXPR:
2230       return COMPCODE_LE;
2231     case GT_EXPR:
2232       return COMPCODE_GT;
2233     case NE_EXPR:
2234       return COMPCODE_NE;
2235     case GE_EXPR:
2236       return COMPCODE_GE;
2237     case ORDERED_EXPR:
2238       return COMPCODE_ORD;
2239     case UNORDERED_EXPR:
2240       return COMPCODE_UNORD;
2241     case UNLT_EXPR:
2242       return COMPCODE_UNLT;
2243     case UNEQ_EXPR:
2244       return COMPCODE_UNEQ;
2245     case UNLE_EXPR:
2246       return COMPCODE_UNLE;
2247     case UNGT_EXPR:
2248       return COMPCODE_UNGT;
2249     case LTGT_EXPR:
2250       return COMPCODE_LTGT;
2251     case UNGE_EXPR:
2252       return COMPCODE_UNGE;
2253     default:
2254       gcc_unreachable ();
2255     }
2256 }
2257
2258 /* Convert a compcode bit-based encoding of a comparison operator back
2259    to GCC's enum tree_code representation.  This function is the
2260    inverse of comparison_to_compcode.  */
2261
2262 static enum tree_code
2263 compcode_to_comparison (enum comparison_code code)
2264 {
2265   switch (code)
2266     {
2267     case COMPCODE_LT:
2268       return LT_EXPR;
2269     case COMPCODE_EQ:
2270       return EQ_EXPR;
2271     case COMPCODE_LE:
2272       return LE_EXPR;
2273     case COMPCODE_GT:
2274       return GT_EXPR;
2275     case COMPCODE_NE:
2276       return NE_EXPR;
2277     case COMPCODE_GE:
2278       return GE_EXPR;
2279     case COMPCODE_ORD:
2280       return ORDERED_EXPR;
2281     case COMPCODE_UNORD:
2282       return UNORDERED_EXPR;
2283     case COMPCODE_UNLT:
2284       return UNLT_EXPR;
2285     case COMPCODE_UNEQ:
2286       return UNEQ_EXPR;
2287     case COMPCODE_UNLE:
2288       return UNLE_EXPR;
2289     case COMPCODE_UNGT:
2290       return UNGT_EXPR;
2291     case COMPCODE_LTGT:
2292       return LTGT_EXPR;
2293     case COMPCODE_UNGE:
2294       return UNGE_EXPR;
2295     default:
2296       gcc_unreachable ();
2297     }
2298 }
2299
2300 /* Return a tree for the comparison which is the combination of
2301    doing the AND or OR (depending on CODE) of the two operations LCODE
2302    and RCODE on the identical operands LL_ARG and LR_ARG.  Take into account
2303    the possibility of trapping if the mode has NaNs, and return NULL_TREE
2304    if this makes the transformation invalid.  */
2305
2306 tree
2307 combine_comparisons (location_t loc,
2308                      enum tree_code code, enum tree_code lcode,
2309                      enum tree_code rcode, tree truth_type,
2310                      tree ll_arg, tree lr_arg)
2311 {
2312   bool honor_nans = HONOR_NANS (TYPE_MODE (TREE_TYPE (ll_arg)));
2313   enum comparison_code lcompcode = comparison_to_compcode (lcode);
2314   enum comparison_code rcompcode = comparison_to_compcode (rcode);
2315   int compcode;
2316
2317   switch (code)
2318     {
2319     case TRUTH_AND_EXPR: case TRUTH_ANDIF_EXPR:
2320       compcode = lcompcode & rcompcode;
2321       break;
2322
2323     case TRUTH_OR_EXPR: case TRUTH_ORIF_EXPR:
2324       compcode = lcompcode | rcompcode;
2325       break;
2326
2327     default:
2328       return NULL_TREE;
2329     }
2330
2331   if (!honor_nans)
2332     {
2333       /* Eliminate unordered comparisons, as well as LTGT and ORD
2334          which are not used unless the mode has NaNs.  */
2335       compcode &= ~COMPCODE_UNORD;
2336       if (compcode == COMPCODE_LTGT)
2337         compcode = COMPCODE_NE;
2338       else if (compcode == COMPCODE_ORD)
2339         compcode = COMPCODE_TRUE;
2340     }
2341    else if (flag_trapping_math)
2342      {
2343         /* Check that the original operation and the optimized ones will trap
2344            under the same condition.  */
2345         bool ltrap = (lcompcode & COMPCODE_UNORD) == 0
2346                      && (lcompcode != COMPCODE_EQ)
2347                      && (lcompcode != COMPCODE_ORD);
2348         bool rtrap = (rcompcode & COMPCODE_UNORD) == 0
2349                      && (rcompcode != COMPCODE_EQ)
2350                      && (rcompcode != COMPCODE_ORD);
2351         bool trap = (compcode & COMPCODE_UNORD) == 0
2352                     && (compcode != COMPCODE_EQ)
2353                     && (compcode != COMPCODE_ORD);
2354
2355         /* In a short-circuited boolean expression the LHS might be
2356            such that the RHS, if evaluated, will never trap.  For
2357            example, in ORD (x, y) && (x < y), we evaluate the RHS only
2358            if neither x nor y is NaN.  (This is a mixed blessing: for
2359            example, the expression above will never trap, hence
2360            optimizing it to x < y would be invalid).  */
2361         if ((code == TRUTH_ORIF_EXPR && (lcompcode & COMPCODE_UNORD))
2362             || (code == TRUTH_ANDIF_EXPR && !(lcompcode & COMPCODE_UNORD)))
2363           rtrap = false;
2364
2365         /* If the comparison was short-circuited, and only the RHS
2366            trapped, we may now generate a spurious trap.  */
2367         if (rtrap && !ltrap
2368             && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
2369           return NULL_TREE;
2370
2371         /* If we changed the conditions that cause a trap, we lose.  */
2372         if ((ltrap || rtrap) != trap)
2373           return NULL_TREE;
2374       }
2375
2376   if (compcode == COMPCODE_TRUE)
2377     return constant_boolean_node (true, truth_type);
2378   else if (compcode == COMPCODE_FALSE)
2379     return constant_boolean_node (false, truth_type);
2380   else
2381     {
2382       enum tree_code tcode;
2383
2384       tcode = compcode_to_comparison ((enum comparison_code) compcode);
2385       return fold_build2_loc (loc, tcode, truth_type, ll_arg, lr_arg);
2386     }
2387 }
2388 \f
2389 /* Return nonzero if two operands (typically of the same tree node)
2390    are necessarily equal.  If either argument has side-effects this
2391    function returns zero.  FLAGS modifies behavior as follows:
2392
2393    If OEP_ONLY_CONST is set, only return nonzero for constants.
2394    This function tests whether the operands are indistinguishable;
2395    it does not test whether they are equal using C's == operation.
2396    The distinction is important for IEEE floating point, because
2397    (1) -0.0 and 0.0 are distinguishable, but -0.0==0.0, and
2398    (2) two NaNs may be indistinguishable, but NaN!=NaN.
2399
2400    If OEP_ONLY_CONST is unset, a VAR_DECL is considered equal to itself
2401    even though it may hold multiple values during a function.
2402    This is because a GCC tree node guarantees that nothing else is
2403    executed between the evaluation of its "operands" (which may often
2404    be evaluated in arbitrary order).  Hence if the operands themselves
2405    don't side-effect, the VAR_DECLs, PARM_DECLs etc... must hold the
2406    same value in each operand/subexpression.  Hence leaving OEP_ONLY_CONST
2407    unset means assuming isochronic (or instantaneous) tree equivalence.
2408    Unless comparing arbitrary expression trees, such as from different
2409    statements, this flag can usually be left unset.
2410
2411    If OEP_PURE_SAME is set, then pure functions with identical arguments
2412    are considered the same.  It is used when the caller has other ways
2413    to ensure that global memory is unchanged in between.  */
2414
2415 int
2416 operand_equal_p (const_tree arg0, const_tree arg1, unsigned int flags)
2417 {
2418   /* If either is ERROR_MARK, they aren't equal.  */
2419   if (TREE_CODE (arg0) == ERROR_MARK || TREE_CODE (arg1) == ERROR_MARK
2420       || TREE_TYPE (arg0) == error_mark_node
2421       || TREE_TYPE (arg1) == error_mark_node)
2422     return 0;
2423
2424   /* Similar, if either does not have a type (like a released SSA name), 
2425      they aren't equal.  */
2426   if (!TREE_TYPE (arg0) || !TREE_TYPE (arg1))
2427     return 0;
2428
2429   /* Check equality of integer constants before bailing out due to
2430      precision differences.  */
2431   if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
2432     return tree_int_cst_equal (arg0, arg1);
2433
2434   /* If both types don't have the same signedness, then we can't consider
2435      them equal.  We must check this before the STRIP_NOPS calls
2436      because they may change the signedness of the arguments.  As pointers
2437      strictly don't have a signedness, require either two pointers or
2438      two non-pointers as well.  */
2439   if (TYPE_UNSIGNED (TREE_TYPE (arg0)) != TYPE_UNSIGNED (TREE_TYPE (arg1))
2440       || POINTER_TYPE_P (TREE_TYPE (arg0)) != POINTER_TYPE_P (TREE_TYPE (arg1)))
2441     return 0;
2442
2443   /* We cannot consider pointers to different address space equal.  */
2444   if (POINTER_TYPE_P (TREE_TYPE (arg0)) && POINTER_TYPE_P (TREE_TYPE (arg1))
2445       && (TYPE_ADDR_SPACE (TREE_TYPE (TREE_TYPE (arg0)))
2446           != TYPE_ADDR_SPACE (TREE_TYPE (TREE_TYPE (arg1)))))
2447     return 0;
2448
2449   /* If both types don't have the same precision, then it is not safe
2450      to strip NOPs.  */
2451   if (TYPE_PRECISION (TREE_TYPE (arg0)) != TYPE_PRECISION (TREE_TYPE (arg1)))
2452     return 0;
2453
2454   STRIP_NOPS (arg0);
2455   STRIP_NOPS (arg1);
2456
2457   /* In case both args are comparisons but with different comparison
2458      code, try to swap the comparison operands of one arg to produce
2459      a match and compare that variant.  */
2460   if (TREE_CODE (arg0) != TREE_CODE (arg1)
2461       && COMPARISON_CLASS_P (arg0)
2462       && COMPARISON_CLASS_P (arg1))
2463     {
2464       enum tree_code swap_code = swap_tree_comparison (TREE_CODE (arg1));
2465
2466       if (TREE_CODE (arg0) == swap_code)
2467         return operand_equal_p (TREE_OPERAND (arg0, 0),
2468                                 TREE_OPERAND (arg1, 1), flags)
2469                && operand_equal_p (TREE_OPERAND (arg0, 1),
2470                                    TREE_OPERAND (arg1, 0), flags);
2471     }
2472
2473   if (TREE_CODE (arg0) != TREE_CODE (arg1)
2474       /* This is needed for conversions and for COMPONENT_REF.
2475          Might as well play it safe and always test this.  */
2476       || TREE_CODE (TREE_TYPE (arg0)) == ERROR_MARK
2477       || TREE_CODE (TREE_TYPE (arg1)) == ERROR_MARK
2478       || TYPE_MODE (TREE_TYPE (arg0)) != TYPE_MODE (TREE_TYPE (arg1)))
2479     return 0;
2480
2481   /* If ARG0 and ARG1 are the same SAVE_EXPR, they are necessarily equal.
2482      We don't care about side effects in that case because the SAVE_EXPR
2483      takes care of that for us. In all other cases, two expressions are
2484      equal if they have no side effects.  If we have two identical
2485      expressions with side effects that should be treated the same due
2486      to the only side effects being identical SAVE_EXPR's, that will
2487      be detected in the recursive calls below.  */
2488   if (arg0 == arg1 && ! (flags & OEP_ONLY_CONST)
2489       && (TREE_CODE (arg0) == SAVE_EXPR
2490           || (! TREE_SIDE_EFFECTS (arg0) && ! TREE_SIDE_EFFECTS (arg1))))
2491     return 1;
2492
2493   /* Next handle constant cases, those for which we can return 1 even
2494      if ONLY_CONST is set.  */
2495   if (TREE_CONSTANT (arg0) && TREE_CONSTANT (arg1))
2496     switch (TREE_CODE (arg0))
2497       {
2498       case INTEGER_CST:
2499         return tree_int_cst_equal (arg0, arg1);
2500
2501       case FIXED_CST:
2502         return FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (arg0),
2503                                        TREE_FIXED_CST (arg1));
2504
2505       case REAL_CST:
2506         if (REAL_VALUES_IDENTICAL (TREE_REAL_CST (arg0),
2507                                    TREE_REAL_CST (arg1)))
2508           return 1;
2509
2510
2511         if (!HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg0))))
2512           {
2513             /* If we do not distinguish between signed and unsigned zero,
2514                consider them equal.  */
2515             if (real_zerop (arg0) && real_zerop (arg1))
2516               return 1;
2517           }
2518         return 0;
2519
2520       case VECTOR_CST:
2521         {
2522           tree v1, v2;
2523
2524           v1 = TREE_VECTOR_CST_ELTS (arg0);
2525           v2 = TREE_VECTOR_CST_ELTS (arg1);
2526           while (v1 && v2)
2527             {
2528               if (!operand_equal_p (TREE_VALUE (v1), TREE_VALUE (v2),
2529                                     flags))
2530                 return 0;
2531               v1 = TREE_CHAIN (v1);
2532               v2 = TREE_CHAIN (v2);
2533             }
2534
2535           return v1 == v2;
2536         }
2537
2538       case COMPLEX_CST:
2539         return (operand_equal_p (TREE_REALPART (arg0), TREE_REALPART (arg1),
2540                                  flags)
2541                 && operand_equal_p (TREE_IMAGPART (arg0), TREE_IMAGPART (arg1),
2542                                     flags));
2543
2544       case STRING_CST:
2545         return (TREE_STRING_LENGTH (arg0) == TREE_STRING_LENGTH (arg1)
2546                 && ! memcmp (TREE_STRING_POINTER (arg0),
2547                               TREE_STRING_POINTER (arg1),
2548                               TREE_STRING_LENGTH (arg0)));
2549
2550       case ADDR_EXPR:
2551         return operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0),
2552                                 0);
2553       default:
2554         break;
2555       }
2556
2557   if (flags & OEP_ONLY_CONST)
2558     return 0;
2559
2560 /* Define macros to test an operand from arg0 and arg1 for equality and a
2561    variant that allows null and views null as being different from any
2562    non-null value.  In the latter case, if either is null, the both
2563    must be; otherwise, do the normal comparison.  */
2564 #define OP_SAME(N) operand_equal_p (TREE_OPERAND (arg0, N),     \
2565                                     TREE_OPERAND (arg1, N), flags)
2566
2567 #define OP_SAME_WITH_NULL(N)                            \
2568   ((!TREE_OPERAND (arg0, N) || !TREE_OPERAND (arg1, N)) \
2569    ? TREE_OPERAND (arg0, N) == TREE_OPERAND (arg1, N) : OP_SAME (N))
2570
2571   switch (TREE_CODE_CLASS (TREE_CODE (arg0)))
2572     {
2573     case tcc_unary:
2574       /* Two conversions are equal only if signedness and modes match.  */
2575       switch (TREE_CODE (arg0))
2576         {
2577         CASE_CONVERT:
2578         case FIX_TRUNC_EXPR:
2579           if (TYPE_UNSIGNED (TREE_TYPE (arg0))
2580               != TYPE_UNSIGNED (TREE_TYPE (arg1)))
2581             return 0;
2582           break;
2583         default:
2584           break;
2585         }
2586
2587       return OP_SAME (0);
2588
2589
2590     case tcc_comparison:
2591     case tcc_binary:
2592       if (OP_SAME (0) && OP_SAME (1))
2593         return 1;
2594
2595       /* For commutative ops, allow the other order.  */
2596       return (commutative_tree_code (TREE_CODE (arg0))
2597               && operand_equal_p (TREE_OPERAND (arg0, 0),
2598                                   TREE_OPERAND (arg1, 1), flags)
2599               && operand_equal_p (TREE_OPERAND (arg0, 1),
2600                                   TREE_OPERAND (arg1, 0), flags));
2601
2602     case tcc_reference:
2603       /* If either of the pointer (or reference) expressions we are
2604          dereferencing contain a side effect, these cannot be equal.  */
2605       if (TREE_SIDE_EFFECTS (arg0)
2606           || TREE_SIDE_EFFECTS (arg1))
2607         return 0;
2608
2609       switch (TREE_CODE (arg0))
2610         {
2611         case INDIRECT_REF:
2612         case ALIGN_INDIRECT_REF:
2613         case MISALIGNED_INDIRECT_REF:
2614         case REALPART_EXPR:
2615         case IMAGPART_EXPR:
2616           return OP_SAME (0);
2617
2618         case ARRAY_REF:
2619         case ARRAY_RANGE_REF:
2620           /* Operands 2 and 3 may be null.
2621              Compare the array index by value if it is constant first as we
2622              may have different types but same value here.  */
2623           return (OP_SAME (0)
2624                   && (tree_int_cst_equal (TREE_OPERAND (arg0, 1),
2625                                           TREE_OPERAND (arg1, 1))
2626                       || OP_SAME (1))
2627                   && OP_SAME_WITH_NULL (2)
2628                   && OP_SAME_WITH_NULL (3));
2629
2630         case COMPONENT_REF:
2631           /* Handle operand 2 the same as for ARRAY_REF.  Operand 0
2632              may be NULL when we're called to compare MEM_EXPRs.  */
2633           return OP_SAME_WITH_NULL (0)
2634                  && OP_SAME (1)
2635                  && OP_SAME_WITH_NULL (2);
2636
2637         case BIT_FIELD_REF:
2638           return OP_SAME (0) && OP_SAME (1) && OP_SAME (2);
2639
2640         default:
2641           return 0;
2642         }
2643
2644     case tcc_expression:
2645       switch (TREE_CODE (arg0))
2646         {
2647         case ADDR_EXPR:
2648         case TRUTH_NOT_EXPR:
2649           return OP_SAME (0);
2650
2651         case TRUTH_ANDIF_EXPR:
2652         case TRUTH_ORIF_EXPR:
2653           return OP_SAME (0) && OP_SAME (1);
2654
2655         case TRUTH_AND_EXPR:
2656         case TRUTH_OR_EXPR:
2657         case TRUTH_XOR_EXPR:
2658           if (OP_SAME (0) && OP_SAME (1))
2659             return 1;
2660
2661           /* Otherwise take into account this is a commutative operation.  */
2662           return (operand_equal_p (TREE_OPERAND (arg0, 0),
2663                                    TREE_OPERAND (arg1, 1), flags)
2664                   && operand_equal_p (TREE_OPERAND (arg0, 1),
2665                                       TREE_OPERAND (arg1, 0), flags));
2666
2667         case COND_EXPR:
2668           return OP_SAME (0) && OP_SAME (1) && OP_SAME (2);
2669
2670         default:
2671           return 0;
2672         }
2673
2674     case tcc_vl_exp:
2675       switch (TREE_CODE (arg0))
2676         {
2677         case CALL_EXPR:
2678           /* If the CALL_EXPRs call different functions, then they
2679              clearly can not be equal.  */
2680           if (! operand_equal_p (CALL_EXPR_FN (arg0), CALL_EXPR_FN (arg1),
2681                                  flags))
2682             return 0;
2683
2684           {
2685             unsigned int cef = call_expr_flags (arg0);
2686             if (flags & OEP_PURE_SAME)
2687               cef &= ECF_CONST | ECF_PURE;
2688             else
2689               cef &= ECF_CONST;
2690             if (!cef)
2691               return 0;
2692           }
2693
2694           /* Now see if all the arguments are the same.  */
2695           {
2696             const_call_expr_arg_iterator iter0, iter1;
2697             const_tree a0, a1;
2698             for (a0 = first_const_call_expr_arg (arg0, &iter0),
2699                    a1 = first_const_call_expr_arg (arg1, &iter1);
2700                  a0 && a1;
2701                  a0 = next_const_call_expr_arg (&iter0),
2702                    a1 = next_const_call_expr_arg (&iter1))
2703               if (! operand_equal_p (a0, a1, flags))
2704                 return 0;
2705
2706             /* If we get here and both argument lists are exhausted
2707                then the CALL_EXPRs are equal.  */
2708             return ! (a0 || a1);
2709           }
2710         default:
2711           return 0;
2712         }
2713
2714     case tcc_declaration:
2715       /* Consider __builtin_sqrt equal to sqrt.  */
2716       return (TREE_CODE (arg0) == FUNCTION_DECL
2717               && DECL_BUILT_IN (arg0) && DECL_BUILT_IN (arg1)
2718               && DECL_BUILT_IN_CLASS (arg0) == DECL_BUILT_IN_CLASS (arg1)
2719               && DECL_FUNCTION_CODE (arg0) == DECL_FUNCTION_CODE (arg1));
2720
2721     default:
2722       return 0;
2723     }
2724
2725 #undef OP_SAME
2726 #undef OP_SAME_WITH_NULL
2727 }
2728 \f
2729 /* Similar to operand_equal_p, but see if ARG0 might have been made by
2730    shorten_compare from ARG1 when ARG1 was being compared with OTHER.
2731
2732    When in doubt, return 0.  */
2733
2734 static int
2735 operand_equal_for_comparison_p (tree arg0, tree arg1, tree other)
2736 {
2737   int unsignedp1, unsignedpo;
2738   tree primarg0, primarg1, primother;
2739   unsigned int correct_width;
2740
2741   if (operand_equal_p (arg0, arg1, 0))
2742     return 1;
2743
2744   if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0))
2745       || ! INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
2746     return 0;
2747
2748   /* Discard any conversions that don't change the modes of ARG0 and ARG1
2749      and see if the inner values are the same.  This removes any
2750      signedness comparison, which doesn't matter here.  */
2751   primarg0 = arg0, primarg1 = arg1;
2752   STRIP_NOPS (primarg0);
2753   STRIP_NOPS (primarg1);
2754   if (operand_equal_p (primarg0, primarg1, 0))
2755     return 1;
2756
2757   /* Duplicate what shorten_compare does to ARG1 and see if that gives the
2758      actual comparison operand, ARG0.
2759
2760      First throw away any conversions to wider types
2761      already present in the operands.  */
2762
2763   primarg1 = get_narrower (arg1, &unsignedp1);
2764   primother = get_narrower (other, &unsignedpo);
2765
2766   correct_width = TYPE_PRECISION (TREE_TYPE (arg1));
2767   if (unsignedp1 == unsignedpo
2768       && TYPE_PRECISION (TREE_TYPE (primarg1)) < correct_width
2769       && TYPE_PRECISION (TREE_TYPE (primother)) < correct_width)
2770     {
2771       tree type = TREE_TYPE (arg0);
2772
2773       /* Make sure shorter operand is extended the right way
2774          to match the longer operand.  */
2775       primarg1 = fold_convert (signed_or_unsigned_type_for
2776                                (unsignedp1, TREE_TYPE (primarg1)), primarg1);
2777
2778       if (operand_equal_p (arg0, fold_convert (type, primarg1), 0))
2779         return 1;
2780     }
2781
2782   return 0;
2783 }
2784 \f
2785 /* See if ARG is an expression that is either a comparison or is performing
2786    arithmetic on comparisons.  The comparisons must only be comparing
2787    two different values, which will be stored in *CVAL1 and *CVAL2; if
2788    they are nonzero it means that some operands have already been found.
2789    No variables may be used anywhere else in the expression except in the
2790    comparisons.  If SAVE_P is true it means we removed a SAVE_EXPR around
2791    the expression and save_expr needs to be called with CVAL1 and CVAL2.
2792
2793    If this is true, return 1.  Otherwise, return zero.  */
2794
2795 static int
2796 twoval_comparison_p (tree arg, tree *cval1, tree *cval2, int *save_p)
2797 {
2798   enum tree_code code = TREE_CODE (arg);
2799   enum tree_code_class tclass = TREE_CODE_CLASS (code);
2800
2801   /* We can handle some of the tcc_expression cases here.  */
2802   if (tclass == tcc_expression && code == TRUTH_NOT_EXPR)
2803     tclass = tcc_unary;
2804   else if (tclass == tcc_expression
2805            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR
2806                || code == COMPOUND_EXPR))
2807     tclass = tcc_binary;
2808
2809   else if (tclass == tcc_expression && code == SAVE_EXPR
2810            && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg, 0)))
2811     {
2812       /* If we've already found a CVAL1 or CVAL2, this expression is
2813          two complex to handle.  */
2814       if (*cval1 || *cval2)
2815         return 0;
2816
2817       tclass = tcc_unary;
2818       *save_p = 1;
2819     }
2820
2821   switch (tclass)
2822     {
2823     case tcc_unary:
2824       return twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p);
2825
2826     case tcc_binary:
2827       return (twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p)
2828               && twoval_comparison_p (TREE_OPERAND (arg, 1),
2829                                       cval1, cval2, save_p));
2830
2831     case tcc_constant:
2832       return 1;
2833
2834     case tcc_expression:
2835       if (code == COND_EXPR)
2836         return (twoval_comparison_p (TREE_OPERAND (arg, 0),
2837                                      cval1, cval2, save_p)
2838                 && twoval_comparison_p (TREE_OPERAND (arg, 1),
2839                                         cval1, cval2, save_p)
2840                 && twoval_comparison_p (TREE_OPERAND (arg, 2),
2841                                         cval1, cval2, save_p));
2842       return 0;
2843
2844     case tcc_comparison:
2845       /* First see if we can handle the first operand, then the second.  For
2846          the second operand, we know *CVAL1 can't be zero.  It must be that
2847          one side of the comparison is each of the values; test for the
2848          case where this isn't true by failing if the two operands
2849          are the same.  */
2850
2851       if (operand_equal_p (TREE_OPERAND (arg, 0),
2852                            TREE_OPERAND (arg, 1), 0))
2853         return 0;
2854
2855       if (*cval1 == 0)
2856         *cval1 = TREE_OPERAND (arg, 0);
2857       else if (operand_equal_p (*cval1, TREE_OPERAND (arg, 0), 0))
2858         ;
2859       else if (*cval2 == 0)
2860         *cval2 = TREE_OPERAND (arg, 0);
2861       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 0), 0))
2862         ;
2863       else
2864         return 0;
2865
2866       if (operand_equal_p (*cval1, TREE_OPERAND (arg, 1), 0))
2867         ;
2868       else if (*cval2 == 0)
2869         *cval2 = TREE_OPERAND (arg, 1);
2870       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 1), 0))
2871         ;
2872       else
2873         return 0;
2874
2875       return 1;
2876
2877     default:
2878       return 0;
2879     }
2880 }
2881 \f
2882 /* ARG is a tree that is known to contain just arithmetic operations and
2883    comparisons.  Evaluate the operations in the tree substituting NEW0 for
2884    any occurrence of OLD0 as an operand of a comparison and likewise for
2885    NEW1 and OLD1.  */
2886
2887 static tree
2888 eval_subst (location_t loc, tree arg, tree old0, tree new0,
2889             tree old1, tree new1)
2890 {
2891   tree type = TREE_TYPE (arg);
2892   enum tree_code code = TREE_CODE (arg);
2893   enum tree_code_class tclass = TREE_CODE_CLASS (code);
2894
2895   /* We can handle some of the tcc_expression cases here.  */
2896   if (tclass == tcc_expression && code == TRUTH_NOT_EXPR)
2897     tclass = tcc_unary;
2898   else if (tclass == tcc_expression
2899            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
2900     tclass = tcc_binary;
2901
2902   switch (tclass)
2903     {
2904     case tcc_unary:
2905       return fold_build1_loc (loc, code, type,
2906                           eval_subst (loc, TREE_OPERAND (arg, 0),
2907                                       old0, new0, old1, new1));
2908
2909     case tcc_binary:
2910       return fold_build2_loc (loc, code, type,
2911                           eval_subst (loc, TREE_OPERAND (arg, 0),
2912                                       old0, new0, old1, new1),
2913                           eval_subst (loc, TREE_OPERAND (arg, 1),
2914                                       old0, new0, old1, new1));
2915
2916     case tcc_expression:
2917       switch (code)
2918         {
2919         case SAVE_EXPR:
2920           return eval_subst (loc, TREE_OPERAND (arg, 0), old0, new0,
2921                              old1, new1);
2922
2923         case COMPOUND_EXPR:
2924           return eval_subst (loc, TREE_OPERAND (arg, 1), old0, new0,
2925                              old1, new1);
2926
2927         case COND_EXPR:
2928           return fold_build3_loc (loc, code, type,
2929                               eval_subst (loc, TREE_OPERAND (arg, 0),
2930                                           old0, new0, old1, new1),
2931                               eval_subst (loc, TREE_OPERAND (arg, 1),
2932                                           old0, new0, old1, new1),
2933                               eval_subst (loc, TREE_OPERAND (arg, 2),
2934                                           old0, new0, old1, new1));
2935         default:
2936           break;
2937         }
2938       /* Fall through - ???  */
2939
2940     case tcc_comparison:
2941       {
2942         tree arg0 = TREE_OPERAND (arg, 0);
2943         tree arg1 = TREE_OPERAND (arg, 1);
2944
2945         /* We need to check both for exact equality and tree equality.  The
2946            former will be true if the operand has a side-effect.  In that
2947            case, we know the operand occurred exactly once.  */
2948
2949         if (arg0 == old0 || operand_equal_p (arg0, old0, 0))
2950           arg0 = new0;
2951         else if (arg0 == old1 || operand_equal_p (arg0, old1, 0))
2952           arg0 = new1;
2953
2954         if (arg1 == old0 || operand_equal_p (arg1, old0, 0))
2955           arg1 = new0;
2956         else if (arg1 == old1 || operand_equal_p (arg1, old1, 0))
2957           arg1 = new1;
2958
2959         return fold_build2_loc (loc, code, type, arg0, arg1);
2960       }
2961
2962     default:
2963       return arg;
2964     }
2965 }
2966 \f
2967 /* Return a tree for the case when the result of an expression is RESULT
2968    converted to TYPE and OMITTED was previously an operand of the expression
2969    but is now not needed (e.g., we folded OMITTED * 0).
2970
2971    If OMITTED has side effects, we must evaluate it.  Otherwise, just do
2972    the conversion of RESULT to TYPE.  */
2973
2974 tree
2975 omit_one_operand_loc (location_t loc, tree type, tree result, tree omitted)
2976 {
2977   tree t = fold_convert_loc (loc, type, result);
2978
2979   /* If the resulting operand is an empty statement, just return the omitted
2980      statement casted to void. */
2981   if (IS_EMPTY_STMT (t) && TREE_SIDE_EFFECTS (omitted))
2982     {
2983       t = build1 (NOP_EXPR, void_type_node, fold_ignored_result (omitted));
2984       goto omit_one_operand_exit;
2985     }
2986
2987   if (TREE_SIDE_EFFECTS (omitted))
2988     {
2989       t = build2 (COMPOUND_EXPR, type, fold_ignored_result (omitted), t);
2990       goto omit_one_operand_exit;
2991     }
2992
2993   return non_lvalue_loc (loc, t);
2994
2995  omit_one_operand_exit:
2996   protected_set_expr_location (t, loc);
2997   return t;
2998 }
2999
3000 /* Similar, but call pedantic_non_lvalue instead of non_lvalue.  */
3001
3002 static tree
3003 pedantic_omit_one_operand_loc (location_t loc, tree type, tree result,
3004                                tree omitted)
3005 {
3006   tree t = fold_convert_loc (loc, type, result);
3007
3008   /* If the resulting operand is an empty statement, just return the omitted
3009      statement casted to void. */
3010   if (IS_EMPTY_STMT (t) && TREE_SIDE_EFFECTS (omitted))
3011     {
3012       t = build1 (NOP_EXPR, void_type_node, fold_ignored_result (omitted));
3013       goto pedantic_omit_one_operand_exit;
3014     }
3015
3016   if (TREE_SIDE_EFFECTS (omitted))
3017     {
3018       t = build2 (COMPOUND_EXPR, type, fold_ignored_result (omitted), t);
3019       goto pedantic_omit_one_operand_exit;
3020     }
3021
3022   return pedantic_non_lvalue_loc (loc, t);
3023
3024  pedantic_omit_one_operand_exit:
3025   protected_set_expr_location (t, loc);
3026   return t;
3027 }
3028
3029 /* Return a tree for the case when the result of an expression is RESULT
3030    converted to TYPE and OMITTED1 and OMITTED2 were previously operands
3031    of the expression but are now not needed.
3032
3033    If OMITTED1 or OMITTED2 has side effects, they must be evaluated.
3034    If both OMITTED1 and OMITTED2 have side effects, OMITTED1 is
3035    evaluated before OMITTED2.  Otherwise, if neither has side effects,
3036    just do the conversion of RESULT to TYPE.  */
3037
3038 tree
3039 omit_two_operands_loc (location_t loc, tree type, tree result,
3040                    tree omitted1, tree omitted2)
3041 {
3042   tree t = fold_convert_loc (loc, type, result);
3043
3044   if (TREE_SIDE_EFFECTS (omitted2))
3045     {
3046       t = build2 (COMPOUND_EXPR, type, omitted2, t);
3047       SET_EXPR_LOCATION (t, loc);
3048     }
3049   if (TREE_SIDE_EFFECTS (omitted1))
3050     {
3051       t = build2 (COMPOUND_EXPR, type, omitted1, t);
3052       SET_EXPR_LOCATION (t, loc);
3053     }
3054
3055   return TREE_CODE (t) != COMPOUND_EXPR ? non_lvalue_loc (loc, t) : t;
3056 }
3057
3058 \f
3059 /* Return a simplified tree node for the truth-negation of ARG.  This
3060    never alters ARG itself.  We assume that ARG is an operation that
3061    returns a truth value (0 or 1).
3062
3063    FIXME: one would think we would fold the result, but it causes
3064    problems with the dominator optimizer.  */
3065
3066 tree
3067 fold_truth_not_expr (location_t loc, tree arg)
3068 {
3069   tree t, type = TREE_TYPE (arg);
3070   enum tree_code code = TREE_CODE (arg);
3071   location_t loc1, loc2;
3072
3073   /* If this is a comparison, we can simply invert it, except for
3074      floating-point non-equality comparisons, in which case we just
3075      enclose a TRUTH_NOT_EXPR around what we have.  */
3076
3077   if (TREE_CODE_CLASS (code) == tcc_comparison)
3078     {
3079       tree op_type = TREE_TYPE (TREE_OPERAND (arg, 0));
3080       if (FLOAT_TYPE_P (op_type)
3081           && flag_trapping_math
3082           && code != ORDERED_EXPR && code != UNORDERED_EXPR
3083           && code != NE_EXPR && code != EQ_EXPR)
3084         return NULL_TREE;
3085
3086       code = invert_tree_comparison (code, HONOR_NANS (TYPE_MODE (op_type)));
3087       if (code == ERROR_MARK)
3088         return NULL_TREE;
3089
3090       t = build2 (code, type, TREE_OPERAND (arg, 0), TREE_OPERAND (arg, 1));
3091       SET_EXPR_LOCATION (t, loc);
3092       return t;
3093     }
3094
3095   switch (code)
3096     {
3097     case INTEGER_CST:
3098       return constant_boolean_node (integer_zerop (arg), type);
3099
3100     case TRUTH_AND_EXPR:
3101       loc1 = EXPR_LOCATION (TREE_OPERAND (arg, 0));
3102       loc2 = EXPR_LOCATION (TREE_OPERAND (arg, 1));
3103       if (loc1 == UNKNOWN_LOCATION)
3104         loc1 = loc;
3105       if (loc2 == UNKNOWN_LOCATION)
3106         loc2 = loc;
3107       t = build2 (TRUTH_OR_EXPR, type,
3108                   invert_truthvalue_loc (loc1, TREE_OPERAND (arg, 0)),
3109                   invert_truthvalue_loc (loc2, TREE_OPERAND (arg, 1)));
3110       break;
3111
3112     case TRUTH_OR_EXPR:
3113       loc1 = EXPR_LOCATION (TREE_OPERAND (arg, 0));
3114       loc2 = EXPR_LOCATION (TREE_OPERAND (arg, 1));
3115       if (loc1 == UNKNOWN_LOCATION)
3116         loc1 = loc;
3117       if (loc2 == UNKNOWN_LOCATION)
3118         loc2 = loc;
3119       t = build2 (TRUTH_AND_EXPR, type,
3120                   invert_truthvalue_loc (loc1, TREE_OPERAND (arg, 0)),
3121                   invert_truthvalue_loc (loc2, TREE_OPERAND (arg, 1)));
3122       break;
3123
3124     case TRUTH_XOR_EXPR:
3125       /* Here we can invert either operand.  We invert the first operand
3126          unless the second operand is a TRUTH_NOT_EXPR in which case our
3127          result is the XOR of the first operand with the inside of the
3128          negation of the second operand.  */
3129
3130       if (TREE_CODE (TREE_OPERAND (arg, 1)) == TRUTH_NOT_EXPR)
3131         t = build2 (TRUTH_XOR_EXPR, type, TREE_OPERAND (arg, 0),
3132                     TREE_OPERAND (TREE_OPERAND (arg, 1), 0));
3133       else
3134         t = build2 (TRUTH_XOR_EXPR, type,
3135                     invert_truthvalue_loc (loc, TREE_OPERAND (arg, 0)),
3136                     TREE_OPERAND (arg, 1));
3137       break;
3138
3139     case TRUTH_ANDIF_EXPR:
3140       loc1 = EXPR_LOCATION (TREE_OPERAND (arg, 0));
3141       loc2 = EXPR_LOCATION (TREE_OPERAND (arg, 1));
3142       if (loc1 == UNKNOWN_LOCATION)
3143         loc1 = loc;
3144       if (loc2 == UNKNOWN_LOCATION)
3145         loc2 = loc;
3146       t = build2 (TRUTH_ORIF_EXPR, type,
3147                   invert_truthvalue_loc (loc1, TREE_OPERAND (arg, 0)),
3148                   invert_truthvalue_loc (loc2, TREE_OPERAND (arg, 1)));
3149       break;
3150
3151     case TRUTH_ORIF_EXPR:
3152       loc1 = EXPR_LOCATION (TREE_OPERAND (arg, 0));
3153       loc2 = EXPR_LOCATION (TREE_OPERAND (arg, 1));
3154       if (loc1 == UNKNOWN_LOCATION)
3155         loc1 = loc;
3156       if (loc2 == UNKNOWN_LOCATION)
3157         loc2 = loc;
3158       t = build2 (TRUTH_ANDIF_EXPR, type,
3159                   invert_truthvalue_loc (loc1, TREE_OPERAND (arg, 0)),
3160                   invert_truthvalue_loc (loc2, TREE_OPERAND (arg, 1)));
3161       break;
3162
3163     case TRUTH_NOT_EXPR:
3164       return TREE_OPERAND (arg, 0);
3165
3166     case COND_EXPR:
3167       {
3168         tree arg1 = TREE_OPERAND (arg, 1);
3169         tree arg2 = TREE_OPERAND (arg, 2);
3170
3171         loc1 = EXPR_LOCATION (TREE_OPERAND (arg, 1));
3172         loc2 = EXPR_LOCATION (TREE_OPERAND (arg, 2));
3173         if (loc1 == UNKNOWN_LOCATION)
3174           loc1 = loc;
3175         if (loc2 == UNKNOWN_LOCATION)
3176           loc2 = loc;
3177
3178         /* A COND_EXPR may have a throw as one operand, which
3179            then has void type.  Just leave void operands
3180            as they are.  */
3181         t = build3 (COND_EXPR, type, TREE_OPERAND (arg, 0),
3182                     VOID_TYPE_P (TREE_TYPE (arg1))
3183                     ? arg1 : invert_truthvalue_loc (loc1, arg1),
3184                     VOID_TYPE_P (TREE_TYPE (arg2))
3185                     ? arg2 : invert_truthvalue_loc (loc2, arg2));
3186         break;
3187       }
3188
3189     case COMPOUND_EXPR:
3190       loc1 = EXPR_LOCATION (TREE_OPERAND (arg, 1));
3191       if (loc1 == UNKNOWN_LOCATION)
3192         loc1 = loc;
3193       t = build2 (COMPOUND_EXPR, type,
3194                   TREE_OPERAND (arg, 0),
3195                   invert_truthvalue_loc (loc1, TREE_OPERAND (arg, 1)));
3196       break;
3197
3198     case NON_LVALUE_EXPR:
3199       loc1 = EXPR_LOCATION (TREE_OPERAND (arg, 0));
3200       if (loc1 == UNKNOWN_LOCATION)
3201         loc1 = loc;
3202       return invert_truthvalue_loc (loc1, TREE_OPERAND (arg, 0));
3203
3204     CASE_CONVERT:
3205       if (TREE_CODE (TREE_TYPE (arg)) == BOOLEAN_TYPE)
3206         {
3207           t = build1 (TRUTH_NOT_EXPR, type, arg);
3208           break;
3209         }
3210
3211       /* ... fall through ...  */
3212
3213     case FLOAT_EXPR:
3214       loc1 = EXPR_LOCATION (TREE_OPERAND (arg, 0));
3215       if (loc1 == UNKNOWN_LOCATION)
3216         loc1 = loc;
3217       t = build1 (TREE_CODE (arg), type,
3218                   invert_truthvalue_loc (loc1, TREE_OPERAND (arg, 0)));
3219       break;
3220
3221     case BIT_AND_EXPR:
3222       if (!integer_onep (TREE_OPERAND (arg, 1)))
3223         return NULL_TREE;
3224       t = build2 (EQ_EXPR, type, arg, build_int_cst (type, 0));
3225       break;
3226
3227     case SAVE_EXPR:
3228       t = build1 (TRUTH_NOT_EXPR, type, arg);
3229       break;
3230
3231     case CLEANUP_POINT_EXPR:
3232       loc1 = EXPR_LOCATION (TREE_OPERAND (arg, 0));
3233       if (loc1 == UNKNOWN_LOCATION)
3234         loc1 = loc;
3235       t = build1 (CLEANUP_POINT_EXPR, type,
3236                   invert_truthvalue_loc (loc1, TREE_OPERAND (arg, 0)));
3237       break;
3238
3239     default:
3240       t = NULL_TREE;
3241       break;
3242     }
3243
3244   if (t)
3245     SET_EXPR_LOCATION (t, loc);
3246
3247   return t;
3248 }
3249
3250 /* Return a simplified tree node for the truth-negation of ARG.  This
3251    never alters ARG itself.  We assume that ARG is an operation that
3252    returns a truth value (0 or 1).
3253
3254    FIXME: one would think we would fold the result, but it causes
3255    problems with the dominator optimizer.  */
3256
3257 tree
3258 invert_truthvalue_loc (location_t loc, tree arg)
3259 {
3260   tree tem;
3261
3262   if (TREE_CODE (arg) == ERROR_MARK)
3263     return arg;
3264
3265   tem = fold_truth_not_expr (loc, arg);
3266   if (!tem)
3267     {
3268       tem = build1 (TRUTH_NOT_EXPR, TREE_TYPE (arg), arg);
3269       SET_EXPR_LOCATION (tem, loc);
3270     }
3271
3272   return tem;
3273 }
3274
3275 /* Given a bit-wise operation CODE applied to ARG0 and ARG1, see if both
3276    operands are another bit-wise operation with a common input.  If so,
3277    distribute the bit operations to save an operation and possibly two if
3278    constants are involved.  For example, convert
3279         (A | B) & (A | C) into A | (B & C)
3280    Further simplification will occur if B and C are constants.
3281
3282    If this optimization cannot be done, 0 will be returned.  */
3283
3284 static tree
3285 distribute_bit_expr (location_t loc, enum tree_code code, tree type,
3286                      tree arg0, tree arg1)
3287 {
3288   tree common;
3289   tree left, right;
3290
3291   if (TREE_CODE (arg0) != TREE_CODE (arg1)
3292       || TREE_CODE (arg0) == code
3293       || (TREE_CODE (arg0) != BIT_AND_EXPR
3294           && TREE_CODE (arg0) != BIT_IOR_EXPR))
3295     return 0;
3296
3297   if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0))
3298     {
3299       common = TREE_OPERAND (arg0, 0);
3300       left = TREE_OPERAND (arg0, 1);
3301       right = TREE_OPERAND (arg1, 1);
3302     }
3303   else if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 1), 0))
3304     {
3305       common = TREE_OPERAND (arg0, 0);
3306       left = TREE_OPERAND (arg0, 1);
3307       right = TREE_OPERAND (arg1, 0);
3308     }
3309   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 0), 0))
3310     {
3311       common = TREE_OPERAND (arg0, 1);
3312       left = TREE_OPERAND (arg0, 0);
3313       right = TREE_OPERAND (arg1, 1);
3314     }
3315   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1), 0))
3316     {
3317       common = TREE_OPERAND (arg0, 1);
3318       left = TREE_OPERAND (arg0, 0);
3319       right = TREE_OPERAND (arg1, 0);
3320     }
3321   else
3322     return 0;
3323
3324   common = fold_convert_loc (loc, type, common);
3325   left = fold_convert_loc (loc, type, left);
3326   right = fold_convert_loc (loc, type, right);
3327   return fold_build2_loc (loc, TREE_CODE (arg0), type, common,
3328                       fold_build2_loc (loc, code, type, left, right));
3329 }
3330
3331 /* Knowing that ARG0 and ARG1 are both RDIV_EXPRs, simplify a binary operation
3332    with code CODE.  This optimization is unsafe.  */
3333 static tree
3334 distribute_real_division (location_t loc, enum tree_code code, tree type,
3335                           tree arg0, tree arg1)
3336 {
3337   bool mul0 = TREE_CODE (arg0) == MULT_EXPR;
3338   bool mul1 = TREE_CODE (arg1) == MULT_EXPR;
3339
3340   /* (A / C) +- (B / C) -> (A +- B) / C.  */
3341   if (mul0 == mul1
3342       && operand_equal_p (TREE_OPERAND (arg0, 1),
3343                        TREE_OPERAND (arg1, 1), 0))
3344     return fold_build2_loc (loc, mul0 ? MULT_EXPR : RDIV_EXPR, type,
3345                         fold_build2_loc (loc, code, type,
3346                                      TREE_OPERAND (arg0, 0),
3347                                      TREE_OPERAND (arg1, 0)),
3348                         TREE_OPERAND (arg0, 1));
3349
3350   /* (A / C1) +- (A / C2) -> A * (1 / C1 +- 1 / C2).  */
3351   if (operand_equal_p (TREE_OPERAND (arg0, 0),
3352                        TREE_OPERAND (arg1, 0), 0)
3353       && TREE_CODE (TREE_OPERAND (arg0, 1)) == REAL_CST
3354       && TREE_CODE (TREE_OPERAND (arg1, 1)) == REAL_CST)
3355     {
3356       REAL_VALUE_TYPE r0, r1;
3357       r0 = TREE_REAL_CST (TREE_OPERAND (arg0, 1));
3358       r1 = TREE_REAL_CST (TREE_OPERAND (arg1, 1));
3359       if (!mul0)
3360         real_arithmetic (&r0, RDIV_EXPR, &dconst1, &r0);
3361       if (!mul1)
3362         real_arithmetic (&r1, RDIV_EXPR, &dconst1, &r1);
3363       real_arithmetic (&r0, code, &r0, &r1);
3364       return fold_build2_loc (loc, MULT_EXPR, type,
3365                           TREE_OPERAND (arg0, 0),
3366                           build_real (type, r0));
3367     }
3368
3369   return NULL_TREE;
3370 }
3371 \f
3372 /* Return a BIT_FIELD_REF of type TYPE to refer to BITSIZE bits of INNER
3373    starting at BITPOS.  The field is unsigned if UNSIGNEDP is nonzero.  */
3374
3375 static tree
3376 make_bit_field_ref (location_t loc, tree inner, tree type,
3377                     HOST_WIDE_INT bitsize, HOST_WIDE_INT bitpos, int unsignedp)
3378 {
3379   tree result, bftype;
3380
3381   if (bitpos == 0)
3382     {
3383       tree size = TYPE_SIZE (TREE_TYPE (inner));
3384       if ((INTEGRAL_TYPE_P (TREE_TYPE (inner))
3385            || POINTER_TYPE_P (TREE_TYPE (inner)))
3386           && host_integerp (size, 0)
3387           && tree_low_cst (size, 0) == bitsize)
3388         return fold_convert_loc (loc, type, inner);
3389     }
3390
3391   bftype = type;
3392   if (TYPE_PRECISION (bftype) != bitsize
3393       || TYPE_UNSIGNED (bftype) == !unsignedp)
3394     bftype = build_nonstandard_integer_type (bitsize, 0);
3395
3396   result = build3 (BIT_FIELD_REF, bftype, inner,
3397                    size_int (bitsize), bitsize_int (bitpos));
3398   SET_EXPR_LOCATION (result, loc);
3399
3400   if (bftype != type)
3401     result = fold_convert_loc (loc, type, result);
3402
3403   return result;
3404 }
3405
3406 /* Optimize a bit-field compare.
3407
3408    There are two cases:  First is a compare against a constant and the
3409    second is a comparison of two items where the fields are at the same
3410    bit position relative to the start of a chunk (byte, halfword, word)
3411    large enough to contain it.  In these cases we can avoid the shift
3412    implicit in bitfield extractions.
3413
3414    For constants, we emit a compare of the shifted constant with the
3415    BIT_AND_EXPR of a mask and a byte, halfword, or word of the operand being
3416    compared.  For two fields at the same position, we do the ANDs with the
3417    similar mask and compare the result of the ANDs.
3418
3419    CODE is the comparison code, known to be either NE_EXPR or EQ_EXPR.
3420    COMPARE_TYPE is the type of the comparison, and LHS and RHS
3421    are the left and right operands of the comparison, respectively.
3422
3423    If the optimization described above can be done, we return the resulting
3424    tree.  Otherwise we return zero.  */
3425
3426 static tree
3427 optimize_bit_field_compare (location_t loc, enum tree_code code,
3428                             tree compare_type, tree lhs, tree rhs)
3429 {
3430   HOST_WIDE_INT lbitpos, lbitsize, rbitpos, rbitsize, nbitpos, nbitsize;
3431   tree type = TREE_TYPE (lhs);
3432   tree signed_type, unsigned_type;
3433   int const_p = TREE_CODE (rhs) == INTEGER_CST;
3434   enum machine_mode lmode, rmode, nmode;
3435   int lunsignedp, runsignedp;
3436   int lvolatilep = 0, rvolatilep = 0;
3437   tree linner, rinner = NULL_TREE;
3438   tree mask;
3439   tree offset;
3440
3441   /* Get all the information about the extractions being done.  If the bit size
3442      if the same as the size of the underlying object, we aren't doing an
3443      extraction at all and so can do nothing.  We also don't want to
3444      do anything if the inner expression is a PLACEHOLDER_EXPR since we
3445      then will no longer be able to replace it.  */
3446   linner = get_inner_reference (lhs, &lbitsize, &lbitpos, &offset, &lmode,
3447                                 &lunsignedp, &lvolatilep, false);
3448   if (linner == lhs || lbitsize == GET_MODE_BITSIZE (lmode) || lbitsize < 0
3449       || offset != 0 || TREE_CODE (linner) == PLACEHOLDER_EXPR)
3450     return 0;
3451
3452  if (!const_p)
3453    {
3454      /* If this is not a constant, we can only do something if bit positions,
3455         sizes, and signedness are the same.  */
3456      rinner = get_inner_reference (rhs, &rbitsize, &rbitpos, &offset, &rmode,
3457                                    &runsignedp, &rvolatilep, false);
3458
3459      if (rinner == rhs || lbitpos != rbitpos || lbitsize != rbitsize
3460          || lunsignedp != runsignedp || offset != 0
3461          || TREE_CODE (rinner) == PLACEHOLDER_EXPR)
3462        return 0;
3463    }
3464
3465   /* See if we can find a mode to refer to this field.  We should be able to,
3466      but fail if we can't.  */
3467   nmode = get_best_mode (lbitsize, lbitpos,
3468                          const_p ? TYPE_ALIGN (TREE_TYPE (linner))
3469                          : MIN (TYPE_ALIGN (TREE_TYPE (linner)),
3470                                 TYPE_ALIGN (TREE_TYPE (rinner))),
3471                          word_mode, lvolatilep || rvolatilep);
3472   if (nmode == VOIDmode)
3473     return 0;
3474
3475   /* Set signed and unsigned types of the precision of this mode for the
3476      shifts below.  */
3477   signed_type = lang_hooks.types.type_for_mode (nmode, 0);
3478   unsigned_type = lang_hooks.types.type_for_mode (nmode, 1);
3479
3480   /* Compute the bit position and size for the new reference and our offset
3481      within it. If the new reference is the same size as the original, we
3482      won't optimize anything, so return zero.  */
3483   nbitsize = GET_MODE_BITSIZE (nmode);
3484   nbitpos = lbitpos & ~ (nbitsize - 1);
3485   lbitpos -= nbitpos;
3486   if (nbitsize == lbitsize)
3487     return 0;
3488
3489   if (BYTES_BIG_ENDIAN)
3490     lbitpos = nbitsize - lbitsize - lbitpos;