OSDN Git Service

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