OSDN Git Service

* lib/target-supports.exp (check_effective_target_vect_condition):
[pf3gnuchains/gcc-fork.git] / gcc / gimple-fold.c
1 /* Statement simplification on GIMPLE.
2    Copyright (C) 2010, 2011, 2012 Free Software Foundation, Inc.
3    Split out from tree-ssa-ccp.c.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
10 later version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "flags.h"
27 #include "function.h"
28 #include "tree-dump.h"
29 #include "tree-flow.h"
30 #include "tree-pass.h"
31 #include "tree-ssa-propagate.h"
32 #include "target.h"
33 #include "gimple-fold.h"
34
35 /* Return true when DECL can be referenced from current unit.
36    We can get declarations that are not possible to reference for
37    various reasons:
38
39      1) When analyzing C++ virtual tables.
40         C++ virtual tables do have known constructors even
41         when they are keyed to other compilation unit.
42         Those tables can contain pointers to methods and vars
43         in other units.  Those methods have both STATIC and EXTERNAL
44         set.
45      2) In WHOPR mode devirtualization might lead to reference
46         to method that was partitioned elsehwere.
47         In this case we have static VAR_DECL or FUNCTION_DECL
48         that has no corresponding callgraph/varpool node
49         declaring the body.  
50      3) COMDAT functions referred by external vtables that
51         we devirtualize only during final copmilation stage.
52         At this time we already decided that we will not output
53         the function body and thus we can't reference the symbol
54         directly.  */
55
56 static bool
57 can_refer_decl_in_current_unit_p (tree decl)
58 {
59   struct varpool_node *vnode;
60   struct cgraph_node *node;
61
62   if (!TREE_STATIC (decl) && !DECL_EXTERNAL (decl))
63     return true;
64   /* External flag is set, so we deal with C++ reference
65      to static object from other file.  */
66   if (DECL_EXTERNAL (decl) && TREE_STATIC (decl)
67       && TREE_CODE (decl) == VAR_DECL)
68     {
69       /* Just be sure it is not big in frontend setting
70          flags incorrectly.  Those variables should never
71          be finalized.  */
72       gcc_checking_assert (!(vnode = varpool_get_node (decl))
73                            || !vnode->finalized);
74       return false;
75     }
76   /* When function is public, we always can introduce new reference.
77      Exception are the COMDAT functions where introducing a direct
78      reference imply need to include function body in the curren tunit.  */
79   if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl))
80     return true;
81   /* We are not at ltrans stage; so don't worry about WHOPR.
82      Also when still gimplifying all referred comdat functions will be
83      produced.
84      ??? as observed in PR20991 for already optimized out comdat virtual functions
85      we may not neccesarily give up because the copy will be output elsewhere when
86      corresponding vtable is output.  */
87   if (!flag_ltrans && (!DECL_COMDAT (decl) || !cgraph_function_flags_ready))
88     return true;
89   /* If we already output the function body, we are safe.  */
90   if (TREE_ASM_WRITTEN (decl))
91     return true;
92   if (TREE_CODE (decl) == FUNCTION_DECL)
93     {
94       node = cgraph_get_node (decl);
95       /* Check that we still have function body and that we didn't took
96          the decision to eliminate offline copy of the function yet.
97          The second is important when devirtualization happens during final
98          compilation stage when making a new reference no longer makes callee
99          to be compiled.  */
100       if (!node || !node->analyzed || node->global.inlined_to)
101         return false;
102     }
103   else if (TREE_CODE (decl) == VAR_DECL)
104     {
105       vnode = varpool_get_node (decl);
106       if (!vnode || !vnode->finalized)
107         return false;
108     }
109   return true;
110 }
111
112 /* CVAL is value taken from DECL_INITIAL of variable.  Try to transform it into
113    acceptable form for is_gimple_min_invariant.   */
114
115 tree
116 canonicalize_constructor_val (tree cval)
117 {
118   STRIP_NOPS (cval);
119   if (TREE_CODE (cval) == POINTER_PLUS_EXPR
120       && TREE_CODE (TREE_OPERAND (cval, 1)) == INTEGER_CST)
121     {
122       tree ptr = TREE_OPERAND (cval, 0);
123       if (is_gimple_min_invariant (ptr))
124         cval = build1_loc (EXPR_LOCATION (cval),
125                            ADDR_EXPR, TREE_TYPE (ptr),
126                            fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (ptr)),
127                                         ptr,
128                                         fold_convert (ptr_type_node,
129                                                       TREE_OPERAND (cval, 1))));
130     }
131   if (TREE_CODE (cval) == ADDR_EXPR)
132     {
133       tree base = get_base_address (TREE_OPERAND (cval, 0));
134
135       if (base
136           && (TREE_CODE (base) == VAR_DECL
137               || TREE_CODE (base) == FUNCTION_DECL)
138           && !can_refer_decl_in_current_unit_p (base))
139         return NULL_TREE;
140       if (base && TREE_CODE (base) == VAR_DECL)
141         {
142           TREE_ADDRESSABLE (base) = 1;
143           if (cfun && gimple_referenced_vars (cfun))
144             add_referenced_var (base);
145         }
146       /* Fixup types in global initializers.  */
147       if (TREE_TYPE (TREE_TYPE (cval)) != TREE_TYPE (TREE_OPERAND (cval, 0)))
148         cval = build_fold_addr_expr (TREE_OPERAND (cval, 0));
149     }
150   return cval;
151 }
152
153 /* If SYM is a constant variable with known value, return the value.
154    NULL_TREE is returned otherwise.  */
155
156 tree
157 get_symbol_constant_value (tree sym)
158 {
159   if (const_value_known_p (sym))
160     {
161       tree val = DECL_INITIAL (sym);
162       if (val)
163         {
164           val = canonicalize_constructor_val (val);
165           if (val && is_gimple_min_invariant (val))
166             return val;
167           else
168             return NULL_TREE;
169         }
170       /* Variables declared 'const' without an initializer
171          have zero as the initializer if they may not be
172          overridden at link or run time.  */
173       if (!val
174           && (INTEGRAL_TYPE_P (TREE_TYPE (sym))
175                || SCALAR_FLOAT_TYPE_P (TREE_TYPE (sym))))
176         return build_zero_cst (TREE_TYPE (sym));
177     }
178
179   return NULL_TREE;
180 }
181
182
183
184 /* Subroutine of fold_stmt.  We perform several simplifications of the
185    memory reference tree EXPR and make sure to re-gimplify them properly
186    after propagation of constant addresses.  IS_LHS is true if the
187    reference is supposed to be an lvalue.  */
188
189 static tree
190 maybe_fold_reference (tree expr, bool is_lhs)
191 {
192   tree *t = &expr;
193   tree result;
194
195   if ((TREE_CODE (expr) == VIEW_CONVERT_EXPR
196        || TREE_CODE (expr) == REALPART_EXPR
197        || TREE_CODE (expr) == IMAGPART_EXPR)
198       && CONSTANT_CLASS_P (TREE_OPERAND (expr, 0)))
199     return fold_unary_loc (EXPR_LOCATION (expr),
200                            TREE_CODE (expr),
201                            TREE_TYPE (expr),
202                            TREE_OPERAND (expr, 0));
203   else if (TREE_CODE (expr) == BIT_FIELD_REF
204            && CONSTANT_CLASS_P (TREE_OPERAND (expr, 0)))
205     return fold_ternary_loc (EXPR_LOCATION (expr),
206                              TREE_CODE (expr),
207                              TREE_TYPE (expr),
208                              TREE_OPERAND (expr, 0),
209                              TREE_OPERAND (expr, 1),
210                              TREE_OPERAND (expr, 2));
211
212   while (handled_component_p (*t))
213     t = &TREE_OPERAND (*t, 0);
214
215   /* Canonicalize MEM_REFs invariant address operand.  Do this first
216      to avoid feeding non-canonical MEM_REFs elsewhere.  */
217   if (TREE_CODE (*t) == MEM_REF
218       && !is_gimple_mem_ref_addr (TREE_OPERAND (*t, 0)))
219     {
220       bool volatile_p = TREE_THIS_VOLATILE (*t);
221       tree tem = fold_binary (MEM_REF, TREE_TYPE (*t),
222                               TREE_OPERAND (*t, 0),
223                               TREE_OPERAND (*t, 1));
224       if (tem)
225         {
226           TREE_THIS_VOLATILE (tem) = volatile_p;
227           *t = tem;
228           tem = maybe_fold_reference (expr, is_lhs);
229           if (tem)
230             return tem;
231           return expr;
232         }
233     }
234
235   if (!is_lhs
236       && (result = fold_const_aggregate_ref (expr))
237       && is_gimple_min_invariant (result))
238     return result;
239
240   /* Fold back MEM_REFs to reference trees.  */
241   if (TREE_CODE (*t) == MEM_REF
242       && TREE_CODE (TREE_OPERAND (*t, 0)) == ADDR_EXPR
243       && integer_zerop (TREE_OPERAND (*t, 1))
244       && (TREE_THIS_VOLATILE (*t)
245           == TREE_THIS_VOLATILE (TREE_OPERAND (TREE_OPERAND (*t, 0), 0)))
246       && !TYPE_REF_CAN_ALIAS_ALL (TREE_TYPE (TREE_OPERAND (*t, 1)))
247       && (TYPE_MAIN_VARIANT (TREE_TYPE (*t))
248           == TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (TREE_OPERAND (*t, 1)))))
249       /* We have to look out here to not drop a required conversion
250          from the rhs to the lhs if is_lhs, but we don't have the
251          rhs here to verify that.  Thus require strict type
252          compatibility.  */
253       && types_compatible_p (TREE_TYPE (*t),
254                              TREE_TYPE (TREE_OPERAND
255                                         (TREE_OPERAND (*t, 0), 0))))
256     {
257       tree tem;
258       *t = TREE_OPERAND (TREE_OPERAND (*t, 0), 0);
259       tem = maybe_fold_reference (expr, is_lhs);
260       if (tem)
261         return tem;
262       return expr;
263     }
264   else if (TREE_CODE (*t) == TARGET_MEM_REF)
265     {
266       tree tem = maybe_fold_tmr (*t);
267       if (tem)
268         {
269           *t = tem;
270           tem = maybe_fold_reference (expr, is_lhs);
271           if (tem)
272             return tem;
273           return expr;
274         }
275     }
276
277   return NULL_TREE;
278 }
279
280
281 /* Attempt to fold an assignment statement pointed-to by SI.  Returns a
282    replacement rhs for the statement or NULL_TREE if no simplification
283    could be made.  It is assumed that the operands have been previously
284    folded.  */
285
286 static tree
287 fold_gimple_assign (gimple_stmt_iterator *si)
288 {
289   gimple stmt = gsi_stmt (*si);
290   enum tree_code subcode = gimple_assign_rhs_code (stmt);
291   location_t loc = gimple_location (stmt);
292
293   tree result = NULL_TREE;
294
295   switch (get_gimple_rhs_class (subcode))
296     {
297     case GIMPLE_SINGLE_RHS:
298       {
299         tree rhs = gimple_assign_rhs1 (stmt);
300
301         if (REFERENCE_CLASS_P (rhs))
302           return maybe_fold_reference (rhs, false);
303
304         else if (TREE_CODE (rhs) == ADDR_EXPR)
305           {
306             tree ref = TREE_OPERAND (rhs, 0);
307             tree tem = maybe_fold_reference (ref, true);
308             if (tem
309                 && TREE_CODE (tem) == MEM_REF
310                 && integer_zerop (TREE_OPERAND (tem, 1)))
311               result = fold_convert (TREE_TYPE (rhs), TREE_OPERAND (tem, 0));
312             else if (tem)
313               result = fold_convert (TREE_TYPE (rhs),
314                                      build_fold_addr_expr_loc (loc, tem));
315             else if (TREE_CODE (ref) == MEM_REF
316                      && integer_zerop (TREE_OPERAND (ref, 1)))
317               result = fold_convert (TREE_TYPE (rhs), TREE_OPERAND (ref, 0));
318           }
319
320         else if (TREE_CODE (rhs) == CONSTRUCTOR
321                  && TREE_CODE (TREE_TYPE (rhs)) == VECTOR_TYPE
322                  && (CONSTRUCTOR_NELTS (rhs)
323                      == TYPE_VECTOR_SUBPARTS (TREE_TYPE (rhs))))
324           {
325             /* Fold a constant vector CONSTRUCTOR to VECTOR_CST.  */
326             unsigned i;
327             tree val;
328
329             FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (rhs), i, val)
330               if (TREE_CODE (val) != INTEGER_CST
331                   && TREE_CODE (val) != REAL_CST
332                   && TREE_CODE (val) != FIXED_CST)
333                 return NULL_TREE;
334
335             return build_vector_from_ctor (TREE_TYPE (rhs),
336                                            CONSTRUCTOR_ELTS (rhs));
337           }
338
339         else if (DECL_P (rhs))
340           return unshare_expr (get_symbol_constant_value (rhs));
341
342         /* If we couldn't fold the RHS, hand over to the generic
343            fold routines.  */
344         if (result == NULL_TREE)
345           result = fold (rhs);
346
347         /* Strip away useless type conversions.  Both the NON_LVALUE_EXPR
348            that may have been added by fold, and "useless" type
349            conversions that might now be apparent due to propagation.  */
350         STRIP_USELESS_TYPE_CONVERSION (result);
351
352         if (result != rhs && valid_gimple_rhs_p (result))
353           return result;
354
355         return NULL_TREE;
356       }
357       break;
358
359     case GIMPLE_UNARY_RHS:
360       {
361         tree rhs = gimple_assign_rhs1 (stmt);
362
363         result = fold_unary_loc (loc, subcode, gimple_expr_type (stmt), rhs);
364         if (result)
365           {
366             /* If the operation was a conversion do _not_ mark a
367                resulting constant with TREE_OVERFLOW if the original
368                constant was not.  These conversions have implementation
369                defined behavior and retaining the TREE_OVERFLOW flag
370                here would confuse later passes such as VRP.  */
371             if (CONVERT_EXPR_CODE_P (subcode)
372                 && TREE_CODE (result) == INTEGER_CST
373                 && TREE_CODE (rhs) == INTEGER_CST)
374               TREE_OVERFLOW (result) = TREE_OVERFLOW (rhs);
375
376             STRIP_USELESS_TYPE_CONVERSION (result);
377             if (valid_gimple_rhs_p (result))
378               return result;
379           }
380       }
381       break;
382
383     case GIMPLE_BINARY_RHS:
384       /* Try to canonicalize for boolean-typed X the comparisons
385          X == 0, X == 1, X != 0, and X != 1.  */
386       if (gimple_assign_rhs_code (stmt) == EQ_EXPR
387           || gimple_assign_rhs_code (stmt) == NE_EXPR)
388         {
389           tree lhs = gimple_assign_lhs (stmt);
390           tree op1 = gimple_assign_rhs1 (stmt);
391           tree op2 = gimple_assign_rhs2 (stmt);
392           tree type = TREE_TYPE (op1);
393
394           /* Check whether the comparison operands are of the same boolean
395              type as the result type is.
396              Check that second operand is an integer-constant with value
397              one or zero.  */
398           if (TREE_CODE (op2) == INTEGER_CST
399               && (integer_zerop (op2) || integer_onep (op2))
400               && useless_type_conversion_p (TREE_TYPE (lhs), type))
401             {
402               enum tree_code cmp_code = gimple_assign_rhs_code (stmt);
403               bool is_logical_not = false;
404
405               /* X == 0 and X != 1 is a logical-not.of X
406                  X == 1 and X != 0 is X  */
407               if ((cmp_code == EQ_EXPR && integer_zerop (op2))
408                   || (cmp_code == NE_EXPR && integer_onep (op2)))
409                 is_logical_not = true;
410
411               if (is_logical_not == false)
412                 result = op1;
413               /* Only for one-bit precision typed X the transformation
414                  !X -> ~X is valied.  */
415               else if (TYPE_PRECISION (type) == 1)
416                 result = build1_loc (gimple_location (stmt), BIT_NOT_EXPR,
417                                      type, op1);
418               /* Otherwise we use !X -> X ^ 1.  */
419               else
420                 result = build2_loc (gimple_location (stmt), BIT_XOR_EXPR,
421                                      type, op1, build_int_cst (type, 1));
422              
423             }
424         }
425
426       if (!result)
427         result = fold_binary_loc (loc, subcode,
428                                   TREE_TYPE (gimple_assign_lhs (stmt)),
429                                   gimple_assign_rhs1 (stmt),
430                                   gimple_assign_rhs2 (stmt));
431
432       if (result)
433         {
434           STRIP_USELESS_TYPE_CONVERSION (result);
435           if (valid_gimple_rhs_p (result))
436             return result;
437         }
438       break;
439
440     case GIMPLE_TERNARY_RHS:
441       /* Try to fold a conditional expression.  */
442       if (gimple_assign_rhs_code (stmt) == COND_EXPR)
443         {
444           tree op0 = gimple_assign_rhs1 (stmt);
445           tree tem;
446           bool set = false;
447           location_t cond_loc = gimple_location (stmt);
448
449           if (COMPARISON_CLASS_P (op0))
450             {
451               fold_defer_overflow_warnings ();
452               tem = fold_binary_loc (cond_loc,
453                                      TREE_CODE (op0), TREE_TYPE (op0),
454                                      TREE_OPERAND (op0, 0),
455                                      TREE_OPERAND (op0, 1));
456               /* This is actually a conditional expression, not a GIMPLE
457                  conditional statement, however, the valid_gimple_rhs_p
458                  test still applies.  */
459               set = (tem && is_gimple_condexpr (tem)
460                      && valid_gimple_rhs_p (tem));
461               fold_undefer_overflow_warnings (set, stmt, 0);
462             }
463           else if (is_gimple_min_invariant (op0))
464             {
465               tem = op0;
466               set = true;
467             }
468           else
469             return NULL_TREE;
470
471           if (set)
472             result = fold_build3_loc (cond_loc, COND_EXPR,
473                                       TREE_TYPE (gimple_assign_lhs (stmt)), tem,
474                                       gimple_assign_rhs2 (stmt),
475                                       gimple_assign_rhs3 (stmt));
476         }
477
478       if (!result)
479         result = fold_ternary_loc (loc, subcode,
480                                    TREE_TYPE (gimple_assign_lhs (stmt)),
481                                    gimple_assign_rhs1 (stmt),
482                                    gimple_assign_rhs2 (stmt),
483                                    gimple_assign_rhs3 (stmt));
484
485       if (result)
486         {
487           STRIP_USELESS_TYPE_CONVERSION (result);
488           if (valid_gimple_rhs_p (result))
489             return result;
490         }
491       break;
492
493     case GIMPLE_INVALID_RHS:
494       gcc_unreachable ();
495     }
496
497   return NULL_TREE;
498 }
499
500 /* Attempt to fold a conditional statement. Return true if any changes were
501    made. We only attempt to fold the condition expression, and do not perform
502    any transformation that would require alteration of the cfg.  It is
503    assumed that the operands have been previously folded.  */
504
505 static bool
506 fold_gimple_cond (gimple stmt)
507 {
508   tree result = fold_binary_loc (gimple_location (stmt),
509                              gimple_cond_code (stmt),
510                              boolean_type_node,
511                              gimple_cond_lhs (stmt),
512                              gimple_cond_rhs (stmt));
513
514   if (result)
515     {
516       STRIP_USELESS_TYPE_CONVERSION (result);
517       if (is_gimple_condexpr (result) && valid_gimple_rhs_p (result))
518         {
519           gimple_cond_set_condition_from_tree (stmt, result);
520           return true;
521         }
522     }
523
524   return false;
525 }
526
527 /* Convert EXPR into a GIMPLE value suitable for substitution on the
528    RHS of an assignment.  Insert the necessary statements before
529    iterator *SI_P.  The statement at *SI_P, which must be a GIMPLE_CALL
530    is replaced.  If the call is expected to produces a result, then it
531    is replaced by an assignment of the new RHS to the result variable.
532    If the result is to be ignored, then the call is replaced by a
533    GIMPLE_NOP.  A proper VDEF chain is retained by making the first
534    VUSE and the last VDEF of the whole sequence be the same as the replaced
535    statement and using new SSA names for stores in between.  */
536
537 void
538 gimplify_and_update_call_from_tree (gimple_stmt_iterator *si_p, tree expr)
539 {
540   tree lhs;
541   gimple stmt, new_stmt;
542   gimple_stmt_iterator i;
543   gimple_seq stmts = gimple_seq_alloc();
544   struct gimplify_ctx gctx;
545   gimple last;
546   gimple laststore;
547   tree reaching_vuse;
548
549   stmt = gsi_stmt (*si_p);
550
551   gcc_assert (is_gimple_call (stmt));
552
553   push_gimplify_context (&gctx);
554   gctx.into_ssa = gimple_in_ssa_p (cfun);
555
556   lhs = gimple_call_lhs (stmt);
557   if (lhs == NULL_TREE)
558     {
559       gimplify_and_add (expr, &stmts);
560       /* We can end up with folding a memcpy of an empty class assignment
561          which gets optimized away by C++ gimplification.  */
562       if (gimple_seq_empty_p (stmts))
563         {
564           pop_gimplify_context (NULL);
565           if (gimple_in_ssa_p (cfun))
566             {
567               unlink_stmt_vdef (stmt);
568               release_defs (stmt);
569             }
570           gsi_remove (si_p, true);
571           return;
572         }
573     }
574   else
575     {
576       tree tmp = get_initialized_tmp_var (expr, &stmts, NULL);
577       new_stmt = gimple_build_assign (lhs, tmp);
578       i = gsi_last (stmts);
579       gsi_insert_after_without_update (&i, new_stmt,
580                                        GSI_CONTINUE_LINKING);
581     }
582
583   pop_gimplify_context (NULL);
584
585   if (gimple_has_location (stmt))
586     annotate_all_with_location (stmts, gimple_location (stmt));
587
588   /* First iterate over the replacement statements backward, assigning
589      virtual operands to their defining statements.  */
590   laststore = NULL;
591   for (i = gsi_last (stmts); !gsi_end_p (i); gsi_prev (&i))
592     {
593       new_stmt = gsi_stmt (i);
594       if ((gimple_assign_single_p (new_stmt)
595            && !is_gimple_reg (gimple_assign_lhs (new_stmt)))
596           || (is_gimple_call (new_stmt)
597               && (gimple_call_flags (new_stmt)
598                   & (ECF_NOVOPS | ECF_PURE | ECF_CONST | ECF_NORETURN)) == 0))
599         {
600           tree vdef;
601           if (!laststore)
602             vdef = gimple_vdef (stmt);
603           else
604             vdef = make_ssa_name (gimple_vop (cfun), new_stmt);
605           gimple_set_vdef (new_stmt, vdef);
606           if (vdef && TREE_CODE (vdef) == SSA_NAME)
607             SSA_NAME_DEF_STMT (vdef) = new_stmt;
608           laststore = new_stmt;
609         }
610     }
611
612   /* Second iterate over the statements forward, assigning virtual
613      operands to their uses.  */
614   last = NULL;
615   reaching_vuse = gimple_vuse (stmt);
616   for (i = gsi_start (stmts); !gsi_end_p (i); gsi_next (&i))
617     {
618       /* Do not insert the last stmt in this loop but remember it
619          for replacing the original statement.  */
620       if (last)
621         {
622           gsi_insert_before (si_p, last, GSI_NEW_STMT);
623           gsi_next (si_p);
624         }
625       new_stmt = gsi_stmt (i);
626       /* The replacement can expose previously unreferenced variables.  */
627       if (gimple_in_ssa_p (cfun))
628         find_new_referenced_vars (new_stmt);
629       /* If the new statement possibly has a VUSE, update it with exact SSA
630          name we know will reach this one.  */
631       if (gimple_has_mem_ops (new_stmt))
632         gimple_set_vuse (new_stmt, reaching_vuse);
633       gimple_set_modified (new_stmt, true);
634       if (gimple_vdef (new_stmt))
635         reaching_vuse = gimple_vdef (new_stmt);
636       last = new_stmt;
637     }
638
639   /* If the new sequence does not do a store release the virtual
640      definition of the original statement.  */
641   if (reaching_vuse
642       && reaching_vuse == gimple_vuse (stmt))
643     {
644       tree vdef = gimple_vdef (stmt);
645       if (vdef
646           && TREE_CODE (vdef) == SSA_NAME)
647         {
648           unlink_stmt_vdef (stmt);
649           release_ssa_name (vdef);
650         }
651     }
652
653   /* Finally replace rhe original statement with the last.  */
654   gsi_replace (si_p, last, false);
655 }
656
657 /* Return the string length, maximum string length or maximum value of
658    ARG in LENGTH.
659    If ARG is an SSA name variable, follow its use-def chains.  If LENGTH
660    is not NULL and, for TYPE == 0, its value is not equal to the length
661    we determine or if we are unable to determine the length or value,
662    return false.  VISITED is a bitmap of visited variables.
663    TYPE is 0 if string length should be returned, 1 for maximum string
664    length and 2 for maximum value ARG can have.  */
665
666 static bool
667 get_maxval_strlen (tree arg, tree *length, bitmap visited, int type)
668 {
669   tree var, val;
670   gimple def_stmt;
671
672   if (TREE_CODE (arg) != SSA_NAME)
673     {
674       if (TREE_CODE (arg) == COND_EXPR)
675         return get_maxval_strlen (COND_EXPR_THEN (arg), length, visited, type)
676                && get_maxval_strlen (COND_EXPR_ELSE (arg), length, visited, type);
677       /* We can end up with &(*iftmp_1)[0] here as well, so handle it.  */
678       else if (TREE_CODE (arg) == ADDR_EXPR
679                && TREE_CODE (TREE_OPERAND (arg, 0)) == ARRAY_REF
680                && integer_zerop (TREE_OPERAND (TREE_OPERAND (arg, 0), 1)))
681         {
682           tree aop0 = TREE_OPERAND (TREE_OPERAND (arg, 0), 0);
683           if (TREE_CODE (aop0) == INDIRECT_REF
684               && TREE_CODE (TREE_OPERAND (aop0, 0)) == SSA_NAME)
685             return get_maxval_strlen (TREE_OPERAND (aop0, 0),
686                                       length, visited, type);
687         }
688
689       if (type == 2)
690         {
691           val = arg;
692           if (TREE_CODE (val) != INTEGER_CST
693               || tree_int_cst_sgn (val) < 0)
694             return false;
695         }
696       else
697         val = c_strlen (arg, 1);
698       if (!val)
699         return false;
700
701       if (*length)
702         {
703           if (type > 0)
704             {
705               if (TREE_CODE (*length) != INTEGER_CST
706                   || TREE_CODE (val) != INTEGER_CST)
707                 return false;
708
709               if (tree_int_cst_lt (*length, val))
710                 *length = val;
711               return true;
712             }
713           else if (simple_cst_equal (val, *length) != 1)
714             return false;
715         }
716
717       *length = val;
718       return true;
719     }
720
721   /* If we were already here, break the infinite cycle.  */
722   if (!bitmap_set_bit (visited, SSA_NAME_VERSION (arg)))
723     return true;
724
725   var = arg;
726   def_stmt = SSA_NAME_DEF_STMT (var);
727
728   switch (gimple_code (def_stmt))
729     {
730       case GIMPLE_ASSIGN:
731         /* The RHS of the statement defining VAR must either have a
732            constant length or come from another SSA_NAME with a constant
733            length.  */
734         if (gimple_assign_single_p (def_stmt)
735             || gimple_assign_unary_nop_p (def_stmt))
736           {
737             tree rhs = gimple_assign_rhs1 (def_stmt);
738             return get_maxval_strlen (rhs, length, visited, type);
739           }
740         return false;
741
742       case GIMPLE_PHI:
743         {
744           /* All the arguments of the PHI node must have the same constant
745              length.  */
746           unsigned i;
747
748           for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
749           {
750             tree arg = gimple_phi_arg (def_stmt, i)->def;
751
752             /* If this PHI has itself as an argument, we cannot
753                determine the string length of this argument.  However,
754                if we can find a constant string length for the other
755                PHI args then we can still be sure that this is a
756                constant string length.  So be optimistic and just
757                continue with the next argument.  */
758             if (arg == gimple_phi_result (def_stmt))
759               continue;
760
761             if (!get_maxval_strlen (arg, length, visited, type))
762               return false;
763           }
764         }
765         return true;
766
767       default:
768         return false;
769     }
770 }
771
772
773 /* Fold builtin call in statement STMT.  Returns a simplified tree.
774    We may return a non-constant expression, including another call
775    to a different function and with different arguments, e.g.,
776    substituting memcpy for strcpy when the string length is known.
777    Note that some builtins expand into inline code that may not
778    be valid in GIMPLE.  Callers must take care.  */
779
780 tree
781 gimple_fold_builtin (gimple stmt)
782 {
783   tree result, val[3];
784   tree callee, a;
785   int arg_idx, type;
786   bitmap visited;
787   bool ignore;
788   int nargs;
789   location_t loc = gimple_location (stmt);
790
791   gcc_assert (is_gimple_call (stmt));
792
793   ignore = (gimple_call_lhs (stmt) == NULL);
794
795   /* First try the generic builtin folder.  If that succeeds, return the
796      result directly.  */
797   result = fold_call_stmt (stmt, ignore);
798   if (result)
799     {
800       if (ignore)
801         STRIP_NOPS (result);
802       return result;
803     }
804
805   /* Ignore MD builtins.  */
806   callee = gimple_call_fndecl (stmt);
807   if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_MD)
808     return NULL_TREE;
809
810   /* Give up for always_inline inline builtins until they are
811      inlined.  */
812   if (avoid_folding_inline_builtin (callee))
813     return NULL_TREE;
814
815   /* If the builtin could not be folded, and it has no argument list,
816      we're done.  */
817   nargs = gimple_call_num_args (stmt);
818   if (nargs == 0)
819     return NULL_TREE;
820
821   /* Limit the work only for builtins we know how to simplify.  */
822   switch (DECL_FUNCTION_CODE (callee))
823     {
824     case BUILT_IN_STRLEN:
825     case BUILT_IN_FPUTS:
826     case BUILT_IN_FPUTS_UNLOCKED:
827       arg_idx = 0;
828       type = 0;
829       break;
830     case BUILT_IN_STRCPY:
831     case BUILT_IN_STRNCPY:
832       arg_idx = 1;
833       type = 0;
834       break;
835     case BUILT_IN_MEMCPY_CHK:
836     case BUILT_IN_MEMPCPY_CHK:
837     case BUILT_IN_MEMMOVE_CHK:
838     case BUILT_IN_MEMSET_CHK:
839     case BUILT_IN_STRNCPY_CHK:
840     case BUILT_IN_STPNCPY_CHK:
841       arg_idx = 2;
842       type = 2;
843       break;
844     case BUILT_IN_STRCPY_CHK:
845     case BUILT_IN_STPCPY_CHK:
846       arg_idx = 1;
847       type = 1;
848       break;
849     case BUILT_IN_SNPRINTF_CHK:
850     case BUILT_IN_VSNPRINTF_CHK:
851       arg_idx = 1;
852       type = 2;
853       break;
854     default:
855       return NULL_TREE;
856     }
857
858   if (arg_idx >= nargs)
859     return NULL_TREE;
860
861   /* Try to use the dataflow information gathered by the CCP process.  */
862   visited = BITMAP_ALLOC (NULL);
863   bitmap_clear (visited);
864
865   memset (val, 0, sizeof (val));
866   a = gimple_call_arg (stmt, arg_idx);
867   if (!get_maxval_strlen (a, &val[arg_idx], visited, type))
868     val[arg_idx] = NULL_TREE;
869
870   BITMAP_FREE (visited);
871
872   result = NULL_TREE;
873   switch (DECL_FUNCTION_CODE (callee))
874     {
875     case BUILT_IN_STRLEN:
876       if (val[0] && nargs == 1)
877         {
878           tree new_val =
879               fold_convert (TREE_TYPE (gimple_call_lhs (stmt)), val[0]);
880
881           /* If the result is not a valid gimple value, or not a cast
882              of a valid gimple value, then we cannot use the result.  */
883           if (is_gimple_val (new_val)
884               || (CONVERT_EXPR_P (new_val)
885                   && is_gimple_val (TREE_OPERAND (new_val, 0))))
886             return new_val;
887         }
888       break;
889
890     case BUILT_IN_STRCPY:
891       if (val[1] && is_gimple_val (val[1]) && nargs == 2)
892         result = fold_builtin_strcpy (loc, callee,
893                                       gimple_call_arg (stmt, 0),
894                                       gimple_call_arg (stmt, 1),
895                                       val[1]);
896       break;
897
898     case BUILT_IN_STRNCPY:
899       if (val[1] && is_gimple_val (val[1]) && nargs == 3)
900         result = fold_builtin_strncpy (loc, callee,
901                                        gimple_call_arg (stmt, 0),
902                                        gimple_call_arg (stmt, 1),
903                                        gimple_call_arg (stmt, 2),
904                                        val[1]);
905       break;
906
907     case BUILT_IN_FPUTS:
908       if (nargs == 2)
909         result = fold_builtin_fputs (loc, gimple_call_arg (stmt, 0),
910                                      gimple_call_arg (stmt, 1),
911                                      ignore, false, val[0]);
912       break;
913
914     case BUILT_IN_FPUTS_UNLOCKED:
915       if (nargs == 2)
916         result = fold_builtin_fputs (loc, gimple_call_arg (stmt, 0),
917                                      gimple_call_arg (stmt, 1),
918                                      ignore, true, val[0]);
919       break;
920
921     case BUILT_IN_MEMCPY_CHK:
922     case BUILT_IN_MEMPCPY_CHK:
923     case BUILT_IN_MEMMOVE_CHK:
924     case BUILT_IN_MEMSET_CHK:
925       if (val[2] && is_gimple_val (val[2]) && nargs == 4)
926         result = fold_builtin_memory_chk (loc, callee,
927                                           gimple_call_arg (stmt, 0),
928                                           gimple_call_arg (stmt, 1),
929                                           gimple_call_arg (stmt, 2),
930                                           gimple_call_arg (stmt, 3),
931                                           val[2], ignore,
932                                           DECL_FUNCTION_CODE (callee));
933       break;
934
935     case BUILT_IN_STRCPY_CHK:
936     case BUILT_IN_STPCPY_CHK:
937       if (val[1] && is_gimple_val (val[1]) && nargs == 3)
938         result = fold_builtin_stxcpy_chk (loc, callee,
939                                           gimple_call_arg (stmt, 0),
940                                           gimple_call_arg (stmt, 1),
941                                           gimple_call_arg (stmt, 2),
942                                           val[1], ignore,
943                                           DECL_FUNCTION_CODE (callee));
944       break;
945
946     case BUILT_IN_STRNCPY_CHK:
947     case BUILT_IN_STPNCPY_CHK:
948       if (val[2] && is_gimple_val (val[2]) && nargs == 4)
949         result = fold_builtin_stxncpy_chk (loc, gimple_call_arg (stmt, 0),
950                                            gimple_call_arg (stmt, 1),
951                                            gimple_call_arg (stmt, 2),
952                                            gimple_call_arg (stmt, 3),
953                                            val[2], ignore,
954                                            DECL_FUNCTION_CODE (callee));
955       break;
956
957     case BUILT_IN_SNPRINTF_CHK:
958     case BUILT_IN_VSNPRINTF_CHK:
959       if (val[1] && is_gimple_val (val[1]))
960         result = gimple_fold_builtin_snprintf_chk (stmt, val[1],
961                                                    DECL_FUNCTION_CODE (callee));
962       break;
963
964     default:
965       gcc_unreachable ();
966     }
967
968   if (result && ignore)
969     result = fold_ignored_result (result);
970   return result;
971 }
972
973 /* Generate code adjusting the first parameter of a call statement determined
974    by GSI by DELTA.  */
975
976 void
977 gimple_adjust_this_by_delta (gimple_stmt_iterator *gsi, tree delta)
978 {
979   gimple call_stmt = gsi_stmt (*gsi);
980   tree parm, tmp;
981   gimple new_stmt;
982
983   delta = convert_to_ptrofftype (delta);
984   gcc_assert (gimple_call_num_args (call_stmt) >= 1);
985   parm = gimple_call_arg (call_stmt, 0);
986   gcc_assert (POINTER_TYPE_P (TREE_TYPE (parm)));
987   tmp = create_tmp_var (TREE_TYPE (parm), NULL);
988   add_referenced_var (tmp);
989
990   tmp = make_ssa_name (tmp, NULL);
991   new_stmt = gimple_build_assign_with_ops (POINTER_PLUS_EXPR, tmp, parm, delta);
992   SSA_NAME_DEF_STMT (tmp) = new_stmt;
993   gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
994   gimple_call_set_arg (call_stmt, 0, tmp);
995 }
996
997 /* Return a binfo to be used for devirtualization of calls based on an object
998    represented by a declaration (i.e. a global or automatically allocated one)
999    or NULL if it cannot be found or is not safe.  CST is expected to be an
1000    ADDR_EXPR of such object or the function will return NULL.  Currently it is
1001    safe to use such binfo only if it has no base binfo (i.e. no ancestors).  */
1002
1003 tree
1004 gimple_extract_devirt_binfo_from_cst (tree cst)
1005 {
1006   HOST_WIDE_INT offset, size, max_size;
1007   tree base, type, expected_type, binfo;
1008   bool last_artificial = false;
1009
1010   if (!flag_devirtualize
1011       || TREE_CODE (cst) != ADDR_EXPR
1012       || TREE_CODE (TREE_TYPE (TREE_TYPE (cst))) != RECORD_TYPE)
1013     return NULL_TREE;
1014
1015   cst = TREE_OPERAND (cst, 0);
1016   expected_type = TREE_TYPE (cst);
1017   base = get_ref_base_and_extent (cst, &offset, &size, &max_size);
1018   type = TREE_TYPE (base);
1019   if (!DECL_P (base)
1020       || max_size == -1
1021       || max_size != size
1022       || TREE_CODE (type) != RECORD_TYPE)
1023     return NULL_TREE;
1024
1025   /* Find the sub-object the constant actually refers to and mark whether it is
1026      an artificial one (as opposed to a user-defined one).  */
1027   while (true)
1028     {
1029       HOST_WIDE_INT pos, size;
1030       tree fld;
1031
1032       if (TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (expected_type))
1033         break;
1034       if (offset < 0)
1035         return NULL_TREE;
1036
1037       for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
1038         {
1039           if (TREE_CODE (fld) != FIELD_DECL)
1040             continue;
1041
1042           pos = int_bit_position (fld);
1043           size = tree_low_cst (DECL_SIZE (fld), 1);
1044           if (pos <= offset && (pos + size) > offset)
1045             break;
1046         }
1047       if (!fld || TREE_CODE (TREE_TYPE (fld)) != RECORD_TYPE)
1048         return NULL_TREE;
1049
1050       last_artificial = DECL_ARTIFICIAL (fld);
1051       type = TREE_TYPE (fld);
1052       offset -= pos;
1053     }
1054   /* Artifical sub-objects are ancestors, we do not want to use them for
1055      devirtualization, at least not here.  */
1056   if (last_artificial)
1057     return NULL_TREE;
1058   binfo = TYPE_BINFO (type);
1059   if (!binfo || BINFO_N_BASE_BINFOS (binfo) > 0)
1060     return NULL_TREE;
1061   else
1062     return binfo;
1063 }
1064
1065 /* Attempt to fold a call statement referenced by the statement iterator GSI.
1066    The statement may be replaced by another statement, e.g., if the call
1067    simplifies to a constant value. Return true if any changes were made.
1068    It is assumed that the operands have been previously folded.  */
1069
1070 static bool
1071 gimple_fold_call (gimple_stmt_iterator *gsi, bool inplace)
1072 {
1073   gimple stmt = gsi_stmt (*gsi);
1074   tree callee;
1075   bool changed = false;
1076   unsigned i;
1077
1078   /* Fold *& in call arguments.  */
1079   for (i = 0; i < gimple_call_num_args (stmt); ++i)
1080     if (REFERENCE_CLASS_P (gimple_call_arg (stmt, i)))
1081       {
1082         tree tmp = maybe_fold_reference (gimple_call_arg (stmt, i), false);
1083         if (tmp)
1084           {
1085             gimple_call_set_arg (stmt, i, tmp);
1086             changed = true;
1087           }
1088       }
1089
1090   /* Check for virtual calls that became direct calls.  */
1091   callee = gimple_call_fn (stmt);
1092   if (callee && TREE_CODE (callee) == OBJ_TYPE_REF)
1093     {
1094       if (gimple_call_addr_fndecl (OBJ_TYPE_REF_EXPR (callee)) != NULL_TREE)
1095         {
1096           gimple_call_set_fn (stmt, OBJ_TYPE_REF_EXPR (callee));
1097           changed = true;
1098         }
1099       else
1100         {
1101           tree obj = OBJ_TYPE_REF_OBJECT (callee);
1102           tree binfo = gimple_extract_devirt_binfo_from_cst (obj);
1103           if (binfo)
1104             {
1105               HOST_WIDE_INT token
1106                 = TREE_INT_CST_LOW (OBJ_TYPE_REF_TOKEN (callee));
1107               tree fndecl = gimple_get_virt_method_for_binfo (token, binfo);
1108               if (fndecl)
1109                 {
1110                   gimple_call_set_fndecl (stmt, fndecl);
1111                   changed = true;
1112                 }
1113             }
1114         }
1115     }
1116
1117   if (inplace)
1118     return changed;
1119
1120   /* Check for builtins that CCP can handle using information not
1121      available in the generic fold routines.  */
1122   callee = gimple_call_fndecl (stmt);
1123   if (callee && DECL_BUILT_IN (callee))
1124     {
1125       tree result = gimple_fold_builtin (stmt);
1126       if (result)
1127         {
1128           if (!update_call_from_tree (gsi, result))
1129             gimplify_and_update_call_from_tree (gsi, result);
1130           changed = true;
1131         }
1132     }
1133
1134   return changed;
1135 }
1136
1137 /* Worker for both fold_stmt and fold_stmt_inplace.  The INPLACE argument
1138    distinguishes both cases.  */
1139
1140 static bool
1141 fold_stmt_1 (gimple_stmt_iterator *gsi, bool inplace)
1142 {
1143   bool changed = false;
1144   gimple stmt = gsi_stmt (*gsi);
1145   unsigned i;
1146   gimple_stmt_iterator gsinext = *gsi;
1147   gimple next_stmt;
1148
1149   gsi_next (&gsinext);
1150   next_stmt = gsi_end_p (gsinext) ? NULL : gsi_stmt (gsinext);
1151
1152   /* Fold the main computation performed by the statement.  */
1153   switch (gimple_code (stmt))
1154     {
1155     case GIMPLE_ASSIGN:
1156       {
1157         unsigned old_num_ops = gimple_num_ops (stmt);
1158         enum tree_code subcode = gimple_assign_rhs_code (stmt);
1159         tree lhs = gimple_assign_lhs (stmt);
1160         tree new_rhs;
1161         /* First canonicalize operand order.  This avoids building new
1162            trees if this is the only thing fold would later do.  */
1163         if ((commutative_tree_code (subcode)
1164              || commutative_ternary_tree_code (subcode))
1165             && tree_swap_operands_p (gimple_assign_rhs1 (stmt),
1166                                      gimple_assign_rhs2 (stmt), false))
1167           {
1168             tree tem = gimple_assign_rhs1 (stmt);
1169             gimple_assign_set_rhs1 (stmt, gimple_assign_rhs2 (stmt));
1170             gimple_assign_set_rhs2 (stmt, tem);
1171             changed = true;
1172           }
1173         new_rhs = fold_gimple_assign (gsi);
1174         if (new_rhs
1175             && !useless_type_conversion_p (TREE_TYPE (lhs),
1176                                            TREE_TYPE (new_rhs)))
1177           new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs);
1178         if (new_rhs
1179             && (!inplace
1180                 || get_gimple_rhs_num_ops (TREE_CODE (new_rhs)) < old_num_ops))
1181           {
1182             gimple_assign_set_rhs_from_tree (gsi, new_rhs);
1183             changed = true;
1184           }
1185         break;
1186       }
1187
1188     case GIMPLE_COND:
1189       changed |= fold_gimple_cond (stmt);
1190       break;
1191
1192     case GIMPLE_CALL:
1193       changed |= gimple_fold_call (gsi, inplace);
1194       break;
1195
1196     case GIMPLE_ASM:
1197       /* Fold *& in asm operands.  */
1198       {
1199         size_t noutputs;
1200         const char **oconstraints;
1201         const char *constraint;
1202         bool allows_mem, allows_reg;
1203
1204         noutputs = gimple_asm_noutputs (stmt);
1205         oconstraints = XALLOCAVEC (const char *, noutputs);
1206
1207         for (i = 0; i < gimple_asm_noutputs (stmt); ++i)
1208           {
1209             tree link = gimple_asm_output_op (stmt, i);
1210             tree op = TREE_VALUE (link);
1211             oconstraints[i]
1212               = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1213             if (REFERENCE_CLASS_P (op)
1214                 && (op = maybe_fold_reference (op, true)) != NULL_TREE)
1215               {
1216                 TREE_VALUE (link) = op;
1217                 changed = true;
1218               }
1219           }
1220         for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
1221           {
1222             tree link = gimple_asm_input_op (stmt, i);
1223             tree op = TREE_VALUE (link);
1224             constraint
1225               = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1226             parse_input_constraint (&constraint, 0, 0, noutputs, 0,
1227                                     oconstraints, &allows_mem, &allows_reg);
1228             if (REFERENCE_CLASS_P (op)
1229                 && (op = maybe_fold_reference (op, !allows_reg && allows_mem))
1230                    != NULL_TREE)
1231               {
1232                 TREE_VALUE (link) = op;
1233                 changed = true;
1234               }
1235           }
1236       }
1237       break;
1238
1239     case GIMPLE_DEBUG:
1240       if (gimple_debug_bind_p (stmt))
1241         {
1242           tree val = gimple_debug_bind_get_value (stmt);
1243           if (val
1244               && REFERENCE_CLASS_P (val))
1245             {
1246               tree tem = maybe_fold_reference (val, false);
1247               if (tem)
1248                 {
1249                   gimple_debug_bind_set_value (stmt, tem);
1250                   changed = true;
1251                 }
1252             }
1253         }
1254       break;
1255
1256     default:;
1257     }
1258
1259   /* If stmt folds into nothing and it was the last stmt in a bb,
1260      don't call gsi_stmt.  */
1261   if (gsi_end_p (*gsi))
1262     {
1263       gcc_assert (next_stmt == NULL);
1264       return changed;
1265     }
1266
1267   stmt = gsi_stmt (*gsi);
1268
1269   /* Fold *& on the lhs.  Don't do this if stmt folded into nothing,
1270      as we'd changing the next stmt.  */
1271   if (gimple_has_lhs (stmt) && stmt != next_stmt)
1272     {
1273       tree lhs = gimple_get_lhs (stmt);
1274       if (lhs && REFERENCE_CLASS_P (lhs))
1275         {
1276           tree new_lhs = maybe_fold_reference (lhs, true);
1277           if (new_lhs)
1278             {
1279               gimple_set_lhs (stmt, new_lhs);
1280               changed = true;
1281             }
1282         }
1283     }
1284
1285   return changed;
1286 }
1287
1288 /* Fold the statement pointed to by GSI.  In some cases, this function may
1289    replace the whole statement with a new one.  Returns true iff folding
1290    makes any changes.
1291    The statement pointed to by GSI should be in valid gimple form but may
1292    be in unfolded state as resulting from for example constant propagation
1293    which can produce *&x = 0.  */
1294
1295 bool
1296 fold_stmt (gimple_stmt_iterator *gsi)
1297 {
1298   return fold_stmt_1 (gsi, false);
1299 }
1300
1301 /* Perform the minimal folding on statement *GSI.  Only operations like
1302    *&x created by constant propagation are handled.  The statement cannot
1303    be replaced with a new one.  Return true if the statement was
1304    changed, false otherwise.
1305    The statement *GSI should be in valid gimple form but may
1306    be in unfolded state as resulting from for example constant propagation
1307    which can produce *&x = 0.  */
1308
1309 bool
1310 fold_stmt_inplace (gimple_stmt_iterator *gsi)
1311 {
1312   gimple stmt = gsi_stmt (*gsi);
1313   bool changed = fold_stmt_1 (gsi, true);
1314   gcc_assert (gsi_stmt (*gsi) == stmt);
1315   return changed;
1316 }
1317
1318 /* Canonicalize and possibly invert the boolean EXPR; return NULL_TREE 
1319    if EXPR is null or we don't know how.
1320    If non-null, the result always has boolean type.  */
1321
1322 static tree
1323 canonicalize_bool (tree expr, bool invert)
1324 {
1325   if (!expr)
1326     return NULL_TREE;
1327   else if (invert)
1328     {
1329       if (integer_nonzerop (expr))
1330         return boolean_false_node;
1331       else if (integer_zerop (expr))
1332         return boolean_true_node;
1333       else if (TREE_CODE (expr) == SSA_NAME)
1334         return fold_build2 (EQ_EXPR, boolean_type_node, expr,
1335                             build_int_cst (TREE_TYPE (expr), 0));
1336       else if (TREE_CODE_CLASS (TREE_CODE (expr)) == tcc_comparison)
1337         return fold_build2 (invert_tree_comparison (TREE_CODE (expr), false),
1338                             boolean_type_node,
1339                             TREE_OPERAND (expr, 0),
1340                             TREE_OPERAND (expr, 1));
1341       else
1342         return NULL_TREE;
1343     }
1344   else
1345     {
1346       if (TREE_CODE (TREE_TYPE (expr)) == BOOLEAN_TYPE)
1347         return expr;
1348       if (integer_nonzerop (expr))
1349         return boolean_true_node;
1350       else if (integer_zerop (expr))
1351         return boolean_false_node;
1352       else if (TREE_CODE (expr) == SSA_NAME)
1353         return fold_build2 (NE_EXPR, boolean_type_node, expr,
1354                             build_int_cst (TREE_TYPE (expr), 0));
1355       else if (TREE_CODE_CLASS (TREE_CODE (expr)) == tcc_comparison)
1356         return fold_build2 (TREE_CODE (expr),
1357                             boolean_type_node,
1358                             TREE_OPERAND (expr, 0),
1359                             TREE_OPERAND (expr, 1));
1360       else
1361         return NULL_TREE;
1362     }
1363 }
1364
1365 /* Check to see if a boolean expression EXPR is logically equivalent to the
1366    comparison (OP1 CODE OP2).  Check for various identities involving
1367    SSA_NAMEs.  */
1368
1369 static bool
1370 same_bool_comparison_p (const_tree expr, enum tree_code code,
1371                         const_tree op1, const_tree op2)
1372 {
1373   gimple s;
1374
1375   /* The obvious case.  */
1376   if (TREE_CODE (expr) == code
1377       && operand_equal_p (TREE_OPERAND (expr, 0), op1, 0)
1378       && operand_equal_p (TREE_OPERAND (expr, 1), op2, 0))
1379     return true;
1380
1381   /* Check for comparing (name, name != 0) and the case where expr
1382      is an SSA_NAME with a definition matching the comparison.  */
1383   if (TREE_CODE (expr) == SSA_NAME
1384       && TREE_CODE (TREE_TYPE (expr)) == BOOLEAN_TYPE)
1385     {
1386       if (operand_equal_p (expr, op1, 0))
1387         return ((code == NE_EXPR && integer_zerop (op2))
1388                 || (code == EQ_EXPR && integer_nonzerop (op2)));
1389       s = SSA_NAME_DEF_STMT (expr);
1390       if (is_gimple_assign (s)
1391           && gimple_assign_rhs_code (s) == code
1392           && operand_equal_p (gimple_assign_rhs1 (s), op1, 0)
1393           && operand_equal_p (gimple_assign_rhs2 (s), op2, 0))
1394         return true;
1395     }
1396
1397   /* If op1 is of the form (name != 0) or (name == 0), and the definition
1398      of name is a comparison, recurse.  */
1399   if (TREE_CODE (op1) == SSA_NAME
1400       && TREE_CODE (TREE_TYPE (op1)) == BOOLEAN_TYPE)
1401     {
1402       s = SSA_NAME_DEF_STMT (op1);
1403       if (is_gimple_assign (s)
1404           && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
1405         {
1406           enum tree_code c = gimple_assign_rhs_code (s);
1407           if ((c == NE_EXPR && integer_zerop (op2))
1408               || (c == EQ_EXPR && integer_nonzerop (op2)))
1409             return same_bool_comparison_p (expr, c,
1410                                            gimple_assign_rhs1 (s),
1411                                            gimple_assign_rhs2 (s));
1412           if ((c == EQ_EXPR && integer_zerop (op2))
1413               || (c == NE_EXPR && integer_nonzerop (op2)))
1414             return same_bool_comparison_p (expr,
1415                                            invert_tree_comparison (c, false),
1416                                            gimple_assign_rhs1 (s),
1417                                            gimple_assign_rhs2 (s));
1418         }
1419     }
1420   return false;
1421 }
1422
1423 /* Check to see if two boolean expressions OP1 and OP2 are logically
1424    equivalent.  */
1425
1426 static bool
1427 same_bool_result_p (const_tree op1, const_tree op2)
1428 {
1429   /* Simple cases first.  */
1430   if (operand_equal_p (op1, op2, 0))
1431     return true;
1432
1433   /* Check the cases where at least one of the operands is a comparison.
1434      These are a bit smarter than operand_equal_p in that they apply some
1435      identifies on SSA_NAMEs.  */
1436   if (TREE_CODE_CLASS (TREE_CODE (op2)) == tcc_comparison
1437       && same_bool_comparison_p (op1, TREE_CODE (op2),
1438                                  TREE_OPERAND (op2, 0),
1439                                  TREE_OPERAND (op2, 1)))
1440     return true;
1441   if (TREE_CODE_CLASS (TREE_CODE (op1)) == tcc_comparison
1442       && same_bool_comparison_p (op2, TREE_CODE (op1),
1443                                  TREE_OPERAND (op1, 0),
1444                                  TREE_OPERAND (op1, 1)))
1445     return true;
1446
1447   /* Default case.  */
1448   return false;
1449 }
1450
1451 /* Forward declarations for some mutually recursive functions.  */
1452
1453 static tree
1454 and_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
1455                    enum tree_code code2, tree op2a, tree op2b);
1456 static tree
1457 and_var_with_comparison (tree var, bool invert,
1458                          enum tree_code code2, tree op2a, tree op2b);
1459 static tree
1460 and_var_with_comparison_1 (gimple stmt, 
1461                            enum tree_code code2, tree op2a, tree op2b);
1462 static tree
1463 or_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
1464                   enum tree_code code2, tree op2a, tree op2b);
1465 static tree
1466 or_var_with_comparison (tree var, bool invert,
1467                         enum tree_code code2, tree op2a, tree op2b);
1468 static tree
1469 or_var_with_comparison_1 (gimple stmt, 
1470                           enum tree_code code2, tree op2a, tree op2b);
1471
1472 /* Helper function for and_comparisons_1:  try to simplify the AND of the
1473    ssa variable VAR with the comparison specified by (OP2A CODE2 OP2B).
1474    If INVERT is true, invert the value of the VAR before doing the AND.
1475    Return NULL_EXPR if we can't simplify this to a single expression.  */
1476
1477 static tree
1478 and_var_with_comparison (tree var, bool invert,
1479                          enum tree_code code2, tree op2a, tree op2b)
1480 {
1481   tree t;
1482   gimple stmt = SSA_NAME_DEF_STMT (var);
1483
1484   /* We can only deal with variables whose definitions are assignments.  */
1485   if (!is_gimple_assign (stmt))
1486     return NULL_TREE;
1487   
1488   /* If we have an inverted comparison, apply DeMorgan's law and rewrite
1489      !var AND (op2a code2 op2b) => !(var OR !(op2a code2 op2b))
1490      Then we only have to consider the simpler non-inverted cases.  */
1491   if (invert)
1492     t = or_var_with_comparison_1 (stmt, 
1493                                   invert_tree_comparison (code2, false),
1494                                   op2a, op2b);
1495   else
1496     t = and_var_with_comparison_1 (stmt, code2, op2a, op2b);
1497   return canonicalize_bool (t, invert);
1498 }
1499
1500 /* Try to simplify the AND of the ssa variable defined by the assignment
1501    STMT with the comparison specified by (OP2A CODE2 OP2B).
1502    Return NULL_EXPR if we can't simplify this to a single expression.  */
1503
1504 static tree
1505 and_var_with_comparison_1 (gimple stmt,
1506                            enum tree_code code2, tree op2a, tree op2b)
1507 {
1508   tree var = gimple_assign_lhs (stmt);
1509   tree true_test_var = NULL_TREE;
1510   tree false_test_var = NULL_TREE;
1511   enum tree_code innercode = gimple_assign_rhs_code (stmt);
1512
1513   /* Check for identities like (var AND (var == 0)) => false.  */
1514   if (TREE_CODE (op2a) == SSA_NAME
1515       && TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE)
1516     {
1517       if ((code2 == NE_EXPR && integer_zerop (op2b))
1518           || (code2 == EQ_EXPR && integer_nonzerop (op2b)))
1519         {
1520           true_test_var = op2a;
1521           if (var == true_test_var)
1522             return var;
1523         }
1524       else if ((code2 == EQ_EXPR && integer_zerop (op2b))
1525                || (code2 == NE_EXPR && integer_nonzerop (op2b)))
1526         {
1527           false_test_var = op2a;
1528           if (var == false_test_var)
1529             return boolean_false_node;
1530         }
1531     }
1532
1533   /* If the definition is a comparison, recurse on it.  */
1534   if (TREE_CODE_CLASS (innercode) == tcc_comparison)
1535     {
1536       tree t = and_comparisons_1 (innercode,
1537                                   gimple_assign_rhs1 (stmt),
1538                                   gimple_assign_rhs2 (stmt),
1539                                   code2,
1540                                   op2a,
1541                                   op2b);
1542       if (t)
1543         return t;
1544     }
1545
1546   /* If the definition is an AND or OR expression, we may be able to
1547      simplify by reassociating.  */
1548   if (TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE
1549       && (innercode == BIT_AND_EXPR || innercode == BIT_IOR_EXPR))
1550     {
1551       tree inner1 = gimple_assign_rhs1 (stmt);
1552       tree inner2 = gimple_assign_rhs2 (stmt);
1553       gimple s;
1554       tree t;
1555       tree partial = NULL_TREE;
1556       bool is_and = (innercode == BIT_AND_EXPR);
1557       
1558       /* Check for boolean identities that don't require recursive examination
1559          of inner1/inner2:
1560          inner1 AND (inner1 AND inner2) => inner1 AND inner2 => var
1561          inner1 AND (inner1 OR inner2) => inner1
1562          !inner1 AND (inner1 AND inner2) => false
1563          !inner1 AND (inner1 OR inner2) => !inner1 AND inner2
1564          Likewise for similar cases involving inner2.  */
1565       if (inner1 == true_test_var)
1566         return (is_and ? var : inner1);
1567       else if (inner2 == true_test_var)
1568         return (is_and ? var : inner2);
1569       else if (inner1 == false_test_var)
1570         return (is_and
1571                 ? boolean_false_node
1572                 : and_var_with_comparison (inner2, false, code2, op2a, op2b));
1573       else if (inner2 == false_test_var)
1574         return (is_and
1575                 ? boolean_false_node
1576                 : and_var_with_comparison (inner1, false, code2, op2a, op2b));
1577
1578       /* Next, redistribute/reassociate the AND across the inner tests.
1579          Compute the first partial result, (inner1 AND (op2a code op2b))  */
1580       if (TREE_CODE (inner1) == SSA_NAME
1581           && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner1))
1582           && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
1583           && (t = maybe_fold_and_comparisons (gimple_assign_rhs_code (s),
1584                                               gimple_assign_rhs1 (s),
1585                                               gimple_assign_rhs2 (s),
1586                                               code2, op2a, op2b)))
1587         {
1588           /* Handle the AND case, where we are reassociating:
1589              (inner1 AND inner2) AND (op2a code2 op2b)
1590              => (t AND inner2)
1591              If the partial result t is a constant, we win.  Otherwise
1592              continue on to try reassociating with the other inner test.  */
1593           if (is_and)
1594             {
1595               if (integer_onep (t))
1596                 return inner2;
1597               else if (integer_zerop (t))
1598                 return boolean_false_node;
1599             }
1600
1601           /* Handle the OR case, where we are redistributing:
1602              (inner1 OR inner2) AND (op2a code2 op2b)
1603              => (t OR (inner2 AND (op2a code2 op2b)))  */
1604           else if (integer_onep (t))
1605             return boolean_true_node;
1606
1607           /* Save partial result for later.  */
1608           partial = t;
1609         }
1610       
1611       /* Compute the second partial result, (inner2 AND (op2a code op2b)) */
1612       if (TREE_CODE (inner2) == SSA_NAME
1613           && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner2))
1614           && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
1615           && (t = maybe_fold_and_comparisons (gimple_assign_rhs_code (s),
1616                                               gimple_assign_rhs1 (s),
1617                                               gimple_assign_rhs2 (s),
1618                                               code2, op2a, op2b)))
1619         {
1620           /* Handle the AND case, where we are reassociating:
1621              (inner1 AND inner2) AND (op2a code2 op2b)
1622              => (inner1 AND t)  */
1623           if (is_and)
1624             {
1625               if (integer_onep (t))
1626                 return inner1;
1627               else if (integer_zerop (t))
1628                 return boolean_false_node;
1629               /* If both are the same, we can apply the identity
1630                  (x AND x) == x.  */
1631               else if (partial && same_bool_result_p (t, partial))
1632                 return t;
1633             }
1634
1635           /* Handle the OR case. where we are redistributing:
1636              (inner1 OR inner2) AND (op2a code2 op2b)
1637              => (t OR (inner1 AND (op2a code2 op2b)))
1638              => (t OR partial)  */
1639           else
1640             {
1641               if (integer_onep (t))
1642                 return boolean_true_node;
1643               else if (partial)
1644                 {
1645                   /* We already got a simplification for the other
1646                      operand to the redistributed OR expression.  The
1647                      interesting case is when at least one is false.
1648                      Or, if both are the same, we can apply the identity
1649                      (x OR x) == x.  */
1650                   if (integer_zerop (partial))
1651                     return t;
1652                   else if (integer_zerop (t))
1653                     return partial;
1654                   else if (same_bool_result_p (t, partial))
1655                     return t;
1656                 }
1657             }
1658         }
1659     }
1660   return NULL_TREE;
1661 }
1662
1663 /* Try to simplify the AND of two comparisons defined by
1664    (OP1A CODE1 OP1B) and (OP2A CODE2 OP2B), respectively.
1665    If this can be done without constructing an intermediate value,
1666    return the resulting tree; otherwise NULL_TREE is returned.
1667    This function is deliberately asymmetric as it recurses on SSA_DEFs
1668    in the first comparison but not the second.  */
1669
1670 static tree
1671 and_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
1672                    enum tree_code code2, tree op2a, tree op2b)
1673 {
1674   /* First check for ((x CODE1 y) AND (x CODE2 y)).  */
1675   if (operand_equal_p (op1a, op2a, 0)
1676       && operand_equal_p (op1b, op2b, 0))
1677     {
1678       /* Result will be either NULL_TREE, or a combined comparison.  */
1679       tree t = combine_comparisons (UNKNOWN_LOCATION,
1680                                     TRUTH_ANDIF_EXPR, code1, code2,
1681                                     boolean_type_node, op1a, op1b);
1682       if (t)
1683         return t;
1684     }
1685
1686   /* Likewise the swapped case of the above.  */
1687   if (operand_equal_p (op1a, op2b, 0)
1688       && operand_equal_p (op1b, op2a, 0))
1689     {
1690       /* Result will be either NULL_TREE, or a combined comparison.  */
1691       tree t = combine_comparisons (UNKNOWN_LOCATION,
1692                                     TRUTH_ANDIF_EXPR, code1,
1693                                     swap_tree_comparison (code2),
1694                                     boolean_type_node, op1a, op1b);
1695       if (t)
1696         return t;
1697     }
1698
1699   /* If both comparisons are of the same value against constants, we might
1700      be able to merge them.  */
1701   if (operand_equal_p (op1a, op2a, 0)
1702       && TREE_CODE (op1b) == INTEGER_CST
1703       && TREE_CODE (op2b) == INTEGER_CST)
1704     {
1705       int cmp = tree_int_cst_compare (op1b, op2b);
1706
1707       /* If we have (op1a == op1b), we should either be able to
1708          return that or FALSE, depending on whether the constant op1b
1709          also satisfies the other comparison against op2b.  */
1710       if (code1 == EQ_EXPR)
1711         {
1712           bool done = true;
1713           bool val;
1714           switch (code2)
1715             {
1716             case EQ_EXPR: val = (cmp == 0); break;
1717             case NE_EXPR: val = (cmp != 0); break;
1718             case LT_EXPR: val = (cmp < 0); break;
1719             case GT_EXPR: val = (cmp > 0); break;
1720             case LE_EXPR: val = (cmp <= 0); break;
1721             case GE_EXPR: val = (cmp >= 0); break;
1722             default: done = false;
1723             }
1724           if (done)
1725             {
1726               if (val)
1727                 return fold_build2 (code1, boolean_type_node, op1a, op1b);
1728               else
1729                 return boolean_false_node;
1730             }
1731         }
1732       /* Likewise if the second comparison is an == comparison.  */
1733       else if (code2 == EQ_EXPR)
1734         {
1735           bool done = true;
1736           bool val;
1737           switch (code1)
1738             {
1739             case EQ_EXPR: val = (cmp == 0); break;
1740             case NE_EXPR: val = (cmp != 0); break;
1741             case LT_EXPR: val = (cmp > 0); break;
1742             case GT_EXPR: val = (cmp < 0); break;
1743             case LE_EXPR: val = (cmp >= 0); break;
1744             case GE_EXPR: val = (cmp <= 0); break;
1745             default: done = false;
1746             }
1747           if (done)
1748             {
1749               if (val)
1750                 return fold_build2 (code2, boolean_type_node, op2a, op2b);
1751               else
1752                 return boolean_false_node;
1753             }
1754         }
1755
1756       /* Same business with inequality tests.  */
1757       else if (code1 == NE_EXPR)
1758         {
1759           bool val;
1760           switch (code2)
1761             {
1762             case EQ_EXPR: val = (cmp != 0); break;
1763             case NE_EXPR: val = (cmp == 0); break;
1764             case LT_EXPR: val = (cmp >= 0); break;
1765             case GT_EXPR: val = (cmp <= 0); break;
1766             case LE_EXPR: val = (cmp > 0); break;
1767             case GE_EXPR: val = (cmp < 0); break;
1768             default:
1769               val = false;
1770             }
1771           if (val)
1772             return fold_build2 (code2, boolean_type_node, op2a, op2b);
1773         }
1774       else if (code2 == NE_EXPR)
1775         {
1776           bool val;
1777           switch (code1)
1778             {
1779             case EQ_EXPR: val = (cmp == 0); break;
1780             case NE_EXPR: val = (cmp != 0); break;
1781             case LT_EXPR: val = (cmp <= 0); break;
1782             case GT_EXPR: val = (cmp >= 0); break;
1783             case LE_EXPR: val = (cmp < 0); break;
1784             case GE_EXPR: val = (cmp > 0); break;
1785             default:
1786               val = false;
1787             }
1788           if (val)
1789             return fold_build2 (code1, boolean_type_node, op1a, op1b);
1790         }
1791
1792       /* Chose the more restrictive of two < or <= comparisons.  */
1793       else if ((code1 == LT_EXPR || code1 == LE_EXPR)
1794                && (code2 == LT_EXPR || code2 == LE_EXPR))
1795         {
1796           if ((cmp < 0) || (cmp == 0 && code1 == LT_EXPR))
1797             return fold_build2 (code1, boolean_type_node, op1a, op1b);
1798           else
1799             return fold_build2 (code2, boolean_type_node, op2a, op2b);
1800         }
1801
1802       /* Likewise chose the more restrictive of two > or >= comparisons.  */
1803       else if ((code1 == GT_EXPR || code1 == GE_EXPR)
1804                && (code2 == GT_EXPR || code2 == GE_EXPR))
1805         {
1806           if ((cmp > 0) || (cmp == 0 && code1 == GT_EXPR))
1807             return fold_build2 (code1, boolean_type_node, op1a, op1b);
1808           else
1809             return fold_build2 (code2, boolean_type_node, op2a, op2b);
1810         }
1811
1812       /* Check for singleton ranges.  */
1813       else if (cmp == 0
1814                && ((code1 == LE_EXPR && code2 == GE_EXPR)
1815                    || (code1 == GE_EXPR && code2 == LE_EXPR)))
1816         return fold_build2 (EQ_EXPR, boolean_type_node, op1a, op2b);
1817
1818       /* Check for disjoint ranges. */
1819       else if (cmp <= 0
1820                && (code1 == LT_EXPR || code1 == LE_EXPR)
1821                && (code2 == GT_EXPR || code2 == GE_EXPR))
1822         return boolean_false_node;
1823       else if (cmp >= 0
1824                && (code1 == GT_EXPR || code1 == GE_EXPR)
1825                && (code2 == LT_EXPR || code2 == LE_EXPR))
1826         return boolean_false_node;
1827     }
1828
1829   /* Perhaps the first comparison is (NAME != 0) or (NAME == 1) where
1830      NAME's definition is a truth value.  See if there are any simplifications
1831      that can be done against the NAME's definition.  */
1832   if (TREE_CODE (op1a) == SSA_NAME
1833       && (code1 == NE_EXPR || code1 == EQ_EXPR)
1834       && (integer_zerop (op1b) || integer_onep (op1b)))
1835     {
1836       bool invert = ((code1 == EQ_EXPR && integer_zerop (op1b))
1837                      || (code1 == NE_EXPR && integer_onep (op1b)));
1838       gimple stmt = SSA_NAME_DEF_STMT (op1a);
1839       switch (gimple_code (stmt))
1840         {
1841         case GIMPLE_ASSIGN:
1842           /* Try to simplify by copy-propagating the definition.  */
1843           return and_var_with_comparison (op1a, invert, code2, op2a, op2b);
1844
1845         case GIMPLE_PHI:
1846           /* If every argument to the PHI produces the same result when
1847              ANDed with the second comparison, we win.
1848              Do not do this unless the type is bool since we need a bool
1849              result here anyway.  */
1850           if (TREE_CODE (TREE_TYPE (op1a)) == BOOLEAN_TYPE)
1851             {
1852               tree result = NULL_TREE;
1853               unsigned i;
1854               for (i = 0; i < gimple_phi_num_args (stmt); i++)
1855                 {
1856                   tree arg = gimple_phi_arg_def (stmt, i);
1857                   
1858                   /* If this PHI has itself as an argument, ignore it.
1859                      If all the other args produce the same result,
1860                      we're still OK.  */
1861                   if (arg == gimple_phi_result (stmt))
1862                     continue;
1863                   else if (TREE_CODE (arg) == INTEGER_CST)
1864                     {
1865                       if (invert ? integer_nonzerop (arg) : integer_zerop (arg))
1866                         {
1867                           if (!result)
1868                             result = boolean_false_node;
1869                           else if (!integer_zerop (result))
1870                             return NULL_TREE;
1871                         }
1872                       else if (!result)
1873                         result = fold_build2 (code2, boolean_type_node,
1874                                               op2a, op2b);
1875                       else if (!same_bool_comparison_p (result,
1876                                                         code2, op2a, op2b))
1877                         return NULL_TREE;
1878                     }
1879                   else if (TREE_CODE (arg) == SSA_NAME
1880                            && !SSA_NAME_IS_DEFAULT_DEF (arg))
1881                     {
1882                       tree temp;
1883                       gimple def_stmt = SSA_NAME_DEF_STMT (arg);
1884                       /* In simple cases we can look through PHI nodes,
1885                          but we have to be careful with loops.
1886                          See PR49073.  */
1887                       if (! dom_info_available_p (CDI_DOMINATORS)
1888                           || gimple_bb (def_stmt) == gimple_bb (stmt)
1889                           || dominated_by_p (CDI_DOMINATORS,
1890                                              gimple_bb (def_stmt),
1891                                              gimple_bb (stmt)))
1892                         return NULL_TREE;
1893                       temp = and_var_with_comparison (arg, invert, code2,
1894                                                       op2a, op2b);
1895                       if (!temp)
1896                         return NULL_TREE;
1897                       else if (!result)
1898                         result = temp;
1899                       else if (!same_bool_result_p (result, temp))
1900                         return NULL_TREE;
1901                     }
1902                   else
1903                     return NULL_TREE;
1904                 }
1905               return result;
1906             }
1907
1908         default:
1909           break;
1910         }
1911     }
1912   return NULL_TREE;
1913 }
1914
1915 /* Try to simplify the AND of two comparisons, specified by
1916    (OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
1917    If this can be simplified to a single expression (without requiring
1918    introducing more SSA variables to hold intermediate values),
1919    return the resulting tree.  Otherwise return NULL_TREE.
1920    If the result expression is non-null, it has boolean type.  */
1921
1922 tree
1923 maybe_fold_and_comparisons (enum tree_code code1, tree op1a, tree op1b,
1924                             enum tree_code code2, tree op2a, tree op2b)
1925 {
1926   tree t = and_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
1927   if (t)
1928     return t;
1929   else
1930     return and_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
1931 }
1932
1933 /* Helper function for or_comparisons_1:  try to simplify the OR of the
1934    ssa variable VAR with the comparison specified by (OP2A CODE2 OP2B).
1935    If INVERT is true, invert the value of VAR before doing the OR.
1936    Return NULL_EXPR if we can't simplify this to a single expression.  */
1937
1938 static tree
1939 or_var_with_comparison (tree var, bool invert,
1940                         enum tree_code code2, tree op2a, tree op2b)
1941 {
1942   tree t;
1943   gimple stmt = SSA_NAME_DEF_STMT (var);
1944
1945   /* We can only deal with variables whose definitions are assignments.  */
1946   if (!is_gimple_assign (stmt))
1947     return NULL_TREE;
1948   
1949   /* If we have an inverted comparison, apply DeMorgan's law and rewrite
1950      !var OR (op2a code2 op2b) => !(var AND !(op2a code2 op2b))
1951      Then we only have to consider the simpler non-inverted cases.  */
1952   if (invert)
1953     t = and_var_with_comparison_1 (stmt, 
1954                                    invert_tree_comparison (code2, false),
1955                                    op2a, op2b);
1956   else
1957     t = or_var_with_comparison_1 (stmt, code2, op2a, op2b);
1958   return canonicalize_bool (t, invert);
1959 }
1960
1961 /* Try to simplify the OR of the ssa variable defined by the assignment
1962    STMT with the comparison specified by (OP2A CODE2 OP2B).
1963    Return NULL_EXPR if we can't simplify this to a single expression.  */
1964
1965 static tree
1966 or_var_with_comparison_1 (gimple stmt,
1967                           enum tree_code code2, tree op2a, tree op2b)
1968 {
1969   tree var = gimple_assign_lhs (stmt);
1970   tree true_test_var = NULL_TREE;
1971   tree false_test_var = NULL_TREE;
1972   enum tree_code innercode = gimple_assign_rhs_code (stmt);
1973
1974   /* Check for identities like (var OR (var != 0)) => true .  */
1975   if (TREE_CODE (op2a) == SSA_NAME
1976       && TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE)
1977     {
1978       if ((code2 == NE_EXPR && integer_zerop (op2b))
1979           || (code2 == EQ_EXPR && integer_nonzerop (op2b)))
1980         {
1981           true_test_var = op2a;
1982           if (var == true_test_var)
1983             return var;
1984         }
1985       else if ((code2 == EQ_EXPR && integer_zerop (op2b))
1986                || (code2 == NE_EXPR && integer_nonzerop (op2b)))
1987         {
1988           false_test_var = op2a;
1989           if (var == false_test_var)
1990             return boolean_true_node;
1991         }
1992     }
1993
1994   /* If the definition is a comparison, recurse on it.  */
1995   if (TREE_CODE_CLASS (innercode) == tcc_comparison)
1996     {
1997       tree t = or_comparisons_1 (innercode,
1998                                  gimple_assign_rhs1 (stmt),
1999                                  gimple_assign_rhs2 (stmt),
2000                                  code2,
2001                                  op2a,
2002                                  op2b);
2003       if (t)
2004         return t;
2005     }
2006   
2007   /* If the definition is an AND or OR expression, we may be able to
2008      simplify by reassociating.  */
2009   if (TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE
2010       && (innercode == BIT_AND_EXPR || innercode == BIT_IOR_EXPR))
2011     {
2012       tree inner1 = gimple_assign_rhs1 (stmt);
2013       tree inner2 = gimple_assign_rhs2 (stmt);
2014       gimple s;
2015       tree t;
2016       tree partial = NULL_TREE;
2017       bool is_or = (innercode == BIT_IOR_EXPR);
2018       
2019       /* Check for boolean identities that don't require recursive examination
2020          of inner1/inner2:
2021          inner1 OR (inner1 OR inner2) => inner1 OR inner2 => var
2022          inner1 OR (inner1 AND inner2) => inner1
2023          !inner1 OR (inner1 OR inner2) => true
2024          !inner1 OR (inner1 AND inner2) => !inner1 OR inner2
2025       */
2026       if (inner1 == true_test_var)
2027         return (is_or ? var : inner1);
2028       else if (inner2 == true_test_var)
2029         return (is_or ? var : inner2);
2030       else if (inner1 == false_test_var)
2031         return (is_or
2032                 ? boolean_true_node
2033                 : or_var_with_comparison (inner2, false, code2, op2a, op2b));
2034       else if (inner2 == false_test_var)
2035         return (is_or
2036                 ? boolean_true_node
2037                 : or_var_with_comparison (inner1, false, code2, op2a, op2b));
2038       
2039       /* Next, redistribute/reassociate the OR across the inner tests.
2040          Compute the first partial result, (inner1 OR (op2a code op2b))  */
2041       if (TREE_CODE (inner1) == SSA_NAME
2042           && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner1))
2043           && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
2044           && (t = maybe_fold_or_comparisons (gimple_assign_rhs_code (s),
2045                                              gimple_assign_rhs1 (s),
2046                                              gimple_assign_rhs2 (s),
2047                                              code2, op2a, op2b)))
2048         {
2049           /* Handle the OR case, where we are reassociating:
2050              (inner1 OR inner2) OR (op2a code2 op2b)
2051              => (t OR inner2)
2052              If the partial result t is a constant, we win.  Otherwise
2053              continue on to try reassociating with the other inner test.  */
2054           if (is_or)
2055             {
2056               if (integer_onep (t))
2057                 return boolean_true_node;
2058               else if (integer_zerop (t))
2059                 return inner2;
2060             }
2061           
2062           /* Handle the AND case, where we are redistributing:
2063              (inner1 AND inner2) OR (op2a code2 op2b)
2064              => (t AND (inner2 OR (op2a code op2b)))  */
2065           else if (integer_zerop (t))
2066             return boolean_false_node;
2067
2068           /* Save partial result for later.  */
2069           partial = t;
2070         }
2071       
2072       /* Compute the second partial result, (inner2 OR (op2a code op2b)) */
2073       if (TREE_CODE (inner2) == SSA_NAME
2074           && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner2))
2075           && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
2076           && (t = maybe_fold_or_comparisons (gimple_assign_rhs_code (s),
2077                                              gimple_assign_rhs1 (s),
2078                                              gimple_assign_rhs2 (s),
2079                                              code2, op2a, op2b)))
2080         {
2081           /* Handle the OR case, where we are reassociating:
2082              (inner1 OR inner2) OR (op2a code2 op2b)
2083              => (inner1 OR t)
2084              => (t OR partial)  */
2085           if (is_or)
2086             {
2087               if (integer_zerop (t))
2088                 return inner1;
2089               else if (integer_onep (t))
2090                 return boolean_true_node;
2091               /* If both are the same, we can apply the identity
2092                  (x OR x) == x.  */
2093               else if (partial && same_bool_result_p (t, partial))
2094                 return t;
2095             }
2096           
2097           /* Handle the AND case, where we are redistributing:
2098              (inner1 AND inner2) OR (op2a code2 op2b)
2099              => (t AND (inner1 OR (op2a code2 op2b)))
2100              => (t AND partial)  */
2101           else 
2102             {
2103               if (integer_zerop (t))
2104                 return boolean_false_node;
2105               else if (partial)
2106                 {
2107                   /* We already got a simplification for the other
2108                      operand to the redistributed AND expression.  The
2109                      interesting case is when at least one is true.
2110                      Or, if both are the same, we can apply the identity
2111                      (x AND x) == x.  */
2112                   if (integer_onep (partial))
2113                     return t;
2114                   else if (integer_onep (t))
2115                     return partial;
2116                   else if (same_bool_result_p (t, partial))
2117                     return t;
2118                 }
2119             }
2120         }
2121     }
2122   return NULL_TREE;
2123 }
2124
2125 /* Try to simplify the OR of two comparisons defined by
2126    (OP1A CODE1 OP1B) and (OP2A CODE2 OP2B), respectively.
2127    If this can be done without constructing an intermediate value,
2128    return the resulting tree; otherwise NULL_TREE is returned.
2129    This function is deliberately asymmetric as it recurses on SSA_DEFs
2130    in the first comparison but not the second.  */
2131
2132 static tree
2133 or_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
2134                   enum tree_code code2, tree op2a, tree op2b)
2135 {
2136   /* First check for ((x CODE1 y) OR (x CODE2 y)).  */
2137   if (operand_equal_p (op1a, op2a, 0)
2138       && operand_equal_p (op1b, op2b, 0))
2139     {
2140       /* Result will be either NULL_TREE, or a combined comparison.  */
2141       tree t = combine_comparisons (UNKNOWN_LOCATION,
2142                                     TRUTH_ORIF_EXPR, code1, code2,
2143                                     boolean_type_node, op1a, op1b);
2144       if (t)
2145         return t;
2146     }
2147
2148   /* Likewise the swapped case of the above.  */
2149   if (operand_equal_p (op1a, op2b, 0)
2150       && operand_equal_p (op1b, op2a, 0))
2151     {
2152       /* Result will be either NULL_TREE, or a combined comparison.  */
2153       tree t = combine_comparisons (UNKNOWN_LOCATION,
2154                                     TRUTH_ORIF_EXPR, code1,
2155                                     swap_tree_comparison (code2),
2156                                     boolean_type_node, op1a, op1b);
2157       if (t)
2158         return t;
2159     }
2160
2161   /* If both comparisons are of the same value against constants, we might
2162      be able to merge them.  */
2163   if (operand_equal_p (op1a, op2a, 0)
2164       && TREE_CODE (op1b) == INTEGER_CST
2165       && TREE_CODE (op2b) == INTEGER_CST)
2166     {
2167       int cmp = tree_int_cst_compare (op1b, op2b);
2168
2169       /* If we have (op1a != op1b), we should either be able to
2170          return that or TRUE, depending on whether the constant op1b
2171          also satisfies the other comparison against op2b.  */
2172       if (code1 == NE_EXPR)
2173         {
2174           bool done = true;
2175           bool val;
2176           switch (code2)
2177             {
2178             case EQ_EXPR: val = (cmp == 0); break;
2179             case NE_EXPR: val = (cmp != 0); break;
2180             case LT_EXPR: val = (cmp < 0); break;
2181             case GT_EXPR: val = (cmp > 0); break;
2182             case LE_EXPR: val = (cmp <= 0); break;
2183             case GE_EXPR: val = (cmp >= 0); break;
2184             default: done = false;
2185             }
2186           if (done)
2187             {
2188               if (val)
2189                 return boolean_true_node;
2190               else
2191                 return fold_build2 (code1, boolean_type_node, op1a, op1b);
2192             }
2193         }
2194       /* Likewise if the second comparison is a != comparison.  */
2195       else if (code2 == NE_EXPR)
2196         {
2197           bool done = true;
2198           bool val;
2199           switch (code1)
2200             {
2201             case EQ_EXPR: val = (cmp == 0); break;
2202             case NE_EXPR: val = (cmp != 0); break;
2203             case LT_EXPR: val = (cmp > 0); break;
2204             case GT_EXPR: val = (cmp < 0); break;
2205             case LE_EXPR: val = (cmp >= 0); break;
2206             case GE_EXPR: val = (cmp <= 0); break;
2207             default: done = false;
2208             }
2209           if (done)
2210             {
2211               if (val)
2212                 return boolean_true_node;
2213               else
2214                 return fold_build2 (code2, boolean_type_node, op2a, op2b);
2215             }
2216         }
2217
2218       /* See if an equality test is redundant with the other comparison.  */
2219       else if (code1 == EQ_EXPR)
2220         {
2221           bool val;
2222           switch (code2)
2223             {
2224             case EQ_EXPR: val = (cmp == 0); break;
2225             case NE_EXPR: val = (cmp != 0); break;
2226             case LT_EXPR: val = (cmp < 0); break;
2227             case GT_EXPR: val = (cmp > 0); break;
2228             case LE_EXPR: val = (cmp <= 0); break;
2229             case GE_EXPR: val = (cmp >= 0); break;
2230             default:
2231               val = false;
2232             }
2233           if (val)
2234             return fold_build2 (code2, boolean_type_node, op2a, op2b);
2235         }
2236       else if (code2 == EQ_EXPR)
2237         {
2238           bool val;
2239           switch (code1)
2240             {
2241             case EQ_EXPR: val = (cmp == 0); break;
2242             case NE_EXPR: val = (cmp != 0); break;
2243             case LT_EXPR: val = (cmp > 0); break;
2244             case GT_EXPR: val = (cmp < 0); break;
2245             case LE_EXPR: val = (cmp >= 0); break;
2246             case GE_EXPR: val = (cmp <= 0); break;
2247             default:
2248               val = false;
2249             }
2250           if (val)
2251             return fold_build2 (code1, boolean_type_node, op1a, op1b);
2252         }
2253
2254       /* Chose the less restrictive of two < or <= comparisons.  */
2255       else if ((code1 == LT_EXPR || code1 == LE_EXPR)
2256                && (code2 == LT_EXPR || code2 == LE_EXPR))
2257         {
2258           if ((cmp < 0) || (cmp == 0 && code1 == LT_EXPR))
2259             return fold_build2 (code2, boolean_type_node, op2a, op2b);
2260           else
2261             return fold_build2 (code1, boolean_type_node, op1a, op1b);
2262         }
2263
2264       /* Likewise chose the less restrictive of two > or >= comparisons.  */
2265       else if ((code1 == GT_EXPR || code1 == GE_EXPR)
2266                && (code2 == GT_EXPR || code2 == GE_EXPR))
2267         {
2268           if ((cmp > 0) || (cmp == 0 && code1 == GT_EXPR))
2269             return fold_build2 (code2, boolean_type_node, op2a, op2b);
2270           else
2271             return fold_build2 (code1, boolean_type_node, op1a, op1b);
2272         }
2273
2274       /* Check for singleton ranges.  */
2275       else if (cmp == 0
2276                && ((code1 == LT_EXPR && code2 == GT_EXPR)
2277                    || (code1 == GT_EXPR && code2 == LT_EXPR)))
2278         return fold_build2 (NE_EXPR, boolean_type_node, op1a, op2b);
2279
2280       /* Check for less/greater pairs that don't restrict the range at all.  */
2281       else if (cmp >= 0
2282                && (code1 == LT_EXPR || code1 == LE_EXPR)
2283                && (code2 == GT_EXPR || code2 == GE_EXPR))
2284         return boolean_true_node;
2285       else if (cmp <= 0
2286                && (code1 == GT_EXPR || code1 == GE_EXPR)
2287                && (code2 == LT_EXPR || code2 == LE_EXPR))
2288         return boolean_true_node;
2289     }
2290
2291   /* Perhaps the first comparison is (NAME != 0) or (NAME == 1) where
2292      NAME's definition is a truth value.  See if there are any simplifications
2293      that can be done against the NAME's definition.  */
2294   if (TREE_CODE (op1a) == SSA_NAME
2295       && (code1 == NE_EXPR || code1 == EQ_EXPR)
2296       && (integer_zerop (op1b) || integer_onep (op1b)))
2297     {
2298       bool invert = ((code1 == EQ_EXPR && integer_zerop (op1b))
2299                      || (code1 == NE_EXPR && integer_onep (op1b)));
2300       gimple stmt = SSA_NAME_DEF_STMT (op1a);
2301       switch (gimple_code (stmt))
2302         {
2303         case GIMPLE_ASSIGN:
2304           /* Try to simplify by copy-propagating the definition.  */
2305           return or_var_with_comparison (op1a, invert, code2, op2a, op2b);
2306
2307         case GIMPLE_PHI:
2308           /* If every argument to the PHI produces the same result when
2309              ORed with the second comparison, we win.
2310              Do not do this unless the type is bool since we need a bool
2311              result here anyway.  */
2312           if (TREE_CODE (TREE_TYPE (op1a)) == BOOLEAN_TYPE)
2313             {
2314               tree result = NULL_TREE;
2315               unsigned i;
2316               for (i = 0; i < gimple_phi_num_args (stmt); i++)
2317                 {
2318                   tree arg = gimple_phi_arg_def (stmt, i);
2319                   
2320                   /* If this PHI has itself as an argument, ignore it.
2321                      If all the other args produce the same result,
2322                      we're still OK.  */
2323                   if (arg == gimple_phi_result (stmt))
2324                     continue;
2325                   else if (TREE_CODE (arg) == INTEGER_CST)
2326                     {
2327                       if (invert ? integer_zerop (arg) : integer_nonzerop (arg))
2328                         {
2329                           if (!result)
2330                             result = boolean_true_node;
2331                           else if (!integer_onep (result))
2332                             return NULL_TREE;
2333                         }
2334                       else if (!result)
2335                         result = fold_build2 (code2, boolean_type_node,
2336                                               op2a, op2b);
2337                       else if (!same_bool_comparison_p (result,
2338                                                         code2, op2a, op2b))
2339                         return NULL_TREE;
2340                     }
2341                   else if (TREE_CODE (arg) == SSA_NAME
2342                            && !SSA_NAME_IS_DEFAULT_DEF (arg))
2343                     {
2344                       tree temp;
2345                       gimple def_stmt = SSA_NAME_DEF_STMT (arg);
2346                       /* In simple cases we can look through PHI nodes,
2347                          but we have to be careful with loops.
2348                          See PR49073.  */
2349                       if (! dom_info_available_p (CDI_DOMINATORS)
2350                           || gimple_bb (def_stmt) == gimple_bb (stmt)
2351                           || dominated_by_p (CDI_DOMINATORS,
2352                                              gimple_bb (def_stmt),
2353                                              gimple_bb (stmt)))
2354                         return NULL_TREE;
2355                       temp = or_var_with_comparison (arg, invert, code2,
2356                                                      op2a, op2b);
2357                       if (!temp)
2358                         return NULL_TREE;
2359                       else if (!result)
2360                         result = temp;
2361                       else if (!same_bool_result_p (result, temp))
2362                         return NULL_TREE;
2363                     }
2364                   else
2365                     return NULL_TREE;
2366                 }
2367               return result;
2368             }
2369
2370         default:
2371           break;
2372         }
2373     }
2374   return NULL_TREE;
2375 }
2376
2377 /* Try to simplify the OR of two comparisons, specified by
2378    (OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
2379    If this can be simplified to a single expression (without requiring
2380    introducing more SSA variables to hold intermediate values),
2381    return the resulting tree.  Otherwise return NULL_TREE.
2382    If the result expression is non-null, it has boolean type.  */
2383
2384 tree
2385 maybe_fold_or_comparisons (enum tree_code code1, tree op1a, tree op1b,
2386                            enum tree_code code2, tree op2a, tree op2b)
2387 {
2388   tree t = or_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
2389   if (t)
2390     return t;
2391   else
2392     return or_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
2393 }
2394
2395
2396 /* Fold STMT to a constant using VALUEIZE to valueize SSA names.
2397
2398    Either NULL_TREE, a simplified but non-constant or a constant
2399    is returned.
2400
2401    ???  This should go into a gimple-fold-inline.h file to be eventually
2402    privatized with the single valueize function used in the various TUs
2403    to avoid the indirect function call overhead.  */
2404
2405 tree
2406 gimple_fold_stmt_to_constant_1 (gimple stmt, tree (*valueize) (tree))
2407 {
2408   location_t loc = gimple_location (stmt);
2409   switch (gimple_code (stmt))
2410     {
2411     case GIMPLE_ASSIGN:
2412       {
2413         enum tree_code subcode = gimple_assign_rhs_code (stmt);
2414
2415         switch (get_gimple_rhs_class (subcode))
2416           {
2417           case GIMPLE_SINGLE_RHS:
2418             {
2419               tree rhs = gimple_assign_rhs1 (stmt);
2420               enum tree_code_class kind = TREE_CODE_CLASS (subcode);
2421
2422               if (TREE_CODE (rhs) == SSA_NAME)
2423                 {
2424                   /* If the RHS is an SSA_NAME, return its known constant value,
2425                      if any.  */
2426                   return (*valueize) (rhs);
2427                 }
2428               /* Handle propagating invariant addresses into address
2429                  operations.  */
2430               else if (TREE_CODE (rhs) == ADDR_EXPR
2431                        && !is_gimple_min_invariant (rhs))
2432                 {
2433                   HOST_WIDE_INT offset;
2434                   tree base;
2435                   base = get_addr_base_and_unit_offset_1 (TREE_OPERAND (rhs, 0),
2436                                                           &offset,
2437                                                           valueize);
2438                   if (base
2439                       && (CONSTANT_CLASS_P (base)
2440                           || decl_address_invariant_p (base)))
2441                     return build_invariant_address (TREE_TYPE (rhs),
2442                                                     base, offset);
2443                 }
2444               else if (TREE_CODE (rhs) == CONSTRUCTOR
2445                        && TREE_CODE (TREE_TYPE (rhs)) == VECTOR_TYPE
2446                        && (CONSTRUCTOR_NELTS (rhs)
2447                            == TYPE_VECTOR_SUBPARTS (TREE_TYPE (rhs))))
2448                 {
2449                   unsigned i;
2450                   tree val, list;
2451
2452                   list = NULL_TREE;
2453                   FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (rhs), i, val)
2454                     {
2455                       val = (*valueize) (val);
2456                       if (TREE_CODE (val) == INTEGER_CST
2457                           || TREE_CODE (val) == REAL_CST
2458                           || TREE_CODE (val) == FIXED_CST)
2459                         list = tree_cons (NULL_TREE, val, list);
2460                       else
2461                         return NULL_TREE;
2462                     }
2463
2464                   return build_vector (TREE_TYPE (rhs), nreverse (list));
2465                 }
2466
2467               if (kind == tcc_reference)
2468                 {
2469                   if ((TREE_CODE (rhs) == VIEW_CONVERT_EXPR
2470                        || TREE_CODE (rhs) == REALPART_EXPR
2471                        || TREE_CODE (rhs) == IMAGPART_EXPR)
2472                       && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
2473                     {
2474                       tree val = (*valueize) (TREE_OPERAND (rhs, 0));
2475                       return fold_unary_loc (EXPR_LOCATION (rhs),
2476                                              TREE_CODE (rhs),
2477                                              TREE_TYPE (rhs), val);
2478                     }
2479                   else if (TREE_CODE (rhs) == BIT_FIELD_REF
2480                            && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
2481                     {
2482                       tree val = (*valueize) (TREE_OPERAND (rhs, 0));
2483                       return fold_ternary_loc (EXPR_LOCATION (rhs),
2484                                                TREE_CODE (rhs),
2485                                                TREE_TYPE (rhs), val,
2486                                                TREE_OPERAND (rhs, 1),
2487                                                TREE_OPERAND (rhs, 2));
2488                     }
2489                   else if (TREE_CODE (rhs) == MEM_REF
2490                            && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
2491                     {
2492                       tree val = (*valueize) (TREE_OPERAND (rhs, 0));
2493                       if (TREE_CODE (val) == ADDR_EXPR
2494                           && is_gimple_min_invariant (val))
2495                         {
2496                           tree tem = fold_build2 (MEM_REF, TREE_TYPE (rhs),
2497                                                   unshare_expr (val),
2498                                                   TREE_OPERAND (rhs, 1));
2499                           if (tem)
2500                             rhs = tem;
2501                         }
2502                     }
2503                   return fold_const_aggregate_ref_1 (rhs, valueize);
2504                 }
2505               else if (kind == tcc_declaration)
2506                 return get_symbol_constant_value (rhs);
2507               return rhs;
2508             }
2509
2510           case GIMPLE_UNARY_RHS:
2511             {
2512               /* Handle unary operators that can appear in GIMPLE form.
2513                  Note that we know the single operand must be a constant,
2514                  so this should almost always return a simplified RHS.  */
2515               tree lhs = gimple_assign_lhs (stmt);
2516               tree op0 = (*valueize) (gimple_assign_rhs1 (stmt));
2517
2518               /* Conversions are useless for CCP purposes if they are
2519                  value-preserving.  Thus the restrictions that
2520                  useless_type_conversion_p places for restrict qualification
2521                  of pointer types should not apply here.
2522                  Substitution later will only substitute to allowed places.  */
2523               if (CONVERT_EXPR_CODE_P (subcode)
2524                   && POINTER_TYPE_P (TREE_TYPE (lhs))
2525                   && POINTER_TYPE_P (TREE_TYPE (op0))
2526                   && TYPE_ADDR_SPACE (TREE_TYPE (lhs))
2527                      == TYPE_ADDR_SPACE (TREE_TYPE (op0))
2528                   && TYPE_MODE (TREE_TYPE (lhs))
2529                      == TYPE_MODE (TREE_TYPE (op0)))
2530                 return op0;
2531
2532               return
2533                 fold_unary_ignore_overflow_loc (loc, subcode,
2534                                                 gimple_expr_type (stmt), op0);
2535             }
2536
2537           case GIMPLE_BINARY_RHS:
2538             {
2539               /* Handle binary operators that can appear in GIMPLE form.  */
2540               tree op0 = (*valueize) (gimple_assign_rhs1 (stmt));
2541               tree op1 = (*valueize) (gimple_assign_rhs2 (stmt));
2542
2543               /* Translate &x + CST into an invariant form suitable for
2544                  further propagation.  */
2545               if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR
2546                   && TREE_CODE (op0) == ADDR_EXPR
2547                   && TREE_CODE (op1) == INTEGER_CST)
2548                 {
2549                   tree off = fold_convert (ptr_type_node, op1);
2550                   return build_fold_addr_expr_loc
2551                            (loc,
2552                             fold_build2 (MEM_REF,
2553                                          TREE_TYPE (TREE_TYPE (op0)),
2554                                          unshare_expr (op0), off));
2555                 }
2556
2557               return fold_binary_loc (loc, subcode,
2558                                       gimple_expr_type (stmt), op0, op1);
2559             }
2560
2561           case GIMPLE_TERNARY_RHS:
2562             {
2563               /* Handle ternary operators that can appear in GIMPLE form.  */
2564               tree op0 = (*valueize) (gimple_assign_rhs1 (stmt));
2565               tree op1 = (*valueize) (gimple_assign_rhs2 (stmt));
2566               tree op2 = (*valueize) (gimple_assign_rhs3 (stmt));
2567
2568               /* Fold embedded expressions in ternary codes.  */
2569               if ((subcode == COND_EXPR
2570                    || subcode == VEC_COND_EXPR)
2571                   && COMPARISON_CLASS_P (op0))
2572                 {
2573                   tree op00 = (*valueize) (TREE_OPERAND (op0, 0));
2574                   tree op01 = (*valueize) (TREE_OPERAND (op0, 1));
2575                   tree tem = fold_binary_loc (loc, TREE_CODE (op0),
2576                                               TREE_TYPE (op0), op00, op01);
2577                   if (tem)
2578                     op0 = tem;
2579                 }
2580
2581               return fold_ternary_loc (loc, subcode,
2582                                        gimple_expr_type (stmt), op0, op1, op2);
2583             }
2584
2585           default:
2586             gcc_unreachable ();
2587           }
2588       }
2589
2590     case GIMPLE_CALL:
2591       {
2592         tree fn;
2593
2594         if (gimple_call_internal_p (stmt))
2595           /* No folding yet for these functions.  */
2596           return NULL_TREE;
2597
2598         fn = (*valueize) (gimple_call_fn (stmt));
2599         if (TREE_CODE (fn) == ADDR_EXPR
2600             && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL
2601             && DECL_BUILT_IN (TREE_OPERAND (fn, 0)))
2602           {
2603             tree *args = XALLOCAVEC (tree, gimple_call_num_args (stmt));
2604             tree call, retval;
2605             unsigned i;
2606             for (i = 0; i < gimple_call_num_args (stmt); ++i)
2607               args[i] = (*valueize) (gimple_call_arg (stmt, i));
2608             call = build_call_array_loc (loc,
2609                                          gimple_call_return_type (stmt),
2610                                          fn, gimple_call_num_args (stmt), args);
2611             retval = fold_call_expr (EXPR_LOCATION (call), call, false);
2612             if (retval)
2613               /* fold_call_expr wraps the result inside a NOP_EXPR.  */
2614               STRIP_NOPS (retval);
2615             return retval;
2616           }
2617         return NULL_TREE;
2618       }
2619
2620     default:
2621       return NULL_TREE;
2622     }
2623 }
2624
2625 /* Fold STMT to a constant using VALUEIZE to valueize SSA names.
2626    Returns NULL_TREE if folding to a constant is not possible, otherwise
2627    returns a constant according to is_gimple_min_invariant.  */
2628
2629 tree
2630 gimple_fold_stmt_to_constant (gimple stmt, tree (*valueize) (tree))
2631 {
2632   tree res = gimple_fold_stmt_to_constant_1 (stmt, valueize);
2633   if (res && is_gimple_min_invariant (res))
2634     return res;
2635   return NULL_TREE;
2636 }
2637
2638
2639 /* The following set of functions are supposed to fold references using
2640    their constant initializers.  */
2641
2642 static tree fold_ctor_reference (tree type, tree ctor,
2643                                  unsigned HOST_WIDE_INT offset,
2644                                  unsigned HOST_WIDE_INT size);
2645
2646 /* See if we can find constructor defining value of BASE.
2647    When we know the consructor with constant offset (such as
2648    base is array[40] and we do know constructor of array), then
2649    BIT_OFFSET is adjusted accordingly.
2650
2651    As a special case, return error_mark_node when constructor
2652    is not explicitly available, but it is known to be zero
2653    such as 'static const int a;'.  */
2654 static tree
2655 get_base_constructor (tree base, HOST_WIDE_INT *bit_offset,
2656                       tree (*valueize)(tree))
2657 {
2658   HOST_WIDE_INT bit_offset2, size, max_size;
2659   if (TREE_CODE (base) == MEM_REF)
2660     {
2661       if (!integer_zerop (TREE_OPERAND (base, 1)))
2662         {
2663           if (!host_integerp (TREE_OPERAND (base, 1), 0))
2664             return NULL_TREE;
2665           *bit_offset += (mem_ref_offset (base).low
2666                           * BITS_PER_UNIT);
2667         }
2668
2669       if (valueize
2670           && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
2671         base = valueize (TREE_OPERAND (base, 0));
2672       if (!base || TREE_CODE (base) != ADDR_EXPR)
2673         return NULL_TREE;
2674       base = TREE_OPERAND (base, 0);
2675     }
2676
2677   /* Get a CONSTRUCTOR.  If BASE is a VAR_DECL, get its
2678      DECL_INITIAL.  If BASE is a nested reference into another
2679      ARRAY_REF or COMPONENT_REF, make a recursive call to resolve
2680      the inner reference.  */
2681   switch (TREE_CODE (base))
2682     {
2683     case VAR_DECL:
2684       if (!const_value_known_p (base))
2685         return NULL_TREE;
2686
2687       /* Fallthru.  */
2688     case CONST_DECL:
2689       if (!DECL_INITIAL (base)
2690           && (TREE_STATIC (base) || DECL_EXTERNAL (base)))
2691         return error_mark_node;
2692       return DECL_INITIAL (base);
2693
2694     case ARRAY_REF:
2695     case COMPONENT_REF:
2696       base = get_ref_base_and_extent (base, &bit_offset2, &size, &max_size);
2697       if (max_size == -1 || size != max_size)
2698         return NULL_TREE;
2699       *bit_offset +=  bit_offset2;
2700       return get_base_constructor (base, bit_offset, valueize);
2701
2702     case STRING_CST:
2703     case CONSTRUCTOR:
2704       return base;
2705
2706     default:
2707       return NULL_TREE;
2708     }
2709 }
2710
2711 /* CTOR is STRING_CST.  Fold reference of type TYPE and size SIZE
2712    to the memory at bit OFFSET.
2713
2714    We do only simple job of folding byte accesses.  */
2715
2716 static tree
2717 fold_string_cst_ctor_reference (tree type, tree ctor,
2718                                 unsigned HOST_WIDE_INT offset,
2719                                 unsigned HOST_WIDE_INT size)
2720 {
2721   if (INTEGRAL_TYPE_P (type)
2722       && (TYPE_MODE (type)
2723           == TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
2724       && (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
2725           == MODE_INT)
2726       && GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor)))) == 1
2727       && size == BITS_PER_UNIT
2728       && !(offset % BITS_PER_UNIT))
2729     {
2730       offset /= BITS_PER_UNIT;
2731       if (offset < (unsigned HOST_WIDE_INT) TREE_STRING_LENGTH (ctor))
2732         return build_int_cst_type (type, (TREE_STRING_POINTER (ctor)
2733                                    [offset]));
2734       /* Folding
2735          const char a[20]="hello";
2736          return a[10];
2737
2738          might lead to offset greater than string length.  In this case we
2739          know value is either initialized to 0 or out of bounds.  Return 0
2740          in both cases.  */
2741       return build_zero_cst (type);
2742     }
2743   return NULL_TREE;
2744 }
2745
2746 /* CTOR is CONSTRUCTOR of an array type.  Fold reference of type TYPE and size
2747    SIZE to the memory at bit OFFSET.  */
2748
2749 static tree
2750 fold_array_ctor_reference (tree type, tree ctor,
2751                            unsigned HOST_WIDE_INT offset,
2752                            unsigned HOST_WIDE_INT size)
2753 {
2754   unsigned HOST_WIDE_INT cnt;
2755   tree cfield, cval;
2756   double_int low_bound, elt_size;
2757   double_int index, max_index;
2758   double_int access_index;
2759   tree domain_type = NULL_TREE;
2760   HOST_WIDE_INT inner_offset;
2761
2762   /* Compute low bound and elt size.  */
2763   if (TREE_CODE (TREE_TYPE (ctor)) == ARRAY_TYPE)
2764     domain_type = TYPE_DOMAIN (TREE_TYPE (ctor));
2765   if (domain_type && TYPE_MIN_VALUE (domain_type))
2766     {
2767       /* Static constructors for variably sized objects makes no sense.  */
2768       gcc_assert (TREE_CODE (TYPE_MIN_VALUE (domain_type)) == INTEGER_CST);
2769       low_bound = tree_to_double_int (TYPE_MIN_VALUE (domain_type));
2770     }
2771   else
2772     low_bound = double_int_zero;
2773   /* Static constructors for variably sized objects makes no sense.  */
2774   gcc_assert (TREE_CODE(TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (ctor))))
2775               == INTEGER_CST);
2776   elt_size =
2777     tree_to_double_int (TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (ctor))));
2778
2779
2780   /* We can handle only constantly sized accesses that are known to not
2781      be larger than size of array element.  */
2782   if (!TYPE_SIZE_UNIT (type)
2783       || TREE_CODE (TYPE_SIZE_UNIT (type)) != INTEGER_CST
2784       || double_int_cmp (elt_size,
2785                          tree_to_double_int (TYPE_SIZE_UNIT (type)), 0) < 0)
2786     return NULL_TREE;
2787
2788   /* Compute the array index we look for.  */
2789   access_index = double_int_udiv (uhwi_to_double_int (offset / BITS_PER_UNIT),
2790                                   elt_size, TRUNC_DIV_EXPR);
2791   access_index = double_int_add (access_index, low_bound);
2792
2793   /* And offset within the access.  */
2794   inner_offset = offset % (double_int_to_uhwi (elt_size) * BITS_PER_UNIT);
2795
2796   /* See if the array field is large enough to span whole access.  We do not
2797      care to fold accesses spanning multiple array indexes.  */
2798   if (inner_offset + size > double_int_to_uhwi (elt_size) * BITS_PER_UNIT)
2799     return NULL_TREE;
2800
2801   index = double_int_sub (low_bound, double_int_one);
2802   FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
2803     {
2804       /* Array constructor might explicitely set index, or specify range
2805          or leave index NULL meaning that it is next index after previous
2806          one.  */
2807       if (cfield)
2808         {
2809           if (TREE_CODE (cfield) == INTEGER_CST)
2810             max_index = index = tree_to_double_int (cfield);
2811           else
2812             {
2813               gcc_assert (TREE_CODE (cfield) == RANGE_EXPR);
2814               index = tree_to_double_int (TREE_OPERAND (cfield, 0));
2815               max_index = tree_to_double_int (TREE_OPERAND (cfield, 1));
2816             }
2817         }
2818       else
2819         max_index = index = double_int_add (index, double_int_one);
2820
2821       /* Do we have match?  */
2822       if (double_int_cmp (access_index, index, 1) >= 0
2823           && double_int_cmp (access_index, max_index, 1) <= 0)
2824         return fold_ctor_reference (type, cval, inner_offset, size);
2825     }
2826   /* When memory is not explicitely mentioned in constructor,
2827      it is 0 (or out of range).  */
2828   return build_zero_cst (type);
2829 }
2830
2831 /* CTOR is CONSTRUCTOR of an aggregate or vector.
2832    Fold reference of type TYPE and size SIZE to the memory at bit OFFSET.  */
2833
2834 static tree
2835 fold_nonarray_ctor_reference (tree type, tree ctor,
2836                               unsigned HOST_WIDE_INT offset,
2837                               unsigned HOST_WIDE_INT size)
2838 {
2839   unsigned HOST_WIDE_INT cnt;
2840   tree cfield, cval;
2841
2842   FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield,
2843                             cval)
2844     {
2845       tree byte_offset = DECL_FIELD_OFFSET (cfield);
2846       tree field_offset = DECL_FIELD_BIT_OFFSET (cfield);
2847       tree field_size = DECL_SIZE (cfield);
2848       double_int bitoffset;
2849       double_int byte_offset_cst = tree_to_double_int (byte_offset);
2850       double_int bits_per_unit_cst = uhwi_to_double_int (BITS_PER_UNIT);
2851       double_int bitoffset_end, access_end;
2852
2853       /* Variable sized objects in static constructors makes no sense,
2854          but field_size can be NULL for flexible array members.  */
2855       gcc_assert (TREE_CODE (field_offset) == INTEGER_CST
2856                   && TREE_CODE (byte_offset) == INTEGER_CST
2857                   && (field_size != NULL_TREE
2858                       ? TREE_CODE (field_size) == INTEGER_CST
2859                       : TREE_CODE (TREE_TYPE (cfield)) == ARRAY_TYPE));
2860
2861       /* Compute bit offset of the field.  */
2862       bitoffset = double_int_add (tree_to_double_int (field_offset),
2863                                   double_int_mul (byte_offset_cst,
2864                                                   bits_per_unit_cst));
2865       /* Compute bit offset where the field ends.  */
2866       if (field_size != NULL_TREE)
2867         bitoffset_end = double_int_add (bitoffset,
2868                                         tree_to_double_int (field_size));
2869       else
2870         bitoffset_end = double_int_zero;
2871
2872       access_end = double_int_add (uhwi_to_double_int (offset),
2873                                    uhwi_to_double_int (size));
2874
2875       /* Is there any overlap between [OFFSET, OFFSET+SIZE) and
2876          [BITOFFSET, BITOFFSET_END)?  */
2877       if (double_int_cmp (access_end, bitoffset, 0) > 0
2878           && (field_size == NULL_TREE
2879               || double_int_cmp (uhwi_to_double_int (offset),
2880                                  bitoffset_end, 0) < 0))
2881         {
2882           double_int inner_offset = double_int_sub (uhwi_to_double_int (offset),
2883                                                     bitoffset);
2884           /* We do have overlap.  Now see if field is large enough to
2885              cover the access.  Give up for accesses spanning multiple
2886              fields.  */
2887           if (double_int_cmp (access_end, bitoffset_end, 0) > 0)
2888             return NULL_TREE;
2889           if (double_int_cmp (uhwi_to_double_int (offset), bitoffset, 0) < 0)
2890             return NULL_TREE;
2891           return fold_ctor_reference (type, cval,
2892                                       double_int_to_uhwi (inner_offset), size);
2893         }
2894     }
2895   /* When memory is not explicitely mentioned in constructor, it is 0.  */
2896   return build_zero_cst (type);
2897 }
2898
2899 /* CTOR is value initializing memory, fold reference of type TYPE and size SIZE
2900    to the memory at bit OFFSET.  */
2901
2902 static tree
2903 fold_ctor_reference (tree type, tree ctor, unsigned HOST_WIDE_INT offset,
2904                      unsigned HOST_WIDE_INT size)
2905 {
2906   tree ret;
2907
2908   /* We found the field with exact match.  */
2909   if (useless_type_conversion_p (type, TREE_TYPE (ctor))
2910       && !offset)
2911     return canonicalize_constructor_val (ctor);
2912
2913   /* We are at the end of walk, see if we can view convert the
2914      result.  */
2915   if (!AGGREGATE_TYPE_P (TREE_TYPE (ctor)) && !offset
2916       /* VIEW_CONVERT_EXPR is defined only for matching sizes.  */
2917       && operand_equal_p (TYPE_SIZE (type),
2918                           TYPE_SIZE (TREE_TYPE (ctor)), 0))
2919     {
2920       ret = canonicalize_constructor_val (ctor);
2921       ret = fold_unary (VIEW_CONVERT_EXPR, type, ret);
2922       if (ret)
2923         STRIP_NOPS (ret);
2924       return ret;
2925     }
2926   if (TREE_CODE (ctor) == STRING_CST)
2927     return fold_string_cst_ctor_reference (type, ctor, offset, size);
2928   if (TREE_CODE (ctor) == CONSTRUCTOR)
2929     {
2930
2931       if (TREE_CODE (TREE_TYPE (ctor)) == ARRAY_TYPE
2932           || TREE_CODE (TREE_TYPE (ctor)) == VECTOR_TYPE)
2933         return fold_array_ctor_reference (type, ctor, offset, size);
2934       else
2935         return fold_nonarray_ctor_reference (type, ctor, offset, size);
2936     }
2937
2938   return NULL_TREE;
2939 }
2940
2941 /* Return the tree representing the element referenced by T if T is an
2942    ARRAY_REF or COMPONENT_REF into constant aggregates valuezing SSA
2943    names using VALUEIZE.  Return NULL_TREE otherwise.  */
2944
2945 tree
2946 fold_const_aggregate_ref_1 (tree t, tree (*valueize) (tree))
2947 {
2948   tree ctor, idx, base;
2949   HOST_WIDE_INT offset, size, max_size;
2950   tree tem;
2951
2952   if (TREE_THIS_VOLATILE (t))
2953     return NULL_TREE;
2954
2955   if (TREE_CODE_CLASS (TREE_CODE (t)) == tcc_declaration)
2956     return get_symbol_constant_value (t);
2957
2958   tem = fold_read_from_constant_string (t);
2959   if (tem)
2960     return tem;
2961
2962   switch (TREE_CODE (t))
2963     {
2964     case ARRAY_REF:
2965     case ARRAY_RANGE_REF:
2966       /* Constant indexes are handled well by get_base_constructor.
2967          Only special case variable offsets.
2968          FIXME: This code can't handle nested references with variable indexes
2969          (they will be handled only by iteration of ccp).  Perhaps we can bring
2970          get_ref_base_and_extent here and make it use a valueize callback.  */
2971       if (TREE_CODE (TREE_OPERAND (t, 1)) == SSA_NAME
2972           && valueize
2973           && (idx = (*valueize) (TREE_OPERAND (t, 1)))
2974           && host_integerp (idx, 0))
2975         {
2976           tree low_bound, unit_size;
2977
2978           /* If the resulting bit-offset is constant, track it.  */
2979           if ((low_bound = array_ref_low_bound (t),
2980                host_integerp (low_bound, 0))
2981               && (unit_size = array_ref_element_size (t),
2982                   host_integerp (unit_size, 1)))
2983             {
2984               offset = TREE_INT_CST_LOW (idx);
2985               offset -= TREE_INT_CST_LOW (low_bound);
2986               offset *= TREE_INT_CST_LOW (unit_size);
2987               offset *= BITS_PER_UNIT;
2988
2989               base = TREE_OPERAND (t, 0);
2990               ctor = get_base_constructor (base, &offset, valueize);
2991               /* Empty constructor.  Always fold to 0.  */
2992               if (ctor == error_mark_node)
2993                 return build_zero_cst (TREE_TYPE (t));
2994               /* Out of bound array access.  Value is undefined,
2995                  but don't fold.  */
2996               if (offset < 0)
2997                 return NULL_TREE;
2998               /* We can not determine ctor.  */
2999               if (!ctor)
3000                 return NULL_TREE;
3001               return fold_ctor_reference (TREE_TYPE (t), ctor, offset,
3002                                           TREE_INT_CST_LOW (unit_size)
3003                                           * BITS_PER_UNIT);
3004             }
3005         }
3006       /* Fallthru.  */
3007
3008     case COMPONENT_REF:
3009     case BIT_FIELD_REF:
3010     case TARGET_MEM_REF:
3011     case MEM_REF:
3012       base = get_ref_base_and_extent (t, &offset, &size, &max_size);
3013       ctor = get_base_constructor (base, &offset, valueize);
3014
3015       /* Empty constructor.  Always fold to 0.  */
3016       if (ctor == error_mark_node)
3017         return build_zero_cst (TREE_TYPE (t));
3018       /* We do not know precise address.  */
3019       if (max_size == -1 || max_size != size)
3020         return NULL_TREE;
3021       /* We can not determine ctor.  */
3022       if (!ctor)
3023         return NULL_TREE;
3024
3025       /* Out of bound array access.  Value is undefined, but don't fold.  */
3026       if (offset < 0)
3027         return NULL_TREE;
3028
3029       return fold_ctor_reference (TREE_TYPE (t), ctor, offset, size);
3030
3031     case REALPART_EXPR:
3032     case IMAGPART_EXPR:
3033       {
3034         tree c = fold_const_aggregate_ref_1 (TREE_OPERAND (t, 0), valueize);
3035         if (c && TREE_CODE (c) == COMPLEX_CST)
3036           return fold_build1_loc (EXPR_LOCATION (t),
3037                               TREE_CODE (t), TREE_TYPE (t), c);
3038         break;
3039       }
3040
3041     default:
3042       break;
3043     }
3044
3045   return NULL_TREE;
3046 }
3047
3048 tree
3049 fold_const_aggregate_ref (tree t)
3050 {
3051   return fold_const_aggregate_ref_1 (t, NULL);
3052 }
3053
3054 /* Return a declaration of a function which an OBJ_TYPE_REF references. TOKEN
3055    is integer form of OBJ_TYPE_REF_TOKEN of the reference expression.
3056    KNOWN_BINFO carries the binfo describing the true type of
3057    OBJ_TYPE_REF_OBJECT(REF).  */
3058
3059 tree
3060 gimple_get_virt_method_for_binfo (HOST_WIDE_INT token, tree known_binfo)
3061 {
3062   unsigned HOST_WIDE_INT offset, size;
3063   tree v, fn;
3064
3065   v = BINFO_VTABLE (known_binfo);
3066   /* If there is no virtual methods table, leave the OBJ_TYPE_REF alone.  */
3067   if (!v)
3068     return NULL_TREE;
3069
3070   if (TREE_CODE (v) == POINTER_PLUS_EXPR)
3071     {
3072       offset = tree_low_cst (TREE_OPERAND (v, 1), 1) * BITS_PER_UNIT;
3073       v = TREE_OPERAND (v, 0);
3074     }
3075   else
3076     offset = 0;
3077
3078   if (TREE_CODE (v) != ADDR_EXPR)
3079     return NULL_TREE;
3080   v = TREE_OPERAND (v, 0);
3081
3082   if (TREE_CODE (v) != VAR_DECL
3083       || !DECL_VIRTUAL_P (v)
3084       || !DECL_INITIAL (v)
3085       || DECL_INITIAL (v) == error_mark_node)
3086     return NULL_TREE;
3087   gcc_checking_assert (TREE_CODE (TREE_TYPE (v)) == ARRAY_TYPE);
3088   size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (v))), 1);
3089   offset += token * size;
3090   fn = fold_ctor_reference (TREE_TYPE (TREE_TYPE (v)), DECL_INITIAL (v),
3091                             offset, size);
3092   if (!fn)
3093     return NULL_TREE;
3094   gcc_assert (TREE_CODE (fn) == ADDR_EXPR
3095               || TREE_CODE (fn) == FDESC_EXPR);
3096   fn = TREE_OPERAND (fn, 0);
3097   gcc_assert (TREE_CODE (fn) == FUNCTION_DECL);
3098
3099   /* When cgraph node is missing and function is not public, we cannot
3100      devirtualize.  This can happen in WHOPR when the actual method
3101      ends up in other partition, because we found devirtualization
3102      possibility too late.  */
3103   if (!can_refer_decl_in_current_unit_p (fn))
3104     return NULL_TREE;
3105
3106   return fn;
3107 }
3108
3109 /* Return true iff VAL is a gimple expression that is known to be
3110    non-negative.  Restricted to floating-point inputs.  */
3111
3112 bool
3113 gimple_val_nonnegative_real_p (tree val)
3114 {
3115   gimple def_stmt;
3116
3117   gcc_assert (val && SCALAR_FLOAT_TYPE_P (TREE_TYPE (val)));
3118
3119   /* Use existing logic for non-gimple trees.  */
3120   if (tree_expr_nonnegative_p (val))
3121     return true;
3122
3123   if (TREE_CODE (val) != SSA_NAME)
3124     return false;
3125
3126   /* Currently we look only at the immediately defining statement
3127      to make this determination, since recursion on defining 
3128      statements of operands can lead to quadratic behavior in the
3129      worst case.  This is expected to catch almost all occurrences
3130      in practice.  It would be possible to implement limited-depth
3131      recursion if important cases are lost.  Alternatively, passes
3132      that need this information (such as the pow/powi lowering code
3133      in the cse_sincos pass) could be revised to provide it through
3134      dataflow propagation.  */
3135
3136   def_stmt = SSA_NAME_DEF_STMT (val);
3137
3138   if (is_gimple_assign (def_stmt))
3139     {
3140       tree op0, op1;
3141
3142       /* See fold-const.c:tree_expr_nonnegative_p for additional
3143          cases that could be handled with recursion.  */
3144
3145       switch (gimple_assign_rhs_code (def_stmt))
3146         {
3147         case ABS_EXPR:
3148           /* Always true for floating-point operands.  */
3149           return true;
3150
3151         case MULT_EXPR:
3152           /* True if the two operands are identical (since we are
3153              restricted to floating-point inputs).  */
3154           op0 = gimple_assign_rhs1 (def_stmt);
3155           op1 = gimple_assign_rhs2 (def_stmt);
3156
3157           if (op0 == op1
3158               || operand_equal_p (op0, op1, 0))
3159             return true;
3160
3161         default:
3162           return false;
3163         }
3164     }
3165   else if (is_gimple_call (def_stmt))
3166     {
3167       tree fndecl = gimple_call_fndecl (def_stmt);
3168       if (fndecl
3169           && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
3170         {
3171           tree arg1;
3172
3173           switch (DECL_FUNCTION_CODE (fndecl))
3174             {
3175             CASE_FLT_FN (BUILT_IN_ACOS):
3176             CASE_FLT_FN (BUILT_IN_ACOSH):
3177             CASE_FLT_FN (BUILT_IN_CABS):
3178             CASE_FLT_FN (BUILT_IN_COSH):
3179             CASE_FLT_FN (BUILT_IN_ERFC):
3180             CASE_FLT_FN (BUILT_IN_EXP):
3181             CASE_FLT_FN (BUILT_IN_EXP10):
3182             CASE_FLT_FN (BUILT_IN_EXP2):
3183             CASE_FLT_FN (BUILT_IN_FABS):
3184             CASE_FLT_FN (BUILT_IN_FDIM):
3185             CASE_FLT_FN (BUILT_IN_HYPOT):
3186             CASE_FLT_FN (BUILT_IN_POW10):
3187               return true;
3188
3189             CASE_FLT_FN (BUILT_IN_SQRT):
3190               /* sqrt(-0.0) is -0.0, and sqrt is not defined over other
3191                  nonnegative inputs.  */
3192               if (!HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (val))))
3193                 return true;
3194
3195               break;
3196
3197             CASE_FLT_FN (BUILT_IN_POWI):
3198               /* True if the second argument is an even integer.  */
3199               arg1 = gimple_call_arg (def_stmt, 1);
3200
3201               if (TREE_CODE (arg1) == INTEGER_CST
3202                   && (TREE_INT_CST_LOW (arg1) & 1) == 0)
3203                 return true;
3204
3205               break;
3206               
3207             CASE_FLT_FN (BUILT_IN_POW):
3208               /* True if the second argument is an even integer-valued
3209                  real.  */
3210               arg1 = gimple_call_arg (def_stmt, 1);
3211
3212               if (TREE_CODE (arg1) == REAL_CST)
3213                 {
3214                   REAL_VALUE_TYPE c;
3215                   HOST_WIDE_INT n;
3216
3217                   c = TREE_REAL_CST (arg1);
3218                   n = real_to_integer (&c);
3219
3220                   if ((n & 1) == 0)
3221                     {
3222                       REAL_VALUE_TYPE cint;
3223                       real_from_integer (&cint, VOIDmode, n, n < 0 ? -1 : 0, 0);
3224                       if (real_identical (&c, &cint))
3225                         return true;
3226                     }
3227                 }
3228
3229               break;
3230
3231             default:
3232               return false;
3233             }
3234         }
3235     }
3236
3237   return false;
3238 }