OSDN Git Service

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