OSDN Git Service

d4a7a31c1017623f85d7f3173f189954f4a0276b
[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, 2008, 2009,
3    2010 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 "tm_p.h"
195 #include "basic-block.h"
196 #include "output.h"
197 #include "expr.h"
198 #include "function.h"
199 #include "diagnostic.h"
200 #include "tree-pretty-print.h"
201 #include "gimple-pretty-print.h"
202 #include "timevar.h"
203 #include "tree-dump.h"
204 #include "tree-flow.h"
205 #include "tree-pass.h"
206 #include "tree-ssa-propagate.h"
207 #include "value-prof.h"
208 #include "langhooks.h"
209 #include "target.h"
210 #include "toplev.h"
211 #include "dbgcnt.h"
212
213
214 /* Possible lattice values.  */
215 typedef enum
216 {
217   UNINITIALIZED,
218   UNDEFINED,
219   CONSTANT,
220   VARYING
221 } ccp_lattice_t;
222
223 /* Array of propagated constant values.  After propagation,
224    CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I).  If
225    the constant is held in an SSA name representing a memory store
226    (i.e., a VDEF), CONST_VAL[I].MEM_REF will contain the actual
227    memory reference used to store (i.e., the LHS of the assignment
228    doing the store).  */
229 static prop_value_t *const_val;
230
231 static void canonicalize_float_value (prop_value_t *);
232 static bool ccp_fold_stmt (gimple_stmt_iterator *);
233
234 /* Dump constant propagation value VAL to file OUTF prefixed by PREFIX.  */
235
236 static void
237 dump_lattice_value (FILE *outf, const char *prefix, prop_value_t val)
238 {
239   switch (val.lattice_val)
240     {
241     case UNINITIALIZED:
242       fprintf (outf, "%sUNINITIALIZED", prefix);
243       break;
244     case UNDEFINED:
245       fprintf (outf, "%sUNDEFINED", prefix);
246       break;
247     case VARYING:
248       fprintf (outf, "%sVARYING", prefix);
249       break;
250     case CONSTANT:
251       fprintf (outf, "%sCONSTANT ", prefix);
252       print_generic_expr (outf, val.value, dump_flags);
253       break;
254     default:
255       gcc_unreachable ();
256     }
257 }
258
259
260 /* Print lattice value VAL to stderr.  */
261
262 void debug_lattice_value (prop_value_t val);
263
264 void
265 debug_lattice_value (prop_value_t val)
266 {
267   dump_lattice_value (stderr, "", val);
268   fprintf (stderr, "\n");
269 }
270
271
272 /* Compute a default value for variable VAR and store it in the
273    CONST_VAL array.  The following rules are used to get default
274    values:
275
276    1- Global and static variables that are declared constant are
277       considered CONSTANT.
278
279    2- Any other value is considered UNDEFINED.  This is useful when
280       considering PHI nodes.  PHI arguments that are undefined do not
281       change the constant value of the PHI node, which allows for more
282       constants to be propagated.
283
284    3- Variables defined by statements other than assignments and PHI
285       nodes are considered VARYING.
286
287    4- Initial values of variables that are not GIMPLE registers are
288       considered VARYING.  */
289
290 static prop_value_t
291 get_default_value (tree var)
292 {
293   tree sym = SSA_NAME_VAR (var);
294   prop_value_t val = { UNINITIALIZED, NULL_TREE };
295   gimple stmt;
296
297   stmt = SSA_NAME_DEF_STMT (var);
298
299   if (gimple_nop_p (stmt))
300     {
301       /* Variables defined by an empty statement are those used
302          before being initialized.  If VAR is a local variable, we
303          can assume initially that it is UNDEFINED, otherwise we must
304          consider it VARYING.  */
305       if (is_gimple_reg (sym) && TREE_CODE (sym) != PARM_DECL)
306         val.lattice_val = UNDEFINED;
307       else
308         val.lattice_val = VARYING;
309     }
310   else if (is_gimple_assign (stmt)
311            /* Value-returning GIMPLE_CALL statements assign to
312               a variable, and are treated similarly to GIMPLE_ASSIGN.  */
313            || (is_gimple_call (stmt)
314                && gimple_call_lhs (stmt) != NULL_TREE)
315            || gimple_code (stmt) == GIMPLE_PHI)
316     {
317       tree cst;
318       if (gimple_assign_single_p (stmt)
319           && DECL_P (gimple_assign_rhs1 (stmt))
320           && (cst = get_symbol_constant_value (gimple_assign_rhs1 (stmt))))
321         {
322           val.lattice_val = CONSTANT;
323           val.value = cst;
324         }
325       else
326         /* Any other variable defined by an assignment or a PHI node
327            is considered UNDEFINED.  */
328         val.lattice_val = UNDEFINED;
329     }
330   else
331     {
332       /* Otherwise, VAR will never take on a constant value.  */
333       val.lattice_val = VARYING;
334     }
335
336   return val;
337 }
338
339
340 /* Get the constant value associated with variable VAR.  */
341
342 static inline prop_value_t *
343 get_value (tree var)
344 {
345   prop_value_t *val;
346
347   if (const_val == NULL)
348     return NULL;
349
350   val = &const_val[SSA_NAME_VERSION (var)];
351   if (val->lattice_val == UNINITIALIZED)
352     *val = get_default_value (var);
353
354   canonicalize_float_value (val);
355
356   return val;
357 }
358
359 /* Sets the value associated with VAR to VARYING.  */
360
361 static inline void
362 set_value_varying (tree var)
363 {
364   prop_value_t *val = &const_val[SSA_NAME_VERSION (var)];
365
366   val->lattice_val = VARYING;
367   val->value = NULL_TREE;
368 }
369
370 /* For float types, modify the value of VAL to make ccp work correctly
371    for non-standard values (-0, NaN):
372
373    If HONOR_SIGNED_ZEROS is false, and VAL = -0, we canonicalize it to 0.
374    If HONOR_NANS is false, and VAL is NaN, we canonicalize it to UNDEFINED.
375      This is to fix the following problem (see PR 29921): Suppose we have
376
377      x = 0.0 * y
378
379      and we set value of y to NaN.  This causes value of x to be set to NaN.
380      When we later determine that y is in fact VARYING, fold uses the fact
381      that HONOR_NANS is false, and we try to change the value of x to 0,
382      causing an ICE.  With HONOR_NANS being false, the real appearance of
383      NaN would cause undefined behavior, though, so claiming that y (and x)
384      are UNDEFINED initially is correct.  */
385
386 static void
387 canonicalize_float_value (prop_value_t *val)
388 {
389   enum machine_mode mode;
390   tree type;
391   REAL_VALUE_TYPE d;
392
393   if (val->lattice_val != CONSTANT
394       || TREE_CODE (val->value) != REAL_CST)
395     return;
396
397   d = TREE_REAL_CST (val->value);
398   type = TREE_TYPE (val->value);
399   mode = TYPE_MODE (type);
400
401   if (!HONOR_SIGNED_ZEROS (mode)
402       && REAL_VALUE_MINUS_ZERO (d))
403     {
404       val->value = build_real (type, dconst0);
405       return;
406     }
407
408   if (!HONOR_NANS (mode)
409       && REAL_VALUE_ISNAN (d))
410     {
411       val->lattice_val = UNDEFINED;
412       val->value = NULL;
413       return;
414     }
415 }
416
417 /* Set the value for variable VAR to NEW_VAL.  Return true if the new
418    value is different from VAR's previous value.  */
419
420 static bool
421 set_lattice_value (tree var, prop_value_t new_val)
422 {
423   prop_value_t *old_val = get_value (var);
424
425   canonicalize_float_value (&new_val);
426
427   /* Lattice transitions must always be monotonically increasing in
428      value.  If *OLD_VAL and NEW_VAL are the same, return false to
429      inform the caller that this was a non-transition.  */
430
431   gcc_assert (old_val->lattice_val < new_val.lattice_val
432               || (old_val->lattice_val == new_val.lattice_val
433                   && ((!old_val->value && !new_val.value)
434                       || operand_equal_p (old_val->value, new_val.value, 0))));
435
436   if (old_val->lattice_val != new_val.lattice_val)
437     {
438       if (dump_file && (dump_flags & TDF_DETAILS))
439         {
440           dump_lattice_value (dump_file, "Lattice value changed to ", new_val);
441           fprintf (dump_file, ".  Adding SSA edges to worklist.\n");
442         }
443
444       *old_val = new_val;
445
446       gcc_assert (new_val.lattice_val != UNDEFINED);
447       return true;
448     }
449
450   return false;
451 }
452
453
454 /* Return the likely CCP lattice value for STMT.
455
456    If STMT has no operands, then return CONSTANT.
457
458    Else if undefinedness of operands of STMT cause its value to be
459    undefined, then return UNDEFINED.
460
461    Else if any operands of STMT are constants, then return CONSTANT.
462
463    Else return VARYING.  */
464
465 static ccp_lattice_t
466 likely_value (gimple stmt)
467 {
468   bool has_constant_operand, has_undefined_operand, all_undefined_operands;
469   tree use;
470   ssa_op_iter iter;
471   unsigned i;
472
473   enum gimple_code code = gimple_code (stmt);
474
475   /* This function appears to be called only for assignments, calls,
476      conditionals, and switches, due to the logic in visit_stmt.  */
477   gcc_assert (code == GIMPLE_ASSIGN
478               || code == GIMPLE_CALL
479               || code == GIMPLE_COND
480               || code == GIMPLE_SWITCH);
481
482   /* If the statement has volatile operands, it won't fold to a
483      constant value.  */
484   if (gimple_has_volatile_ops (stmt))
485     return VARYING;
486
487   /* Arrive here for more complex cases.  */
488   has_constant_operand = false;
489   has_undefined_operand = false;
490   all_undefined_operands = true;
491   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
492     {
493       prop_value_t *val = get_value (use);
494
495       if (val->lattice_val == UNDEFINED)
496         has_undefined_operand = true;
497       else
498         all_undefined_operands = false;
499
500       if (val->lattice_val == CONSTANT)
501         has_constant_operand = true;
502     }
503
504   /* There may be constants in regular rhs operands.  For calls we
505      have to ignore lhs, fndecl and static chain, otherwise only
506      the lhs.  */
507   for (i = (is_gimple_call (stmt) ? 2 : 0) + gimple_has_lhs (stmt);
508        i < gimple_num_ops (stmt); ++i)
509     {
510       tree op = gimple_op (stmt, i);
511       if (!op || TREE_CODE (op) == SSA_NAME)
512         continue;
513       if (is_gimple_min_invariant (op))
514         has_constant_operand = true;
515     }
516
517   if (has_constant_operand)
518     all_undefined_operands = false;
519
520   /* If the operation combines operands like COMPLEX_EXPR make sure to
521      not mark the result UNDEFINED if only one part of the result is
522      undefined.  */
523   if (has_undefined_operand && all_undefined_operands)
524     return UNDEFINED;
525   else if (code == GIMPLE_ASSIGN && has_undefined_operand)
526     {
527       switch (gimple_assign_rhs_code (stmt))
528         {
529         /* Unary operators are handled with all_undefined_operands.  */
530         case PLUS_EXPR:
531         case MINUS_EXPR:
532         case POINTER_PLUS_EXPR:
533           /* Not MIN_EXPR, MAX_EXPR.  One VARYING operand may be selected.
534              Not bitwise operators, one VARYING operand may specify the
535              result completely.  Not logical operators for the same reason.
536              Not COMPLEX_EXPR as one VARYING operand makes the result partly
537              not UNDEFINED.  Not *DIV_EXPR, comparisons and shifts because
538              the undefined operand may be promoted.  */
539           return UNDEFINED;
540
541         default:
542           ;
543         }
544     }
545   /* If there was an UNDEFINED operand but the result may be not UNDEFINED
546      fall back to VARYING even if there were CONSTANT operands.  */
547   if (has_undefined_operand)
548     return VARYING;
549
550   /* We do not consider virtual operands here -- load from read-only
551      memory may have only VARYING virtual operands, but still be
552      constant.  */
553   if (has_constant_operand
554       || gimple_references_memory_p (stmt))
555     return CONSTANT;
556
557   return VARYING;
558 }
559
560 /* Returns true if STMT cannot be constant.  */
561
562 static bool
563 surely_varying_stmt_p (gimple stmt)
564 {
565   /* If the statement has operands that we cannot handle, it cannot be
566      constant.  */
567   if (gimple_has_volatile_ops (stmt))
568     return true;
569
570   /* If it is a call and does not return a value or is not a
571      builtin and not an indirect call, it is varying.  */
572   if (is_gimple_call (stmt))
573     {
574       tree fndecl;
575       if (!gimple_call_lhs (stmt)
576           || ((fndecl = gimple_call_fndecl (stmt)) != NULL_TREE
577               && !DECL_BUILT_IN (fndecl)))
578         return true;
579     }
580
581   /* Any other store operation is not interesting.  */
582   else if (gimple_vdef (stmt))
583     return true;
584
585   /* Anything other than assignments and conditional jumps are not
586      interesting for CCP.  */
587   if (gimple_code (stmt) != GIMPLE_ASSIGN
588       && gimple_code (stmt) != GIMPLE_COND
589       && gimple_code (stmt) != GIMPLE_SWITCH
590       && gimple_code (stmt) != GIMPLE_CALL)
591     return true;
592
593   return false;
594 }
595
596 /* Initialize local data structures for CCP.  */
597
598 static void
599 ccp_initialize (void)
600 {
601   basic_block bb;
602
603   const_val = XCNEWVEC (prop_value_t, num_ssa_names);
604
605   /* Initialize simulation flags for PHI nodes and statements.  */
606   FOR_EACH_BB (bb)
607     {
608       gimple_stmt_iterator i;
609
610       for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
611         {
612           gimple stmt = gsi_stmt (i);
613           bool is_varying;
614
615           /* If the statement is a control insn, then we do not
616              want to avoid simulating the statement once.  Failure
617              to do so means that those edges will never get added.  */
618           if (stmt_ends_bb_p (stmt))
619             is_varying = false;
620           else
621             is_varying = surely_varying_stmt_p (stmt);
622
623           if (is_varying)
624             {
625               tree def;
626               ssa_op_iter iter;
627
628               /* If the statement will not produce a constant, mark
629                  all its outputs VARYING.  */
630               FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
631                 set_value_varying (def);
632             }
633           prop_set_simulate_again (stmt, !is_varying);
634         }
635     }
636
637   /* Now process PHI nodes.  We never clear the simulate_again flag on
638      phi nodes, since we do not know which edges are executable yet,
639      except for phi nodes for virtual operands when we do not do store ccp.  */
640   FOR_EACH_BB (bb)
641     {
642       gimple_stmt_iterator i;
643
644       for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
645         {
646           gimple phi = gsi_stmt (i);
647
648           if (!is_gimple_reg (gimple_phi_result (phi)))
649             prop_set_simulate_again (phi, false);
650           else
651             prop_set_simulate_again (phi, true);
652         }
653     }
654 }
655
656 /* Debug count support. Reset the values of ssa names
657    VARYING when the total number ssa names analyzed is
658    beyond the debug count specified.  */
659
660 static void
661 do_dbg_cnt (void)
662 {
663   unsigned i;
664   for (i = 0; i < num_ssa_names; i++)
665     {
666       if (!dbg_cnt (ccp))
667         {
668           const_val[i].lattice_val = VARYING;
669           const_val[i].value = NULL_TREE;
670         }
671     }
672 }
673
674
675 /* Do final substitution of propagated values, cleanup the flowgraph and
676    free allocated storage.
677
678    Return TRUE when something was optimized.  */
679
680 static bool
681 ccp_finalize (void)
682 {
683   bool something_changed;
684
685   do_dbg_cnt ();
686   /* Perform substitutions based on the known constant values.  */
687   something_changed = substitute_and_fold (const_val, ccp_fold_stmt);
688
689   free (const_val);
690   const_val = NULL;
691   return something_changed;;
692 }
693
694
695 /* Compute the meet operator between *VAL1 and *VAL2.  Store the result
696    in VAL1.
697
698                 any  M UNDEFINED   = any
699                 any  M VARYING     = VARYING
700                 Ci   M Cj          = Ci         if (i == j)
701                 Ci   M Cj          = VARYING    if (i != j)
702    */
703
704 static void
705 ccp_lattice_meet (prop_value_t *val1, prop_value_t *val2)
706 {
707   if (val1->lattice_val == UNDEFINED)
708     {
709       /* UNDEFINED M any = any   */
710       *val1 = *val2;
711     }
712   else if (val2->lattice_val == UNDEFINED)
713     {
714       /* any M UNDEFINED = any
715          Nothing to do.  VAL1 already contains the value we want.  */
716       ;
717     }
718   else if (val1->lattice_val == VARYING
719            || val2->lattice_val == VARYING)
720     {
721       /* any M VARYING = VARYING.  */
722       val1->lattice_val = VARYING;
723       val1->value = NULL_TREE;
724     }
725   else if (val1->lattice_val == CONSTANT
726            && val2->lattice_val == CONSTANT
727            && simple_cst_equal (val1->value, val2->value) == 1)
728     {
729       /* Ci M Cj = Ci           if (i == j)
730          Ci M Cj = VARYING      if (i != j)
731
732          If these two values come from memory stores, make sure that
733          they come from the same memory reference.  */
734       val1->lattice_val = CONSTANT;
735       val1->value = val1->value;
736     }
737   else
738     {
739       /* Any other combination is VARYING.  */
740       val1->lattice_val = VARYING;
741       val1->value = NULL_TREE;
742     }
743 }
744
745
746 /* Loop through the PHI_NODE's parameters for BLOCK and compare their
747    lattice values to determine PHI_NODE's lattice value.  The value of a
748    PHI node is determined calling ccp_lattice_meet with all the arguments
749    of the PHI node that are incoming via executable edges.  */
750
751 static enum ssa_prop_result
752 ccp_visit_phi_node (gimple phi)
753 {
754   unsigned i;
755   prop_value_t *old_val, new_val;
756
757   if (dump_file && (dump_flags & TDF_DETAILS))
758     {
759       fprintf (dump_file, "\nVisiting PHI node: ");
760       print_gimple_stmt (dump_file, phi, 0, dump_flags);
761     }
762
763   old_val = get_value (gimple_phi_result (phi));
764   switch (old_val->lattice_val)
765     {
766     case VARYING:
767       return SSA_PROP_VARYING;
768
769     case CONSTANT:
770       new_val = *old_val;
771       break;
772
773     case UNDEFINED:
774       new_val.lattice_val = UNDEFINED;
775       new_val.value = NULL_TREE;
776       break;
777
778     default:
779       gcc_unreachable ();
780     }
781
782   for (i = 0; i < gimple_phi_num_args (phi); i++)
783     {
784       /* Compute the meet operator over all the PHI arguments flowing
785          through executable edges.  */
786       edge e = gimple_phi_arg_edge (phi, i);
787
788       if (dump_file && (dump_flags & TDF_DETAILS))
789         {
790           fprintf (dump_file,
791               "\n    Argument #%d (%d -> %d %sexecutable)\n",
792               i, e->src->index, e->dest->index,
793               (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
794         }
795
796       /* If the incoming edge is executable, Compute the meet operator for
797          the existing value of the PHI node and the current PHI argument.  */
798       if (e->flags & EDGE_EXECUTABLE)
799         {
800           tree arg = gimple_phi_arg (phi, i)->def;
801           prop_value_t arg_val;
802
803           if (is_gimple_min_invariant (arg))
804             {
805               arg_val.lattice_val = CONSTANT;
806               arg_val.value = arg;
807             }
808           else
809             arg_val = *(get_value (arg));
810
811           ccp_lattice_meet (&new_val, &arg_val);
812
813           if (dump_file && (dump_flags & TDF_DETAILS))
814             {
815               fprintf (dump_file, "\t");
816               print_generic_expr (dump_file, arg, dump_flags);
817               dump_lattice_value (dump_file, "\tValue: ", arg_val);
818               fprintf (dump_file, "\n");
819             }
820
821           if (new_val.lattice_val == VARYING)
822             break;
823         }
824     }
825
826   if (dump_file && (dump_flags & TDF_DETAILS))
827     {
828       dump_lattice_value (dump_file, "\n    PHI node value: ", new_val);
829       fprintf (dump_file, "\n\n");
830     }
831
832   /* Make the transition to the new value.  */
833   if (set_lattice_value (gimple_phi_result (phi), new_val))
834     {
835       if (new_val.lattice_val == VARYING)
836         return SSA_PROP_VARYING;
837       else
838         return SSA_PROP_INTERESTING;
839     }
840   else
841     return SSA_PROP_NOT_INTERESTING;
842 }
843
844 /* CCP specific front-end to the non-destructive constant folding
845    routines.
846
847    Attempt to simplify the RHS of STMT knowing that one or more
848    operands are constants.
849
850    If simplification is possible, return the simplified RHS,
851    otherwise return the original RHS or NULL_TREE.  */
852
853 static tree
854 ccp_fold (gimple stmt)
855 {
856   location_t loc = gimple_location (stmt);
857   switch (gimple_code (stmt))
858     {
859     case GIMPLE_ASSIGN:
860       {
861         enum tree_code subcode = gimple_assign_rhs_code (stmt);
862
863         switch (get_gimple_rhs_class (subcode))
864           {
865           case GIMPLE_SINGLE_RHS:
866             {
867               tree rhs = gimple_assign_rhs1 (stmt);
868               enum tree_code_class kind = TREE_CODE_CLASS (subcode);
869
870               if (TREE_CODE (rhs) == SSA_NAME)
871                 {
872                   /* If the RHS is an SSA_NAME, return its known constant value,
873                      if any.  */
874                   return get_value (rhs)->value;
875                 }
876               /* Handle propagating invariant addresses into address operations.
877                  The folding we do here matches that in tree-ssa-forwprop.c.  */
878               else if (TREE_CODE (rhs) == ADDR_EXPR)
879                 {
880                   tree *base;
881                   base = &TREE_OPERAND (rhs, 0);
882                   while (handled_component_p (*base))
883                     base = &TREE_OPERAND (*base, 0);
884                   if (TREE_CODE (*base) == INDIRECT_REF
885                       && TREE_CODE (TREE_OPERAND (*base, 0)) == SSA_NAME)
886                     {
887                       prop_value_t *val = get_value (TREE_OPERAND (*base, 0));
888                       if (val->lattice_val == CONSTANT
889                           && TREE_CODE (val->value) == ADDR_EXPR
890                           && may_propagate_address_into_dereference
891                                (val->value, *base))
892                         {
893                           /* We need to return a new tree, not modify the IL
894                              or share parts of it.  So play some tricks to
895                              avoid manually building it.  */
896                           tree ret, save = *base;
897                           *base = TREE_OPERAND (val->value, 0);
898                           ret = unshare_expr (rhs);
899                           recompute_tree_invariant_for_addr_expr (ret);
900                           *base = save;
901                           return ret;
902                         }
903                     }
904                 }
905               else if (TREE_CODE (rhs) == CONSTRUCTOR
906                        && TREE_CODE (TREE_TYPE (rhs)) == VECTOR_TYPE
907                        && (CONSTRUCTOR_NELTS (rhs)
908                            == TYPE_VECTOR_SUBPARTS (TREE_TYPE (rhs))))
909                 {
910                   unsigned i;
911                   tree val, list;
912
913                   list = NULL_TREE;
914                   FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (rhs), i, val)
915                     {
916                       if (TREE_CODE (val) == SSA_NAME
917                           && get_value (val)->lattice_val == CONSTANT)
918                         val = get_value (val)->value;
919                       if (TREE_CODE (val) == INTEGER_CST
920                           || TREE_CODE (val) == REAL_CST
921                           || TREE_CODE (val) == FIXED_CST)
922                         list = tree_cons (NULL_TREE, val, list);
923                       else
924                         return NULL_TREE;
925                     }
926
927                   return build_vector (TREE_TYPE (rhs), nreverse (list));
928                 }
929
930               if (kind == tcc_reference)
931                 {
932                   if ((TREE_CODE (rhs) == VIEW_CONVERT_EXPR
933                        || TREE_CODE (rhs) == REALPART_EXPR
934                        || TREE_CODE (rhs) == IMAGPART_EXPR)
935                       && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
936                     {
937                       prop_value_t *val = get_value (TREE_OPERAND (rhs, 0));
938                       if (val->lattice_val == CONSTANT)
939                         return fold_unary_loc (EXPR_LOCATION (rhs),
940                                            TREE_CODE (rhs),
941                                            TREE_TYPE (rhs), val->value);
942                     }
943                   else if (TREE_CODE (rhs) == INDIRECT_REF
944                            && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
945                     {
946                       prop_value_t *val = get_value (TREE_OPERAND (rhs, 0));
947                       if (val->lattice_val == CONSTANT
948                           && TREE_CODE (val->value) == ADDR_EXPR
949                           && useless_type_conversion_p (TREE_TYPE (rhs),
950                                                         TREE_TYPE (TREE_TYPE (val->value))))
951                         rhs = TREE_OPERAND (val->value, 0);
952                     }
953                   return fold_const_aggregate_ref (rhs);
954                 }
955               else if (kind == tcc_declaration)
956                 return get_symbol_constant_value (rhs);
957               return rhs;
958             }
959
960           case GIMPLE_UNARY_RHS:
961             {
962               /* Handle unary operators that can appear in GIMPLE form.
963                  Note that we know the single operand must be a constant,
964                  so this should almost always return a simplified RHS.  */
965               tree lhs = gimple_assign_lhs (stmt);
966               tree op0 = gimple_assign_rhs1 (stmt);
967
968               /* Simplify the operand down to a constant.  */
969               if (TREE_CODE (op0) == SSA_NAME)
970                 {
971                   prop_value_t *val = get_value (op0);
972                   if (val->lattice_val == CONSTANT)
973                     op0 = get_value (op0)->value;
974                 }
975
976               /* Conversions are useless for CCP purposes if they are
977                  value-preserving.  Thus the restrictions that
978                  useless_type_conversion_p places for pointer type conversions
979                  do not apply here.  Substitution later will only substitute to
980                  allowed places.  */
981               if (CONVERT_EXPR_CODE_P (subcode)
982                   && POINTER_TYPE_P (TREE_TYPE (lhs))
983                   && POINTER_TYPE_P (TREE_TYPE (op0))
984                   /* Do not allow differences in volatile qualification
985                      as this might get us confused as to whether a
986                      propagation destination statement is volatile
987                      or not.  See PR36988.  */
988                   && (TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (lhs)))
989                       == TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (op0)))))
990                 {
991                   tree tem;
992                   /* Still try to generate a constant of correct type.  */
993                   if (!useless_type_conversion_p (TREE_TYPE (lhs),
994                                                   TREE_TYPE (op0))
995                       && ((tem = maybe_fold_offset_to_address
996                            (loc,
997                             op0, integer_zero_node, TREE_TYPE (lhs)))
998                           != NULL_TREE))
999                     return tem;
1000                   return op0;
1001                 }
1002
1003               return
1004                 fold_unary_ignore_overflow_loc (loc, subcode,
1005                                                 gimple_expr_type (stmt), op0);
1006             }
1007
1008           case GIMPLE_BINARY_RHS:
1009             {
1010               /* Handle binary operators that can appear in GIMPLE form.  */
1011               tree op0 = gimple_assign_rhs1 (stmt);
1012               tree op1 = gimple_assign_rhs2 (stmt);
1013
1014               /* Simplify the operands down to constants when appropriate.  */
1015               if (TREE_CODE (op0) == SSA_NAME)
1016                 {
1017                   prop_value_t *val = get_value (op0);
1018                   if (val->lattice_val == CONSTANT)
1019                     op0 = val->value;
1020                 }
1021
1022               if (TREE_CODE (op1) == SSA_NAME)
1023                 {
1024                   prop_value_t *val = get_value (op1);
1025                   if (val->lattice_val == CONSTANT)
1026                     op1 = val->value;
1027                 }
1028
1029               /* Fold &foo + CST into an invariant reference if possible.  */
1030               if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR
1031                   && TREE_CODE (op0) == ADDR_EXPR
1032                   && TREE_CODE (op1) == INTEGER_CST)
1033                 {
1034                   tree tem = maybe_fold_offset_to_address
1035                     (loc, op0, op1, TREE_TYPE (op0));
1036                   if (tem != NULL_TREE)
1037                     return tem;
1038                 }
1039
1040               return fold_binary_loc (loc, subcode,
1041                                   gimple_expr_type (stmt), op0, op1);
1042             }
1043
1044           default:
1045             gcc_unreachable ();
1046           }
1047       }
1048       break;
1049
1050     case GIMPLE_CALL:
1051       {
1052         tree fn = gimple_call_fn (stmt);
1053         prop_value_t *val;
1054
1055         if (TREE_CODE (fn) == SSA_NAME)
1056           {
1057             val = get_value (fn);
1058             if (val->lattice_val == CONSTANT)
1059               fn = val->value;
1060           }
1061         if (TREE_CODE (fn) == ADDR_EXPR
1062             && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL
1063             && DECL_BUILT_IN (TREE_OPERAND (fn, 0)))
1064           {
1065             tree *args = XALLOCAVEC (tree, gimple_call_num_args (stmt));
1066             tree call, retval;
1067             unsigned i;
1068             for (i = 0; i < gimple_call_num_args (stmt); ++i)
1069               {
1070                 args[i] = gimple_call_arg (stmt, i);
1071                 if (TREE_CODE (args[i]) == SSA_NAME)
1072                   {
1073                     val = get_value (args[i]);
1074                     if (val->lattice_val == CONSTANT)
1075                       args[i] = val->value;
1076                   }
1077               }
1078             call = build_call_array_loc (loc,
1079                                          gimple_call_return_type (stmt),
1080                                          fn, gimple_call_num_args (stmt), args);
1081             retval = fold_call_expr (EXPR_LOCATION (call), call, false);
1082             if (retval)
1083               /* fold_call_expr wraps the result inside a NOP_EXPR.  */
1084               STRIP_NOPS (retval);
1085             return retval;
1086           }
1087         return NULL_TREE;
1088       }
1089
1090     case GIMPLE_COND:
1091       {
1092         /* Handle comparison operators that can appear in GIMPLE form.  */
1093         tree op0 = gimple_cond_lhs (stmt);
1094         tree op1 = gimple_cond_rhs (stmt);
1095         enum tree_code code = gimple_cond_code (stmt);
1096
1097         /* Simplify the operands down to constants when appropriate.  */
1098         if (TREE_CODE (op0) == SSA_NAME)
1099           {
1100             prop_value_t *val = get_value (op0);
1101             if (val->lattice_val == CONSTANT)
1102               op0 = val->value;
1103           }
1104
1105         if (TREE_CODE (op1) == SSA_NAME)
1106           {
1107             prop_value_t *val = get_value (op1);
1108             if (val->lattice_val == CONSTANT)
1109               op1 = val->value;
1110           }
1111
1112         return fold_binary_loc (loc, code, boolean_type_node, op0, op1);
1113       }
1114
1115     case GIMPLE_SWITCH:
1116       {
1117         tree rhs = gimple_switch_index (stmt);
1118
1119         if (TREE_CODE (rhs) == SSA_NAME)
1120           {
1121             /* If the RHS is an SSA_NAME, return its known constant value,
1122                if any.  */
1123             return get_value (rhs)->value;
1124           }
1125
1126         return rhs;
1127       }
1128
1129     default:
1130       gcc_unreachable ();
1131     }
1132 }
1133
1134
1135 /* Return the tree representing the element referenced by T if T is an
1136    ARRAY_REF or COMPONENT_REF into constant aggregates.  Return
1137    NULL_TREE otherwise.  */
1138
1139 tree
1140 fold_const_aggregate_ref (tree t)
1141 {
1142   prop_value_t *value;
1143   tree base, ctor, idx, field;
1144   unsigned HOST_WIDE_INT cnt;
1145   tree cfield, cval;
1146
1147   if (TREE_CODE_CLASS (TREE_CODE (t)) == tcc_declaration)
1148     return get_symbol_constant_value (t);
1149
1150   switch (TREE_CODE (t))
1151     {
1152     case ARRAY_REF:
1153       /* Get a CONSTRUCTOR.  If BASE is a VAR_DECL, get its
1154          DECL_INITIAL.  If BASE is a nested reference into another
1155          ARRAY_REF or COMPONENT_REF, make a recursive call to resolve
1156          the inner reference.  */
1157       base = TREE_OPERAND (t, 0);
1158       switch (TREE_CODE (base))
1159         {
1160         case VAR_DECL:
1161           if (!TREE_READONLY (base)
1162               || TREE_CODE (TREE_TYPE (base)) != ARRAY_TYPE
1163               || !targetm.binds_local_p (base))
1164             return NULL_TREE;
1165
1166           ctor = DECL_INITIAL (base);
1167           break;
1168
1169         case ARRAY_REF:
1170         case COMPONENT_REF:
1171           ctor = fold_const_aggregate_ref (base);
1172           break;
1173
1174         case STRING_CST:
1175         case CONSTRUCTOR:
1176           ctor = base;
1177           break;
1178
1179         default:
1180           return NULL_TREE;
1181         }
1182
1183       if (ctor == NULL_TREE
1184           || (TREE_CODE (ctor) != CONSTRUCTOR
1185               && TREE_CODE (ctor) != STRING_CST)
1186           || !TREE_STATIC (ctor))
1187         return NULL_TREE;
1188
1189       /* Get the index.  If we have an SSA_NAME, try to resolve it
1190          with the current lattice value for the SSA_NAME.  */
1191       idx = TREE_OPERAND (t, 1);
1192       switch (TREE_CODE (idx))
1193         {
1194         case SSA_NAME:
1195           if ((value = get_value (idx))
1196               && value->lattice_val == CONSTANT
1197               && TREE_CODE (value->value) == INTEGER_CST)
1198             idx = value->value;
1199           else
1200             return NULL_TREE;
1201           break;
1202
1203         case INTEGER_CST:
1204           break;
1205
1206         default:
1207           return NULL_TREE;
1208         }
1209
1210       /* Fold read from constant string.  */
1211       if (TREE_CODE (ctor) == STRING_CST)
1212         {
1213           if ((TYPE_MODE (TREE_TYPE (t))
1214                == TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
1215               && (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
1216                   == MODE_INT)
1217               && GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor)))) == 1
1218               && compare_tree_int (idx, TREE_STRING_LENGTH (ctor)) < 0)
1219             return build_int_cst_type (TREE_TYPE (t),
1220                                        (TREE_STRING_POINTER (ctor)
1221                                         [TREE_INT_CST_LOW (idx)]));
1222           return NULL_TREE;
1223         }
1224
1225       /* Whoo-hoo!  I'll fold ya baby.  Yeah!  */
1226       FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
1227         if (tree_int_cst_equal (cfield, idx))
1228           {
1229             STRIP_NOPS (cval);
1230             if (TREE_CODE (cval) == ADDR_EXPR)
1231               {
1232                 tree base = get_base_address (TREE_OPERAND (cval, 0));
1233                 if (base && TREE_CODE (base) == VAR_DECL)
1234                   add_referenced_var (base);
1235               }
1236             return cval;
1237           }
1238       break;
1239
1240     case COMPONENT_REF:
1241       /* Get a CONSTRUCTOR.  If BASE is a VAR_DECL, get its
1242          DECL_INITIAL.  If BASE is a nested reference into another
1243          ARRAY_REF or COMPONENT_REF, make a recursive call to resolve
1244          the inner reference.  */
1245       base = TREE_OPERAND (t, 0);
1246       switch (TREE_CODE (base))
1247         {
1248         case VAR_DECL:
1249           if (!TREE_READONLY (base)
1250               || TREE_CODE (TREE_TYPE (base)) != RECORD_TYPE
1251               || !targetm.binds_local_p (base))
1252             return NULL_TREE;
1253
1254           ctor = DECL_INITIAL (base);
1255           break;
1256
1257         case ARRAY_REF:
1258         case COMPONENT_REF:
1259           ctor = fold_const_aggregate_ref (base);
1260           break;
1261
1262         default:
1263           return NULL_TREE;
1264         }
1265
1266       if (ctor == NULL_TREE
1267           || TREE_CODE (ctor) != CONSTRUCTOR
1268           || !TREE_STATIC (ctor))
1269         return NULL_TREE;
1270
1271       field = TREE_OPERAND (t, 1);
1272
1273       FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
1274         if (cfield == field
1275             /* FIXME: Handle bit-fields.  */
1276             && ! DECL_BIT_FIELD (cfield))
1277           {
1278             STRIP_NOPS (cval);
1279             if (TREE_CODE (cval) == ADDR_EXPR)
1280               {
1281                 tree base = get_base_address (TREE_OPERAND (cval, 0));
1282                 if (base && TREE_CODE (base) == VAR_DECL)
1283                   add_referenced_var (base);
1284               }
1285             return cval;
1286           }
1287       break;
1288
1289     case REALPART_EXPR:
1290     case IMAGPART_EXPR:
1291       {
1292         tree c = fold_const_aggregate_ref (TREE_OPERAND (t, 0));
1293         if (c && TREE_CODE (c) == COMPLEX_CST)
1294           return fold_build1_loc (EXPR_LOCATION (t),
1295                               TREE_CODE (t), TREE_TYPE (t), c);
1296         break;
1297       }
1298
1299     case INDIRECT_REF:
1300       {
1301         tree base = TREE_OPERAND (t, 0);
1302         if (TREE_CODE (base) == SSA_NAME
1303             && (value = get_value (base))
1304             && value->lattice_val == CONSTANT
1305             && TREE_CODE (value->value) == ADDR_EXPR
1306             && useless_type_conversion_p (TREE_TYPE (t),
1307                                           TREE_TYPE (TREE_TYPE (value->value))))
1308           return fold_const_aggregate_ref (TREE_OPERAND (value->value, 0));
1309         break;
1310       }
1311
1312     default:
1313       break;
1314     }
1315
1316   return NULL_TREE;
1317 }
1318
1319 /* Evaluate statement STMT.
1320    Valid only for assignments, calls, conditionals, and switches. */
1321
1322 static prop_value_t
1323 evaluate_stmt (gimple stmt)
1324 {
1325   prop_value_t val;
1326   tree simplified = NULL_TREE;
1327   ccp_lattice_t likelyvalue = likely_value (stmt);
1328   bool is_constant;
1329
1330   fold_defer_overflow_warnings ();
1331
1332   /* If the statement is likely to have a CONSTANT result, then try
1333      to fold the statement to determine the constant value.  */
1334   /* FIXME.  This is the only place that we call ccp_fold.
1335      Since likely_value never returns CONSTANT for calls, we will
1336      not attempt to fold them, including builtins that may profit.  */
1337   if (likelyvalue == CONSTANT)
1338     simplified = ccp_fold (stmt);
1339   /* If the statement is likely to have a VARYING result, then do not
1340      bother folding the statement.  */
1341   else if (likelyvalue == VARYING)
1342     {
1343       enum gimple_code code = gimple_code (stmt);
1344       if (code == GIMPLE_ASSIGN)
1345         {
1346           enum tree_code subcode = gimple_assign_rhs_code (stmt);
1347
1348           /* Other cases cannot satisfy is_gimple_min_invariant
1349              without folding.  */
1350           if (get_gimple_rhs_class (subcode) == GIMPLE_SINGLE_RHS)
1351             simplified = gimple_assign_rhs1 (stmt);
1352         }
1353       else if (code == GIMPLE_SWITCH)
1354         simplified = gimple_switch_index (stmt);
1355       else
1356         /* These cannot satisfy is_gimple_min_invariant without folding.  */
1357         gcc_assert (code == GIMPLE_CALL || code == GIMPLE_COND);
1358     }
1359
1360   is_constant = simplified && is_gimple_min_invariant (simplified);
1361
1362   fold_undefer_overflow_warnings (is_constant, stmt, 0);
1363
1364   if (dump_file && (dump_flags & TDF_DETAILS))
1365     {
1366       fprintf (dump_file, "which is likely ");
1367       switch (likelyvalue)
1368         {
1369         case CONSTANT:
1370           fprintf (dump_file, "CONSTANT");
1371           break;
1372         case UNDEFINED:
1373           fprintf (dump_file, "UNDEFINED");
1374           break;
1375         case VARYING:
1376           fprintf (dump_file, "VARYING");
1377           break;
1378         default:;
1379         }
1380       fprintf (dump_file, "\n");
1381     }
1382
1383   if (is_constant)
1384     {
1385       /* The statement produced a constant value.  */
1386       val.lattice_val = CONSTANT;
1387       val.value = simplified;
1388     }
1389   else
1390     {
1391       /* The statement produced a nonconstant value.  If the statement
1392          had UNDEFINED operands, then the result of the statement
1393          should be UNDEFINED.  Otherwise, the statement is VARYING.  */
1394       if (likelyvalue == UNDEFINED)
1395         val.lattice_val = likelyvalue;
1396       else
1397         val.lattice_val = VARYING;
1398
1399       val.value = NULL_TREE;
1400     }
1401
1402   return val;
1403 }
1404
1405 /* Fold the stmt at *GSI with CCP specific information that propagating
1406    and regular folding does not catch.  */
1407
1408 static bool
1409 ccp_fold_stmt (gimple_stmt_iterator *gsi)
1410 {
1411   gimple stmt = gsi_stmt (*gsi);
1412
1413   switch (gimple_code (stmt))
1414     {
1415     case GIMPLE_COND:
1416       {
1417         prop_value_t val;
1418         /* Statement evaluation will handle type mismatches in constants
1419            more gracefully than the final propagation.  This allows us to
1420            fold more conditionals here.  */
1421         val = evaluate_stmt (stmt);
1422         if (val.lattice_val != CONSTANT
1423             || TREE_CODE (val.value) != INTEGER_CST)
1424           return false;
1425
1426         if (integer_zerop (val.value))
1427           gimple_cond_make_false (stmt);
1428         else
1429           gimple_cond_make_true (stmt);
1430
1431         return true;
1432       }
1433
1434     case GIMPLE_CALL:
1435       {
1436         tree lhs = gimple_call_lhs (stmt);
1437         prop_value_t *val;
1438         tree argt;
1439         bool changed = false;
1440         unsigned i;
1441
1442         /* If the call was folded into a constant make sure it goes
1443            away even if we cannot propagate into all uses because of
1444            type issues.  */
1445         if (lhs
1446             && TREE_CODE (lhs) == SSA_NAME
1447             && (val = get_value (lhs))
1448             && val->lattice_val == CONSTANT)
1449           {
1450             tree new_rhs = unshare_expr (val->value);
1451             bool res;
1452             if (!useless_type_conversion_p (TREE_TYPE (lhs),
1453                                             TREE_TYPE (new_rhs)))
1454               new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs);
1455             res = update_call_from_tree (gsi, new_rhs);
1456             gcc_assert (res);
1457             return true;
1458           }
1459
1460         /* Propagate into the call arguments.  Compared to replace_uses_in
1461            this can use the argument slot types for type verification
1462            instead of the current argument type.  We also can safely
1463            drop qualifiers here as we are dealing with constants anyway.  */
1464         argt = TYPE_ARG_TYPES (TREE_TYPE (TREE_TYPE (gimple_call_fn (stmt))));
1465         for (i = 0; i < gimple_call_num_args (stmt) && argt;
1466              ++i, argt = TREE_CHAIN (argt))
1467           {
1468             tree arg = gimple_call_arg (stmt, i);
1469             if (TREE_CODE (arg) == SSA_NAME
1470                 && (val = get_value (arg))
1471                 && val->lattice_val == CONSTANT
1472                 && useless_type_conversion_p
1473                      (TYPE_MAIN_VARIANT (TREE_VALUE (argt)),
1474                       TYPE_MAIN_VARIANT (TREE_TYPE (val->value))))
1475               {
1476                 gimple_call_set_arg (stmt, i, unshare_expr (val->value));
1477                 changed = true;
1478               }
1479           }
1480
1481         return changed;
1482       }
1483
1484     case GIMPLE_ASSIGN:
1485       {
1486         tree lhs = gimple_assign_lhs (stmt);
1487         prop_value_t *val;
1488
1489         /* If we have a load that turned out to be constant replace it
1490            as we cannot propagate into all uses in all cases.  */
1491         if (gimple_assign_single_p (stmt)
1492             && TREE_CODE (lhs) == SSA_NAME
1493             && (val = get_value (lhs))
1494             && val->lattice_val == CONSTANT)
1495           {
1496             tree rhs = unshare_expr (val->value);
1497             if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
1498               rhs = fold_convert (TREE_TYPE (lhs), rhs);
1499             gimple_assign_set_rhs_from_tree (gsi, rhs);
1500             return true;
1501           }
1502
1503         return false;
1504       }
1505
1506     default:
1507       return false;
1508     }
1509 }
1510
1511 /* Visit the assignment statement STMT.  Set the value of its LHS to the
1512    value computed by the RHS and store LHS in *OUTPUT_P.  If STMT
1513    creates virtual definitions, set the value of each new name to that
1514    of the RHS (if we can derive a constant out of the RHS).
1515    Value-returning call statements also perform an assignment, and
1516    are handled here.  */
1517
1518 static enum ssa_prop_result
1519 visit_assignment (gimple stmt, tree *output_p)
1520 {
1521   prop_value_t val;
1522   enum ssa_prop_result retval;
1523
1524   tree lhs = gimple_get_lhs (stmt);
1525
1526   gcc_assert (gimple_code (stmt) != GIMPLE_CALL
1527               || gimple_call_lhs (stmt) != NULL_TREE);
1528
1529   if (gimple_assign_copy_p (stmt))
1530     {
1531       tree rhs = gimple_assign_rhs1 (stmt);
1532
1533       if  (TREE_CODE (rhs) == SSA_NAME)
1534         {
1535           /* For a simple copy operation, we copy the lattice values.  */
1536           prop_value_t *nval = get_value (rhs);
1537           val = *nval;
1538         }
1539       else
1540         val = evaluate_stmt (stmt);
1541     }
1542   else
1543     /* Evaluate the statement, which could be
1544        either a GIMPLE_ASSIGN or a GIMPLE_CALL.  */
1545     val = evaluate_stmt (stmt);
1546
1547   retval = SSA_PROP_NOT_INTERESTING;
1548
1549   /* Set the lattice value of the statement's output.  */
1550   if (TREE_CODE (lhs) == SSA_NAME)
1551     {
1552       /* If STMT is an assignment to an SSA_NAME, we only have one
1553          value to set.  */
1554       if (set_lattice_value (lhs, val))
1555         {
1556           *output_p = lhs;
1557           if (val.lattice_val == VARYING)
1558             retval = SSA_PROP_VARYING;
1559           else
1560             retval = SSA_PROP_INTERESTING;
1561         }
1562     }
1563
1564   return retval;
1565 }
1566
1567
1568 /* Visit the conditional statement STMT.  Return SSA_PROP_INTERESTING
1569    if it can determine which edge will be taken.  Otherwise, return
1570    SSA_PROP_VARYING.  */
1571
1572 static enum ssa_prop_result
1573 visit_cond_stmt (gimple stmt, edge *taken_edge_p)
1574 {
1575   prop_value_t val;
1576   basic_block block;
1577
1578   block = gimple_bb (stmt);
1579   val = evaluate_stmt (stmt);
1580
1581   /* Find which edge out of the conditional block will be taken and add it
1582      to the worklist.  If no single edge can be determined statically,
1583      return SSA_PROP_VARYING to feed all the outgoing edges to the
1584      propagation engine.  */
1585   *taken_edge_p = val.value ? find_taken_edge (block, val.value) : 0;
1586   if (*taken_edge_p)
1587     return SSA_PROP_INTERESTING;
1588   else
1589     return SSA_PROP_VARYING;
1590 }
1591
1592
1593 /* Evaluate statement STMT.  If the statement produces an output value and
1594    its evaluation changes the lattice value of its output, return
1595    SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the
1596    output value.
1597
1598    If STMT is a conditional branch and we can determine its truth
1599    value, set *TAKEN_EDGE_P accordingly.  If STMT produces a varying
1600    value, return SSA_PROP_VARYING.  */
1601
1602 static enum ssa_prop_result
1603 ccp_visit_stmt (gimple stmt, edge *taken_edge_p, tree *output_p)
1604 {
1605   tree def;
1606   ssa_op_iter iter;
1607
1608   if (dump_file && (dump_flags & TDF_DETAILS))
1609     {
1610       fprintf (dump_file, "\nVisiting statement:\n");
1611       print_gimple_stmt (dump_file, stmt, 0, dump_flags);
1612     }
1613
1614   switch (gimple_code (stmt))
1615     {
1616       case GIMPLE_ASSIGN:
1617         /* If the statement is an assignment that produces a single
1618            output value, evaluate its RHS to see if the lattice value of
1619            its output has changed.  */
1620         return visit_assignment (stmt, output_p);
1621
1622       case GIMPLE_CALL:
1623         /* A value-returning call also performs an assignment.  */
1624         if (gimple_call_lhs (stmt) != NULL_TREE)
1625           return visit_assignment (stmt, output_p);
1626         break;
1627
1628       case GIMPLE_COND:
1629       case GIMPLE_SWITCH:
1630         /* If STMT is a conditional branch, see if we can determine
1631            which branch will be taken.   */
1632         /* FIXME.  It appears that we should be able to optimize
1633            computed GOTOs here as well.  */
1634         return visit_cond_stmt (stmt, taken_edge_p);
1635
1636       default:
1637         break;
1638     }
1639
1640   /* Any other kind of statement is not interesting for constant
1641      propagation and, therefore, not worth simulating.  */
1642   if (dump_file && (dump_flags & TDF_DETAILS))
1643     fprintf (dump_file, "No interesting values produced.  Marked VARYING.\n");
1644
1645   /* Definitions made by statements other than assignments to
1646      SSA_NAMEs represent unknown modifications to their outputs.
1647      Mark them VARYING.  */
1648   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
1649     {
1650       prop_value_t v = { VARYING, NULL_TREE };
1651       set_lattice_value (def, v);
1652     }
1653
1654   return SSA_PROP_VARYING;
1655 }
1656
1657
1658 /* Main entry point for SSA Conditional Constant Propagation.  */
1659
1660 static unsigned int
1661 do_ssa_ccp (void)
1662 {
1663   ccp_initialize ();
1664   ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node);
1665   if (ccp_finalize ())
1666     return (TODO_cleanup_cfg | TODO_update_ssa | TODO_remove_unused_locals);
1667   else
1668     return 0;
1669 }
1670
1671
1672 static bool
1673 gate_ccp (void)
1674 {
1675   return flag_tree_ccp != 0;
1676 }
1677
1678
1679 struct gimple_opt_pass pass_ccp =
1680 {
1681  {
1682   GIMPLE_PASS,
1683   "ccp",                                /* name */
1684   gate_ccp,                             /* gate */
1685   do_ssa_ccp,                           /* execute */
1686   NULL,                                 /* sub */
1687   NULL,                                 /* next */
1688   0,                                    /* static_pass_number */
1689   TV_TREE_CCP,                          /* tv_id */
1690   PROP_cfg | PROP_ssa,                  /* properties_required */
1691   0,                                    /* properties_provided */
1692   0,                                    /* properties_destroyed */
1693   0,                                    /* todo_flags_start */
1694   TODO_dump_func | TODO_verify_ssa
1695   | TODO_verify_stmts | TODO_ggc_collect/* todo_flags_finish */
1696  }
1697 };
1698
1699
1700
1701 /* Try to optimize out __builtin_stack_restore.  Optimize it out
1702    if there is another __builtin_stack_restore in the same basic
1703    block and no calls or ASM_EXPRs are in between, or if this block's
1704    only outgoing edge is to EXIT_BLOCK and there are no calls or
1705    ASM_EXPRs after this __builtin_stack_restore.  */
1706
1707 static tree
1708 optimize_stack_restore (gimple_stmt_iterator i)
1709 {
1710   tree callee;
1711   gimple stmt;
1712
1713   basic_block bb = gsi_bb (i);
1714   gimple call = gsi_stmt (i);
1715
1716   if (gimple_code (call) != GIMPLE_CALL
1717       || gimple_call_num_args (call) != 1
1718       || TREE_CODE (gimple_call_arg (call, 0)) != SSA_NAME
1719       || !POINTER_TYPE_P (TREE_TYPE (gimple_call_arg (call, 0))))
1720     return NULL_TREE;
1721
1722   for (gsi_next (&i); !gsi_end_p (i); gsi_next (&i))
1723     {
1724       stmt = gsi_stmt (i);
1725       if (gimple_code (stmt) == GIMPLE_ASM)
1726         return NULL_TREE;
1727       if (gimple_code (stmt) != GIMPLE_CALL)
1728         continue;
1729
1730       callee = gimple_call_fndecl (stmt);
1731       if (!callee
1732           || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL
1733           /* All regular builtins are ok, just obviously not alloca.  */
1734           || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALLOCA)
1735         return NULL_TREE;
1736
1737       if (DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_RESTORE)
1738         goto second_stack_restore;
1739     }
1740
1741   if (!gsi_end_p (i))
1742     return NULL_TREE;
1743
1744   /* Allow one successor of the exit block, or zero successors.  */
1745   switch (EDGE_COUNT (bb->succs))
1746     {
1747     case 0:
1748       break;
1749     case 1:
1750       if (single_succ_edge (bb)->dest != EXIT_BLOCK_PTR)
1751         return NULL_TREE;
1752       break;
1753     default:
1754       return NULL_TREE;
1755     }
1756  second_stack_restore:
1757
1758   /* If there's exactly one use, then zap the call to __builtin_stack_save.
1759      If there are multiple uses, then the last one should remove the call.
1760      In any case, whether the call to __builtin_stack_save can be removed
1761      or not is irrelevant to removing the call to __builtin_stack_restore.  */
1762   if (has_single_use (gimple_call_arg (call, 0)))
1763     {
1764       gimple stack_save = SSA_NAME_DEF_STMT (gimple_call_arg (call, 0));
1765       if (is_gimple_call (stack_save))
1766         {
1767           callee = gimple_call_fndecl (stack_save);
1768           if (callee
1769               && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
1770               && DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_SAVE)
1771             {
1772               gimple_stmt_iterator stack_save_gsi;
1773               tree rhs;
1774
1775               stack_save_gsi = gsi_for_stmt (stack_save);
1776               rhs = build_int_cst (TREE_TYPE (gimple_call_arg (call, 0)), 0);
1777               update_call_from_tree (&stack_save_gsi, rhs);
1778             }
1779         }
1780     }
1781
1782   /* No effect, so the statement will be deleted.  */
1783   return integer_zero_node;
1784 }
1785
1786 /* If va_list type is a simple pointer and nothing special is needed,
1787    optimize __builtin_va_start (&ap, 0) into ap = __builtin_next_arg (0),
1788    __builtin_va_end (&ap) out as NOP and __builtin_va_copy into a simple
1789    pointer assignment.  */
1790
1791 static tree
1792 optimize_stdarg_builtin (gimple call)
1793 {
1794   tree callee, lhs, rhs, cfun_va_list;
1795   bool va_list_simple_ptr;
1796   location_t loc = gimple_location (call);
1797
1798   if (gimple_code (call) != GIMPLE_CALL)
1799     return NULL_TREE;
1800
1801   callee = gimple_call_fndecl (call);
1802
1803   cfun_va_list = targetm.fn_abi_va_list (callee);
1804   va_list_simple_ptr = POINTER_TYPE_P (cfun_va_list)
1805                        && (TREE_TYPE (cfun_va_list) == void_type_node
1806                            || TREE_TYPE (cfun_va_list) == char_type_node);
1807
1808   switch (DECL_FUNCTION_CODE (callee))
1809     {
1810     case BUILT_IN_VA_START:
1811       if (!va_list_simple_ptr
1812           || targetm.expand_builtin_va_start != NULL
1813           || built_in_decls[BUILT_IN_NEXT_ARG] == NULL)
1814         return NULL_TREE;
1815
1816       if (gimple_call_num_args (call) != 2)
1817         return NULL_TREE;
1818
1819       lhs = gimple_call_arg (call, 0);
1820       if (!POINTER_TYPE_P (TREE_TYPE (lhs))
1821           || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs)))
1822              != TYPE_MAIN_VARIANT (cfun_va_list))
1823         return NULL_TREE;
1824
1825       lhs = build_fold_indirect_ref_loc (loc, lhs);
1826       rhs = build_call_expr_loc (loc, built_in_decls[BUILT_IN_NEXT_ARG],
1827                              1, integer_zero_node);
1828       rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
1829       return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
1830
1831     case BUILT_IN_VA_COPY:
1832       if (!va_list_simple_ptr)
1833         return NULL_TREE;
1834
1835       if (gimple_call_num_args (call) != 2)
1836         return NULL_TREE;
1837
1838       lhs = gimple_call_arg (call, 0);
1839       if (!POINTER_TYPE_P (TREE_TYPE (lhs))
1840           || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs)))
1841              != TYPE_MAIN_VARIANT (cfun_va_list))
1842         return NULL_TREE;
1843
1844       lhs = build_fold_indirect_ref_loc (loc, lhs);
1845       rhs = gimple_call_arg (call, 1);
1846       if (TYPE_MAIN_VARIANT (TREE_TYPE (rhs))
1847           != TYPE_MAIN_VARIANT (cfun_va_list))
1848         return NULL_TREE;
1849
1850       rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
1851       return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
1852
1853     case BUILT_IN_VA_END:
1854       /* No effect, so the statement will be deleted.  */
1855       return integer_zero_node;
1856
1857     default:
1858       gcc_unreachable ();
1859     }
1860 }
1861
1862 /* A simple pass that attempts to fold all builtin functions.  This pass
1863    is run after we've propagated as many constants as we can.  */
1864
1865 static unsigned int
1866 execute_fold_all_builtins (void)
1867 {
1868   bool cfg_changed = false;
1869   basic_block bb;
1870   unsigned int todoflags = 0;
1871
1872   FOR_EACH_BB (bb)
1873     {
1874       gimple_stmt_iterator i;
1875       for (i = gsi_start_bb (bb); !gsi_end_p (i); )
1876         {
1877           gimple stmt, old_stmt;
1878           tree callee, result;
1879           enum built_in_function fcode;
1880
1881           stmt = gsi_stmt (i);
1882
1883           if (gimple_code (stmt) != GIMPLE_CALL)
1884             {
1885               gsi_next (&i);
1886               continue;
1887             }
1888           callee = gimple_call_fndecl (stmt);
1889           if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
1890             {
1891               gsi_next (&i);
1892               continue;
1893             }
1894           fcode = DECL_FUNCTION_CODE (callee);
1895
1896           result = gimple_fold_builtin (stmt);
1897
1898           if (result)
1899             gimple_remove_stmt_histograms (cfun, stmt);
1900
1901           if (!result)
1902             switch (DECL_FUNCTION_CODE (callee))
1903               {
1904               case BUILT_IN_CONSTANT_P:
1905                 /* Resolve __builtin_constant_p.  If it hasn't been
1906                    folded to integer_one_node by now, it's fairly
1907                    certain that the value simply isn't constant.  */
1908                 result = integer_zero_node;
1909                 break;
1910
1911               case BUILT_IN_STACK_RESTORE:
1912                 result = optimize_stack_restore (i);
1913                 if (result)
1914                   break;
1915                 gsi_next (&i);
1916                 continue;
1917
1918               case BUILT_IN_VA_START:
1919               case BUILT_IN_VA_END:
1920               case BUILT_IN_VA_COPY:
1921                 /* These shouldn't be folded before pass_stdarg.  */
1922                 result = optimize_stdarg_builtin (stmt);
1923                 if (result)
1924                   break;
1925                 /* FALLTHRU */
1926
1927               default:
1928                 gsi_next (&i);
1929                 continue;
1930               }
1931
1932           if (dump_file && (dump_flags & TDF_DETAILS))
1933             {
1934               fprintf (dump_file, "Simplified\n  ");
1935               print_gimple_stmt (dump_file, stmt, 0, dump_flags);
1936             }
1937
1938           old_stmt = stmt;
1939           if (!update_call_from_tree (&i, result))
1940             {
1941               gimplify_and_update_call_from_tree (&i, result);
1942               todoflags |= TODO_update_address_taken;
1943             }
1944
1945           stmt = gsi_stmt (i);
1946           update_stmt (stmt);
1947
1948           if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)
1949               && gimple_purge_dead_eh_edges (bb))
1950             cfg_changed = true;
1951
1952           if (dump_file && (dump_flags & TDF_DETAILS))
1953             {
1954               fprintf (dump_file, "to\n  ");
1955               print_gimple_stmt (dump_file, stmt, 0, dump_flags);
1956               fprintf (dump_file, "\n");
1957             }
1958
1959           /* Retry the same statement if it changed into another
1960              builtin, there might be new opportunities now.  */
1961           if (gimple_code (stmt) != GIMPLE_CALL)
1962             {
1963               gsi_next (&i);
1964               continue;
1965             }
1966           callee = gimple_call_fndecl (stmt);
1967           if (!callee
1968               || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL
1969               || DECL_FUNCTION_CODE (callee) == fcode)
1970             gsi_next (&i);
1971         }
1972     }
1973
1974   /* Delete unreachable blocks.  */
1975   if (cfg_changed)
1976     todoflags |= TODO_cleanup_cfg;
1977
1978   return todoflags;
1979 }
1980
1981
1982 struct gimple_opt_pass pass_fold_builtins =
1983 {
1984  {
1985   GIMPLE_PASS,
1986   "fab",                                /* name */
1987   NULL,                                 /* gate */
1988   execute_fold_all_builtins,            /* execute */
1989   NULL,                                 /* sub */
1990   NULL,                                 /* next */
1991   0,                                    /* static_pass_number */
1992   TV_NONE,                              /* tv_id */
1993   PROP_cfg | PROP_ssa,                  /* properties_required */
1994   0,                                    /* properties_provided */
1995   0,                                    /* properties_destroyed */
1996   0,                                    /* todo_flags_start */
1997   TODO_dump_func
1998     | TODO_verify_ssa
1999     | TODO_update_ssa                   /* todo_flags_finish */
2000  }
2001 };