OSDN Git Service

PR tree-optimization/36129
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-ccp.c
1 /* Conditional constant propagation pass for the GNU compiler.
2    Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
3    Free Software Foundation, Inc.
4    Adapted from original RTL SSA-CCP by Daniel Berlin <dberlin@dberlin.org>
5    Adapted to GIMPLE trees by Diego Novillo <dnovillo@redhat.com>
6
7 This file is part of GCC.
8    
9 GCC is free software; you can redistribute it and/or modify it
10 under the terms of the GNU General Public License as published by the
11 Free Software Foundation; either version 3, or (at your option) any
12 later version.
13    
14 GCC is distributed in the hope that it will be useful, but WITHOUT
15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
17 for more details.
18    
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3.  If not see
21 <http://www.gnu.org/licenses/>.  */
22
23 /* Conditional constant propagation (CCP) is based on the SSA
24    propagation engine (tree-ssa-propagate.c).  Constant assignments of
25    the form VAR = CST are propagated from the assignments into uses of
26    VAR, which in turn may generate new constants.  The simulation uses
27    a four level lattice to keep track of constant values associated
28    with SSA names.  Given an SSA name V_i, it may take one of the
29    following values:
30
31         UNINITIALIZED   ->  the initial state of the value.  This value
32                             is replaced with a correct initial value
33                             the first time the value is used, so the
34                             rest of the pass does not need to care about
35                             it.  Using this value simplifies initialization
36                             of the pass, and prevents us from needlessly
37                             scanning statements that are never reached.
38
39         UNDEFINED       ->  V_i is a local variable whose definition
40                             has not been processed yet.  Therefore we
41                             don't yet know if its value is a constant
42                             or not.
43
44         CONSTANT        ->  V_i has been found to hold a constant
45                             value C.
46
47         VARYING         ->  V_i cannot take a constant value, or if it
48                             does, it is not possible to determine it
49                             at compile time.
50
51    The core of SSA-CCP is in ccp_visit_stmt and ccp_visit_phi_node:
52
53    1- In ccp_visit_stmt, we are interested in assignments whose RHS
54       evaluates into a constant and conditional jumps whose predicate
55       evaluates into a boolean true or false.  When an assignment of
56       the form V_i = CONST is found, V_i's lattice value is set to
57       CONSTANT and CONST is associated with it.  This causes the
58       propagation engine to add all the SSA edges coming out the
59       assignment into the worklists, so that statements that use V_i
60       can be visited.
61
62       If the statement is a conditional with a constant predicate, we
63       mark the outgoing edges as executable or not executable
64       depending on the predicate's value.  This is then used when
65       visiting PHI nodes to know when a PHI argument can be ignored.
66       
67
68    2- In ccp_visit_phi_node, if all the PHI arguments evaluate to the
69       same constant C, then the LHS of the PHI is set to C.  This
70       evaluation is known as the "meet operation".  Since one of the
71       goals of this evaluation is to optimistically return constant
72       values as often as possible, it uses two main short cuts:
73
74       - If an argument is flowing in through a non-executable edge, it
75         is ignored.  This is useful in cases like this:
76
77                         if (PRED)
78                           a_9 = 3;
79                         else
80                           a_10 = 100;
81                         a_11 = PHI (a_9, a_10)
82
83         If PRED is known to always evaluate to false, then we can
84         assume that a_11 will always take its value from a_10, meaning
85         that instead of consider it VARYING (a_9 and a_10 have
86         different values), we can consider it CONSTANT 100.
87
88       - If an argument has an UNDEFINED value, then it does not affect
89         the outcome of the meet operation.  If a variable V_i has an
90         UNDEFINED value, it means that either its defining statement
91         hasn't been visited yet or V_i has no defining statement, in
92         which case the original symbol 'V' is being used
93         uninitialized.  Since 'V' is a local variable, the compiler
94         may assume any initial value for it.
95
96
97    After propagation, every variable V_i that ends up with a lattice
98    value of CONSTANT will have the associated constant value in the
99    array CONST_VAL[i].VALUE.  That is fed into substitute_and_fold for
100    final substitution and folding.
101
102
103    Constant propagation in stores and loads (STORE-CCP)
104    ----------------------------------------------------
105
106    While CCP has all the logic to propagate constants in GIMPLE
107    registers, it is missing the ability to associate constants with
108    stores and loads (i.e., pointer dereferences, structures and
109    global/aliased variables).  We don't keep loads and stores in
110    SSA, but we do build a factored use-def web for them (in the
111    virtual operands).
112
113    For instance, consider the following code fragment:
114
115           struct A a;
116           const int B = 42;
117
118           void foo (int i)
119           {
120             if (i > 10)
121               a.a = 42;
122             else
123               {
124                 a.b = 21;
125                 a.a = a.b + 21;
126               }
127
128             if (a.a != B)
129               never_executed ();
130           }
131
132    We should be able to deduce that the predicate 'a.a != B' is always
133    false.  To achieve this, we associate constant values to the SSA
134    names in the VDEF operands for each store.  Additionally,
135    since we also glob partial loads/stores with the base symbol, we
136    also keep track of the memory reference where the constant value
137    was stored (in the MEM_REF field of PROP_VALUE_T).  For instance,
138
139         # a_5 = VDEF <a_4>
140         a.a = 2;
141
142         # VUSE <a_5>
143         x_3 = a.b;
144
145    In the example above, CCP will associate value '2' with 'a_5', but
146    it would be wrong to replace the load from 'a.b' with '2', because
147    '2' had been stored into a.a.
148
149    Note that the initial value of virtual operands is VARYING, not
150    UNDEFINED.  Consider, for instance global variables:
151
152         int A;
153
154         foo (int i)
155         {
156           if (i_3 > 10)
157             A_4 = 3;
158           # A_5 = PHI (A_4, A_2);
159
160           # VUSE <A_5>
161           A.0_6 = A;
162
163           return A.0_6;
164         }
165
166    The value of A_2 cannot be assumed to be UNDEFINED, as it may have
167    been defined outside of foo.  If we were to assume it UNDEFINED, we
168    would erroneously optimize the above into 'return 3;'.
169
170    Though STORE-CCP is not too expensive, it does have to do more work
171    than regular CCP, so it is only enabled at -O2.  Both regular CCP
172    and STORE-CCP use the exact same algorithm.  The only distinction
173    is that when doing STORE-CCP, the boolean variable DO_STORE_CCP is
174    set to true.  This affects the evaluation of statements and PHI
175    nodes.
176
177    References:
178
179      Constant propagation with conditional branches,
180      Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
181
182      Building an Optimizing Compiler,
183      Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
184
185      Advanced Compiler Design and Implementation,
186      Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6  */
187
188 #include "config.h"
189 #include "system.h"
190 #include "coretypes.h"
191 #include "tm.h"
192 #include "tree.h"
193 #include "flags.h"
194 #include "rtl.h"
195 #include "tm_p.h"
196 #include "ggc.h"
197 #include "basic-block.h"
198 #include "output.h"
199 #include "expr.h"
200 #include "function.h"
201 #include "diagnostic.h"
202 #include "timevar.h"
203 #include "tree-dump.h"
204 #include "tree-flow.h"
205 #include "tree-pass.h"
206 #include "tree-ssa-propagate.h"
207 #include "value-prof.h"
208 #include "langhooks.h"
209 #include "target.h"
210 #include "toplev.h"
211
212
213 /* Possible lattice values.  */
214 typedef enum
215 {
216   UNINITIALIZED,
217   UNDEFINED,
218   CONSTANT,
219   VARYING
220 } ccp_lattice_t;
221
222 /* Array of propagated constant values.  After propagation,
223    CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I).  If
224    the constant is held in an SSA name representing a memory store
225    (i.e., a VDEF), CONST_VAL[I].MEM_REF will contain the actual
226    memory reference used to store (i.e., the LHS of the assignment
227    doing the store).  */
228 static prop_value_t *const_val;
229
230 /* True if we are also propagating constants in stores and loads.  */
231 static bool do_store_ccp;
232
233 /* Dump constant propagation value VAL to file OUTF prefixed by PREFIX.  */
234
235 static void
236 dump_lattice_value (FILE *outf, const char *prefix, prop_value_t val)
237 {
238   switch (val.lattice_val)
239     {
240     case UNINITIALIZED:
241       fprintf (outf, "%sUNINITIALIZED", prefix);
242       break;
243     case UNDEFINED:
244       fprintf (outf, "%sUNDEFINED", prefix);
245       break;
246     case VARYING:
247       fprintf (outf, "%sVARYING", prefix);
248       break;
249     case CONSTANT:
250       fprintf (outf, "%sCONSTANT ", prefix);
251       print_generic_expr (outf, val.value, dump_flags);
252       break;
253     default:
254       gcc_unreachable ();
255     }
256 }
257
258
259 /* Print lattice value VAL to stderr.  */
260
261 void debug_lattice_value (prop_value_t val);
262
263 void
264 debug_lattice_value (prop_value_t val)
265 {
266   dump_lattice_value (stderr, "", val);
267   fprintf (stderr, "\n");
268 }
269
270
271 /* If SYM is a constant variable with known value, return the value.
272    NULL_TREE is returned otherwise.  */
273
274 tree
275 get_symbol_constant_value (tree sym)
276 {
277   if (TREE_STATIC (sym)
278       && TREE_READONLY (sym)
279       && !MTAG_P (sym))
280     {
281       tree val = DECL_INITIAL (sym);
282       if (val)
283         {
284           STRIP_USELESS_TYPE_CONVERSION (val);
285           if (is_gimple_min_invariant (val))
286             return val;
287         }
288       /* Variables declared 'const' without an initializer
289          have zero as the intializer if they may not be
290          overridden at link or run time.  */
291       if (!val
292           && targetm.binds_local_p (sym)
293           && (INTEGRAL_TYPE_P (TREE_TYPE (sym))
294                || SCALAR_FLOAT_TYPE_P (TREE_TYPE (sym))))
295         return fold_convert (TREE_TYPE (sym), integer_zero_node);
296     }
297
298   return NULL_TREE;
299 }
300
301 /* Compute a default value for variable VAR and store it in the
302    CONST_VAL array.  The following rules are used to get default
303    values:
304
305    1- Global and static variables that are declared constant are
306       considered CONSTANT.
307
308    2- Any other value is considered UNDEFINED.  This is useful when
309       considering PHI nodes.  PHI arguments that are undefined do not
310       change the constant value of the PHI node, which allows for more
311       constants to be propagated.
312
313    3- If SSA_NAME_VALUE is set and it is a constant, its value is
314       used.
315
316    4- Variables defined by statements other than assignments and PHI
317       nodes are considered VARYING.
318
319    5- Initial values of variables that are not GIMPLE registers are
320       considered VARYING.  */
321
322 static prop_value_t
323 get_default_value (tree var)
324 {
325   tree sym = SSA_NAME_VAR (var);
326   prop_value_t val = { UNINITIALIZED, NULL_TREE, NULL_TREE };
327   tree cst_val;
328   
329   if (!do_store_ccp && !is_gimple_reg (var))
330     {
331       /* Short circuit for regular CCP.  We are not interested in any
332          non-register when DO_STORE_CCP is false.  */
333       val.lattice_val = VARYING;
334     }
335   else if (SSA_NAME_VALUE (var)
336            && is_gimple_min_invariant (SSA_NAME_VALUE (var)))
337     {
338       val.lattice_val = CONSTANT;
339       val.value = SSA_NAME_VALUE (var);
340     }
341   else if ((cst_val = get_symbol_constant_value (sym)) != NULL_TREE)
342     {
343       /* Globals and static variables declared 'const' take their
344          initial value.  */
345       val.lattice_val = CONSTANT;
346       val.value = cst_val;
347       val.mem_ref = sym;
348     }
349   else
350     {
351       tree stmt = SSA_NAME_DEF_STMT (var);
352
353       if (IS_EMPTY_STMT (stmt))
354         {
355           /* Variables defined by an empty statement are those used
356              before being initialized.  If VAR is a local variable, we
357              can assume initially that it is UNDEFINED, otherwise we must
358              consider it VARYING.  */
359           if (is_gimple_reg (sym) && TREE_CODE (sym) != PARM_DECL)
360             val.lattice_val = UNDEFINED;
361           else
362             val.lattice_val = VARYING;
363         }
364       else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
365                || TREE_CODE (stmt) == PHI_NODE)
366         {
367           /* Any other variable defined by an assignment or a PHI node
368              is considered UNDEFINED.  */
369           val.lattice_val = UNDEFINED;
370         }
371       else
372         {
373           /* Otherwise, VAR will never take on a constant value.  */
374           val.lattice_val = VARYING;
375         }
376     }
377
378   return val;
379 }
380
381
382 /* Get the constant value associated with variable VAR.  */
383
384 static inline prop_value_t *
385 get_value (tree var)
386 {
387   prop_value_t *val;
388
389   if (const_val == NULL)
390     return NULL;
391
392   val = &const_val[SSA_NAME_VERSION (var)];
393   if (val->lattice_val == UNINITIALIZED)
394     *val = get_default_value (var);
395
396   return val;
397 }
398
399 /* Sets the value associated with VAR to VARYING.  */
400
401 static inline void
402 set_value_varying (tree var)
403 {
404   prop_value_t *val = &const_val[SSA_NAME_VERSION (var)];
405
406   val->lattice_val = VARYING;
407   val->value = NULL_TREE;
408   val->mem_ref = NULL_TREE;
409 }
410
411 /* For float types, modify the value of VAL to make ccp work correctly
412    for non-standard values (-0, NaN):
413
414    If HONOR_SIGNED_ZEROS is false, and VAL = -0, we canonicalize it to 0.
415    If HONOR_NANS is false, and VAL is NaN, we canonicalize it to UNDEFINED.
416      This is to fix the following problem (see PR 29921): Suppose we have
417
418      x = 0.0 * y
419
420      and we set value of y to NaN.  This causes value of x to be set to NaN.
421      When we later determine that y is in fact VARYING, fold uses the fact
422      that HONOR_NANS is false, and we try to change the value of x to 0,
423      causing an ICE.  With HONOR_NANS being false, the real appearance of
424      NaN would cause undefined behavior, though, so claiming that y (and x)
425      are UNDEFINED initially is correct.  */
426
427 static void
428 canonicalize_float_value (prop_value_t *val)
429 {
430   enum machine_mode mode;
431   tree type;
432   REAL_VALUE_TYPE d;
433
434   if (val->lattice_val != CONSTANT
435       || TREE_CODE (val->value) != REAL_CST)
436     return;
437
438   d = TREE_REAL_CST (val->value);
439   type = TREE_TYPE (val->value);
440   mode = TYPE_MODE (type);
441
442   if (!HONOR_SIGNED_ZEROS (mode)
443       && REAL_VALUE_MINUS_ZERO (d))
444     {
445       val->value = build_real (type, dconst0);
446       return;
447     }
448
449   if (!HONOR_NANS (mode)
450       && REAL_VALUE_ISNAN (d))
451     {
452       val->lattice_val = UNDEFINED;
453       val->value = NULL;
454       val->mem_ref = NULL;
455       return;
456     }
457 }
458
459 /* Set the value for variable VAR to NEW_VAL.  Return true if the new
460    value is different from VAR's previous value.  */
461
462 static bool
463 set_lattice_value (tree var, prop_value_t new_val)
464 {
465   prop_value_t *old_val = get_value (var);
466
467   canonicalize_float_value (&new_val);
468
469   /* Lattice transitions must always be monotonically increasing in
470      value.  If *OLD_VAL and NEW_VAL are the same, return false to
471      inform the caller that this was a non-transition.  */
472
473   gcc_assert (old_val->lattice_val < new_val.lattice_val
474               || (old_val->lattice_val == new_val.lattice_val
475                   && ((!old_val->value && !new_val.value)
476                       || operand_equal_p (old_val->value, new_val.value, 0))
477                   && old_val->mem_ref == new_val.mem_ref));
478
479   if (old_val->lattice_val != new_val.lattice_val)
480     {
481       if (dump_file && (dump_flags & TDF_DETAILS))
482         {
483           dump_lattice_value (dump_file, "Lattice value changed to ", new_val);
484           fprintf (dump_file, ".  Adding SSA edges to worklist.\n");
485         }
486
487       *old_val = new_val;
488
489       gcc_assert (new_val.lattice_val != UNDEFINED);
490       return true;
491     }
492
493   return false;
494 }
495
496
497 /* Return the likely CCP lattice value for STMT.
498
499    If STMT has no operands, then return CONSTANT.
500
501    Else if undefinedness of operands of STMT cause its value to be
502    undefined, then return UNDEFINED.
503
504    Else if any operands of STMT are constants, then return CONSTANT.
505
506    Else return VARYING.  */
507
508 static ccp_lattice_t
509 likely_value (tree stmt)
510 {
511   bool has_constant_operand, has_undefined_operand, all_undefined_operands;
512   stmt_ann_t ann;
513   tree use;
514   ssa_op_iter iter;
515
516   ann = stmt_ann (stmt);
517
518   /* If the statement has volatile operands, it won't fold to a
519      constant value.  */
520   if (ann->has_volatile_ops)
521     return VARYING;
522
523   /* If we are not doing store-ccp, statements with loads
524      and/or stores will never fold into a constant.  */
525   if (!do_store_ccp
526       && !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
527     return VARYING;
528
529
530   /* A CALL_EXPR is assumed to be varying.  NOTE: This may be overly
531      conservative, in the presence of const and pure calls.  */
532   if (get_call_expr_in (stmt) != NULL_TREE)
533     return VARYING;
534
535   /* Anything other than assignments and conditional jumps are not
536      interesting for CCP.  */
537   if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT
538       && !(TREE_CODE (stmt) == RETURN_EXPR && get_rhs (stmt) != NULL_TREE)
539       && TREE_CODE (stmt) != COND_EXPR
540       && TREE_CODE (stmt) != SWITCH_EXPR)
541     return VARYING;
542
543   if (is_gimple_min_invariant (get_rhs (stmt)))
544     return CONSTANT;
545
546   has_constant_operand = false;
547   has_undefined_operand = false;
548   all_undefined_operands = true;
549   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
550     {
551       prop_value_t *val = get_value (use);
552
553       if (val->lattice_val == UNDEFINED)
554         has_undefined_operand = true;
555       else
556         all_undefined_operands = false;
557
558       if (val->lattice_val == CONSTANT)
559         has_constant_operand = true;
560     }
561
562   /* If the operation combines operands like COMPLEX_EXPR make sure to
563      not mark the result UNDEFINED if only one part of the result is
564      undefined.  */
565   if (has_undefined_operand
566       && all_undefined_operands)
567     return UNDEFINED;
568   else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
569            && has_undefined_operand)
570     {
571       switch (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)))
572         {
573         /* Unary operators are handled with all_undefined_operands.  */
574         case PLUS_EXPR:
575         case MINUS_EXPR:
576         case POINTER_PLUS_EXPR:
577           /* Not MIN_EXPR, MAX_EXPR.  One VARYING operand may be selected.
578              Not bitwise operators, one VARYING operand may specify the
579              result completely.  Not logical operators for the same reason.
580              Not COMPLEX_EXPR as one VARYING operand makes the result partly
581              not UNDEFINED.  Not *DIV_EXPR, comparisons and shifts because
582              the undefined operand may be promoted.  */
583           return UNDEFINED;
584
585         default:
586           ;
587         }
588     }
589   /* If there was an UNDEFINED operand but the result may be not UNDEFINED
590      fall back to VARYING even if there were CONSTANT operands.  */
591   if (has_undefined_operand)
592     return VARYING;
593
594   if (has_constant_operand
595       /* We do not consider virtual operands here -- load from read-only
596          memory may have only VARYING virtual operands, but still be
597          constant.  */
598       || ZERO_SSA_OPERANDS (stmt, SSA_OP_USE))
599     return CONSTANT;
600
601   return VARYING;
602 }
603
604 /* Returns true if STMT cannot be constant.  */
605
606 static bool
607 surely_varying_stmt_p (tree stmt)
608 {
609   /* If the statement has operands that we cannot handle, it cannot be
610      constant.  */
611   if (stmt_ann (stmt)->has_volatile_ops)
612     return true;
613
614   if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
615     {
616       if (!do_store_ccp)
617         return true;
618
619       /* We can only handle simple loads and stores.  */
620       if (!stmt_makes_single_load (stmt)
621           && !stmt_makes_single_store (stmt))
622         return true;
623     }
624
625   /* If it contains a call, it is varying.  */
626   if (get_call_expr_in (stmt) != NULL_TREE)
627     return true;
628
629   /* Anything other than assignments and conditional jumps are not
630      interesting for CCP.  */
631   if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT
632       && !(TREE_CODE (stmt) == RETURN_EXPR && get_rhs (stmt) != NULL_TREE)
633       && TREE_CODE (stmt) != COND_EXPR
634       && TREE_CODE (stmt) != SWITCH_EXPR)
635     return true;
636
637   return false;
638 }
639
640 /* Initialize local data structures for CCP.  */
641
642 static void
643 ccp_initialize (void)
644 {
645   basic_block bb;
646
647   const_val = XCNEWVEC (prop_value_t, num_ssa_names);
648
649   /* Initialize simulation flags for PHI nodes and statements.  */
650   FOR_EACH_BB (bb)
651     {
652       block_stmt_iterator i;
653
654       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
655         {
656           tree stmt = bsi_stmt (i);
657           bool is_varying = surely_varying_stmt_p (stmt);
658
659           if (is_varying)
660             {
661               tree def;
662               ssa_op_iter iter;
663
664               /* If the statement will not produce a constant, mark
665                  all its outputs VARYING.  */
666               FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
667                 {
668                   if (is_varying)
669                     set_value_varying (def);
670                 }
671             }
672
673           DONT_SIMULATE_AGAIN (stmt) = is_varying;
674         }
675     }
676
677   /* Now process PHI nodes.  We never set DONT_SIMULATE_AGAIN on phi node,
678      since we do not know which edges are executable yet, except for
679      phi nodes for virtual operands when we do not do store ccp.  */
680   FOR_EACH_BB (bb)
681     {
682       tree phi;
683
684       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
685         {
686           if (!do_store_ccp && !is_gimple_reg (PHI_RESULT (phi)))
687             DONT_SIMULATE_AGAIN (phi) = true;
688           else
689             DONT_SIMULATE_AGAIN (phi) = false;
690         }
691     }
692 }
693
694
695 /* Do final substitution of propagated values, cleanup the flowgraph and
696    free allocated storage.  
697
698    Return TRUE when something was optimized.  */
699
700 static bool
701 ccp_finalize (void)
702 {
703   /* Perform substitutions based on the known constant values.  */
704   bool something_changed = substitute_and_fold (const_val, false);
705
706   free (const_val);
707   const_val = NULL;
708   return something_changed;;
709 }
710
711
712 /* Compute the meet operator between *VAL1 and *VAL2.  Store the result
713    in VAL1.
714
715                 any  M UNDEFINED   = any
716                 any  M VARYING     = VARYING
717                 Ci   M Cj          = Ci         if (i == j)
718                 Ci   M Cj          = VARYING    if (i != j)
719    */
720
721 static void
722 ccp_lattice_meet (prop_value_t *val1, prop_value_t *val2)
723 {
724   if (val1->lattice_val == UNDEFINED)
725     {
726       /* UNDEFINED M any = any   */
727       *val1 = *val2;
728     }
729   else if (val2->lattice_val == UNDEFINED)
730     {
731       /* any M UNDEFINED = any
732          Nothing to do.  VAL1 already contains the value we want.  */
733       ;
734     }
735   else if (val1->lattice_val == VARYING
736            || val2->lattice_val == VARYING)
737     {
738       /* any M VARYING = VARYING.  */
739       val1->lattice_val = VARYING;
740       val1->value = NULL_TREE;
741       val1->mem_ref = NULL_TREE;
742     }
743   else if (val1->lattice_val == CONSTANT
744            && val2->lattice_val == CONSTANT
745            && simple_cst_equal (val1->value, val2->value) == 1
746            && (!do_store_ccp
747                || (val1->mem_ref && val2->mem_ref
748                    && operand_equal_p (val1->mem_ref, val2->mem_ref, 0))))
749     {
750       /* Ci M Cj = Ci           if (i == j)
751          Ci M Cj = VARYING      if (i != j)
752
753          If these two values come from memory stores, make sure that
754          they come from the same memory reference.  */
755       val1->lattice_val = CONSTANT;
756       val1->value = val1->value;
757       val1->mem_ref = val1->mem_ref;
758     }
759   else
760     {
761       /* Any other combination is VARYING.  */
762       val1->lattice_val = VARYING;
763       val1->value = NULL_TREE;
764       val1->mem_ref = NULL_TREE;
765     }
766 }
767
768
769 /* Loop through the PHI_NODE's parameters for BLOCK and compare their
770    lattice values to determine PHI_NODE's lattice value.  The value of a
771    PHI node is determined calling ccp_lattice_meet with all the arguments
772    of the PHI node that are incoming via executable edges.  */
773
774 static enum ssa_prop_result
775 ccp_visit_phi_node (tree phi)
776 {
777   int i;
778   prop_value_t *old_val, new_val;
779
780   if (dump_file && (dump_flags & TDF_DETAILS))
781     {
782       fprintf (dump_file, "\nVisiting PHI node: ");
783       print_generic_expr (dump_file, phi, dump_flags);
784     }
785
786   old_val = get_value (PHI_RESULT (phi));
787   switch (old_val->lattice_val)
788     {
789     case VARYING:
790       return SSA_PROP_VARYING;
791
792     case CONSTANT:
793       new_val = *old_val;
794       break;
795
796     case UNDEFINED:
797       new_val.lattice_val = UNDEFINED;
798       new_val.value = NULL_TREE;
799       new_val.mem_ref = NULL_TREE;
800       break;
801
802     default:
803       gcc_unreachable ();
804     }
805
806   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
807     {
808       /* Compute the meet operator over all the PHI arguments flowing
809          through executable edges.  */
810       edge e = PHI_ARG_EDGE (phi, i);
811
812       if (dump_file && (dump_flags & TDF_DETAILS))
813         {
814           fprintf (dump_file,
815               "\n    Argument #%d (%d -> %d %sexecutable)\n",
816               i, e->src->index, e->dest->index,
817               (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
818         }
819
820       /* If the incoming edge is executable, Compute the meet operator for
821          the existing value of the PHI node and the current PHI argument.  */
822       if (e->flags & EDGE_EXECUTABLE)
823         {
824           tree arg = PHI_ARG_DEF (phi, i);
825           prop_value_t arg_val;
826
827           if (is_gimple_min_invariant (arg))
828             {
829               arg_val.lattice_val = CONSTANT;
830               arg_val.value = arg;
831               arg_val.mem_ref = NULL_TREE;
832             }
833           else
834             arg_val = *(get_value (arg));
835
836           ccp_lattice_meet (&new_val, &arg_val);
837
838           if (dump_file && (dump_flags & TDF_DETAILS))
839             {
840               fprintf (dump_file, "\t");
841               print_generic_expr (dump_file, arg, dump_flags);
842               dump_lattice_value (dump_file, "\tValue: ", arg_val);
843               fprintf (dump_file, "\n");
844             }
845
846           if (new_val.lattice_val == VARYING)
847             break;
848         }
849     }
850
851   if (dump_file && (dump_flags & TDF_DETAILS))
852     {
853       dump_lattice_value (dump_file, "\n    PHI node value: ", new_val);
854       fprintf (dump_file, "\n\n");
855     }
856
857   /* Make the transition to the new value.  */
858   if (set_lattice_value (PHI_RESULT (phi), new_val))
859     {
860       if (new_val.lattice_val == VARYING)
861         return SSA_PROP_VARYING;
862       else
863         return SSA_PROP_INTERESTING;
864     }
865   else
866     return SSA_PROP_NOT_INTERESTING;
867 }
868
869
870 /* CCP specific front-end to the non-destructive constant folding
871    routines.
872
873    Attempt to simplify the RHS of STMT knowing that one or more
874    operands are constants.
875
876    If simplification is possible, return the simplified RHS,
877    otherwise return the original RHS.  */
878
879 static tree
880 ccp_fold (tree stmt)
881 {
882   tree rhs = get_rhs (stmt);
883   enum tree_code code = TREE_CODE (rhs);
884   enum tree_code_class kind = TREE_CODE_CLASS (code);
885   tree retval = NULL_TREE;
886
887   if (TREE_CODE (rhs) == SSA_NAME)
888     {
889       /* If the RHS is an SSA_NAME, return its known constant value,
890          if any.  */
891       return get_value (rhs)->value;
892     }
893   else if (do_store_ccp && stmt_makes_single_load (stmt))
894     {
895       /* If the RHS is a memory load, see if the VUSEs associated with
896          it are a valid constant for that memory load.  */
897       prop_value_t *val = get_value_loaded_by (stmt, const_val);
898       if (val && val->mem_ref)
899         {
900           if (operand_equal_p (val->mem_ref, rhs, 0))
901             return val->value;
902
903           /* If RHS is extracting REALPART_EXPR or IMAGPART_EXPR of a
904              complex type with a known constant value, return it.  */
905           if ((TREE_CODE (rhs) == REALPART_EXPR
906                || TREE_CODE (rhs) == IMAGPART_EXPR)
907               && operand_equal_p (val->mem_ref, TREE_OPERAND (rhs, 0), 0))
908             return fold_build1 (TREE_CODE (rhs), TREE_TYPE (rhs), val->value);
909         }
910       return NULL_TREE;
911     }
912
913   /* Unary operators.  Note that we know the single operand must
914      be a constant.  So this should almost always return a
915      simplified RHS.  */
916   if (kind == tcc_unary)
917     {
918       /* Handle unary operators which can appear in GIMPLE form.  */
919       tree op0 = TREE_OPERAND (rhs, 0);
920
921       /* Simplify the operand down to a constant.  */
922       if (TREE_CODE (op0) == SSA_NAME)
923         {
924           prop_value_t *val = get_value (op0);
925           if (val->lattice_val == CONSTANT)
926             op0 = get_value (op0)->value;
927         }
928
929       /* Conversions are useless for CCP purposes if they are
930          value-preserving.  Thus the restrictions that
931          useless_type_conversion_p places for pointer type conversions do
932          not apply here.  Substitution later will only substitute to
933          allowed places.  */
934       if ((code == NOP_EXPR || code == CONVERT_EXPR)
935           && ((POINTER_TYPE_P (TREE_TYPE (rhs))
936                && POINTER_TYPE_P (TREE_TYPE (op0)))
937               || useless_type_conversion_p (TREE_TYPE (rhs), TREE_TYPE (op0))))
938         return op0;
939       return fold_unary (code, TREE_TYPE (rhs), op0);
940     }
941
942   /* Binary and comparison operators.  We know one or both of the
943      operands are constants.  */
944   else if (kind == tcc_binary
945            || kind == tcc_comparison
946            || code == TRUTH_AND_EXPR
947            || code == TRUTH_OR_EXPR
948            || code == TRUTH_XOR_EXPR)
949     {
950       /* Handle binary and comparison operators that can appear in
951          GIMPLE form.  */
952       tree op0 = TREE_OPERAND (rhs, 0);
953       tree op1 = TREE_OPERAND (rhs, 1);
954
955       /* Simplify the operands down to constants when appropriate.  */
956       if (TREE_CODE (op0) == SSA_NAME)
957         {
958           prop_value_t *val = get_value (op0);
959           if (val->lattice_val == CONSTANT)
960             op0 = val->value;
961         }
962
963       if (TREE_CODE (op1) == SSA_NAME)
964         {
965           prop_value_t *val = get_value (op1);
966           if (val->lattice_val == CONSTANT)
967             op1 = val->value;
968         }
969
970       return fold_binary (code, TREE_TYPE (rhs), op0, op1);
971     }
972
973   else if (kind == tcc_declaration)
974     return get_symbol_constant_value (rhs);
975
976   else if (kind == tcc_reference)
977     return fold_const_aggregate_ref (rhs);
978
979   /* Handle propagating invariant addresses into address operations.
980      The folding we do here matches that in tree-ssa-forwprop.c.  */
981   else if (code == ADDR_EXPR)
982     {
983       tree *base;
984       base = &TREE_OPERAND (rhs, 0);
985       while (handled_component_p (*base))
986         base = &TREE_OPERAND (*base, 0);
987       if (TREE_CODE (*base) == INDIRECT_REF
988           && TREE_CODE (TREE_OPERAND (*base, 0)) == SSA_NAME)
989         {
990           prop_value_t *val = get_value (TREE_OPERAND (*base, 0));
991           if (val->lattice_val == CONSTANT
992               && TREE_CODE (val->value) == ADDR_EXPR
993               && useless_type_conversion_p (TREE_TYPE (TREE_OPERAND (*base, 0)),
994                                             TREE_TYPE (val->value))
995               && useless_type_conversion_p (TREE_TYPE (*base),
996                                             TREE_TYPE (TREE_OPERAND (val->value, 0))))
997             {
998               /* We need to return a new tree, not modify the IL or share
999                  parts of it.  So play some tricks to avoid manually
1000                  building it.  */
1001               tree ret, save = *base;
1002               *base = TREE_OPERAND (val->value, 0);
1003               ret = unshare_expr (rhs);
1004               recompute_tree_invariant_for_addr_expr (ret);
1005               *base = save;
1006               return ret;
1007             }
1008         }
1009     }
1010
1011   /* We may be able to fold away calls to builtin functions if their
1012      arguments are constants.  */
1013   else if (code == CALL_EXPR
1014            && TREE_CODE (CALL_EXPR_FN (rhs)) == ADDR_EXPR
1015            && TREE_CODE (TREE_OPERAND (CALL_EXPR_FN (rhs), 0)) == FUNCTION_DECL
1016            && DECL_BUILT_IN (TREE_OPERAND (CALL_EXPR_FN (rhs), 0)))
1017     {
1018       if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_USE))
1019         {
1020           tree *orig, var;
1021           size_t i = 0;
1022           ssa_op_iter iter;
1023           use_operand_p var_p;
1024
1025           /* Preserve the original values of every operand.  */
1026           orig = XNEWVEC (tree,  NUM_SSA_OPERANDS (stmt, SSA_OP_USE));
1027           FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
1028             orig[i++] = var;
1029
1030           /* Substitute operands with their values and try to fold.  */
1031           replace_uses_in (stmt, NULL, const_val);
1032           retval = fold_call_expr (rhs, false);
1033
1034           /* Restore operands to their original form.  */
1035           i = 0;
1036           FOR_EACH_SSA_USE_OPERAND (var_p, stmt, iter, SSA_OP_USE)
1037             SET_USE (var_p, orig[i++]);
1038           free (orig);
1039         }
1040     }
1041   else
1042     return rhs;
1043
1044   /* If we got a simplified form, see if we need to convert its type.  */
1045   if (retval)
1046     return fold_convert (TREE_TYPE (rhs), retval);
1047
1048   /* No simplification was possible.  */
1049   return rhs;
1050 }
1051
1052
1053 /* Return the tree representing the element referenced by T if T is an
1054    ARRAY_REF or COMPONENT_REF into constant aggregates.  Return
1055    NULL_TREE otherwise.  */
1056
1057 tree
1058 fold_const_aggregate_ref (tree t)
1059 {
1060   prop_value_t *value;
1061   tree base, ctor, idx, field;
1062   unsigned HOST_WIDE_INT cnt;
1063   tree cfield, cval;
1064
1065   switch (TREE_CODE (t))
1066     {
1067     case ARRAY_REF:
1068       /* Get a CONSTRUCTOR.  If BASE is a VAR_DECL, get its
1069          DECL_INITIAL.  If BASE is a nested reference into another
1070          ARRAY_REF or COMPONENT_REF, make a recursive call to resolve
1071          the inner reference.  */
1072       base = TREE_OPERAND (t, 0);
1073       switch (TREE_CODE (base))
1074         {
1075         case VAR_DECL:
1076           if (!TREE_READONLY (base)
1077               || TREE_CODE (TREE_TYPE (base)) != ARRAY_TYPE
1078               || !targetm.binds_local_p (base))
1079             return NULL_TREE;
1080
1081           ctor = DECL_INITIAL (base);
1082           break;
1083
1084         case ARRAY_REF:
1085         case COMPONENT_REF:
1086           ctor = fold_const_aggregate_ref (base);
1087           break;
1088
1089         case STRING_CST:
1090         case CONSTRUCTOR:
1091           ctor = base;
1092           break;
1093
1094         default:
1095           return NULL_TREE;
1096         }
1097
1098       if (ctor == NULL_TREE
1099           || (TREE_CODE (ctor) != CONSTRUCTOR
1100               && TREE_CODE (ctor) != STRING_CST)
1101           || !TREE_STATIC (ctor))
1102         return NULL_TREE;
1103
1104       /* Get the index.  If we have an SSA_NAME, try to resolve it
1105          with the current lattice value for the SSA_NAME.  */
1106       idx = TREE_OPERAND (t, 1);
1107       switch (TREE_CODE (idx))
1108         {
1109         case SSA_NAME:
1110           if ((value = get_value (idx))
1111               && value->lattice_val == CONSTANT
1112               && TREE_CODE (value->value) == INTEGER_CST)
1113             idx = value->value;
1114           else
1115             return NULL_TREE;
1116           break;
1117
1118         case INTEGER_CST:
1119           break;
1120
1121         default:
1122           return NULL_TREE;
1123         }
1124
1125       /* Fold read from constant string.  */
1126       if (TREE_CODE (ctor) == STRING_CST)
1127         {
1128           if ((TYPE_MODE (TREE_TYPE (t))
1129                == TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
1130               && (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
1131                   == MODE_INT)
1132               && GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor)))) == 1
1133               && compare_tree_int (idx, TREE_STRING_LENGTH (ctor)) < 0)
1134             return build_int_cst_type (TREE_TYPE (t),
1135                                        (TREE_STRING_POINTER (ctor)
1136                                         [TREE_INT_CST_LOW (idx)]));
1137           return NULL_TREE;
1138         }
1139
1140       /* Whoo-hoo!  I'll fold ya baby.  Yeah!  */
1141       FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
1142         if (tree_int_cst_equal (cfield, idx))
1143           {
1144             STRIP_USELESS_TYPE_CONVERSION (cval);
1145             return cval;
1146           }
1147       break;
1148
1149     case COMPONENT_REF:
1150       /* Get a CONSTRUCTOR.  If BASE is a VAR_DECL, get its
1151          DECL_INITIAL.  If BASE is a nested reference into another
1152          ARRAY_REF or COMPONENT_REF, make a recursive call to resolve
1153          the inner reference.  */
1154       base = TREE_OPERAND (t, 0);
1155       switch (TREE_CODE (base))
1156         {
1157         case VAR_DECL:
1158           if (!TREE_READONLY (base)
1159               || TREE_CODE (TREE_TYPE (base)) != RECORD_TYPE
1160               || !targetm.binds_local_p (base))
1161             return NULL_TREE;
1162
1163           ctor = DECL_INITIAL (base);
1164           break;
1165
1166         case ARRAY_REF:
1167         case COMPONENT_REF:
1168           ctor = fold_const_aggregate_ref (base);
1169           break;
1170
1171         default:
1172           return NULL_TREE;
1173         }
1174
1175       if (ctor == NULL_TREE
1176           || TREE_CODE (ctor) != CONSTRUCTOR
1177           || !TREE_STATIC (ctor))
1178         return NULL_TREE;
1179
1180       field = TREE_OPERAND (t, 1);
1181
1182       FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
1183         if (cfield == field
1184             /* FIXME: Handle bit-fields.  */
1185             && ! DECL_BIT_FIELD (cfield))
1186           {
1187             STRIP_USELESS_TYPE_CONVERSION (cval);
1188             return cval;
1189           }
1190       break;
1191
1192     case REALPART_EXPR:
1193     case IMAGPART_EXPR:
1194       {
1195         tree c = fold_const_aggregate_ref (TREE_OPERAND (t, 0));
1196         if (c && TREE_CODE (c) == COMPLEX_CST)
1197           return fold_build1 (TREE_CODE (t), TREE_TYPE (t), c);
1198         break;
1199       }
1200
1201     case INDIRECT_REF:
1202       {
1203         tree base = TREE_OPERAND (t, 0);
1204         if (TREE_CODE (base) == SSA_NAME
1205             && (value = get_value (base))
1206             && value->lattice_val == CONSTANT
1207             && TREE_CODE (value->value) == ADDR_EXPR)
1208           return fold_const_aggregate_ref (TREE_OPERAND (value->value, 0));
1209         break;
1210       }
1211
1212     default:
1213       break;
1214     }
1215
1216   return NULL_TREE;
1217 }
1218   
1219 /* Evaluate statement STMT.  */
1220
1221 static prop_value_t
1222 evaluate_stmt (tree stmt)
1223 {
1224   prop_value_t val;
1225   tree simplified = NULL_TREE;
1226   ccp_lattice_t likelyvalue = likely_value (stmt);
1227   bool is_constant;
1228
1229   val.mem_ref = NULL_TREE;
1230
1231   fold_defer_overflow_warnings ();
1232
1233   /* If the statement is likely to have a CONSTANT result, then try
1234      to fold the statement to determine the constant value.  */
1235   if (likelyvalue == CONSTANT)
1236     simplified = ccp_fold (stmt);
1237   /* If the statement is likely to have a VARYING result, then do not
1238      bother folding the statement.  */
1239   else if (likelyvalue == VARYING)
1240     simplified = get_rhs (stmt);
1241
1242   is_constant = simplified && is_gimple_min_invariant (simplified);
1243
1244   fold_undefer_overflow_warnings (is_constant, stmt, 0);
1245
1246   if (dump_file && (dump_flags & TDF_DETAILS))
1247     {
1248       fprintf (dump_file, "which is likely ");
1249       switch (likelyvalue)
1250         {
1251         case CONSTANT:
1252           fprintf (dump_file, "CONSTANT");
1253           break;
1254         case UNDEFINED:
1255           fprintf (dump_file, "UNDEFINED");
1256           break;
1257         case VARYING:
1258           fprintf (dump_file, "VARYING");
1259           break;
1260         default:;
1261         }
1262       fprintf (dump_file, "\n");
1263     }
1264
1265   if (is_constant)
1266     {
1267       /* The statement produced a constant value.  */
1268       val.lattice_val = CONSTANT;
1269       val.value = simplified;
1270     }
1271   else
1272     {
1273       /* The statement produced a nonconstant value.  If the statement
1274          had UNDEFINED operands, then the result of the statement
1275          should be UNDEFINED.  Otherwise, the statement is VARYING.  */
1276       if (likelyvalue == UNDEFINED)
1277         val.lattice_val = likelyvalue;
1278       else
1279         val.lattice_val = VARYING;
1280
1281       val.value = NULL_TREE;
1282     }
1283
1284   return val;
1285 }
1286
1287
1288 /* Visit the assignment statement STMT.  Set the value of its LHS to the
1289    value computed by the RHS and store LHS in *OUTPUT_P.  If STMT
1290    creates virtual definitions, set the value of each new name to that
1291    of the RHS (if we can derive a constant out of the RHS).  */
1292
1293 static enum ssa_prop_result
1294 visit_assignment (tree stmt, tree *output_p)
1295 {
1296   prop_value_t val;
1297   tree lhs, rhs;
1298   enum ssa_prop_result retval;
1299
1300   lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1301   rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1302
1303   if (TREE_CODE (rhs) == SSA_NAME)
1304     {
1305       /* For a simple copy operation, we copy the lattice values.  */
1306       prop_value_t *nval = get_value (rhs);
1307       val = *nval;
1308     }
1309   else if (do_store_ccp && stmt_makes_single_load (stmt))
1310     {
1311       /* Same as above, but the RHS is not a gimple register and yet
1312          has a known VUSE.  If STMT is loading from the same memory
1313          location that created the SSA_NAMEs for the virtual operands,
1314          we can propagate the value on the RHS.  */
1315       prop_value_t *nval = get_value_loaded_by (stmt, const_val);
1316
1317       if (nval
1318           && nval->mem_ref
1319           && operand_equal_p (nval->mem_ref, rhs, 0))
1320         val = *nval;
1321       else
1322         val = evaluate_stmt (stmt);
1323     }
1324   else
1325     /* Evaluate the statement.  */
1326     val = evaluate_stmt (stmt);
1327
1328   retval = SSA_PROP_NOT_INTERESTING;
1329
1330   /* Set the lattice value of the statement's output.  */
1331   if (TREE_CODE (lhs) == SSA_NAME)
1332     {
1333       /* If STMT is an assignment to an SSA_NAME, we only have one
1334          value to set.  */
1335       if (set_lattice_value (lhs, val))
1336         {
1337           *output_p = lhs;
1338           if (val.lattice_val == VARYING)
1339             retval = SSA_PROP_VARYING;
1340           else
1341             retval = SSA_PROP_INTERESTING;
1342         }
1343     }
1344   else if (do_store_ccp && stmt_makes_single_store (stmt))
1345     {
1346       /* Otherwise, set the names in VDEF operands to the new
1347          constant value and mark the LHS as the memory reference
1348          associated with VAL.  */
1349       ssa_op_iter i;
1350       tree vdef;
1351       bool changed;
1352
1353       /* Mark VAL as stored in the LHS of this assignment.  */
1354       if (val.lattice_val == CONSTANT)
1355         val.mem_ref = lhs;
1356
1357       /* Set the value of every VDEF to VAL.  */
1358       changed = false;
1359       FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VIRTUAL_DEFS)
1360         {
1361           /* See PR 29801.  We may have VDEFs for read-only variables
1362              (see the handling of unmodifiable variables in
1363              add_virtual_operand); do not attempt to change their value.  */
1364           if (get_symbol_constant_value (SSA_NAME_VAR (vdef)) != NULL_TREE)
1365             continue;
1366
1367           changed |= set_lattice_value (vdef, val);
1368         }
1369       
1370       /* Note that for propagation purposes, we are only interested in
1371          visiting statements that load the exact same memory reference
1372          stored here.  Those statements will have the exact same list
1373          of virtual uses, so it is enough to set the output of this
1374          statement to be its first virtual definition.  */
1375       *output_p = first_vdef (stmt);
1376       if (changed)
1377         {
1378           if (val.lattice_val == VARYING)
1379             retval = SSA_PROP_VARYING;
1380           else 
1381             retval = SSA_PROP_INTERESTING;
1382         }
1383     }
1384
1385   return retval;
1386 }
1387
1388
1389 /* Visit the conditional statement STMT.  Return SSA_PROP_INTERESTING
1390    if it can determine which edge will be taken.  Otherwise, return
1391    SSA_PROP_VARYING.  */
1392
1393 static enum ssa_prop_result
1394 visit_cond_stmt (tree stmt, edge *taken_edge_p)
1395 {
1396   prop_value_t val;
1397   basic_block block;
1398
1399   block = bb_for_stmt (stmt);
1400   val = evaluate_stmt (stmt);
1401
1402   /* Find which edge out of the conditional block will be taken and add it
1403      to the worklist.  If no single edge can be determined statically,
1404      return SSA_PROP_VARYING to feed all the outgoing edges to the
1405      propagation engine.  */
1406   *taken_edge_p = val.value ? find_taken_edge (block, val.value) : 0;
1407   if (*taken_edge_p)
1408     return SSA_PROP_INTERESTING;
1409   else
1410     return SSA_PROP_VARYING;
1411 }
1412
1413
1414 /* Evaluate statement STMT.  If the statement produces an output value and
1415    its evaluation changes the lattice value of its output, return
1416    SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the
1417    output value.
1418    
1419    If STMT is a conditional branch and we can determine its truth
1420    value, set *TAKEN_EDGE_P accordingly.  If STMT produces a varying
1421    value, return SSA_PROP_VARYING.  */
1422
1423 static enum ssa_prop_result
1424 ccp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
1425 {
1426   tree def;
1427   ssa_op_iter iter;
1428
1429   if (dump_file && (dump_flags & TDF_DETAILS))
1430     {
1431       fprintf (dump_file, "\nVisiting statement:\n");
1432       print_generic_stmt (dump_file, stmt, dump_flags);
1433     }
1434
1435   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1436     {
1437       /* If the statement is an assignment that produces a single
1438          output value, evaluate its RHS to see if the lattice value of
1439          its output has changed.  */
1440       return visit_assignment (stmt, output_p);
1441     }
1442   else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
1443     {
1444       /* If STMT is a conditional branch, see if we can determine
1445          which branch will be taken.  */
1446       return visit_cond_stmt (stmt, taken_edge_p);
1447     }
1448
1449   /* Any other kind of statement is not interesting for constant
1450      propagation and, therefore, not worth simulating.  */
1451   if (dump_file && (dump_flags & TDF_DETAILS))
1452     fprintf (dump_file, "No interesting values produced.  Marked VARYING.\n");
1453
1454   /* Definitions made by statements other than assignments to
1455      SSA_NAMEs represent unknown modifications to their outputs.
1456      Mark them VARYING.  */
1457   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
1458     {
1459       prop_value_t v = { VARYING, NULL_TREE, NULL_TREE };
1460       set_lattice_value (def, v);
1461     }
1462
1463   return SSA_PROP_VARYING;
1464 }
1465
1466
1467 /* Main entry point for SSA Conditional Constant Propagation.  */
1468
1469 static unsigned int
1470 execute_ssa_ccp (bool store_ccp)
1471 {
1472   do_store_ccp = store_ccp;
1473   ccp_initialize ();
1474   ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node);
1475   if (ccp_finalize ())
1476     return (TODO_cleanup_cfg | TODO_update_ssa | TODO_remove_unused_locals);
1477   else
1478     return 0;
1479 }
1480
1481
1482 static unsigned int
1483 do_ssa_ccp (void)
1484 {
1485   return execute_ssa_ccp (false);
1486 }
1487
1488
1489 static bool
1490 gate_ccp (void)
1491 {
1492   return flag_tree_ccp != 0;
1493 }
1494
1495
1496 struct gimple_opt_pass pass_ccp = 
1497 {
1498  {
1499   GIMPLE_PASS,
1500   "ccp",                                /* name */
1501   gate_ccp,                             /* gate */
1502   do_ssa_ccp,                           /* execute */
1503   NULL,                                 /* sub */
1504   NULL,                                 /* next */
1505   0,                                    /* static_pass_number */
1506   TV_TREE_CCP,                          /* tv_id */
1507   PROP_cfg | PROP_ssa,                  /* properties_required */
1508   0,                                    /* properties_provided */
1509   0,                                    /* properties_destroyed */
1510   0,                                    /* todo_flags_start */
1511   TODO_dump_func | TODO_verify_ssa
1512   | TODO_verify_stmts | TODO_ggc_collect/* todo_flags_finish */
1513  }
1514 };
1515
1516
1517 static unsigned int
1518 do_ssa_store_ccp (void)
1519 {
1520   /* If STORE-CCP is not enabled, we just run regular CCP.  */
1521   return execute_ssa_ccp (flag_tree_store_ccp != 0);
1522 }
1523
1524 static bool
1525 gate_store_ccp (void)
1526 {
1527   /* STORE-CCP is enabled only with -ftree-store-ccp, but when
1528      -fno-tree-store-ccp is specified, we should run regular CCP.
1529      That's why the pass is enabled with either flag.  */
1530   return flag_tree_store_ccp != 0 || flag_tree_ccp != 0;
1531 }
1532
1533
1534 struct gimple_opt_pass pass_store_ccp = 
1535 {
1536  {
1537   GIMPLE_PASS,
1538   "store_ccp",                          /* name */
1539   gate_store_ccp,                       /* gate */
1540   do_ssa_store_ccp,                     /* execute */
1541   NULL,                                 /* sub */
1542   NULL,                                 /* next */
1543   0,                                    /* static_pass_number */
1544   TV_TREE_STORE_CCP,                    /* tv_id */
1545   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1546   0,                                    /* properties_provided */
1547   0,                                    /* properties_destroyed */
1548   0,                                    /* todo_flags_start */
1549   TODO_dump_func | TODO_verify_ssa
1550   | TODO_verify_stmts | TODO_ggc_collect/* todo_flags_finish */
1551  }
1552 };
1553
1554 /* A subroutine of fold_stmt_r.  Attempts to fold *(A+O) to A[X].
1555    BASE is an array type.  OFFSET is a byte displacement.  ORIG_TYPE
1556    is the desired result type.  */
1557
1558 static tree
1559 maybe_fold_offset_to_array_ref (tree base, tree offset, tree orig_type,
1560                                 bool allow_negative_idx)
1561 {
1562   tree min_idx, idx, idx_type, elt_offset = integer_zero_node;
1563   tree array_type, elt_type, elt_size;
1564   tree domain_type;
1565
1566   /* If BASE is an ARRAY_REF, we can pick up another offset (this time
1567      measured in units of the size of elements type) from that ARRAY_REF).
1568      We can't do anything if either is variable.
1569
1570      The case we handle here is *(&A[N]+O).  */
1571   if (TREE_CODE (base) == ARRAY_REF)
1572     {
1573       tree low_bound = array_ref_low_bound (base);
1574
1575       elt_offset = TREE_OPERAND (base, 1);
1576       if (TREE_CODE (low_bound) != INTEGER_CST
1577           || TREE_CODE (elt_offset) != INTEGER_CST)
1578         return NULL_TREE;
1579
1580       elt_offset = int_const_binop (MINUS_EXPR, elt_offset, low_bound, 0);
1581       base = TREE_OPERAND (base, 0);
1582     }
1583
1584   /* Ignore stupid user tricks of indexing non-array variables.  */
1585   array_type = TREE_TYPE (base);
1586   if (TREE_CODE (array_type) != ARRAY_TYPE)
1587     return NULL_TREE;
1588   elt_type = TREE_TYPE (array_type);
1589   if (!useless_type_conversion_p (orig_type, elt_type))
1590     return NULL_TREE;
1591
1592   /* Use signed size type for intermediate computation on the index.  */
1593   idx_type = signed_type_for (size_type_node);
1594
1595   /* If OFFSET and ELT_OFFSET are zero, we don't care about the size of the
1596      element type (so we can use the alignment if it's not constant).
1597      Otherwise, compute the offset as an index by using a division.  If the
1598      division isn't exact, then don't do anything.  */
1599   elt_size = TYPE_SIZE_UNIT (elt_type);
1600   if (!elt_size)
1601     return NULL;
1602   if (integer_zerop (offset))
1603     {
1604       if (TREE_CODE (elt_size) != INTEGER_CST)
1605         elt_size = size_int (TYPE_ALIGN (elt_type));
1606
1607       idx = build_int_cst (idx_type, 0);
1608     }
1609   else
1610     {
1611       unsigned HOST_WIDE_INT lquo, lrem;
1612       HOST_WIDE_INT hquo, hrem;
1613       double_int soffset;
1614
1615       /* The final array offset should be signed, so we need
1616          to sign-extend the (possibly pointer) offset here
1617          and use signed division.  */
1618       soffset = double_int_sext (tree_to_double_int (offset),
1619                                  TYPE_PRECISION (TREE_TYPE (offset)));
1620       if (TREE_CODE (elt_size) != INTEGER_CST
1621           || div_and_round_double (TRUNC_DIV_EXPR, 0,
1622                                    soffset.low, soffset.high,
1623                                    TREE_INT_CST_LOW (elt_size),
1624                                    TREE_INT_CST_HIGH (elt_size),
1625                                    &lquo, &hquo, &lrem, &hrem)
1626           || lrem || hrem)
1627         return NULL_TREE;
1628
1629       idx = build_int_cst_wide (idx_type, lquo, hquo);
1630     }
1631
1632   /* Assume the low bound is zero.  If there is a domain type, get the
1633      low bound, if any, convert the index into that type, and add the
1634      low bound.  */
1635   min_idx = build_int_cst (idx_type, 0);
1636   domain_type = TYPE_DOMAIN (array_type);
1637   if (domain_type)
1638     {
1639       idx_type = domain_type;
1640       if (TYPE_MIN_VALUE (idx_type))
1641         min_idx = TYPE_MIN_VALUE (idx_type);
1642       else
1643         min_idx = fold_convert (idx_type, min_idx);
1644
1645       if (TREE_CODE (min_idx) != INTEGER_CST)
1646         return NULL_TREE;
1647
1648       elt_offset = fold_convert (idx_type, elt_offset);
1649     }
1650
1651   if (!integer_zerop (min_idx))
1652     idx = int_const_binop (PLUS_EXPR, idx, min_idx, 0);
1653   if (!integer_zerop (elt_offset))
1654     idx = int_const_binop (PLUS_EXPR, idx, elt_offset, 0);
1655
1656   /* Make sure to possibly truncate late after offsetting.  */
1657   idx = fold_convert (idx_type, idx);
1658
1659   /* We don't want to construct access past array bounds. For example
1660        char *(c[4]);
1661        c[3][2];
1662      should not be simplified into (*c)[14] or tree-vrp will
1663      give false warnings.  The same is true for
1664        struct A { long x; char d[0]; } *a;
1665        (char *)a - 4;
1666      which should be not folded to &a->d[-8].  */
1667   if (domain_type
1668       && TYPE_MAX_VALUE (domain_type) 
1669       && TREE_CODE (TYPE_MAX_VALUE (domain_type)) == INTEGER_CST)
1670     {
1671       tree up_bound = TYPE_MAX_VALUE (domain_type);
1672
1673       if (tree_int_cst_lt (up_bound, idx)
1674           /* Accesses after the end of arrays of size 0 (gcc
1675              extension) and 1 are likely intentional ("struct
1676              hack").  */
1677           && compare_tree_int (up_bound, 1) > 0)
1678         return NULL_TREE;
1679     }
1680   if (domain_type
1681       && TYPE_MIN_VALUE (domain_type))
1682     {
1683       if (!allow_negative_idx
1684           && TREE_CODE (TYPE_MIN_VALUE (domain_type)) == INTEGER_CST
1685           && tree_int_cst_lt (idx, TYPE_MIN_VALUE (domain_type)))
1686         return NULL_TREE;
1687     }
1688   else if (!allow_negative_idx
1689            && compare_tree_int (idx, 0) < 0)
1690     return NULL_TREE;
1691
1692   return build4 (ARRAY_REF, elt_type, base, idx, NULL_TREE, NULL_TREE);
1693 }
1694
1695
1696 /* Attempt to fold *(S+O) to S.X.
1697    BASE is a record type.  OFFSET is a byte displacement.  ORIG_TYPE
1698    is the desired result type.  */
1699
1700 static tree
1701 maybe_fold_offset_to_component_ref (tree record_type, tree base, tree offset,
1702                                     tree orig_type, bool base_is_ptr)
1703 {
1704   tree f, t, field_type, tail_array_field, field_offset;
1705   tree ret;
1706   tree new_base;
1707
1708   if (TREE_CODE (record_type) != RECORD_TYPE
1709       && TREE_CODE (record_type) != UNION_TYPE
1710       && TREE_CODE (record_type) != QUAL_UNION_TYPE)
1711     return NULL_TREE;
1712
1713   /* Short-circuit silly cases.  */
1714   if (useless_type_conversion_p (record_type, orig_type))
1715     return NULL_TREE;
1716
1717   tail_array_field = NULL_TREE;
1718   for (f = TYPE_FIELDS (record_type); f ; f = TREE_CHAIN (f))
1719     {
1720       int cmp;
1721
1722       if (TREE_CODE (f) != FIELD_DECL)
1723         continue;
1724       if (DECL_BIT_FIELD (f))
1725         continue;
1726
1727       if (!DECL_FIELD_OFFSET (f))
1728         continue;
1729       field_offset = byte_position (f);
1730       if (TREE_CODE (field_offset) != INTEGER_CST)
1731         continue;
1732
1733       /* ??? Java creates "interesting" fields for representing base classes.
1734          They have no name, and have no context.  With no context, we get into
1735          trouble with nonoverlapping_component_refs_p.  Skip them.  */
1736       if (!DECL_FIELD_CONTEXT (f))
1737         continue;
1738
1739       /* The previous array field isn't at the end.  */
1740       tail_array_field = NULL_TREE;
1741
1742       /* Check to see if this offset overlaps with the field.  */
1743       cmp = tree_int_cst_compare (field_offset, offset);
1744       if (cmp > 0)
1745         continue;
1746
1747       field_type = TREE_TYPE (f);
1748
1749       /* Here we exactly match the offset being checked.  If the types match,
1750          then we can return that field.  */
1751       if (cmp == 0
1752           && useless_type_conversion_p (orig_type, field_type))
1753         {
1754           if (base_is_ptr)
1755             base = build1 (INDIRECT_REF, record_type, base);
1756           t = build3 (COMPONENT_REF, field_type, base, f, NULL_TREE);
1757           return t;
1758         }
1759       
1760       /* Don't care about offsets into the middle of scalars.  */
1761       if (!AGGREGATE_TYPE_P (field_type))
1762         continue;
1763
1764       /* Check for array at the end of the struct.  This is often
1765          used as for flexible array members.  We should be able to
1766          turn this into an array access anyway.  */
1767       if (TREE_CODE (field_type) == ARRAY_TYPE)
1768         tail_array_field = f;
1769
1770       /* Check the end of the field against the offset.  */
1771       if (!DECL_SIZE_UNIT (f)
1772           || TREE_CODE (DECL_SIZE_UNIT (f)) != INTEGER_CST)
1773         continue;
1774       t = int_const_binop (MINUS_EXPR, offset, field_offset, 1);
1775       if (!tree_int_cst_lt (t, DECL_SIZE_UNIT (f)))
1776         continue;
1777
1778       /* If we matched, then set offset to the displacement into
1779          this field.  */
1780       if (base_is_ptr)
1781         new_base = build1 (INDIRECT_REF, record_type, base);
1782       else
1783         new_base = base;
1784       new_base = build3 (COMPONENT_REF, field_type, new_base, f, NULL_TREE);
1785
1786       /* Recurse to possibly find the match.  */
1787       ret = maybe_fold_offset_to_array_ref (new_base, t, orig_type,
1788                                             f == TYPE_FIELDS (record_type));
1789       if (ret)
1790         return ret;
1791       ret = maybe_fold_offset_to_component_ref (field_type, new_base, t,
1792                                                 orig_type, false);
1793       if (ret)
1794         return ret;
1795     }
1796
1797   if (!tail_array_field)
1798     return NULL_TREE;
1799
1800   f = tail_array_field;
1801   field_type = TREE_TYPE (f);
1802   offset = int_const_binop (MINUS_EXPR, offset, byte_position (f), 1);
1803
1804   /* If we get here, we've got an aggregate field, and a possibly 
1805      nonzero offset into them.  Recurse and hope for a valid match.  */
1806   if (base_is_ptr)
1807     base = build1 (INDIRECT_REF, record_type, base);
1808   base = build3 (COMPONENT_REF, field_type, base, f, NULL_TREE);
1809
1810   t = maybe_fold_offset_to_array_ref (base, offset, orig_type,
1811                                       f == TYPE_FIELDS (record_type));
1812   if (t)
1813     return t;
1814   return maybe_fold_offset_to_component_ref (field_type, base, offset,
1815                                              orig_type, false);
1816 }
1817
1818 /* Attempt to express (ORIG_TYPE)BASE+OFFSET as BASE->field_of_orig_type
1819    or BASE[index] or by combination of those. 
1820
1821    Before attempting the conversion strip off existing ADDR_EXPRs and
1822    handled component refs.  */
1823
1824 tree
1825 maybe_fold_offset_to_reference (tree base, tree offset, tree orig_type)
1826 {
1827   tree ret;
1828   tree type;
1829   bool base_is_ptr = true;
1830
1831   STRIP_NOPS (base);
1832   if (TREE_CODE (base) == ADDR_EXPR)
1833     {
1834       base_is_ptr = false;
1835
1836       base = TREE_OPERAND (base, 0);
1837
1838       /* Handle case where existing COMPONENT_REF pick e.g. wrong field of union,
1839          so it needs to be removed and new COMPONENT_REF constructed.
1840          The wrong COMPONENT_REF are often constructed by folding the
1841          (type *)&object within the expression (type *)&object+offset  */
1842       if (handled_component_p (base) && 0)
1843         {
1844           HOST_WIDE_INT sub_offset, size, maxsize;
1845           tree newbase;
1846           newbase = get_ref_base_and_extent (base, &sub_offset,
1847                                              &size, &maxsize);
1848           gcc_assert (newbase);
1849           gcc_assert (!(sub_offset & (BITS_PER_UNIT - 1)));
1850           if (size == maxsize)
1851             {
1852               base = newbase;
1853               if (sub_offset)
1854                 offset = int_const_binop (PLUS_EXPR, offset,
1855                                           build_int_cst (TREE_TYPE (offset),
1856                                           sub_offset / BITS_PER_UNIT), 1);
1857             }
1858         }
1859       if (useless_type_conversion_p (orig_type, TREE_TYPE (base))
1860           && integer_zerop (offset))
1861         return base;
1862       type = TREE_TYPE (base);
1863     }
1864   else
1865     {
1866       base_is_ptr = true;
1867       if (!POINTER_TYPE_P (TREE_TYPE (base)))
1868         return NULL_TREE;
1869       type = TREE_TYPE (TREE_TYPE (base));
1870     }
1871   ret = maybe_fold_offset_to_component_ref (type, base, offset,
1872                                             orig_type, base_is_ptr);
1873   if (!ret)
1874     {
1875       if (base_is_ptr)
1876         base = build1 (INDIRECT_REF, type, base);
1877       ret = maybe_fold_offset_to_array_ref (base, offset, orig_type, true);
1878     }
1879   return ret;
1880 }
1881
1882 /* A subroutine of fold_stmt_r.  Attempt to simplify *(BASE+OFFSET).
1883    Return the simplified expression, or NULL if nothing could be done.  */
1884
1885 static tree
1886 maybe_fold_stmt_indirect (tree expr, tree base, tree offset)
1887 {
1888   tree t;
1889   bool volatile_p = TREE_THIS_VOLATILE (expr);
1890
1891   /* We may well have constructed a double-nested PLUS_EXPR via multiple
1892      substitutions.  Fold that down to one.  Remove NON_LVALUE_EXPRs that
1893      are sometimes added.  */
1894   base = fold (base);
1895   STRIP_TYPE_NOPS (base);
1896   TREE_OPERAND (expr, 0) = base;
1897
1898   /* One possibility is that the address reduces to a string constant.  */
1899   t = fold_read_from_constant_string (expr);
1900   if (t)
1901     return t;
1902
1903   /* Add in any offset from a POINTER_PLUS_EXPR.  */
1904   if (TREE_CODE (base) == POINTER_PLUS_EXPR)
1905     {
1906       tree offset2;
1907
1908       offset2 = TREE_OPERAND (base, 1);
1909       if (TREE_CODE (offset2) != INTEGER_CST)
1910         return NULL_TREE;
1911       base = TREE_OPERAND (base, 0);
1912
1913       offset = fold_convert (sizetype,
1914                              int_const_binop (PLUS_EXPR, offset, offset2, 1));
1915     }
1916
1917   if (TREE_CODE (base) == ADDR_EXPR)
1918     {
1919       tree base_addr = base;
1920
1921       /* Strip the ADDR_EXPR.  */
1922       base = TREE_OPERAND (base, 0);
1923
1924       /* Fold away CONST_DECL to its value, if the type is scalar.  */
1925       if (TREE_CODE (base) == CONST_DECL
1926           && is_gimple_min_invariant (DECL_INITIAL (base)))
1927         return DECL_INITIAL (base);
1928
1929       /* Try folding *(&B+O) to B.X.  */
1930       t = maybe_fold_offset_to_reference (base_addr, offset,
1931                                           TREE_TYPE (expr));
1932       if (t)
1933         {
1934           TREE_THIS_VOLATILE (t) = volatile_p;
1935           return t;
1936         }
1937     }
1938   else
1939     {
1940       /* We can get here for out-of-range string constant accesses, 
1941          such as "_"[3].  Bail out of the entire substitution search
1942          and arrange for the entire statement to be replaced by a
1943          call to __builtin_trap.  In all likelihood this will all be
1944          constant-folded away, but in the meantime we can't leave with
1945          something that get_expr_operands can't understand.  */
1946
1947       t = base;
1948       STRIP_NOPS (t);
1949       if (TREE_CODE (t) == ADDR_EXPR
1950           && TREE_CODE (TREE_OPERAND (t, 0)) == STRING_CST)
1951         {
1952           /* FIXME: Except that this causes problems elsewhere with dead
1953              code not being deleted, and we die in the rtl expanders 
1954              because we failed to remove some ssa_name.  In the meantime,
1955              just return zero.  */
1956           /* FIXME2: This condition should be signaled by
1957              fold_read_from_constant_string directly, rather than 
1958              re-checking for it here.  */
1959           return integer_zero_node;
1960         }
1961
1962       /* Try folding *(B+O) to B->X.  Still an improvement.  */
1963       if (POINTER_TYPE_P (TREE_TYPE (base)))
1964         {
1965           t = maybe_fold_offset_to_reference (base, offset,
1966                                               TREE_TYPE (expr));
1967           if (t)
1968             return t;
1969         }
1970     }
1971
1972   /* Otherwise we had an offset that we could not simplify.  */
1973   return NULL_TREE;
1974 }
1975
1976
1977 /* A subroutine of fold_stmt_r.  EXPR is a POINTER_PLUS_EXPR.
1978
1979    A quaint feature extant in our address arithmetic is that there
1980    can be hidden type changes here.  The type of the result need
1981    not be the same as the type of the input pointer.
1982
1983    What we're after here is an expression of the form
1984         (T *)(&array + const)
1985    where the cast doesn't actually exist, but is implicit in the
1986    type of the POINTER_PLUS_EXPR.  We'd like to turn this into
1987         &array[x]
1988    which may be able to propagate further.  */
1989
1990 static tree
1991 maybe_fold_stmt_addition (tree expr)
1992 {
1993   tree op0 = TREE_OPERAND (expr, 0);
1994   tree op1 = TREE_OPERAND (expr, 1);
1995   tree ptr_type = TREE_TYPE (expr);
1996   tree ptd_type;
1997   tree t;
1998
1999   gcc_assert (TREE_CODE (expr) == POINTER_PLUS_EXPR);
2000
2001   /* It had better be a constant.  */
2002   if (TREE_CODE (op1) != INTEGER_CST)
2003     return NULL_TREE;
2004   /* The first operand should be an ADDR_EXPR.  */
2005   if (TREE_CODE (op0) != ADDR_EXPR)
2006     return NULL_TREE;
2007   op0 = TREE_OPERAND (op0, 0);
2008
2009   /* If the first operand is an ARRAY_REF, expand it so that we can fold
2010      the offset into it.  */
2011   while (TREE_CODE (op0) == ARRAY_REF)
2012     {
2013       tree array_obj = TREE_OPERAND (op0, 0);
2014       tree array_idx = TREE_OPERAND (op0, 1);
2015       tree elt_type = TREE_TYPE (op0);
2016       tree elt_size = TYPE_SIZE_UNIT (elt_type);
2017       tree min_idx;
2018
2019       if (TREE_CODE (array_idx) != INTEGER_CST)
2020         break;
2021       if (TREE_CODE (elt_size) != INTEGER_CST)
2022         break;
2023
2024       /* Un-bias the index by the min index of the array type.  */
2025       min_idx = TYPE_DOMAIN (TREE_TYPE (array_obj));
2026       if (min_idx)
2027         {
2028           min_idx = TYPE_MIN_VALUE (min_idx);
2029           if (min_idx)
2030             {
2031               if (TREE_CODE (min_idx) != INTEGER_CST)
2032                 break;
2033
2034               array_idx = fold_convert (TREE_TYPE (min_idx), array_idx);
2035               if (!integer_zerop (min_idx))
2036                 array_idx = int_const_binop (MINUS_EXPR, array_idx,
2037                                              min_idx, 0);
2038             }
2039         }
2040
2041       /* Convert the index to a byte offset.  */
2042       array_idx = fold_convert (sizetype, array_idx);
2043       array_idx = int_const_binop (MULT_EXPR, array_idx, elt_size, 0);
2044
2045       /* Update the operands for the next round, or for folding.  */
2046       op1 = int_const_binop (PLUS_EXPR,
2047                              array_idx, op1, 0);
2048       op0 = array_obj;
2049     }
2050
2051   ptd_type = TREE_TYPE (ptr_type);
2052   /* If we want a pointer to void, reconstruct the reference from the
2053      array element type.  A pointer to that can be trivially converted
2054      to void *.  This happens as we fold (void *)(ptr p+ off).  */
2055   if (VOID_TYPE_P (ptd_type)
2056       && TREE_CODE (TREE_TYPE (op0)) == ARRAY_TYPE)
2057     ptd_type = TREE_TYPE (TREE_TYPE (op0));
2058
2059   /* At which point we can try some of the same things as for indirects.  */
2060   t = maybe_fold_offset_to_array_ref (op0, op1, ptd_type, true);
2061   if (!t)
2062     t = maybe_fold_offset_to_component_ref (TREE_TYPE (op0), op0, op1,
2063                                             ptd_type, false);
2064   if (t)
2065     t = build1 (ADDR_EXPR, ptr_type, t);
2066
2067   return t;
2068 }
2069
2070 /* For passing state through walk_tree into fold_stmt_r and its
2071    children.  */
2072
2073 struct fold_stmt_r_data
2074 {
2075   tree stmt;
2076   bool *changed_p;
2077   bool *inside_addr_expr_p;
2078 };
2079
2080 /* Subroutine of fold_stmt called via walk_tree.  We perform several
2081    simplifications of EXPR_P, mostly having to do with pointer arithmetic.  */
2082
2083 static tree
2084 fold_stmt_r (tree *expr_p, int *walk_subtrees, void *data)
2085 {
2086   struct fold_stmt_r_data *fold_stmt_r_data = (struct fold_stmt_r_data *) data;
2087   bool *inside_addr_expr_p = fold_stmt_r_data->inside_addr_expr_p;
2088   bool *changed_p = fold_stmt_r_data->changed_p;
2089   tree expr = *expr_p, t;
2090   bool volatile_p = TREE_THIS_VOLATILE (expr);
2091
2092   /* ??? It'd be nice if walk_tree had a pre-order option.  */
2093   switch (TREE_CODE (expr))
2094     {
2095     case INDIRECT_REF:
2096       t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
2097       if (t)
2098         return t;
2099       *walk_subtrees = 0;
2100
2101       t = maybe_fold_stmt_indirect (expr, TREE_OPERAND (expr, 0),
2102                                     integer_zero_node);
2103       if (!t
2104           && TREE_CODE (TREE_OPERAND (expr, 0)) == ADDR_EXPR)
2105         /* If we had a good reason for propagating the address here,
2106            make sure we end up with valid gimple.  See PR34989.  */
2107         t = TREE_OPERAND (TREE_OPERAND (expr, 0), 0);
2108       break;
2109
2110     case NOP_EXPR:
2111       t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
2112       if (t)
2113         return t;
2114       *walk_subtrees = 0;
2115
2116       if (POINTER_TYPE_P (TREE_TYPE (expr))
2117           && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)))
2118           && (t = maybe_fold_offset_to_reference
2119                       (TREE_OPERAND (expr, 0),
2120                        integer_zero_node,
2121                        TREE_TYPE (TREE_TYPE (expr)))))
2122         {
2123           tree ptr_type = build_pointer_type (TREE_TYPE (t));
2124           if (!useless_type_conversion_p (TREE_TYPE (expr), ptr_type))
2125             return NULL_TREE;
2126           t = build_fold_addr_expr_with_type (t, ptr_type);
2127         }
2128       break;
2129
2130       /* ??? Could handle more ARRAY_REFs here, as a variant of INDIRECT_REF.
2131          We'd only want to bother decomposing an existing ARRAY_REF if
2132          the base array is found to have another offset contained within.
2133          Otherwise we'd be wasting time.  */
2134     case ARRAY_REF:
2135       /* If we are not processing expressions found within an
2136          ADDR_EXPR, then we can fold constant array references.  */
2137       if (!*inside_addr_expr_p)
2138         t = fold_read_from_constant_string (expr);
2139       else
2140         t = NULL;
2141       break;
2142
2143     case ADDR_EXPR:
2144       *inside_addr_expr_p = true;
2145       t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
2146       *inside_addr_expr_p = false;
2147       if (t)
2148         return t;
2149       *walk_subtrees = 0;
2150
2151       /* Make sure the value is properly considered constant, and so gets
2152          propagated as expected.  */
2153       if (*changed_p)
2154         recompute_tree_invariant_for_addr_expr (expr);
2155       return NULL_TREE;
2156
2157     case POINTER_PLUS_EXPR:
2158       t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
2159       if (t)
2160         return t;
2161       t = walk_tree (&TREE_OPERAND (expr, 1), fold_stmt_r, data, NULL);
2162       if (t)
2163         return t;
2164       *walk_subtrees = 0;
2165
2166       t = maybe_fold_stmt_addition (expr);
2167       break;
2168
2169     case COMPONENT_REF:
2170       t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
2171       if (t)
2172         return t;
2173       *walk_subtrees = 0;
2174
2175       /* Make sure the FIELD_DECL is actually a field in the type on the lhs.
2176          We've already checked that the records are compatible, so we should
2177          come up with a set of compatible fields.  */
2178       {
2179         tree expr_record = TREE_TYPE (TREE_OPERAND (expr, 0));
2180         tree expr_field = TREE_OPERAND (expr, 1);
2181
2182         if (DECL_FIELD_CONTEXT (expr_field) != TYPE_MAIN_VARIANT (expr_record))
2183           {
2184             expr_field = find_compatible_field (expr_record, expr_field);
2185             TREE_OPERAND (expr, 1) = expr_field;
2186           }
2187       }
2188       break;
2189
2190     case TARGET_MEM_REF:
2191       t = maybe_fold_tmr (expr);
2192       break;
2193
2194     case COND_EXPR:
2195       if (COMPARISON_CLASS_P (TREE_OPERAND (expr, 0)))
2196         {
2197           tree op0 = TREE_OPERAND (expr, 0);
2198           tree tem;
2199           bool set;
2200
2201           fold_defer_overflow_warnings ();
2202           tem = fold_binary (TREE_CODE (op0), TREE_TYPE (op0),
2203                              TREE_OPERAND (op0, 0),
2204                              TREE_OPERAND (op0, 1));
2205           set = tem && set_rhs (expr_p, tem);
2206           fold_undefer_overflow_warnings (set, fold_stmt_r_data->stmt, 0);
2207           if (set)
2208             {
2209               t = *expr_p;
2210               break;
2211             }
2212         }
2213       return NULL_TREE;
2214
2215     default:
2216       return NULL_TREE;
2217     }
2218
2219   if (t)
2220     {
2221       /* Preserve volatileness of the original expression.  */
2222       TREE_THIS_VOLATILE (t) = volatile_p;
2223       *expr_p = t;
2224       *changed_p = true;
2225     }
2226
2227   return NULL_TREE;
2228 }
2229
2230
2231 /* Return the string length, maximum string length or maximum value of
2232    ARG in LENGTH.
2233    If ARG is an SSA name variable, follow its use-def chains.  If LENGTH
2234    is not NULL and, for TYPE == 0, its value is not equal to the length
2235    we determine or if we are unable to determine the length or value,
2236    return false.  VISITED is a bitmap of visited variables.
2237    TYPE is 0 if string length should be returned, 1 for maximum string
2238    length and 2 for maximum value ARG can have.  */
2239
2240 static bool
2241 get_maxval_strlen (tree arg, tree *length, bitmap visited, int type)
2242 {
2243   tree var, def_stmt, val;
2244   
2245   if (TREE_CODE (arg) != SSA_NAME)
2246     {
2247       if (TREE_CODE (arg) == COND_EXPR)
2248         return get_maxval_strlen (COND_EXPR_THEN (arg), length, visited, type)
2249                && get_maxval_strlen (COND_EXPR_ELSE (arg), length, visited, type);
2250       /* We can end up with &(*iftmp_1)[0] here as well, so handle it.  */
2251       else if (TREE_CODE (arg) == ADDR_EXPR
2252                && TREE_CODE (TREE_OPERAND (arg, 0)) == ARRAY_REF
2253                && integer_zerop (TREE_OPERAND (TREE_OPERAND (arg, 0), 1)))
2254         {
2255           tree aop0 = TREE_OPERAND (TREE_OPERAND (arg, 0), 0);
2256           if (TREE_CODE (aop0) == INDIRECT_REF
2257               && TREE_CODE (TREE_OPERAND (aop0, 0)) == SSA_NAME)
2258             return get_maxval_strlen (TREE_OPERAND (aop0, 0),
2259                                       length, visited, type);
2260         }
2261
2262       if (type == 2)
2263         {
2264           val = arg;
2265           if (TREE_CODE (val) != INTEGER_CST
2266               || tree_int_cst_sgn (val) < 0)
2267             return false;
2268         }
2269       else
2270         val = c_strlen (arg, 1);
2271       if (!val)
2272         return false;
2273
2274       if (*length)
2275         {
2276           if (type > 0)
2277             {
2278               if (TREE_CODE (*length) != INTEGER_CST
2279                   || TREE_CODE (val) != INTEGER_CST)
2280                 return false;
2281
2282               if (tree_int_cst_lt (*length, val))
2283                 *length = val;
2284               return true;
2285             }
2286           else if (simple_cst_equal (val, *length) != 1)
2287             return false;
2288         }
2289
2290       *length = val;
2291       return true;
2292     }
2293
2294   /* If we were already here, break the infinite cycle.  */
2295   if (bitmap_bit_p (visited, SSA_NAME_VERSION (arg)))
2296     return true;
2297   bitmap_set_bit (visited, SSA_NAME_VERSION (arg));
2298
2299   var = arg;
2300   def_stmt = SSA_NAME_DEF_STMT (var);
2301
2302   switch (TREE_CODE (def_stmt))
2303     {
2304       case GIMPLE_MODIFY_STMT:
2305         {
2306           tree rhs;
2307
2308           /* The RHS of the statement defining VAR must either have a
2309              constant length or come from another SSA_NAME with a constant
2310              length.  */
2311           rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
2312           STRIP_NOPS (rhs);
2313           return get_maxval_strlen (rhs, length, visited, type);
2314         }
2315
2316       case PHI_NODE:
2317         {
2318           /* All the arguments of the PHI node must have the same constant
2319              length.  */
2320           int i;
2321
2322           for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
2323             {
2324               tree arg = PHI_ARG_DEF (def_stmt, i);
2325
2326               /* If this PHI has itself as an argument, we cannot
2327                  determine the string length of this argument.  However,
2328                  if we can find a constant string length for the other
2329                  PHI args then we can still be sure that this is a
2330                  constant string length.  So be optimistic and just
2331                  continue with the next argument.  */
2332               if (arg == PHI_RESULT (def_stmt))
2333                 continue;
2334
2335               if (!get_maxval_strlen (arg, length, visited, type))
2336                 return false;
2337             }
2338
2339           return true;
2340         }
2341
2342       default:
2343         break;
2344     }
2345
2346
2347   return false;
2348 }
2349
2350
2351 /* Fold builtin call FN in statement STMT.  If it cannot be folded into a
2352    constant, return NULL_TREE.  Otherwise, return its constant value.  */
2353
2354 static tree
2355 ccp_fold_builtin (tree stmt, tree fn)
2356 {
2357   tree result, val[3];
2358   tree callee, a;
2359   int arg_mask, i, type;
2360   bitmap visited;
2361   bool ignore;
2362   call_expr_arg_iterator iter;
2363   int nargs;
2364
2365   ignore = TREE_CODE (stmt) != GIMPLE_MODIFY_STMT;
2366
2367   /* First try the generic builtin folder.  If that succeeds, return the
2368      result directly.  */
2369   result = fold_call_expr (fn, ignore);
2370   if (result)
2371     {
2372       if (ignore)
2373         STRIP_NOPS (result);
2374       return result;
2375     }
2376
2377   /* Ignore MD builtins.  */
2378   callee = get_callee_fndecl (fn);
2379   if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_MD)
2380     return NULL_TREE;
2381
2382   /* If the builtin could not be folded, and it has no argument list,
2383      we're done.  */
2384   nargs = call_expr_nargs (fn);
2385   if (nargs == 0)
2386     return NULL_TREE;
2387
2388   /* Limit the work only for builtins we know how to simplify.  */
2389   switch (DECL_FUNCTION_CODE (callee))
2390     {
2391     case BUILT_IN_STRLEN:
2392     case BUILT_IN_FPUTS:
2393     case BUILT_IN_FPUTS_UNLOCKED:
2394       arg_mask = 1;
2395       type = 0;
2396       break;
2397     case BUILT_IN_STRCPY:
2398     case BUILT_IN_STRNCPY:
2399       arg_mask = 2;
2400       type = 0;
2401       break;
2402     case BUILT_IN_MEMCPY_CHK:
2403     case BUILT_IN_MEMPCPY_CHK:
2404     case BUILT_IN_MEMMOVE_CHK:
2405     case BUILT_IN_MEMSET_CHK:
2406     case BUILT_IN_STRNCPY_CHK:
2407       arg_mask = 4;
2408       type = 2;
2409       break;
2410     case BUILT_IN_STRCPY_CHK:
2411     case BUILT_IN_STPCPY_CHK:
2412       arg_mask = 2;
2413       type = 1;
2414       break;
2415     case BUILT_IN_SNPRINTF_CHK:
2416     case BUILT_IN_VSNPRINTF_CHK:
2417       arg_mask = 2;
2418       type = 2;
2419       break;
2420     default:
2421       return NULL_TREE;
2422     }
2423
2424   /* Try to use the dataflow information gathered by the CCP process.  */
2425   visited = BITMAP_ALLOC (NULL);
2426
2427   memset (val, 0, sizeof (val));
2428   init_call_expr_arg_iterator (fn, &iter);
2429   for (i = 0; arg_mask; i++, arg_mask >>= 1)
2430     {
2431       a = next_call_expr_arg (&iter);
2432       if (arg_mask & 1)
2433         {
2434           bitmap_clear (visited);
2435           if (!get_maxval_strlen (a, &val[i], visited, type))
2436             val[i] = NULL_TREE;
2437         }
2438     }
2439
2440   BITMAP_FREE (visited);
2441
2442   result = NULL_TREE;
2443   switch (DECL_FUNCTION_CODE (callee))
2444     {
2445     case BUILT_IN_STRLEN:
2446       if (val[0])
2447         {
2448           tree new_val = fold_convert (TREE_TYPE (fn), val[0]);
2449
2450           /* If the result is not a valid gimple value, or not a cast
2451              of a valid gimple value, then we can not use the result.  */
2452           if (is_gimple_val (new_val)
2453               || (is_gimple_cast (new_val)
2454                   && is_gimple_val (TREE_OPERAND (new_val, 0))))
2455             return new_val;
2456         }
2457       break;
2458
2459     case BUILT_IN_STRCPY:
2460       if (val[1] && is_gimple_val (val[1]) && nargs == 2)
2461         result = fold_builtin_strcpy (callee,
2462                                       CALL_EXPR_ARG (fn, 0),
2463                                       CALL_EXPR_ARG (fn, 1),
2464                                       val[1]);
2465       break;
2466
2467     case BUILT_IN_STRNCPY:
2468       if (val[1] && is_gimple_val (val[1]) && nargs == 3)
2469         result = fold_builtin_strncpy (callee,
2470                                        CALL_EXPR_ARG (fn, 0),
2471                                        CALL_EXPR_ARG (fn, 1),
2472                                        CALL_EXPR_ARG (fn, 2),
2473                                        val[1]);
2474       break;
2475
2476     case BUILT_IN_FPUTS:
2477       result = fold_builtin_fputs (CALL_EXPR_ARG (fn, 0),
2478                                    CALL_EXPR_ARG (fn, 1),
2479                                    TREE_CODE (stmt) != GIMPLE_MODIFY_STMT, 0,
2480                                    val[0]);
2481       break;
2482
2483     case BUILT_IN_FPUTS_UNLOCKED:
2484       result = fold_builtin_fputs (CALL_EXPR_ARG (fn, 0),
2485                                    CALL_EXPR_ARG (fn, 1),
2486                                    TREE_CODE (stmt) != GIMPLE_MODIFY_STMT, 1,
2487                                    val[0]);
2488       break;
2489
2490     case BUILT_IN_MEMCPY_CHK:
2491     case BUILT_IN_MEMPCPY_CHK:
2492     case BUILT_IN_MEMMOVE_CHK:
2493     case BUILT_IN_MEMSET_CHK:
2494       if (val[2] && is_gimple_val (val[2]))
2495         result = fold_builtin_memory_chk (callee,
2496                                           CALL_EXPR_ARG (fn, 0),
2497                                           CALL_EXPR_ARG (fn, 1),
2498                                           CALL_EXPR_ARG (fn, 2),
2499                                           CALL_EXPR_ARG (fn, 3),
2500                                           val[2], ignore,
2501                                           DECL_FUNCTION_CODE (callee));
2502       break;
2503
2504     case BUILT_IN_STRCPY_CHK:
2505     case BUILT_IN_STPCPY_CHK:
2506       if (val[1] && is_gimple_val (val[1]))
2507         result = fold_builtin_stxcpy_chk (callee,
2508                                           CALL_EXPR_ARG (fn, 0),
2509                                           CALL_EXPR_ARG (fn, 1),
2510                                           CALL_EXPR_ARG (fn, 2),
2511                                           val[1], ignore,
2512                                           DECL_FUNCTION_CODE (callee));
2513       break;
2514
2515     case BUILT_IN_STRNCPY_CHK:
2516       if (val[2] && is_gimple_val (val[2]))
2517         result = fold_builtin_strncpy_chk (CALL_EXPR_ARG (fn, 0),
2518                                            CALL_EXPR_ARG (fn, 1),
2519                                            CALL_EXPR_ARG (fn, 2),
2520                                            CALL_EXPR_ARG (fn, 3),
2521                                            val[2]);
2522       break;
2523
2524     case BUILT_IN_SNPRINTF_CHK:
2525     case BUILT_IN_VSNPRINTF_CHK:
2526       if (val[1] && is_gimple_val (val[1]))
2527         result = fold_builtin_snprintf_chk (fn, val[1],
2528                                             DECL_FUNCTION_CODE (callee));
2529       break;
2530
2531     default:
2532       gcc_unreachable ();
2533     }
2534
2535   if (result && ignore)
2536     result = fold_ignored_result (result);
2537   return result;
2538 }
2539
2540
2541 /* Fold the statement pointed to by STMT_P.  In some cases, this function may
2542    replace the whole statement with a new one.  Returns true iff folding
2543    makes any changes.  */
2544
2545 bool
2546 fold_stmt (tree *stmt_p)
2547 {
2548   tree rhs, result, stmt;
2549   struct fold_stmt_r_data fold_stmt_r_data;
2550   bool changed = false;
2551   bool inside_addr_expr = false;
2552
2553   stmt = *stmt_p;
2554
2555   fold_stmt_r_data.stmt = stmt;
2556   fold_stmt_r_data.changed_p = &changed;
2557   fold_stmt_r_data.inside_addr_expr_p = &inside_addr_expr;
2558
2559   /* If we replaced constants and the statement makes pointer dereferences,
2560      then we may need to fold instances of *&VAR into VAR, etc.  */
2561   if (walk_tree (stmt_p, fold_stmt_r, &fold_stmt_r_data, NULL))
2562     {
2563       *stmt_p = build_call_expr (implicit_built_in_decls[BUILT_IN_TRAP], 0);
2564       return true;
2565     }
2566
2567   rhs = get_rhs (stmt);
2568   if (!rhs)
2569     return changed;
2570   result = NULL_TREE;
2571
2572   if (TREE_CODE (rhs) == CALL_EXPR)
2573     {
2574       tree callee;
2575
2576       /* Check for builtins that CCP can handle using information not
2577          available in the generic fold routines.  */
2578       callee = get_callee_fndecl (rhs);
2579       if (callee && DECL_BUILT_IN (callee))
2580         result = ccp_fold_builtin (stmt, rhs);
2581       else
2582         {
2583           /* Check for resolvable OBJ_TYPE_REF.  The only sorts we can resolve
2584              here are when we've propagated the address of a decl into the
2585              object slot.  */
2586           /* ??? Should perhaps do this in fold proper.  However, doing it
2587              there requires that we create a new CALL_EXPR, and that requires
2588              copying EH region info to the new node.  Easier to just do it
2589              here where we can just smash the call operand. Also
2590              CALL_EXPR_RETURN_SLOT_OPT needs to be handled correctly and
2591              copied, fold_call_expr does not have not information. */
2592           callee = CALL_EXPR_FN (rhs);
2593           if (TREE_CODE (callee) == OBJ_TYPE_REF
2594               && lang_hooks.fold_obj_type_ref
2595               && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR
2596               && DECL_P (TREE_OPERAND
2597                          (OBJ_TYPE_REF_OBJECT (callee), 0)))
2598             {
2599               tree t;
2600
2601               /* ??? Caution: Broken ADDR_EXPR semantics means that
2602                  looking at the type of the operand of the addr_expr
2603                  can yield an array type.  See silly exception in
2604                  check_pointer_types_r.  */
2605
2606               t = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (callee)));
2607               t = lang_hooks.fold_obj_type_ref (callee, t);
2608               if (t)
2609                 {
2610                   CALL_EXPR_FN (rhs) = t;
2611                   changed = true;
2612                 }
2613             }
2614         }
2615     }
2616   else if (TREE_CODE (rhs) == COND_EXPR)
2617     {
2618       tree temp = fold (COND_EXPR_COND (rhs));
2619       if (temp != COND_EXPR_COND (rhs))
2620         result = fold_build3 (COND_EXPR, TREE_TYPE (rhs), temp,
2621                               COND_EXPR_THEN (rhs), COND_EXPR_ELSE (rhs));
2622     }
2623
2624   /* If we couldn't fold the RHS, hand over to the generic fold routines.  */
2625   if (result == NULL_TREE)
2626     result = fold (rhs);
2627
2628   /* Strip away useless type conversions.  Both the NON_LVALUE_EXPR that
2629      may have been added by fold, and "useless" type conversions that might
2630      now be apparent due to propagation.  */
2631   STRIP_USELESS_TYPE_CONVERSION (result);
2632
2633   if (result != rhs)
2634     changed |= set_rhs (stmt_p, result);
2635
2636   return changed;
2637 }
2638
2639 /* Perform the minimal folding on statement STMT.  Only operations like
2640    *&x created by constant propagation are handled.  The statement cannot
2641    be replaced with a new one.  */
2642
2643 bool
2644 fold_stmt_inplace (tree stmt)
2645 {
2646   tree old_stmt = stmt, rhs, new_rhs;
2647   struct fold_stmt_r_data fold_stmt_r_data;
2648   bool changed = false;
2649   bool inside_addr_expr = false;
2650
2651   fold_stmt_r_data.stmt = stmt;
2652   fold_stmt_r_data.changed_p = &changed;
2653   fold_stmt_r_data.inside_addr_expr_p = &inside_addr_expr;
2654
2655   walk_tree (&stmt, fold_stmt_r, &fold_stmt_r_data, NULL);
2656   gcc_assert (stmt == old_stmt);
2657
2658   rhs = get_rhs (stmt);
2659   if (!rhs || rhs == stmt)
2660     return changed;
2661
2662   new_rhs = fold (rhs);
2663   STRIP_USELESS_TYPE_CONVERSION (new_rhs);
2664   if (new_rhs == rhs)
2665     return changed;
2666
2667   changed |= set_rhs (&stmt, new_rhs);
2668   gcc_assert (stmt == old_stmt);
2669
2670   return changed;
2671 }
2672 \f
2673 /* Try to optimize out __builtin_stack_restore.  Optimize it out
2674    if there is another __builtin_stack_restore in the same basic
2675    block and no calls or ASM_EXPRs are in between, or if this block's
2676    only outgoing edge is to EXIT_BLOCK and there are no calls or
2677    ASM_EXPRs after this __builtin_stack_restore.  */
2678
2679 static tree
2680 optimize_stack_restore (basic_block bb, tree call, block_stmt_iterator i)
2681 {
2682   tree stack_save, stmt, callee;
2683
2684   if (TREE_CODE (call) != CALL_EXPR
2685       || call_expr_nargs (call) != 1
2686       || TREE_CODE (CALL_EXPR_ARG (call, 0)) != SSA_NAME
2687       || !POINTER_TYPE_P (TREE_TYPE (CALL_EXPR_ARG (call, 0))))
2688     return NULL_TREE;
2689
2690   for (bsi_next (&i); !bsi_end_p (i); bsi_next (&i))
2691     {
2692       tree call;
2693
2694       stmt = bsi_stmt (i);
2695       if (TREE_CODE (stmt) == ASM_EXPR)
2696         return NULL_TREE;
2697       call = get_call_expr_in (stmt);
2698       if (call == NULL)
2699         continue;
2700
2701       callee = get_callee_fndecl (call);
2702       if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
2703         return NULL_TREE;
2704
2705       if (DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_RESTORE)
2706         break;
2707     }
2708
2709   if (bsi_end_p (i)
2710       && (! single_succ_p (bb)
2711           || single_succ_edge (bb)->dest != EXIT_BLOCK_PTR))
2712     return NULL_TREE;
2713
2714   stack_save = SSA_NAME_DEF_STMT (CALL_EXPR_ARG (call, 0));
2715   if (TREE_CODE (stack_save) != GIMPLE_MODIFY_STMT
2716       || GIMPLE_STMT_OPERAND (stack_save, 0) != CALL_EXPR_ARG (call, 0)
2717       || TREE_CODE (GIMPLE_STMT_OPERAND (stack_save, 1)) != CALL_EXPR
2718       || tree_could_throw_p (stack_save)
2719       || !has_single_use (CALL_EXPR_ARG (call, 0)))
2720     return NULL_TREE;
2721
2722   callee = get_callee_fndecl (GIMPLE_STMT_OPERAND (stack_save, 1));
2723   if (!callee
2724       || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL
2725       || DECL_FUNCTION_CODE (callee) != BUILT_IN_STACK_SAVE
2726       || call_expr_nargs (GIMPLE_STMT_OPERAND (stack_save, 1)) != 0)
2727     return NULL_TREE;
2728
2729   stmt = stack_save;
2730   push_stmt_changes (&stmt);
2731   if (!set_rhs (&stmt,
2732                 build_int_cst (TREE_TYPE (CALL_EXPR_ARG (call, 0)), 0)))
2733     {
2734       discard_stmt_changes (&stmt);
2735       return NULL_TREE;
2736     }
2737   gcc_assert (stmt == stack_save);
2738   pop_stmt_changes (&stmt);
2739
2740   return integer_zero_node;
2741 }
2742 \f
2743 /* If va_list type is a simple pointer and nothing special is needed,
2744    optimize __builtin_va_start (&ap, 0) into ap = __builtin_next_arg (0),
2745    __builtin_va_end (&ap) out as NOP and __builtin_va_copy into a simple
2746    pointer assignment.  */
2747
2748 static tree
2749 optimize_stdarg_builtin (tree call)
2750 {
2751   tree callee, lhs, rhs;
2752   bool va_list_simple_ptr;
2753
2754   if (TREE_CODE (call) != CALL_EXPR)
2755     return NULL_TREE;
2756
2757   va_list_simple_ptr = POINTER_TYPE_P (va_list_type_node)
2758                        && (TREE_TYPE (va_list_type_node) == void_type_node
2759                            || TREE_TYPE (va_list_type_node) == char_type_node);
2760
2761   callee = get_callee_fndecl (call);
2762   switch (DECL_FUNCTION_CODE (callee))
2763     {
2764     case BUILT_IN_VA_START:
2765       if (!va_list_simple_ptr
2766           || targetm.expand_builtin_va_start != NULL
2767           || built_in_decls[BUILT_IN_NEXT_ARG] == NULL)
2768         return NULL_TREE;
2769
2770       if (call_expr_nargs (call) != 2)
2771         return NULL_TREE;
2772
2773       lhs = CALL_EXPR_ARG (call, 0);
2774       if (!POINTER_TYPE_P (TREE_TYPE (lhs))
2775           || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs)))
2776              != TYPE_MAIN_VARIANT (va_list_type_node))
2777         return NULL_TREE;
2778
2779       lhs = build_fold_indirect_ref (lhs);
2780       rhs = build_call_expr (built_in_decls[BUILT_IN_NEXT_ARG],
2781                              1, integer_zero_node);
2782       rhs = fold_convert (TREE_TYPE (lhs), rhs);
2783       return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
2784
2785     case BUILT_IN_VA_COPY:
2786       if (!va_list_simple_ptr)
2787         return NULL_TREE;
2788
2789       if (call_expr_nargs (call) != 2)
2790         return NULL_TREE;
2791
2792       lhs = CALL_EXPR_ARG (call, 0);
2793       if (!POINTER_TYPE_P (TREE_TYPE (lhs))
2794           || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs)))
2795              != TYPE_MAIN_VARIANT (va_list_type_node))
2796         return NULL_TREE;
2797
2798       lhs = build_fold_indirect_ref (lhs);
2799       rhs = CALL_EXPR_ARG (call, 1);
2800       if (TYPE_MAIN_VARIANT (TREE_TYPE (rhs))
2801           != TYPE_MAIN_VARIANT (va_list_type_node))
2802         return NULL_TREE;
2803
2804       rhs = fold_convert (TREE_TYPE (lhs), rhs);
2805       return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
2806
2807     case BUILT_IN_VA_END:
2808       return integer_zero_node;
2809
2810     default:
2811       gcc_unreachable ();
2812     }
2813 }
2814 \f
2815 /* Convert EXPR into a GIMPLE value suitable for substitution on the
2816    RHS of an assignment.  Insert the necessary statements before
2817    iterator *SI_P. 
2818    When IGNORE is set, don't worry about the return value.  */
2819
2820 static tree
2821 convert_to_gimple_builtin (block_stmt_iterator *si_p, tree expr, bool ignore)
2822 {
2823   tree_stmt_iterator ti;
2824   tree stmt = bsi_stmt (*si_p);
2825   tree tmp, stmts = NULL;
2826
2827   push_gimplify_context ();
2828   if (ignore)
2829     {
2830       tmp = build_empty_stmt ();
2831       gimplify_and_add (expr, &stmts);
2832     }
2833   else
2834     tmp = get_initialized_tmp_var (expr, &stmts, NULL);
2835   pop_gimplify_context (NULL);
2836
2837   if (EXPR_HAS_LOCATION (stmt))
2838     annotate_all_with_locus (&stmts, EXPR_LOCATION (stmt));
2839
2840   /* The replacement can expose previously unreferenced variables.  */
2841   for (ti = tsi_start (stmts); !tsi_end_p (ti); tsi_next (&ti))
2842     {
2843       tree new_stmt = tsi_stmt (ti);
2844       find_new_referenced_vars (tsi_stmt_ptr (ti));
2845       bsi_insert_before (si_p, new_stmt, BSI_NEW_STMT);
2846       mark_symbols_for_renaming (new_stmt);
2847       bsi_next (si_p);
2848     }
2849
2850   return tmp;
2851 }
2852
2853
2854 /* A simple pass that attempts to fold all builtin functions.  This pass
2855    is run after we've propagated as many constants as we can.  */
2856
2857 static unsigned int
2858 execute_fold_all_builtins (void)
2859 {
2860   bool cfg_changed = false;
2861   basic_block bb;
2862   unsigned int todoflags = 0;
2863   
2864   FOR_EACH_BB (bb)
2865     {
2866       block_stmt_iterator i;
2867       for (i = bsi_start (bb); !bsi_end_p (i); )
2868         {
2869           tree *stmtp = bsi_stmt_ptr (i);
2870           tree old_stmt = *stmtp;
2871           tree call = get_rhs (*stmtp);
2872           tree callee, result;
2873           enum built_in_function fcode;
2874
2875           if (!call || TREE_CODE (call) != CALL_EXPR)
2876             {
2877               bsi_next (&i);
2878               continue;
2879             }
2880           callee = get_callee_fndecl (call);
2881           if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
2882             {
2883               bsi_next (&i);
2884               continue;
2885             }
2886           fcode = DECL_FUNCTION_CODE (callee);
2887
2888           result = ccp_fold_builtin (*stmtp, call);
2889
2890           if (result)
2891             gimple_remove_stmt_histograms (cfun, *stmtp);
2892
2893           if (!result)
2894             switch (DECL_FUNCTION_CODE (callee))
2895               {
2896               case BUILT_IN_CONSTANT_P:
2897                 /* Resolve __builtin_constant_p.  If it hasn't been
2898                    folded to integer_one_node by now, it's fairly
2899                    certain that the value simply isn't constant.  */
2900                 result = integer_zero_node;
2901                 break;
2902
2903               case BUILT_IN_STACK_RESTORE:
2904                 result = optimize_stack_restore (bb, *stmtp, i);
2905                 if (result)
2906                   break;
2907                 bsi_next (&i);
2908                 continue;
2909
2910               case BUILT_IN_VA_START:
2911               case BUILT_IN_VA_END:
2912               case BUILT_IN_VA_COPY:
2913                 /* These shouldn't be folded before pass_stdarg.  */
2914                 result = optimize_stdarg_builtin (*stmtp);
2915                 if (result)
2916                   break;
2917                 /* FALLTHRU */
2918
2919               default:
2920                 bsi_next (&i);
2921                 continue;
2922               }
2923
2924           if (dump_file && (dump_flags & TDF_DETAILS))
2925             {
2926               fprintf (dump_file, "Simplified\n  ");
2927               print_generic_stmt (dump_file, *stmtp, dump_flags);
2928             }
2929
2930           push_stmt_changes (stmtp);
2931
2932           if (!set_rhs (stmtp, result))
2933             {
2934               result = convert_to_gimple_builtin (&i, result,
2935                                                   TREE_CODE (old_stmt)
2936                                                   != GIMPLE_MODIFY_STMT);
2937               if (result)
2938                 {
2939                   bool ok = set_rhs (stmtp, result);
2940                   gcc_assert (ok);
2941                   todoflags |= TODO_rebuild_alias;
2942                 }
2943             }
2944
2945           pop_stmt_changes (stmtp);
2946
2947           if (maybe_clean_or_replace_eh_stmt (old_stmt, *stmtp)
2948               && tree_purge_dead_eh_edges (bb))
2949             cfg_changed = true;
2950
2951           if (dump_file && (dump_flags & TDF_DETAILS))
2952             {
2953               fprintf (dump_file, "to\n  ");
2954               print_generic_stmt (dump_file, *stmtp, dump_flags);
2955               fprintf (dump_file, "\n");
2956             }
2957
2958           /* Retry the same statement if it changed into another
2959              builtin, there might be new opportunities now.  */
2960           call = get_rhs (*stmtp);
2961           if (!call || TREE_CODE (call) != CALL_EXPR)
2962             {
2963               bsi_next (&i);
2964               continue;
2965             }
2966           callee = get_callee_fndecl (call);
2967           if (!callee
2968               || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL
2969               || DECL_FUNCTION_CODE (callee) == fcode)
2970             bsi_next (&i);
2971         }
2972     }
2973   
2974   /* Delete unreachable blocks.  */
2975   if (cfg_changed)
2976     todoflags |= TODO_cleanup_cfg;
2977   
2978   return todoflags;
2979 }
2980
2981
2982 struct gimple_opt_pass pass_fold_builtins = 
2983 {
2984  {
2985   GIMPLE_PASS,
2986   "fab",                                /* name */
2987   NULL,                                 /* gate */
2988   execute_fold_all_builtins,            /* execute */
2989   NULL,                                 /* sub */
2990   NULL,                                 /* next */
2991   0,                                    /* static_pass_number */
2992   0,                                    /* tv_id */
2993   PROP_cfg | PROP_ssa,                  /* properties_required */
2994   0,                                    /* properties_provided */
2995   0,                                    /* properties_destroyed */
2996   0,                                    /* todo_flags_start */
2997   TODO_dump_func
2998     | TODO_verify_ssa
2999     | TODO_update_ssa                   /* todo_flags_finish */
3000  }
3001 };