VOP_FSYNC.9: Missing comma
[dragonfly.git] / contrib / gcc-4.7 / 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, 2011, 2012, 2013 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    References:
103
104      Constant propagation with conditional branches,
105      Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
106
107      Building an Optimizing Compiler,
108      Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
109
110      Advanced Compiler Design and Implementation,
111      Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6  */
112
113 #include "config.h"
114 #include "system.h"
115 #include "coretypes.h"
116 #include "tm.h"
117 #include "tree.h"
118 #include "flags.h"
119 #include "tm_p.h"
120 #include "basic-block.h"
121 #include "output.h"
122 #include "function.h"
123 #include "tree-pretty-print.h"
124 #include "gimple-pretty-print.h"
125 #include "timevar.h"
126 #include "tree-dump.h"
127 #include "tree-flow.h"
128 #include "tree-pass.h"
129 #include "tree-ssa-propagate.h"
130 #include "value-prof.h"
131 #include "langhooks.h"
132 #include "target.h"
133 #include "diagnostic-core.h"
134 #include "dbgcnt.h"
135 #include "gimple-fold.h"
136 #include "params.h"
137
138
139 /* Possible lattice values.  */
140 typedef enum
141 {
142   UNINITIALIZED,
143   UNDEFINED,
144   CONSTANT,
145   VARYING
146 } ccp_lattice_t;
147
148 struct prop_value_d {
149     /* Lattice value.  */
150     ccp_lattice_t lattice_val;
151
152     /* Propagated value.  */
153     tree value;
154
155     /* Mask that applies to the propagated value during CCP.  For
156        X with a CONSTANT lattice value X & ~mask == value & ~mask.  */
157     double_int mask;
158 };
159
160 typedef struct prop_value_d prop_value_t;
161
162 /* Array of propagated constant values.  After propagation,
163    CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I).  If
164    the constant is held in an SSA name representing a memory store
165    (i.e., a VDEF), CONST_VAL[I].MEM_REF will contain the actual
166    memory reference used to store (i.e., the LHS of the assignment
167    doing the store).  */
168 static prop_value_t *const_val;
169
170 static void canonicalize_float_value (prop_value_t *);
171 static bool ccp_fold_stmt (gimple_stmt_iterator *);
172
173 /* Dump constant propagation value VAL to file OUTF prefixed by PREFIX.  */
174
175 static void
176 dump_lattice_value (FILE *outf, const char *prefix, prop_value_t val)
177 {
178   switch (val.lattice_val)
179     {
180     case UNINITIALIZED:
181       fprintf (outf, "%sUNINITIALIZED", prefix);
182       break;
183     case UNDEFINED:
184       fprintf (outf, "%sUNDEFINED", prefix);
185       break;
186     case VARYING:
187       fprintf (outf, "%sVARYING", prefix);
188       break;
189     case CONSTANT:
190       fprintf (outf, "%sCONSTANT ", prefix);
191       if (TREE_CODE (val.value) != INTEGER_CST
192           || double_int_zero_p (val.mask))
193         print_generic_expr (outf, val.value, dump_flags);
194       else
195         {
196           double_int cval = double_int_and_not (tree_to_double_int (val.value),
197                                                 val.mask);
198           fprintf (outf, "%sCONSTANT " HOST_WIDE_INT_PRINT_DOUBLE_HEX,
199                    prefix, cval.high, cval.low);
200           fprintf (outf, " (" HOST_WIDE_INT_PRINT_DOUBLE_HEX ")",
201                    val.mask.high, val.mask.low);
202         }
203       break;
204     default:
205       gcc_unreachable ();
206     }
207 }
208
209
210 /* Print lattice value VAL to stderr.  */
211
212 void debug_lattice_value (prop_value_t val);
213
214 DEBUG_FUNCTION void
215 debug_lattice_value (prop_value_t val)
216 {
217   dump_lattice_value (stderr, "", val);
218   fprintf (stderr, "\n");
219 }
220
221
222 /* Compute a default value for variable VAR and store it in the
223    CONST_VAL array.  The following rules are used to get default
224    values:
225
226    1- Global and static variables that are declared constant are
227       considered CONSTANT.
228
229    2- Any other value is considered UNDEFINED.  This is useful when
230       considering PHI nodes.  PHI arguments that are undefined do not
231       change the constant value of the PHI node, which allows for more
232       constants to be propagated.
233
234    3- Variables defined by statements other than assignments and PHI
235       nodes are considered VARYING.
236
237    4- Initial values of variables that are not GIMPLE registers are
238       considered VARYING.  */
239
240 static prop_value_t
241 get_default_value (tree var)
242 {
243   tree sym = SSA_NAME_VAR (var);
244   prop_value_t val = { UNINITIALIZED, NULL_TREE, { 0, 0 } };
245   gimple stmt;
246
247   stmt = SSA_NAME_DEF_STMT (var);
248
249   if (gimple_nop_p (stmt))
250     {
251       /* Variables defined by an empty statement are those used
252          before being initialized.  If VAR is a local variable, we
253          can assume initially that it is UNDEFINED, otherwise we must
254          consider it VARYING.  */
255       if (is_gimple_reg (sym)
256           && TREE_CODE (sym) == VAR_DECL)
257         val.lattice_val = UNDEFINED;
258       else
259         {
260           val.lattice_val = VARYING;
261           val.mask = double_int_minus_one;
262         }
263     }
264   else if (is_gimple_assign (stmt)
265            /* Value-returning GIMPLE_CALL statements assign to
266               a variable, and are treated similarly to GIMPLE_ASSIGN.  */
267            || (is_gimple_call (stmt)
268                && gimple_call_lhs (stmt) != NULL_TREE)
269            || gimple_code (stmt) == GIMPLE_PHI)
270     {
271       tree cst;
272       if (gimple_assign_single_p (stmt)
273           && DECL_P (gimple_assign_rhs1 (stmt))
274           && (cst = get_symbol_constant_value (gimple_assign_rhs1 (stmt))))
275         {
276           val.lattice_val = CONSTANT;
277           val.value = cst;
278         }
279       else
280         /* Any other variable defined by an assignment or a PHI node
281            is considered UNDEFINED.  */
282         val.lattice_val = UNDEFINED;
283     }
284   else
285     {
286       /* Otherwise, VAR will never take on a constant value.  */
287       val.lattice_val = VARYING;
288       val.mask = double_int_minus_one;
289     }
290
291   return val;
292 }
293
294
295 /* Get the constant value associated with variable VAR.  */
296
297 static inline prop_value_t *
298 get_value (tree var)
299 {
300   prop_value_t *val;
301
302   if (const_val == NULL)
303     return NULL;
304
305   val = &const_val[SSA_NAME_VERSION (var)];
306   if (val->lattice_val == UNINITIALIZED)
307     *val = get_default_value (var);
308
309   canonicalize_float_value (val);
310
311   return val;
312 }
313
314 /* Return the constant tree value associated with VAR.  */
315
316 static inline tree
317 get_constant_value (tree var)
318 {
319   prop_value_t *val;
320   if (TREE_CODE (var) != SSA_NAME)
321     {
322       if (is_gimple_min_invariant (var))
323         return var;
324       return NULL_TREE;
325     }
326   val = get_value (var);
327   if (val
328       && val->lattice_val == CONSTANT
329       && (TREE_CODE (val->value) != INTEGER_CST
330           || double_int_zero_p (val->mask)))
331     return val->value;
332   return NULL_TREE;
333 }
334
335 /* Sets the value associated with VAR to VARYING.  */
336
337 static inline void
338 set_value_varying (tree var)
339 {
340   prop_value_t *val = &const_val[SSA_NAME_VERSION (var)];
341
342   val->lattice_val = VARYING;
343   val->value = NULL_TREE;
344   val->mask = double_int_minus_one;
345 }
346
347 /* For float types, modify the value of VAL to make ccp work correctly
348    for non-standard values (-0, NaN):
349
350    If HONOR_SIGNED_ZEROS is false, and VAL = -0, we canonicalize it to 0.
351    If HONOR_NANS is false, and VAL is NaN, we canonicalize it to UNDEFINED.
352      This is to fix the following problem (see PR 29921): Suppose we have
353
354      x = 0.0 * y
355
356      and we set value of y to NaN.  This causes value of x to be set to NaN.
357      When we later determine that y is in fact VARYING, fold uses the fact
358      that HONOR_NANS is false, and we try to change the value of x to 0,
359      causing an ICE.  With HONOR_NANS being false, the real appearance of
360      NaN would cause undefined behavior, though, so claiming that y (and x)
361      are UNDEFINED initially is correct.  */
362
363 static void
364 canonicalize_float_value (prop_value_t *val)
365 {
366   enum machine_mode mode;
367   tree type;
368   REAL_VALUE_TYPE d;
369
370   if (val->lattice_val != CONSTANT
371       || TREE_CODE (val->value) != REAL_CST)
372     return;
373
374   d = TREE_REAL_CST (val->value);
375   type = TREE_TYPE (val->value);
376   mode = TYPE_MODE (type);
377
378   if (!HONOR_SIGNED_ZEROS (mode)
379       && REAL_VALUE_MINUS_ZERO (d))
380     {
381       val->value = build_real (type, dconst0);
382       return;
383     }
384
385   if (!HONOR_NANS (mode)
386       && REAL_VALUE_ISNAN (d))
387     {
388       val->lattice_val = UNDEFINED;
389       val->value = NULL;
390       return;
391     }
392 }
393
394 /* Return whether the lattice transition is valid.  */
395
396 static bool
397 valid_lattice_transition (prop_value_t old_val, prop_value_t new_val)
398 {
399   /* Lattice transitions must always be monotonically increasing in
400      value.  */
401   if (old_val.lattice_val < new_val.lattice_val)
402     return true;
403
404   if (old_val.lattice_val != new_val.lattice_val)
405     return false;
406
407   if (!old_val.value && !new_val.value)
408     return true;
409
410   /* Now both lattice values are CONSTANT.  */
411
412   /* Allow transitioning from PHI <&x, not executable> == &x
413      to PHI <&x, &y> == common alignment.  */
414   if (TREE_CODE (old_val.value) != INTEGER_CST
415       && TREE_CODE (new_val.value) == INTEGER_CST)
416     return true;
417
418   /* Bit-lattices have to agree in the still valid bits.  */
419   if (TREE_CODE (old_val.value) == INTEGER_CST
420       && TREE_CODE (new_val.value) == INTEGER_CST)
421     return double_int_equal_p
422                 (double_int_and_not (tree_to_double_int (old_val.value),
423                                      new_val.mask),
424                  double_int_and_not (tree_to_double_int (new_val.value),
425                                      new_val.mask));
426
427   /* Otherwise constant values have to agree.  */
428   return operand_equal_p (old_val.value, new_val.value, 0);
429 }
430
431 /* Set the value for variable VAR to NEW_VAL.  Return true if the new
432    value is different from VAR's previous value.  */
433
434 static bool
435 set_lattice_value (tree var, prop_value_t new_val)
436 {
437   /* We can deal with old UNINITIALIZED values just fine here.  */
438   prop_value_t *old_val = &const_val[SSA_NAME_VERSION (var)];
439
440   canonicalize_float_value (&new_val);
441
442   /* We have to be careful to not go up the bitwise lattice
443      represented by the mask.
444      ???  This doesn't seem to be the best place to enforce this.  */
445   if (new_val.lattice_val == CONSTANT
446       && old_val->lattice_val == CONSTANT
447       && TREE_CODE (new_val.value) == INTEGER_CST
448       && TREE_CODE (old_val->value) == INTEGER_CST)
449     {
450       double_int diff;
451       diff = double_int_xor (tree_to_double_int (new_val.value),
452                              tree_to_double_int (old_val->value));
453       new_val.mask = double_int_ior (new_val.mask,
454                                      double_int_ior (old_val->mask, diff));
455     }
456
457   gcc_assert (valid_lattice_transition (*old_val, new_val));
458
459   /* If *OLD_VAL and NEW_VAL are the same, return false to inform the
460      caller that this was a non-transition.  */
461   if (old_val->lattice_val != new_val.lattice_val
462       || (new_val.lattice_val == CONSTANT
463           && TREE_CODE (new_val.value) == INTEGER_CST
464           && (TREE_CODE (old_val->value) != INTEGER_CST
465               || !double_int_equal_p (new_val.mask, old_val->mask))))
466     {
467       /* ???  We would like to delay creation of INTEGER_CSTs from
468          partially constants here.  */
469
470       if (dump_file && (dump_flags & TDF_DETAILS))
471         {
472           dump_lattice_value (dump_file, "Lattice value changed to ", new_val);
473           fprintf (dump_file, ".  Adding SSA edges to worklist.\n");
474         }
475
476       *old_val = new_val;
477
478       gcc_assert (new_val.lattice_val != UNINITIALIZED);
479       return true;
480     }
481
482   return false;
483 }
484
485 static prop_value_t get_value_for_expr (tree, bool);
486 static prop_value_t bit_value_binop (enum tree_code, tree, tree, tree);
487 static void bit_value_binop_1 (enum tree_code, tree, double_int *, double_int *,
488                                tree, double_int, double_int,
489                                tree, double_int, double_int);
490
491 /* Return a double_int that can be used for bitwise simplifications
492    from VAL.  */
493
494 static double_int
495 value_to_double_int (prop_value_t val)
496 {
497   if (val.value
498       && TREE_CODE (val.value) == INTEGER_CST)
499     return tree_to_double_int (val.value);
500   else
501     return double_int_zero;
502 }
503
504 /* Return the value for the address expression EXPR based on alignment
505    information.  */
506
507 static prop_value_t
508 get_value_from_alignment (tree expr)
509 {
510   tree type = TREE_TYPE (expr);
511   prop_value_t val;
512   unsigned HOST_WIDE_INT bitpos;
513   unsigned int align;
514
515   gcc_assert (TREE_CODE (expr) == ADDR_EXPR);
516
517   align = get_object_alignment_1 (TREE_OPERAND (expr, 0), &bitpos);
518   val.mask
519     = double_int_and_not (POINTER_TYPE_P (type) || TYPE_UNSIGNED (type)
520                           ? double_int_mask (TYPE_PRECISION (type))
521                           : double_int_minus_one,
522                           uhwi_to_double_int (align / BITS_PER_UNIT - 1));
523   val.lattice_val = double_int_minus_one_p (val.mask) ? VARYING : CONSTANT;
524   if (val.lattice_val == CONSTANT)
525     val.value
526       = double_int_to_tree (type, uhwi_to_double_int (bitpos / BITS_PER_UNIT));
527   else
528     val.value = NULL_TREE;
529
530   return val;
531 }
532
533 /* Return the value for the tree operand EXPR.  If FOR_BITS_P is true
534    return constant bits extracted from alignment information for
535    invariant addresses.  */
536
537 static prop_value_t
538 get_value_for_expr (tree expr, bool for_bits_p)
539 {
540   prop_value_t val;
541
542   if (TREE_CODE (expr) == SSA_NAME)
543     {
544       val = *get_value (expr);
545       if (for_bits_p
546           && val.lattice_val == CONSTANT
547           && TREE_CODE (val.value) == ADDR_EXPR)
548         val = get_value_from_alignment (val.value);
549     }
550   else if (is_gimple_min_invariant (expr)
551            && (!for_bits_p || TREE_CODE (expr) != ADDR_EXPR))
552     {
553       val.lattice_val = CONSTANT;
554       val.value = expr;
555       val.mask = double_int_zero;
556       canonicalize_float_value (&val);
557     }
558   else if (TREE_CODE (expr) == ADDR_EXPR)
559     val = get_value_from_alignment (expr);
560   else
561     {
562       val.lattice_val = VARYING;
563       val.mask = double_int_minus_one;
564       val.value = NULL_TREE;
565     }
566   return val;
567 }
568
569 /* Return the likely CCP lattice value for STMT.
570
571    If STMT has no operands, then return CONSTANT.
572
573    Else if undefinedness of operands of STMT cause its value to be
574    undefined, then return UNDEFINED.
575
576    Else if any operands of STMT are constants, then return CONSTANT.
577
578    Else return VARYING.  */
579
580 static ccp_lattice_t
581 likely_value (gimple stmt)
582 {
583   bool has_constant_operand, has_undefined_operand, all_undefined_operands;
584   tree use;
585   ssa_op_iter iter;
586   unsigned i;
587
588   enum gimple_code code = gimple_code (stmt);
589
590   /* This function appears to be called only for assignments, calls,
591      conditionals, and switches, due to the logic in visit_stmt.  */
592   gcc_assert (code == GIMPLE_ASSIGN
593               || code == GIMPLE_CALL
594               || code == GIMPLE_COND
595               || code == GIMPLE_SWITCH);
596
597   /* If the statement has volatile operands, it won't fold to a
598      constant value.  */
599   if (gimple_has_volatile_ops (stmt))
600     return VARYING;
601
602   /* Arrive here for more complex cases.  */
603   has_constant_operand = false;
604   has_undefined_operand = false;
605   all_undefined_operands = true;
606   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
607     {
608       prop_value_t *val = get_value (use);
609
610       if (val->lattice_val == UNDEFINED)
611         has_undefined_operand = true;
612       else
613         all_undefined_operands = false;
614
615       if (val->lattice_val == CONSTANT)
616         has_constant_operand = true;
617     }
618
619   /* There may be constants in regular rhs operands.  For calls we
620      have to ignore lhs, fndecl and static chain, otherwise only
621      the lhs.  */
622   for (i = (is_gimple_call (stmt) ? 2 : 0) + gimple_has_lhs (stmt);
623        i < gimple_num_ops (stmt); ++i)
624     {
625       tree op = gimple_op (stmt, i);
626       if (!op || TREE_CODE (op) == SSA_NAME)
627         continue;
628       if (is_gimple_min_invariant (op))
629         has_constant_operand = true;
630     }
631
632   if (has_constant_operand)
633     all_undefined_operands = false;
634
635   /* If the operation combines operands like COMPLEX_EXPR make sure to
636      not mark the result UNDEFINED if only one part of the result is
637      undefined.  */
638   if (has_undefined_operand && all_undefined_operands)
639     return UNDEFINED;
640   else if (code == GIMPLE_ASSIGN && has_undefined_operand)
641     {
642       switch (gimple_assign_rhs_code (stmt))
643         {
644         /* Unary operators are handled with all_undefined_operands.  */
645         case PLUS_EXPR:
646         case MINUS_EXPR:
647         case POINTER_PLUS_EXPR:
648           /* Not MIN_EXPR, MAX_EXPR.  One VARYING operand may be selected.
649              Not bitwise operators, one VARYING operand may specify the
650              result completely.  Not logical operators for the same reason.
651              Not COMPLEX_EXPR as one VARYING operand makes the result partly
652              not UNDEFINED.  Not *DIV_EXPR, comparisons and shifts because
653              the undefined operand may be promoted.  */
654           return UNDEFINED;
655
656         case ADDR_EXPR:
657           /* If any part of an address is UNDEFINED, like the index
658              of an ARRAY_EXPR, then treat the result as UNDEFINED.  */
659           return UNDEFINED;
660
661         default:
662           ;
663         }
664     }
665   /* If there was an UNDEFINED operand but the result may be not UNDEFINED
666      fall back to CONSTANT.  During iteration UNDEFINED may still drop
667      to CONSTANT.  */
668   if (has_undefined_operand)
669     return CONSTANT;
670
671   /* We do not consider virtual operands here -- load from read-only
672      memory may have only VARYING virtual operands, but still be
673      constant.  */
674   if (has_constant_operand
675       || gimple_references_memory_p (stmt))
676     return CONSTANT;
677
678   return VARYING;
679 }
680
681 /* Returns true if STMT cannot be constant.  */
682
683 static bool
684 surely_varying_stmt_p (gimple stmt)
685 {
686   /* If the statement has operands that we cannot handle, it cannot be
687      constant.  */
688   if (gimple_has_volatile_ops (stmt))
689     return true;
690
691   /* If it is a call and does not return a value or is not a
692      builtin and not an indirect call, it is varying.  */
693   if (is_gimple_call (stmt))
694     {
695       tree fndecl;
696       if (!gimple_call_lhs (stmt)
697           || ((fndecl = gimple_call_fndecl (stmt)) != NULL_TREE
698               && !DECL_BUILT_IN (fndecl)))
699         return true;
700     }
701
702   /* Any other store operation is not interesting.  */
703   else if (gimple_vdef (stmt))
704     return true;
705
706   /* Anything other than assignments and conditional jumps are not
707      interesting for CCP.  */
708   if (gimple_code (stmt) != GIMPLE_ASSIGN
709       && gimple_code (stmt) != GIMPLE_COND
710       && gimple_code (stmt) != GIMPLE_SWITCH
711       && gimple_code (stmt) != GIMPLE_CALL)
712     return true;
713
714   return false;
715 }
716
717 /* Initialize local data structures for CCP.  */
718
719 static void
720 ccp_initialize (void)
721 {
722   basic_block bb;
723
724   const_val = XCNEWVEC (prop_value_t, num_ssa_names);
725
726   /* Initialize simulation flags for PHI nodes and statements.  */
727   FOR_EACH_BB (bb)
728     {
729       gimple_stmt_iterator i;
730
731       for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
732         {
733           gimple stmt = gsi_stmt (i);
734           bool is_varying;
735
736           /* If the statement is a control insn, then we do not
737              want to avoid simulating the statement once.  Failure
738              to do so means that those edges will never get added.  */
739           if (stmt_ends_bb_p (stmt))
740             is_varying = false;
741           else
742             is_varying = surely_varying_stmt_p (stmt);
743
744           if (is_varying)
745             {
746               tree def;
747               ssa_op_iter iter;
748
749               /* If the statement will not produce a constant, mark
750                  all its outputs VARYING.  */
751               FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
752                 set_value_varying (def);
753             }
754           prop_set_simulate_again (stmt, !is_varying);
755         }
756     }
757
758   /* Now process PHI nodes.  We never clear the simulate_again flag on
759      phi nodes, since we do not know which edges are executable yet,
760      except for phi nodes for virtual operands when we do not do store ccp.  */
761   FOR_EACH_BB (bb)
762     {
763       gimple_stmt_iterator i;
764
765       for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
766         {
767           gimple phi = gsi_stmt (i);
768
769           if (!is_gimple_reg (gimple_phi_result (phi)))
770             prop_set_simulate_again (phi, false);
771           else
772             prop_set_simulate_again (phi, true);
773         }
774     }
775 }
776
777 /* Debug count support. Reset the values of ssa names
778    VARYING when the total number ssa names analyzed is
779    beyond the debug count specified.  */
780
781 static void
782 do_dbg_cnt (void)
783 {
784   unsigned i;
785   for (i = 0; i < num_ssa_names; i++)
786     {
787       if (!dbg_cnt (ccp))
788         {
789           const_val[i].lattice_val = VARYING;
790           const_val[i].mask = double_int_minus_one;
791           const_val[i].value = NULL_TREE;
792         }
793     }
794 }
795
796
797 /* Do final substitution of propagated values, cleanup the flowgraph and
798    free allocated storage.
799
800    Return TRUE when something was optimized.  */
801
802 static bool
803 ccp_finalize (void)
804 {
805   bool something_changed;
806   unsigned i;
807
808   do_dbg_cnt ();
809
810   /* Derive alignment and misalignment information from partially
811      constant pointers in the lattice.  */
812   for (i = 1; i < num_ssa_names; ++i)
813     {
814       tree name = ssa_name (i);
815       prop_value_t *val;
816       struct ptr_info_def *pi;
817       unsigned int tem, align;
818
819       if (!name
820           || !POINTER_TYPE_P (TREE_TYPE (name)))
821         continue;
822
823       val = get_value (name);
824       if (val->lattice_val != CONSTANT
825           || TREE_CODE (val->value) != INTEGER_CST)
826         continue;
827
828       /* Trailing constant bits specify the alignment, trailing value
829          bits the misalignment.  */
830       tem = val->mask.low;
831       align = (tem & -tem);
832       if (align == 1)
833         continue;
834
835       pi = get_ptr_info (name);
836       pi->align = align;
837       pi->misalign = TREE_INT_CST_LOW (val->value) & (align - 1);
838     }
839
840   /* Perform substitutions based on the known constant values.  */
841   something_changed = substitute_and_fold (get_constant_value,
842                                            ccp_fold_stmt, true);
843
844   free (const_val);
845   const_val = NULL;
846   return something_changed;;
847 }
848
849
850 /* Compute the meet operator between *VAL1 and *VAL2.  Store the result
851    in VAL1.
852
853                 any  M UNDEFINED   = any
854                 any  M VARYING     = VARYING
855                 Ci   M Cj          = Ci         if (i == j)
856                 Ci   M Cj          = VARYING    if (i != j)
857    */
858
859 static void
860 ccp_lattice_meet (prop_value_t *val1, prop_value_t *val2)
861 {
862   if (val1->lattice_val == UNDEFINED)
863     {
864       /* UNDEFINED M any = any   */
865       *val1 = *val2;
866     }
867   else if (val2->lattice_val == UNDEFINED)
868     {
869       /* any M UNDEFINED = any
870          Nothing to do.  VAL1 already contains the value we want.  */
871       ;
872     }
873   else if (val1->lattice_val == VARYING
874            || val2->lattice_val == VARYING)
875     {
876       /* any M VARYING = VARYING.  */
877       val1->lattice_val = VARYING;
878       val1->mask = double_int_minus_one;
879       val1->value = NULL_TREE;
880     }
881   else if (val1->lattice_val == CONSTANT
882            && val2->lattice_val == CONSTANT
883            && TREE_CODE (val1->value) == INTEGER_CST
884            && TREE_CODE (val2->value) == INTEGER_CST)
885     {
886       /* Ci M Cj = Ci           if (i == j)
887          Ci M Cj = VARYING      if (i != j)
888
889          For INTEGER_CSTs mask unequal bits.  If no equal bits remain,
890          drop to varying.  */
891       val1->mask
892           = double_int_ior (double_int_ior (val1->mask,
893                                             val2->mask),
894                             double_int_xor (tree_to_double_int (val1->value),
895                                             tree_to_double_int (val2->value)));
896       if (double_int_minus_one_p (val1->mask))
897         {
898           val1->lattice_val = VARYING;
899           val1->value = NULL_TREE;
900         }
901     }
902   else if (val1->lattice_val == CONSTANT
903            && val2->lattice_val == CONSTANT
904            && simple_cst_equal (val1->value, val2->value) == 1)
905     {
906       /* Ci M Cj = Ci           if (i == j)
907          Ci M Cj = VARYING      if (i != j)
908
909          VAL1 already contains the value we want for equivalent values.  */
910     }
911   else if (val1->lattice_val == CONSTANT
912            && val2->lattice_val == CONSTANT
913            && (TREE_CODE (val1->value) == ADDR_EXPR
914                || TREE_CODE (val2->value) == ADDR_EXPR))
915     {
916       /* When not equal addresses are involved try meeting for
917          alignment.  */
918       prop_value_t tem = *val2;
919       if (TREE_CODE (val1->value) == ADDR_EXPR)
920         *val1 = get_value_for_expr (val1->value, true);
921       if (TREE_CODE (val2->value) == ADDR_EXPR)
922         tem = get_value_for_expr (val2->value, true);
923       ccp_lattice_meet (val1, &tem);
924     }
925   else
926     {
927       /* Any other combination is VARYING.  */
928       val1->lattice_val = VARYING;
929       val1->mask = double_int_minus_one;
930       val1->value = NULL_TREE;
931     }
932 }
933
934
935 /* Loop through the PHI_NODE's parameters for BLOCK and compare their
936    lattice values to determine PHI_NODE's lattice value.  The value of a
937    PHI node is determined calling ccp_lattice_meet with all the arguments
938    of the PHI node that are incoming via executable edges.  */
939
940 static enum ssa_prop_result
941 ccp_visit_phi_node (gimple phi)
942 {
943   unsigned i;
944   prop_value_t *old_val, new_val;
945
946   if (dump_file && (dump_flags & TDF_DETAILS))
947     {
948       fprintf (dump_file, "\nVisiting PHI node: ");
949       print_gimple_stmt (dump_file, phi, 0, dump_flags);
950     }
951
952   old_val = get_value (gimple_phi_result (phi));
953   switch (old_val->lattice_val)
954     {
955     case VARYING:
956       return SSA_PROP_VARYING;
957
958     case CONSTANT:
959       new_val = *old_val;
960       break;
961
962     case UNDEFINED:
963       new_val.lattice_val = UNDEFINED;
964       new_val.value = NULL_TREE;
965       break;
966
967     default:
968       gcc_unreachable ();
969     }
970
971   for (i = 0; i < gimple_phi_num_args (phi); i++)
972     {
973       /* Compute the meet operator over all the PHI arguments flowing
974          through executable edges.  */
975       edge e = gimple_phi_arg_edge (phi, i);
976
977       if (dump_file && (dump_flags & TDF_DETAILS))
978         {
979           fprintf (dump_file,
980               "\n    Argument #%d (%d -> %d %sexecutable)\n",
981               i, e->src->index, e->dest->index,
982               (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
983         }
984
985       /* If the incoming edge is executable, Compute the meet operator for
986          the existing value of the PHI node and the current PHI argument.  */
987       if (e->flags & EDGE_EXECUTABLE)
988         {
989           tree arg = gimple_phi_arg (phi, i)->def;
990           prop_value_t arg_val = get_value_for_expr (arg, false);
991
992           ccp_lattice_meet (&new_val, &arg_val);
993
994           if (dump_file && (dump_flags & TDF_DETAILS))
995             {
996               fprintf (dump_file, "\t");
997               print_generic_expr (dump_file, arg, dump_flags);
998               dump_lattice_value (dump_file, "\tValue: ", arg_val);
999               fprintf (dump_file, "\n");
1000             }
1001
1002           if (new_val.lattice_val == VARYING)
1003             break;
1004         }
1005     }
1006
1007   if (dump_file && (dump_flags & TDF_DETAILS))
1008     {
1009       dump_lattice_value (dump_file, "\n    PHI node value: ", new_val);
1010       fprintf (dump_file, "\n\n");
1011     }
1012
1013   /* Make the transition to the new value.  */
1014   if (set_lattice_value (gimple_phi_result (phi), new_val))
1015     {
1016       if (new_val.lattice_val == VARYING)
1017         return SSA_PROP_VARYING;
1018       else
1019         return SSA_PROP_INTERESTING;
1020     }
1021   else
1022     return SSA_PROP_NOT_INTERESTING;
1023 }
1024
1025 /* Return the constant value for OP or OP otherwise.  */
1026
1027 static tree
1028 valueize_op (tree op)
1029 {
1030   if (TREE_CODE (op) == SSA_NAME)
1031     {
1032       tree tem = get_constant_value (op);
1033       if (tem)
1034         return tem;
1035     }
1036   return op;
1037 }
1038
1039 /* CCP specific front-end to the non-destructive constant folding
1040    routines.
1041
1042    Attempt to simplify the RHS of STMT knowing that one or more
1043    operands are constants.
1044
1045    If simplification is possible, return the simplified RHS,
1046    otherwise return the original RHS or NULL_TREE.  */
1047
1048 static tree
1049 ccp_fold (gimple stmt)
1050 {
1051   location_t loc = gimple_location (stmt);
1052   switch (gimple_code (stmt))
1053     {
1054     case GIMPLE_COND:
1055       {
1056         /* Handle comparison operators that can appear in GIMPLE form.  */
1057         tree op0 = valueize_op (gimple_cond_lhs (stmt));
1058         tree op1 = valueize_op (gimple_cond_rhs (stmt));
1059         enum tree_code code = gimple_cond_code (stmt);
1060         return fold_binary_loc (loc, code, boolean_type_node, op0, op1);
1061       }
1062
1063     case GIMPLE_SWITCH:
1064       {
1065         /* Return the constant switch index.  */
1066         return valueize_op (gimple_switch_index (stmt));
1067       }
1068
1069     case GIMPLE_ASSIGN:
1070     case GIMPLE_CALL:
1071       return gimple_fold_stmt_to_constant_1 (stmt, valueize_op);
1072
1073     default:
1074       gcc_unreachable ();
1075     }
1076 }
1077
1078 /* Apply the operation CODE in type TYPE to the value, mask pair
1079    RVAL and RMASK representing a value of type RTYPE and set
1080    the value, mask pair *VAL and *MASK to the result.  */
1081
1082 static void
1083 bit_value_unop_1 (enum tree_code code, tree type,
1084                   double_int *val, double_int *mask,
1085                   tree rtype, double_int rval, double_int rmask)
1086 {
1087   switch (code)
1088     {
1089     case BIT_NOT_EXPR:
1090       *mask = rmask;
1091       *val = double_int_not (rval);
1092       break;
1093
1094     case NEGATE_EXPR:
1095       {
1096         double_int temv, temm;
1097         /* Return ~rval + 1.  */
1098         bit_value_unop_1 (BIT_NOT_EXPR, type, &temv, &temm, type, rval, rmask);
1099         bit_value_binop_1 (PLUS_EXPR, type, val, mask,
1100                          type, temv, temm,
1101                          type, double_int_one, double_int_zero);
1102         break;
1103       }
1104
1105     CASE_CONVERT:
1106       {
1107         bool uns;
1108
1109         /* First extend mask and value according to the original type.  */
1110         uns = (TREE_CODE (rtype) == INTEGER_TYPE && TYPE_IS_SIZETYPE (rtype)
1111                ? 0 : TYPE_UNSIGNED (rtype));
1112         *mask = double_int_ext (rmask, TYPE_PRECISION (rtype), uns);
1113         *val = double_int_ext (rval, TYPE_PRECISION (rtype), uns);
1114
1115         /* Then extend mask and value according to the target type.  */
1116         uns = (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type)
1117                ? 0 : TYPE_UNSIGNED (type));
1118         *mask = double_int_ext (*mask, TYPE_PRECISION (type), uns);
1119         *val = double_int_ext (*val, TYPE_PRECISION (type), uns);
1120         break;
1121       }
1122
1123     default:
1124       *mask = double_int_minus_one;
1125       break;
1126     }
1127 }
1128
1129 /* Apply the operation CODE in type TYPE to the value, mask pairs
1130    R1VAL, R1MASK and R2VAL, R2MASK representing a values of type R1TYPE
1131    and R2TYPE and set the value, mask pair *VAL and *MASK to the result.  */
1132
1133 static void
1134 bit_value_binop_1 (enum tree_code code, tree type,
1135                    double_int *val, double_int *mask,
1136                    tree r1type, double_int r1val, double_int r1mask,
1137                    tree r2type, double_int r2val, double_int r2mask)
1138 {
1139   bool uns = (TREE_CODE (type) == INTEGER_TYPE
1140               && TYPE_IS_SIZETYPE (type) ? 0 : TYPE_UNSIGNED (type));
1141   /* Assume we'll get a constant result.  Use an initial varying value,
1142      we fall back to varying in the end if necessary.  */
1143   *mask = double_int_minus_one;
1144   switch (code)
1145     {
1146     case BIT_AND_EXPR:
1147       /* The mask is constant where there is a known not
1148          set bit, (m1 | m2) & ((v1 | m1) & (v2 | m2)) */
1149       *mask = double_int_and (double_int_ior (r1mask, r2mask),
1150                               double_int_and (double_int_ior (r1val, r1mask),
1151                                               double_int_ior (r2val, r2mask)));
1152       *val = double_int_and (r1val, r2val);
1153       break;
1154
1155     case BIT_IOR_EXPR:
1156       /* The mask is constant where there is a known
1157          set bit, (m1 | m2) & ~((v1 & ~m1) | (v2 & ~m2)).  */
1158       *mask = double_int_and_not
1159                 (double_int_ior (r1mask, r2mask),
1160                  double_int_ior (double_int_and_not (r1val, r1mask),
1161                                  double_int_and_not (r2val, r2mask)));
1162       *val = double_int_ior (r1val, r2val);
1163       break;
1164
1165     case BIT_XOR_EXPR:
1166       /* m1 | m2  */
1167       *mask = double_int_ior (r1mask, r2mask);
1168       *val = double_int_xor (r1val, r2val);
1169       break;
1170
1171     case LROTATE_EXPR:
1172     case RROTATE_EXPR:
1173       if (double_int_zero_p (r2mask))
1174         {
1175           HOST_WIDE_INT shift = r2val.low;
1176           if (code == RROTATE_EXPR)
1177             shift = -shift;
1178           *mask = double_int_lrotate (r1mask, shift, TYPE_PRECISION (type));
1179           *val = double_int_lrotate (r1val, shift, TYPE_PRECISION (type));
1180         }
1181       break;
1182
1183     case LSHIFT_EXPR:
1184     case RSHIFT_EXPR:
1185       /* ???  We can handle partially known shift counts if we know
1186          its sign.  That way we can tell that (x << (y | 8)) & 255
1187          is zero.  */
1188       if (double_int_zero_p (r2mask))
1189         {
1190           HOST_WIDE_INT shift = r2val.low;
1191           if (code == RSHIFT_EXPR)
1192             shift = -shift;
1193           /* We need to know if we are doing a left or a right shift
1194              to properly shift in zeros for left shift and unsigned
1195              right shifts and the sign bit for signed right shifts.
1196              For signed right shifts we shift in varying in case
1197              the sign bit was varying.  */
1198           if (shift > 0)
1199             {
1200               *mask = double_int_lshift (r1mask, shift,
1201                                          TYPE_PRECISION (type), false);
1202               *val = double_int_lshift (r1val, shift,
1203                                         TYPE_PRECISION (type), false);
1204             }
1205           else if (shift < 0)
1206             {
1207               /* ???  We can have sizetype related inconsistencies in
1208                  the IL.  */
1209               if ((TREE_CODE (r1type) == INTEGER_TYPE
1210                    && (TYPE_IS_SIZETYPE (r1type)
1211                        ? 0 : TYPE_UNSIGNED (r1type))) != uns)
1212                 break;
1213
1214               shift = -shift;
1215               *mask = double_int_rshift (r1mask, shift,
1216                                          TYPE_PRECISION (type), !uns);
1217               *val = double_int_rshift (r1val, shift,
1218                                         TYPE_PRECISION (type), !uns);
1219             }
1220           else
1221             {
1222               *mask = r1mask;
1223               *val = r1val;
1224             }
1225         }
1226       break;
1227
1228     case PLUS_EXPR:
1229     case POINTER_PLUS_EXPR:
1230       {
1231         double_int lo, hi;
1232         /* Do the addition with unknown bits set to zero, to give carry-ins of
1233            zero wherever possible.  */
1234         lo = double_int_add (double_int_and_not (r1val, r1mask),
1235                              double_int_and_not (r2val, r2mask));
1236         lo = double_int_ext (lo, TYPE_PRECISION (type), uns);
1237         /* Do the addition with unknown bits set to one, to give carry-ins of
1238            one wherever possible.  */
1239         hi = double_int_add (double_int_ior (r1val, r1mask),
1240                              double_int_ior (r2val, r2mask));
1241         hi = double_int_ext (hi, TYPE_PRECISION (type), uns);
1242         /* Each bit in the result is known if (a) the corresponding bits in
1243            both inputs are known, and (b) the carry-in to that bit position
1244            is known.  We can check condition (b) by seeing if we got the same
1245            result with minimised carries as with maximised carries.  */
1246         *mask = double_int_ior (double_int_ior (r1mask, r2mask),
1247                                 double_int_xor (lo, hi));
1248         *mask = double_int_ext (*mask, TYPE_PRECISION (type), uns);
1249         /* It shouldn't matter whether we choose lo or hi here.  */
1250         *val = lo;
1251         break;
1252       }
1253
1254     case MINUS_EXPR:
1255       {
1256         double_int temv, temm;
1257         bit_value_unop_1 (NEGATE_EXPR, r2type, &temv, &temm,
1258                           r2type, r2val, r2mask);
1259         bit_value_binop_1 (PLUS_EXPR, type, val, mask,
1260                            r1type, r1val, r1mask,
1261                            r2type, temv, temm);
1262         break;
1263       }
1264
1265     case MULT_EXPR:
1266       {
1267         /* Just track trailing zeros in both operands and transfer
1268            them to the other.  */
1269         int r1tz = double_int_ctz (double_int_ior (r1val, r1mask));
1270         int r2tz = double_int_ctz (double_int_ior (r2val, r2mask));
1271         if (r1tz + r2tz >= HOST_BITS_PER_DOUBLE_INT)
1272           {
1273             *mask = double_int_zero;
1274             *val = double_int_zero;
1275           }
1276         else if (r1tz + r2tz > 0)
1277           {
1278             *mask = double_int_not (double_int_mask (r1tz + r2tz));
1279             *mask = double_int_ext (*mask, TYPE_PRECISION (type), uns);
1280             *val = double_int_zero;
1281           }
1282         break;
1283       }
1284
1285     case EQ_EXPR:
1286     case NE_EXPR:
1287       {
1288         double_int m = double_int_ior (r1mask, r2mask);
1289         if (!double_int_equal_p (double_int_and_not (r1val, m),
1290                                  double_int_and_not (r2val, m)))
1291           {
1292             *mask = double_int_zero;
1293             *val = ((code == EQ_EXPR) ? double_int_zero : double_int_one);
1294           }
1295         else
1296           {
1297             /* We know the result of a comparison is always one or zero.  */
1298             *mask = double_int_one;
1299             *val = double_int_zero;
1300           }
1301         break;
1302       }
1303
1304     case GE_EXPR:
1305     case GT_EXPR:
1306       {
1307         double_int tem = r1val;
1308         r1val = r2val;
1309         r2val = tem;
1310         tem = r1mask;
1311         r1mask = r2mask;
1312         r2mask = tem;
1313         code = swap_tree_comparison (code);
1314       }
1315       /* Fallthru.  */
1316     case LT_EXPR:
1317     case LE_EXPR:
1318       {
1319         int minmax, maxmin;
1320         /* If the most significant bits are not known we know nothing.  */
1321         if (double_int_negative_p (r1mask) || double_int_negative_p (r2mask))
1322           break;
1323
1324         /* For comparisons the signedness is in the comparison operands.  */
1325         uns = (TREE_CODE (r1type) == INTEGER_TYPE
1326                && TYPE_IS_SIZETYPE (r1type) ? 0 : TYPE_UNSIGNED (r1type));
1327         /* ???  We can have sizetype related inconsistencies in the IL.  */
1328         if ((TREE_CODE (r2type) == INTEGER_TYPE
1329              && TYPE_IS_SIZETYPE (r2type) ? 0 : TYPE_UNSIGNED (r2type)) != uns)
1330           break;
1331
1332         /* If we know the most significant bits we know the values
1333            value ranges by means of treating varying bits as zero
1334            or one.  Do a cross comparison of the max/min pairs.  */
1335         maxmin = double_int_cmp (double_int_ior (r1val, r1mask),
1336                                  double_int_and_not (r2val, r2mask), uns);
1337         minmax = double_int_cmp (double_int_and_not (r1val, r1mask),
1338                                  double_int_ior (r2val, r2mask), uns);
1339         if (maxmin < 0)  /* r1 is less than r2.  */
1340           {
1341             *mask = double_int_zero;
1342             *val = double_int_one;
1343           }
1344         else if (minmax > 0)  /* r1 is not less or equal to r2.  */
1345           {
1346             *mask = double_int_zero;
1347             *val = double_int_zero;
1348           }
1349         else if (maxmin == minmax)  /* r1 and r2 are equal.  */
1350           {
1351             /* This probably should never happen as we'd have
1352                folded the thing during fully constant value folding.  */
1353             *mask = double_int_zero;
1354             *val = (code == LE_EXPR ? double_int_one :  double_int_zero);
1355           }
1356         else
1357           {
1358             /* We know the result of a comparison is always one or zero.  */
1359             *mask = double_int_one;
1360             *val = double_int_zero;
1361           }
1362         break;
1363       }
1364
1365     default:;
1366     }
1367 }
1368
1369 /* Return the propagation value when applying the operation CODE to
1370    the value RHS yielding type TYPE.  */
1371
1372 static prop_value_t
1373 bit_value_unop (enum tree_code code, tree type, tree rhs)
1374 {
1375   prop_value_t rval = get_value_for_expr (rhs, true);
1376   double_int value, mask;
1377   prop_value_t val;
1378
1379   if (rval.lattice_val == UNDEFINED)
1380     return rval;
1381
1382   gcc_assert ((rval.lattice_val == CONSTANT
1383                && TREE_CODE (rval.value) == INTEGER_CST)
1384               || double_int_minus_one_p (rval.mask));
1385   bit_value_unop_1 (code, type, &value, &mask,
1386                     TREE_TYPE (rhs), value_to_double_int (rval), rval.mask);
1387   if (!double_int_minus_one_p (mask))
1388     {
1389       val.lattice_val = CONSTANT;
1390       val.mask = mask;
1391       /* ???  Delay building trees here.  */
1392       val.value = double_int_to_tree (type, value);
1393     }
1394   else
1395     {
1396       val.lattice_val = VARYING;
1397       val.value = NULL_TREE;
1398       val.mask = double_int_minus_one;
1399     }
1400   return val;
1401 }
1402
1403 /* Return the propagation value when applying the operation CODE to
1404    the values RHS1 and RHS2 yielding type TYPE.  */
1405
1406 static prop_value_t
1407 bit_value_binop (enum tree_code code, tree type, tree rhs1, tree rhs2)
1408 {
1409   prop_value_t r1val = get_value_for_expr (rhs1, true);
1410   prop_value_t r2val = get_value_for_expr (rhs2, true);
1411   double_int value, mask;
1412   prop_value_t val;
1413
1414   if (r1val.lattice_val == UNDEFINED
1415       || r2val.lattice_val == UNDEFINED)
1416     {
1417       val.lattice_val = VARYING;
1418       val.value = NULL_TREE;
1419       val.mask = double_int_minus_one;
1420       return val;
1421     }
1422
1423   gcc_assert ((r1val.lattice_val == CONSTANT
1424                && TREE_CODE (r1val.value) == INTEGER_CST)
1425               || double_int_minus_one_p (r1val.mask));
1426   gcc_assert ((r2val.lattice_val == CONSTANT
1427                && TREE_CODE (r2val.value) == INTEGER_CST)
1428               || double_int_minus_one_p (r2val.mask));
1429   bit_value_binop_1 (code, type, &value, &mask,
1430                      TREE_TYPE (rhs1), value_to_double_int (r1val), r1val.mask,
1431                      TREE_TYPE (rhs2), value_to_double_int (r2val), r2val.mask);
1432   if (!double_int_minus_one_p (mask))
1433     {
1434       val.lattice_val = CONSTANT;
1435       val.mask = mask;
1436       /* ???  Delay building trees here.  */
1437       val.value = double_int_to_tree (type, value);
1438     }
1439   else
1440     {
1441       val.lattice_val = VARYING;
1442       val.value = NULL_TREE;
1443       val.mask = double_int_minus_one;
1444     }
1445   return val;
1446 }
1447
1448 /* Return the propagation value when applying __builtin_assume_aligned to
1449    its arguments.  */
1450
1451 static prop_value_t
1452 bit_value_assume_aligned (gimple stmt)
1453 {
1454   tree ptr = gimple_call_arg (stmt, 0), align, misalign = NULL_TREE;
1455   tree type = TREE_TYPE (ptr);
1456   unsigned HOST_WIDE_INT aligni, misaligni = 0;
1457   prop_value_t ptrval = get_value_for_expr (ptr, true);
1458   prop_value_t alignval;
1459   double_int value, mask;
1460   prop_value_t val;
1461   if (ptrval.lattice_val == UNDEFINED)
1462     return ptrval;
1463   gcc_assert ((ptrval.lattice_val == CONSTANT
1464                && TREE_CODE (ptrval.value) == INTEGER_CST)
1465               || double_int_minus_one_p (ptrval.mask));
1466   align = gimple_call_arg (stmt, 1);
1467   if (!host_integerp (align, 1))
1468     return ptrval;
1469   aligni = tree_low_cst (align, 1);
1470   if (aligni <= 1
1471       || (aligni & (aligni - 1)) != 0)
1472     return ptrval;
1473   if (gimple_call_num_args (stmt) > 2)
1474     {
1475       misalign = gimple_call_arg (stmt, 2);
1476       if (!host_integerp (misalign, 1))
1477         return ptrval;
1478       misaligni = tree_low_cst (misalign, 1);
1479       if (misaligni >= aligni)
1480         return ptrval;
1481     }
1482   align = build_int_cst_type (type, -aligni);
1483   alignval = get_value_for_expr (align, true);
1484   bit_value_binop_1 (BIT_AND_EXPR, type, &value, &mask,
1485                      type, value_to_double_int (ptrval), ptrval.mask,
1486                      type, value_to_double_int (alignval), alignval.mask);
1487   if (!double_int_minus_one_p (mask))
1488     {
1489       val.lattice_val = CONSTANT;
1490       val.mask = mask;
1491       gcc_assert ((mask.low & (aligni - 1)) == 0);
1492       gcc_assert ((value.low & (aligni - 1)) == 0);
1493       value.low |= misaligni;
1494       /* ???  Delay building trees here.  */
1495       val.value = double_int_to_tree (type, value);
1496     }
1497   else
1498     {
1499       val.lattice_val = VARYING;
1500       val.value = NULL_TREE;
1501       val.mask = double_int_minus_one;
1502     }
1503   return val;
1504 }
1505
1506 /* Evaluate statement STMT.
1507    Valid only for assignments, calls, conditionals, and switches. */
1508
1509 static prop_value_t
1510 evaluate_stmt (gimple stmt)
1511 {
1512   prop_value_t val;
1513   tree simplified = NULL_TREE;
1514   ccp_lattice_t likelyvalue = likely_value (stmt);
1515   bool is_constant = false;
1516   unsigned int align;
1517
1518   if (dump_file && (dump_flags & TDF_DETAILS))
1519     {
1520       fprintf (dump_file, "which is likely ");
1521       switch (likelyvalue)
1522         {
1523         case CONSTANT:
1524           fprintf (dump_file, "CONSTANT");
1525           break;
1526         case UNDEFINED:
1527           fprintf (dump_file, "UNDEFINED");
1528           break;
1529         case VARYING:
1530           fprintf (dump_file, "VARYING");
1531           break;
1532         default:;
1533         }
1534       fprintf (dump_file, "\n");
1535     }
1536
1537   /* If the statement is likely to have a CONSTANT result, then try
1538      to fold the statement to determine the constant value.  */
1539   /* FIXME.  This is the only place that we call ccp_fold.
1540      Since likely_value never returns CONSTANT for calls, we will
1541      not attempt to fold them, including builtins that may profit.  */
1542   if (likelyvalue == CONSTANT)
1543     {
1544       fold_defer_overflow_warnings ();
1545       simplified = ccp_fold (stmt);
1546       is_constant = simplified && is_gimple_min_invariant (simplified);
1547       fold_undefer_overflow_warnings (is_constant, stmt, 0);
1548       if (is_constant)
1549         {
1550           /* The statement produced a constant value.  */
1551           val.lattice_val = CONSTANT;
1552           val.value = simplified;
1553           val.mask = double_int_zero;
1554         }
1555     }
1556   /* If the statement is likely to have a VARYING result, then do not
1557      bother folding the statement.  */
1558   else if (likelyvalue == VARYING)
1559     {
1560       enum gimple_code code = gimple_code (stmt);
1561       if (code == GIMPLE_ASSIGN)
1562         {
1563           enum tree_code subcode = gimple_assign_rhs_code (stmt);
1564
1565           /* Other cases cannot satisfy is_gimple_min_invariant
1566              without folding.  */
1567           if (get_gimple_rhs_class (subcode) == GIMPLE_SINGLE_RHS)
1568             simplified = gimple_assign_rhs1 (stmt);
1569         }
1570       else if (code == GIMPLE_SWITCH)
1571         simplified = gimple_switch_index (stmt);
1572       else
1573         /* These cannot satisfy is_gimple_min_invariant without folding.  */
1574         gcc_assert (code == GIMPLE_CALL || code == GIMPLE_COND);
1575       is_constant = simplified && is_gimple_min_invariant (simplified);
1576       if (is_constant)
1577         {
1578           /* The statement produced a constant value.  */
1579           val.lattice_val = CONSTANT;
1580           val.value = simplified;
1581           val.mask = double_int_zero;
1582         }
1583     }
1584
1585   /* Resort to simplification for bitwise tracking.  */
1586   if (flag_tree_bit_ccp
1587       && (likelyvalue == CONSTANT || is_gimple_call (stmt))
1588       && !is_constant)
1589     {
1590       enum gimple_code code = gimple_code (stmt);
1591       val.lattice_val = VARYING;
1592       val.value = NULL_TREE;
1593       val.mask = double_int_minus_one;
1594       if (code == GIMPLE_ASSIGN)
1595         {
1596           enum tree_code subcode = gimple_assign_rhs_code (stmt);
1597           tree rhs1 = gimple_assign_rhs1 (stmt);
1598           switch (get_gimple_rhs_class (subcode))
1599             {
1600             case GIMPLE_SINGLE_RHS:
1601               if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1602                   || POINTER_TYPE_P (TREE_TYPE (rhs1)))
1603                 val = get_value_for_expr (rhs1, true);
1604               break;
1605
1606             case GIMPLE_UNARY_RHS:
1607               if ((INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1608                    || POINTER_TYPE_P (TREE_TYPE (rhs1)))
1609                   && (INTEGRAL_TYPE_P (gimple_expr_type (stmt))
1610                       || POINTER_TYPE_P (gimple_expr_type (stmt))))
1611                 val = bit_value_unop (subcode, gimple_expr_type (stmt), rhs1);
1612               break;
1613
1614             case GIMPLE_BINARY_RHS:
1615               if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1616                   || POINTER_TYPE_P (TREE_TYPE (rhs1)))
1617                 {
1618                   tree lhs = gimple_assign_lhs (stmt);
1619                   tree rhs2 = gimple_assign_rhs2 (stmt);
1620                   val = bit_value_binop (subcode,
1621                                          TREE_TYPE (lhs), rhs1, rhs2);
1622                 }
1623               break;
1624
1625             default:;
1626             }
1627         }
1628       else if (code == GIMPLE_COND)
1629         {
1630           enum tree_code code = gimple_cond_code (stmt);
1631           tree rhs1 = gimple_cond_lhs (stmt);
1632           tree rhs2 = gimple_cond_rhs (stmt);
1633           if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1634               || POINTER_TYPE_P (TREE_TYPE (rhs1)))
1635             val = bit_value_binop (code, TREE_TYPE (rhs1), rhs1, rhs2);
1636         }
1637       else if (gimple_call_builtin_class_p (stmt, BUILT_IN_NORMAL))
1638         {
1639           tree fndecl = gimple_call_fndecl (stmt);
1640           switch (DECL_FUNCTION_CODE (fndecl))
1641             {
1642             case BUILT_IN_MALLOC:
1643             case BUILT_IN_REALLOC:
1644             case BUILT_IN_CALLOC:
1645             case BUILT_IN_STRDUP:
1646             case BUILT_IN_STRNDUP:
1647               val.lattice_val = CONSTANT;
1648               val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
1649               val.mask = shwi_to_double_int
1650                            (~(((HOST_WIDE_INT) MALLOC_ABI_ALIGNMENT)
1651                               / BITS_PER_UNIT - 1));
1652               break;
1653
1654             case BUILT_IN_ALLOCA:
1655             case BUILT_IN_ALLOCA_WITH_ALIGN:
1656               align = (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_ALLOCA_WITH_ALIGN
1657                        ? TREE_INT_CST_LOW (gimple_call_arg (stmt, 1))
1658                        : BIGGEST_ALIGNMENT);
1659               val.lattice_val = CONSTANT;
1660               val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
1661               val.mask = shwi_to_double_int
1662                            (~(((HOST_WIDE_INT) align)
1663                               / BITS_PER_UNIT - 1));
1664               break;
1665
1666             /* These builtins return their first argument, unmodified.  */
1667             case BUILT_IN_MEMCPY:
1668             case BUILT_IN_MEMMOVE:
1669             case BUILT_IN_MEMSET:
1670             case BUILT_IN_STRCPY:
1671             case BUILT_IN_STRNCPY:
1672             case BUILT_IN_MEMCPY_CHK:
1673             case BUILT_IN_MEMMOVE_CHK:
1674             case BUILT_IN_MEMSET_CHK:
1675             case BUILT_IN_STRCPY_CHK:
1676             case BUILT_IN_STRNCPY_CHK:
1677               val = get_value_for_expr (gimple_call_arg (stmt, 0), true);
1678               break;
1679
1680             case BUILT_IN_ASSUME_ALIGNED:
1681               val = bit_value_assume_aligned (stmt);
1682               break;
1683
1684             default:;
1685             }
1686         }
1687       is_constant = (val.lattice_val == CONSTANT);
1688     }
1689
1690   if (!is_constant)
1691     {
1692       /* The statement produced a nonconstant value.  If the statement
1693          had UNDEFINED operands, then the result of the statement
1694          should be UNDEFINED.  Otherwise, the statement is VARYING.  */
1695       if (likelyvalue == UNDEFINED)
1696         {
1697           val.lattice_val = likelyvalue;
1698           val.mask = double_int_zero;
1699         }
1700       else
1701         {
1702           val.lattice_val = VARYING;
1703           val.mask = double_int_minus_one;
1704         }
1705
1706       val.value = NULL_TREE;
1707     }
1708
1709   return val;
1710 }
1711
1712 /* Given a BUILT_IN_STACK_SAVE value SAVED_VAL, insert a clobber of VAR before
1713    each matching BUILT_IN_STACK_RESTORE.  Mark visited phis in VISITED.  */
1714
1715 static void
1716 insert_clobber_before_stack_restore (tree saved_val, tree var, htab_t *visited)
1717 {
1718   gimple stmt, clobber_stmt;
1719   tree clobber;
1720   imm_use_iterator iter;
1721   gimple_stmt_iterator i;
1722   gimple *slot;
1723
1724   FOR_EACH_IMM_USE_STMT (stmt, iter, saved_val)
1725     if (gimple_call_builtin_p (stmt, BUILT_IN_STACK_RESTORE))
1726       {
1727         clobber = build_constructor (TREE_TYPE (var), NULL);
1728         TREE_THIS_VOLATILE (clobber) = 1;
1729         clobber_stmt = gimple_build_assign (var, clobber);
1730
1731         i = gsi_for_stmt (stmt);
1732         gsi_insert_before (&i, clobber_stmt, GSI_SAME_STMT);
1733       }
1734     else if (gimple_code (stmt) == GIMPLE_PHI)
1735       {
1736         if (*visited == NULL)
1737           *visited = htab_create (10, htab_hash_pointer, htab_eq_pointer, NULL);
1738
1739         slot = (gimple *)htab_find_slot (*visited, stmt, INSERT);
1740         if (*slot != NULL)
1741           continue;
1742
1743         *slot = stmt;
1744         insert_clobber_before_stack_restore (gimple_phi_result (stmt), var,
1745                                              visited);
1746       }
1747     else
1748       gcc_assert (is_gimple_debug (stmt));
1749 }
1750
1751 /* Advance the iterator to the previous non-debug gimple statement in the same
1752    or dominating basic block.  */
1753
1754 static inline void
1755 gsi_prev_dom_bb_nondebug (gimple_stmt_iterator *i)
1756 {
1757   basic_block dom;
1758
1759   gsi_prev_nondebug (i);
1760   while (gsi_end_p (*i))
1761     {
1762       dom = get_immediate_dominator (CDI_DOMINATORS, i->bb);
1763       if (dom == NULL || dom == ENTRY_BLOCK_PTR)
1764         return;
1765
1766       *i = gsi_last_bb (dom);
1767     }
1768 }
1769
1770 /* Find a BUILT_IN_STACK_SAVE dominating gsi_stmt (I), and insert
1771    a clobber of VAR before each matching BUILT_IN_STACK_RESTORE.
1772
1773    It is possible that BUILT_IN_STACK_SAVE cannot be find in a dominator when a
1774    previous pass (such as DOM) duplicated it along multiple paths to a BB.  In
1775    that case the function gives up without inserting the clobbers.  */
1776
1777 static void
1778 insert_clobbers_for_var (gimple_stmt_iterator i, tree var)
1779 {
1780   gimple stmt;
1781   tree saved_val;
1782   htab_t visited = NULL;
1783
1784   for (; !gsi_end_p (i); gsi_prev_dom_bb_nondebug (&i))
1785     {
1786       stmt = gsi_stmt (i);
1787
1788       if (!gimple_call_builtin_p (stmt, BUILT_IN_STACK_SAVE))
1789         continue;
1790
1791       saved_val = gimple_call_lhs (stmt);
1792       if (saved_val == NULL_TREE)
1793         continue;
1794
1795       insert_clobber_before_stack_restore (saved_val, var, &visited);
1796       break;
1797     }
1798
1799   if (visited != NULL)
1800     htab_delete (visited);
1801 }
1802
1803 /* Detects a __builtin_alloca_with_align with constant size argument.  Declares
1804    fixed-size array and returns the address, if found, otherwise returns
1805    NULL_TREE.  */
1806
1807 static tree
1808 fold_builtin_alloca_with_align (gimple stmt)
1809 {
1810   unsigned HOST_WIDE_INT size, threshold, n_elem;
1811   tree lhs, arg, block, var, elem_type, array_type;
1812
1813   /* Get lhs.  */
1814   lhs = gimple_call_lhs (stmt);
1815   if (lhs == NULL_TREE)
1816     return NULL_TREE;
1817
1818   /* Detect constant argument.  */
1819   arg = get_constant_value (gimple_call_arg (stmt, 0));
1820   if (arg == NULL_TREE
1821       || TREE_CODE (arg) != INTEGER_CST
1822       || !host_integerp (arg, 1))
1823     return NULL_TREE;
1824
1825   size = TREE_INT_CST_LOW (arg);
1826
1827   /* Heuristic: don't fold large allocas.  */
1828   threshold = (unsigned HOST_WIDE_INT)PARAM_VALUE (PARAM_LARGE_STACK_FRAME);
1829   /* In case the alloca is located at function entry, it has the same lifetime
1830      as a declared array, so we allow a larger size.  */
1831   block = gimple_block (stmt);
1832   if (!(cfun->after_inlining
1833         && TREE_CODE (BLOCK_SUPERCONTEXT (block)) == FUNCTION_DECL))
1834     threshold /= 10;
1835   if (size > threshold)
1836     return NULL_TREE;
1837
1838   /* Declare array.  */
1839   elem_type = build_nonstandard_integer_type (BITS_PER_UNIT, 1);
1840   n_elem = size * 8 / BITS_PER_UNIT;
1841   array_type = build_array_type_nelts (elem_type, n_elem);
1842   var = create_tmp_var (array_type, NULL);
1843   DECL_ALIGN (var) = TREE_INT_CST_LOW (gimple_call_arg (stmt, 1));
1844   {
1845     struct ptr_info_def *pi = SSA_NAME_PTR_INFO (lhs);
1846     if (pi != NULL && !pi->pt.anything)
1847       {
1848         bool singleton_p;
1849         unsigned uid;
1850         singleton_p = pt_solution_singleton_p (&pi->pt, &uid);
1851         gcc_assert (singleton_p);
1852         SET_DECL_PT_UID (var, uid);
1853       }
1854   }
1855
1856   /* Fold alloca to the address of the array.  */
1857   return fold_convert (TREE_TYPE (lhs), build_fold_addr_expr (var));
1858 }
1859
1860 /* Fold the stmt at *GSI with CCP specific information that propagating
1861    and regular folding does not catch.  */
1862
1863 static bool
1864 ccp_fold_stmt (gimple_stmt_iterator *gsi)
1865 {
1866   gimple stmt = gsi_stmt (*gsi);
1867
1868   switch (gimple_code (stmt))
1869     {
1870     case GIMPLE_COND:
1871       {
1872         prop_value_t val;
1873         /* Statement evaluation will handle type mismatches in constants
1874            more gracefully than the final propagation.  This allows us to
1875            fold more conditionals here.  */
1876         val = evaluate_stmt (stmt);
1877         if (val.lattice_val != CONSTANT
1878             || !double_int_zero_p (val.mask))
1879           return false;
1880
1881         if (dump_file)
1882           {
1883             fprintf (dump_file, "Folding predicate ");
1884             print_gimple_expr (dump_file, stmt, 0, 0);
1885             fprintf (dump_file, " to ");
1886             print_generic_expr (dump_file, val.value, 0);
1887             fprintf (dump_file, "\n");
1888           }
1889
1890         if (integer_zerop (val.value))
1891           gimple_cond_make_false (stmt);
1892         else
1893           gimple_cond_make_true (stmt);
1894
1895         return true;
1896       }
1897
1898     case GIMPLE_CALL:
1899       {
1900         tree lhs = gimple_call_lhs (stmt);
1901         int flags = gimple_call_flags (stmt);
1902         tree val;
1903         tree argt;
1904         bool changed = false;
1905         unsigned i;
1906
1907         /* If the call was folded into a constant make sure it goes
1908            away even if we cannot propagate into all uses because of
1909            type issues.  */
1910         if (lhs
1911             && TREE_CODE (lhs) == SSA_NAME
1912             && (val = get_constant_value (lhs))
1913             /* Don't optimize away calls that have side-effects.  */
1914             && (flags & (ECF_CONST|ECF_PURE)) != 0
1915             && (flags & ECF_LOOPING_CONST_OR_PURE) == 0)
1916           {
1917             tree new_rhs = unshare_expr (val);
1918             bool res;
1919             if (!useless_type_conversion_p (TREE_TYPE (lhs),
1920                                             TREE_TYPE (new_rhs)))
1921               new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs);
1922             res = update_call_from_tree (gsi, new_rhs);
1923             gcc_assert (res);
1924             return true;
1925           }
1926
1927         /* Internal calls provide no argument types, so the extra laxity
1928            for normal calls does not apply.  */
1929         if (gimple_call_internal_p (stmt))
1930           return false;
1931
1932         /* The heuristic of fold_builtin_alloca_with_align differs before and
1933            after inlining, so we don't require the arg to be changed into a
1934            constant for folding, but just to be constant.  */
1935         if (gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN))
1936           {
1937             tree new_rhs = fold_builtin_alloca_with_align (stmt);
1938             if (new_rhs)
1939               {
1940                 bool res = update_call_from_tree (gsi, new_rhs);
1941                 tree var = TREE_OPERAND (TREE_OPERAND (new_rhs, 0),0);
1942                 gcc_assert (res);
1943                 insert_clobbers_for_var (*gsi, var);
1944                 return true;
1945               }
1946           }
1947
1948         /* Propagate into the call arguments.  Compared to replace_uses_in
1949            this can use the argument slot types for type verification
1950            instead of the current argument type.  We also can safely
1951            drop qualifiers here as we are dealing with constants anyway.  */
1952         argt = TYPE_ARG_TYPES (gimple_call_fntype (stmt));
1953         for (i = 0; i < gimple_call_num_args (stmt) && argt;
1954              ++i, argt = TREE_CHAIN (argt))
1955           {
1956             tree arg = gimple_call_arg (stmt, i);
1957             if (TREE_CODE (arg) == SSA_NAME
1958                 && (val = get_constant_value (arg))
1959                 && useless_type_conversion_p
1960                      (TYPE_MAIN_VARIANT (TREE_VALUE (argt)),
1961                       TYPE_MAIN_VARIANT (TREE_TYPE (val))))
1962               {
1963                 gimple_call_set_arg (stmt, i, unshare_expr (val));
1964                 changed = true;
1965               }
1966           }
1967
1968         return changed;
1969       }
1970
1971     case GIMPLE_ASSIGN:
1972       {
1973         tree lhs = gimple_assign_lhs (stmt);
1974         tree val;
1975
1976         /* If we have a load that turned out to be constant replace it
1977            as we cannot propagate into all uses in all cases.  */
1978         if (gimple_assign_single_p (stmt)
1979             && TREE_CODE (lhs) == SSA_NAME
1980             && (val = get_constant_value (lhs)))
1981           {
1982             tree rhs = unshare_expr (val);
1983             if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
1984               rhs = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
1985             gimple_assign_set_rhs_from_tree (gsi, rhs);
1986             return true;
1987           }
1988
1989         return false;
1990       }
1991
1992     default:
1993       return false;
1994     }
1995 }
1996
1997 /* Visit the assignment statement STMT.  Set the value of its LHS to the
1998    value computed by the RHS and store LHS in *OUTPUT_P.  If STMT
1999    creates virtual definitions, set the value of each new name to that
2000    of the RHS (if we can derive a constant out of the RHS).
2001    Value-returning call statements also perform an assignment, and
2002    are handled here.  */
2003
2004 static enum ssa_prop_result
2005 visit_assignment (gimple stmt, tree *output_p)
2006 {
2007   prop_value_t val;
2008   enum ssa_prop_result retval;
2009
2010   tree lhs = gimple_get_lhs (stmt);
2011
2012   gcc_assert (gimple_code (stmt) != GIMPLE_CALL
2013               || gimple_call_lhs (stmt) != NULL_TREE);
2014
2015   if (gimple_assign_single_p (stmt)
2016       && gimple_assign_rhs_code (stmt) == SSA_NAME)
2017     /* For a simple copy operation, we copy the lattice values.  */
2018     val = *get_value (gimple_assign_rhs1 (stmt));
2019   else
2020     /* Evaluate the statement, which could be
2021        either a GIMPLE_ASSIGN or a GIMPLE_CALL.  */
2022     val = evaluate_stmt (stmt);
2023
2024   retval = SSA_PROP_NOT_INTERESTING;
2025
2026   /* Set the lattice value of the statement's output.  */
2027   if (TREE_CODE (lhs) == SSA_NAME)
2028     {
2029       /* If STMT is an assignment to an SSA_NAME, we only have one
2030          value to set.  */
2031       if (set_lattice_value (lhs, val))
2032         {
2033           *output_p = lhs;
2034           if (val.lattice_val == VARYING)
2035             retval = SSA_PROP_VARYING;
2036           else
2037             retval = SSA_PROP_INTERESTING;
2038         }
2039     }
2040
2041   return retval;
2042 }
2043
2044
2045 /* Visit the conditional statement STMT.  Return SSA_PROP_INTERESTING
2046    if it can determine which edge will be taken.  Otherwise, return
2047    SSA_PROP_VARYING.  */
2048
2049 static enum ssa_prop_result
2050 visit_cond_stmt (gimple stmt, edge *taken_edge_p)
2051 {
2052   prop_value_t val;
2053   basic_block block;
2054
2055   block = gimple_bb (stmt);
2056   val = evaluate_stmt (stmt);
2057   if (val.lattice_val != CONSTANT
2058       || !double_int_zero_p (val.mask))
2059     return SSA_PROP_VARYING;
2060
2061   /* Find which edge out of the conditional block will be taken and add it
2062      to the worklist.  If no single edge can be determined statically,
2063      return SSA_PROP_VARYING to feed all the outgoing edges to the
2064      propagation engine.  */
2065   *taken_edge_p = find_taken_edge (block, val.value);
2066   if (*taken_edge_p)
2067     return SSA_PROP_INTERESTING;
2068   else
2069     return SSA_PROP_VARYING;
2070 }
2071
2072
2073 /* Evaluate statement STMT.  If the statement produces an output value and
2074    its evaluation changes the lattice value of its output, return
2075    SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the
2076    output value.
2077
2078    If STMT is a conditional branch and we can determine its truth
2079    value, set *TAKEN_EDGE_P accordingly.  If STMT produces a varying
2080    value, return SSA_PROP_VARYING.  */
2081
2082 static enum ssa_prop_result
2083 ccp_visit_stmt (gimple stmt, edge *taken_edge_p, tree *output_p)
2084 {
2085   tree def;
2086   ssa_op_iter iter;
2087
2088   if (dump_file && (dump_flags & TDF_DETAILS))
2089     {
2090       fprintf (dump_file, "\nVisiting statement:\n");
2091       print_gimple_stmt (dump_file, stmt, 0, dump_flags);
2092     }
2093
2094   switch (gimple_code (stmt))
2095     {
2096       case GIMPLE_ASSIGN:
2097         /* If the statement is an assignment that produces a single
2098            output value, evaluate its RHS to see if the lattice value of
2099            its output has changed.  */
2100         return visit_assignment (stmt, output_p);
2101
2102       case GIMPLE_CALL:
2103         /* A value-returning call also performs an assignment.  */
2104         if (gimple_call_lhs (stmt) != NULL_TREE)
2105           return visit_assignment (stmt, output_p);
2106         break;
2107
2108       case GIMPLE_COND:
2109       case GIMPLE_SWITCH:
2110         /* If STMT is a conditional branch, see if we can determine
2111            which branch will be taken.   */
2112         /* FIXME.  It appears that we should be able to optimize
2113            computed GOTOs here as well.  */
2114         return visit_cond_stmt (stmt, taken_edge_p);
2115
2116       default:
2117         break;
2118     }
2119
2120   /* Any other kind of statement is not interesting for constant
2121      propagation and, therefore, not worth simulating.  */
2122   if (dump_file && (dump_flags & TDF_DETAILS))
2123     fprintf (dump_file, "No interesting values produced.  Marked VARYING.\n");
2124
2125   /* Definitions made by statements other than assignments to
2126      SSA_NAMEs represent unknown modifications to their outputs.
2127      Mark them VARYING.  */
2128   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
2129     {
2130       prop_value_t v = { VARYING, NULL_TREE, { -1, (HOST_WIDE_INT) -1 } };
2131       set_lattice_value (def, v);
2132     }
2133
2134   return SSA_PROP_VARYING;
2135 }
2136
2137
2138 /* Main entry point for SSA Conditional Constant Propagation.  */
2139
2140 static unsigned int
2141 do_ssa_ccp (void)
2142 {
2143   unsigned int todo = 0;
2144   calculate_dominance_info (CDI_DOMINATORS);
2145   ccp_initialize ();
2146   ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node);
2147   if (ccp_finalize ())
2148     todo = (TODO_cleanup_cfg | TODO_update_ssa | TODO_remove_unused_locals);
2149   free_dominance_info (CDI_DOMINATORS);
2150   return todo;
2151 }
2152
2153
2154 static bool
2155 gate_ccp (void)
2156 {
2157   return flag_tree_ccp != 0;
2158 }
2159
2160
2161 struct gimple_opt_pass pass_ccp =
2162 {
2163  {
2164   GIMPLE_PASS,
2165   "ccp",                                /* name */
2166   gate_ccp,                             /* gate */
2167   do_ssa_ccp,                           /* execute */
2168   NULL,                                 /* sub */
2169   NULL,                                 /* next */
2170   0,                                    /* static_pass_number */
2171   TV_TREE_CCP,                          /* tv_id */
2172   PROP_cfg | PROP_ssa,                  /* properties_required */
2173   0,                                    /* properties_provided */
2174   0,                                    /* properties_destroyed */
2175   0,                                    /* todo_flags_start */
2176   TODO_verify_ssa
2177   | TODO_verify_stmts | TODO_ggc_collect/* todo_flags_finish */
2178  }
2179 };
2180
2181
2182
2183 /* Try to optimize out __builtin_stack_restore.  Optimize it out
2184    if there is another __builtin_stack_restore in the same basic
2185    block and no calls or ASM_EXPRs are in between, or if this block's
2186    only outgoing edge is to EXIT_BLOCK and there are no calls or
2187    ASM_EXPRs after this __builtin_stack_restore.  */
2188
2189 static tree
2190 optimize_stack_restore (gimple_stmt_iterator i)
2191 {
2192   tree callee;
2193   gimple stmt;
2194
2195   basic_block bb = gsi_bb (i);
2196   gimple call = gsi_stmt (i);
2197
2198   if (gimple_code (call) != GIMPLE_CALL
2199       || gimple_call_num_args (call) != 1
2200       || TREE_CODE (gimple_call_arg (call, 0)) != SSA_NAME
2201       || !POINTER_TYPE_P (TREE_TYPE (gimple_call_arg (call, 0))))
2202     return NULL_TREE;
2203
2204   for (gsi_next (&i); !gsi_end_p (i); gsi_next (&i))
2205     {
2206       stmt = gsi_stmt (i);
2207       if (gimple_code (stmt) == GIMPLE_ASM)
2208         return NULL_TREE;
2209       if (gimple_code (stmt) != GIMPLE_CALL)
2210         continue;
2211
2212       callee = gimple_call_fndecl (stmt);
2213       if (!callee
2214           || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL
2215           /* All regular builtins are ok, just obviously not alloca.  */
2216           || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALLOCA
2217           || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALLOCA_WITH_ALIGN)
2218         return NULL_TREE;
2219
2220       if (DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_RESTORE)
2221         goto second_stack_restore;
2222     }
2223
2224   if (!gsi_end_p (i))
2225     return NULL_TREE;
2226
2227   /* Allow one successor of the exit block, or zero successors.  */
2228   switch (EDGE_COUNT (bb->succs))
2229     {
2230     case 0:
2231       break;
2232     case 1:
2233       if (single_succ_edge (bb)->dest != EXIT_BLOCK_PTR)
2234         return NULL_TREE;
2235       break;
2236     default:
2237       return NULL_TREE;
2238     }
2239  second_stack_restore:
2240
2241   /* If there's exactly one use, then zap the call to __builtin_stack_save.
2242      If there are multiple uses, then the last one should remove the call.
2243      In any case, whether the call to __builtin_stack_save can be removed
2244      or not is irrelevant to removing the call to __builtin_stack_restore.  */
2245   if (has_single_use (gimple_call_arg (call, 0)))
2246     {
2247       gimple stack_save = SSA_NAME_DEF_STMT (gimple_call_arg (call, 0));
2248       if (is_gimple_call (stack_save))
2249         {
2250           callee = gimple_call_fndecl (stack_save);
2251           if (callee
2252               && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
2253               && DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_SAVE)
2254             {
2255               gimple_stmt_iterator stack_save_gsi;
2256               tree rhs;
2257
2258               stack_save_gsi = gsi_for_stmt (stack_save);
2259               rhs = build_int_cst (TREE_TYPE (gimple_call_arg (call, 0)), 0);
2260               update_call_from_tree (&stack_save_gsi, rhs);
2261             }
2262         }
2263     }
2264
2265   /* No effect, so the statement will be deleted.  */
2266   return integer_zero_node;
2267 }
2268
2269 /* If va_list type is a simple pointer and nothing special is needed,
2270    optimize __builtin_va_start (&ap, 0) into ap = __builtin_next_arg (0),
2271    __builtin_va_end (&ap) out as NOP and __builtin_va_copy into a simple
2272    pointer assignment.  */
2273
2274 static tree
2275 optimize_stdarg_builtin (gimple call)
2276 {
2277   tree callee, lhs, rhs, cfun_va_list;
2278   bool va_list_simple_ptr;
2279   location_t loc = gimple_location (call);
2280
2281   if (gimple_code (call) != GIMPLE_CALL)
2282     return NULL_TREE;
2283
2284   callee = gimple_call_fndecl (call);
2285
2286   cfun_va_list = targetm.fn_abi_va_list (callee);
2287   va_list_simple_ptr = POINTER_TYPE_P (cfun_va_list)
2288                        && (TREE_TYPE (cfun_va_list) == void_type_node
2289                            || TREE_TYPE (cfun_va_list) == char_type_node);
2290
2291   switch (DECL_FUNCTION_CODE (callee))
2292     {
2293     case BUILT_IN_VA_START:
2294       if (!va_list_simple_ptr
2295           || targetm.expand_builtin_va_start != NULL
2296           || !builtin_decl_explicit_p (BUILT_IN_NEXT_ARG))
2297         return NULL_TREE;
2298
2299       if (gimple_call_num_args (call) != 2)
2300         return NULL_TREE;
2301
2302       lhs = gimple_call_arg (call, 0);
2303       if (!POINTER_TYPE_P (TREE_TYPE (lhs))
2304           || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs)))
2305              != TYPE_MAIN_VARIANT (cfun_va_list))
2306         return NULL_TREE;
2307
2308       lhs = build_fold_indirect_ref_loc (loc, lhs);
2309       rhs = build_call_expr_loc (loc, builtin_decl_explicit (BUILT_IN_NEXT_ARG),
2310                              1, integer_zero_node);
2311       rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
2312       return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
2313
2314     case BUILT_IN_VA_COPY:
2315       if (!va_list_simple_ptr)
2316         return NULL_TREE;
2317
2318       if (gimple_call_num_args (call) != 2)
2319         return NULL_TREE;
2320
2321       lhs = gimple_call_arg (call, 0);
2322       if (!POINTER_TYPE_P (TREE_TYPE (lhs))
2323           || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs)))
2324              != TYPE_MAIN_VARIANT (cfun_va_list))
2325         return NULL_TREE;
2326
2327       lhs = build_fold_indirect_ref_loc (loc, lhs);
2328       rhs = gimple_call_arg (call, 1);
2329       if (TYPE_MAIN_VARIANT (TREE_TYPE (rhs))
2330           != TYPE_MAIN_VARIANT (cfun_va_list))
2331         return NULL_TREE;
2332
2333       rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
2334       return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
2335
2336     case BUILT_IN_VA_END:
2337       /* No effect, so the statement will be deleted.  */
2338       return integer_zero_node;
2339
2340     default:
2341       gcc_unreachable ();
2342     }
2343 }
2344
2345 /* A simple pass that attempts to fold all builtin functions.  This pass
2346    is run after we've propagated as many constants as we can.  */
2347
2348 static unsigned int
2349 execute_fold_all_builtins (void)
2350 {
2351   bool cfg_changed = false;
2352   basic_block bb;
2353   unsigned int todoflags = 0;
2354
2355   FOR_EACH_BB (bb)
2356     {
2357       gimple_stmt_iterator i;
2358       for (i = gsi_start_bb (bb); !gsi_end_p (i); )
2359         {
2360           gimple stmt, old_stmt;
2361           tree callee, result;
2362           enum built_in_function fcode;
2363
2364           stmt = gsi_stmt (i);
2365
2366           if (gimple_code (stmt) != GIMPLE_CALL)
2367             {
2368               gsi_next (&i);
2369               continue;
2370             }
2371           callee = gimple_call_fndecl (stmt);
2372           if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
2373             {
2374               gsi_next (&i);
2375               continue;
2376             }
2377           fcode = DECL_FUNCTION_CODE (callee);
2378
2379           result = gimple_fold_builtin (stmt);
2380
2381           if (result)
2382             gimple_remove_stmt_histograms (cfun, stmt);
2383
2384           if (!result)
2385             switch (DECL_FUNCTION_CODE (callee))
2386               {
2387               case BUILT_IN_CONSTANT_P:
2388                 /* Resolve __builtin_constant_p.  If it hasn't been
2389                    folded to integer_one_node by now, it's fairly
2390                    certain that the value simply isn't constant.  */
2391                 result = integer_zero_node;
2392                 break;
2393
2394               case BUILT_IN_ASSUME_ALIGNED:
2395                 /* Remove __builtin_assume_aligned.  */
2396                 result = gimple_call_arg (stmt, 0);
2397                 break;
2398
2399               case BUILT_IN_STACK_RESTORE:
2400                 result = optimize_stack_restore (i);
2401                 if (result)
2402                   break;
2403                 gsi_next (&i);
2404                 continue;
2405
2406               case BUILT_IN_VA_START:
2407               case BUILT_IN_VA_END:
2408               case BUILT_IN_VA_COPY:
2409                 /* These shouldn't be folded before pass_stdarg.  */
2410                 result = optimize_stdarg_builtin (stmt);
2411                 if (result)
2412                   break;
2413                 /* FALLTHRU */
2414
2415               default:
2416                 gsi_next (&i);
2417                 continue;
2418               }
2419
2420           if (dump_file && (dump_flags & TDF_DETAILS))
2421             {
2422               fprintf (dump_file, "Simplified\n  ");
2423               print_gimple_stmt (dump_file, stmt, 0, dump_flags);
2424             }
2425
2426           old_stmt = stmt;
2427           if (!update_call_from_tree (&i, result))
2428             {
2429               gimplify_and_update_call_from_tree (&i, result);
2430               todoflags |= TODO_update_address_taken;
2431             }
2432
2433           stmt = gsi_stmt (i);
2434           update_stmt (stmt);
2435
2436           if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)
2437               && gimple_purge_dead_eh_edges (bb))
2438             cfg_changed = true;
2439
2440           if (dump_file && (dump_flags & TDF_DETAILS))
2441             {
2442               fprintf (dump_file, "to\n  ");
2443               print_gimple_stmt (dump_file, stmt, 0, dump_flags);
2444               fprintf (dump_file, "\n");
2445             }
2446
2447           /* Retry the same statement if it changed into another
2448              builtin, there might be new opportunities now.  */
2449           if (gimple_code (stmt) != GIMPLE_CALL)
2450             {
2451               gsi_next (&i);
2452               continue;
2453             }
2454           callee = gimple_call_fndecl (stmt);
2455           if (!callee
2456               || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL
2457               || DECL_FUNCTION_CODE (callee) == fcode)
2458             gsi_next (&i);
2459         }
2460     }
2461
2462   /* Delete unreachable blocks.  */
2463   if (cfg_changed)
2464     todoflags |= TODO_cleanup_cfg;
2465
2466   return todoflags;
2467 }
2468
2469
2470 struct gimple_opt_pass pass_fold_builtins =
2471 {
2472  {
2473   GIMPLE_PASS,
2474   "fab",                                /* name */
2475   NULL,                                 /* gate */
2476   execute_fold_all_builtins,            /* execute */
2477   NULL,                                 /* sub */
2478   NULL,                                 /* next */
2479   0,                                    /* static_pass_number */
2480   TV_NONE,                              /* tv_id */
2481   PROP_cfg | PROP_ssa,                  /* properties_required */
2482   0,                                    /* properties_provided */
2483   0,                                    /* properties_destroyed */
2484   0,                                    /* todo_flags_start */
2485   TODO_verify_ssa
2486     | TODO_update_ssa                   /* todo_flags_finish */
2487  }
2488 };