OSDN Git Service

2010-04-07 Richard Guenther <rguenther@suse.de>
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-ccp.c
1 /* Conditional constant propagation pass for the GNU compiler.
2    Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 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 "rtl.h"
195 #include "tm_p.h"
196 #include "ggc.h"
197 #include "basic-block.h"
198 #include "output.h"
199 #include "expr.h"
200 #include "function.h"
201 #include "diagnostic.h"
202 #include "timevar.h"
203 #include "tree-dump.h"
204 #include "tree-flow.h"
205 #include "tree-pass.h"
206 #include "tree-ssa-propagate.h"
207 #include "value-prof.h"
208 #include "langhooks.h"
209 #include "target.h"
210 #include "toplev.h"
211 #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
273 /* If SYM is a constant variable with known value, return the value.
274    NULL_TREE is returned otherwise.  */
275
276 tree
277 get_symbol_constant_value (tree sym)
278 {
279   if (TREE_STATIC (sym)
280       && (TREE_READONLY (sym)
281           || TREE_CODE (sym) == CONST_DECL))
282     {
283       tree val = DECL_INITIAL (sym);
284       if (val)
285         {
286           STRIP_NOPS (val);
287           if (is_gimple_min_invariant (val))
288             {
289               if (TREE_CODE (val) == ADDR_EXPR)
290                 {
291                   tree base = get_base_address (TREE_OPERAND (val, 0));
292                   if (base && TREE_CODE (base) == VAR_DECL)
293                     {
294                       TREE_ADDRESSABLE (base) = 1;
295                       if (gimple_referenced_vars (cfun))
296                         add_referenced_var (base);
297                     }
298                 }
299               return val;
300             }
301         }
302       /* Variables declared 'const' without an initializer
303          have zero as the initializer if they may not be
304          overridden at link or run time.  */
305       if (!val
306           && !DECL_EXTERNAL (sym)
307           && targetm.binds_local_p (sym)
308           && (INTEGRAL_TYPE_P (TREE_TYPE (sym))
309                || SCALAR_FLOAT_TYPE_P (TREE_TYPE (sym))))
310         return fold_convert (TREE_TYPE (sym), integer_zero_node);
311     }
312
313   return NULL_TREE;
314 }
315
316 /* Compute a default value for variable VAR and store it in the
317    CONST_VAL array.  The following rules are used to get default
318    values:
319
320    1- Global and static variables that are declared constant are
321       considered CONSTANT.
322
323    2- Any other value is considered UNDEFINED.  This is useful when
324       considering PHI nodes.  PHI arguments that are undefined do not
325       change the constant value of the PHI node, which allows for more
326       constants to be propagated.
327
328    3- Variables defined by statements other than assignments and PHI
329       nodes are considered VARYING.
330
331    4- Initial values of variables that are not GIMPLE registers are
332       considered VARYING.  */
333
334 static prop_value_t
335 get_default_value (tree var)
336 {
337   tree sym = SSA_NAME_VAR (var);
338   prop_value_t val = { UNINITIALIZED, NULL_TREE };
339   gimple stmt;
340
341   stmt = SSA_NAME_DEF_STMT (var);
342
343   if (gimple_nop_p (stmt))
344     {
345       /* Variables defined by an empty statement are those used
346          before being initialized.  If VAR is a local variable, we
347          can assume initially that it is UNDEFINED, otherwise we must
348          consider it VARYING.  */
349       if (is_gimple_reg (sym) && TREE_CODE (sym) != PARM_DECL)
350         val.lattice_val = UNDEFINED;
351       else
352         val.lattice_val = VARYING;
353     }
354   else if (is_gimple_assign (stmt)
355            /* Value-returning GIMPLE_CALL statements assign to
356               a variable, and are treated similarly to GIMPLE_ASSIGN.  */
357            || (is_gimple_call (stmt)
358                && gimple_call_lhs (stmt) != NULL_TREE)
359            || gimple_code (stmt) == GIMPLE_PHI)
360     {
361       tree cst;
362       if (gimple_assign_single_p (stmt)
363           && DECL_P (gimple_assign_rhs1 (stmt))
364           && (cst = get_symbol_constant_value (gimple_assign_rhs1 (stmt))))
365         {
366           val.lattice_val = CONSTANT;
367           val.value = cst;
368         }
369       else
370         /* Any other variable defined by an assignment or a PHI node
371            is considered UNDEFINED.  */
372         val.lattice_val = UNDEFINED;
373     }
374   else
375     {
376       /* Otherwise, VAR will never take on a constant value.  */
377       val.lattice_val = VARYING;
378     }
379
380   return val;
381 }
382
383
384 /* Get the constant value associated with variable VAR.  */
385
386 static inline prop_value_t *
387 get_value (tree var)
388 {
389   prop_value_t *val;
390
391   if (const_val == NULL)
392     return NULL;
393
394   val = &const_val[SSA_NAME_VERSION (var)];
395   if (val->lattice_val == UNINITIALIZED)
396     *val = get_default_value (var);
397
398   canonicalize_float_value (val);
399
400   return val;
401 }
402
403 /* Sets the value associated with VAR to VARYING.  */
404
405 static inline void
406 set_value_varying (tree var)
407 {
408   prop_value_t *val = &const_val[SSA_NAME_VERSION (var)];
409
410   val->lattice_val = VARYING;
411   val->value = NULL_TREE;
412 }
413
414 /* For float types, modify the value of VAL to make ccp work correctly
415    for non-standard values (-0, NaN):
416
417    If HONOR_SIGNED_ZEROS is false, and VAL = -0, we canonicalize it to 0.
418    If HONOR_NANS is false, and VAL is NaN, we canonicalize it to UNDEFINED.
419      This is to fix the following problem (see PR 29921): Suppose we have
420
421      x = 0.0 * y
422
423      and we set value of y to NaN.  This causes value of x to be set to NaN.
424      When we later determine that y is in fact VARYING, fold uses the fact
425      that HONOR_NANS is false, and we try to change the value of x to 0,
426      causing an ICE.  With HONOR_NANS being false, the real appearance of
427      NaN would cause undefined behavior, though, so claiming that y (and x)
428      are UNDEFINED initially is correct.  */
429
430 static void
431 canonicalize_float_value (prop_value_t *val)
432 {
433   enum machine_mode mode;
434   tree type;
435   REAL_VALUE_TYPE d;
436
437   if (val->lattice_val != CONSTANT
438       || TREE_CODE (val->value) != REAL_CST)
439     return;
440
441   d = TREE_REAL_CST (val->value);
442   type = TREE_TYPE (val->value);
443   mode = TYPE_MODE (type);
444
445   if (!HONOR_SIGNED_ZEROS (mode)
446       && REAL_VALUE_MINUS_ZERO (d))
447     {
448       val->value = build_real (type, dconst0);
449       return;
450     }
451
452   if (!HONOR_NANS (mode)
453       && REAL_VALUE_ISNAN (d))
454     {
455       val->lattice_val = UNDEFINED;
456       val->value = NULL;
457       return;
458     }
459 }
460
461 /* Set the value for variable VAR to NEW_VAL.  Return true if the new
462    value is different from VAR's previous value.  */
463
464 static bool
465 set_lattice_value (tree var, prop_value_t new_val)
466 {
467   prop_value_t *old_val = get_value (var);
468
469   canonicalize_float_value (&new_val);
470
471   /* Lattice transitions must always be monotonically increasing in
472      value.  If *OLD_VAL and NEW_VAL are the same, return false to
473      inform the caller that this was a non-transition.  */
474
475   gcc_assert (old_val->lattice_val < new_val.lattice_val
476               || (old_val->lattice_val == new_val.lattice_val
477                   && ((!old_val->value && !new_val.value)
478                       || operand_equal_p (old_val->value, new_val.value, 0))));
479
480   if (old_val->lattice_val != new_val.lattice_val)
481     {
482       if (dump_file && (dump_flags & TDF_DETAILS))
483         {
484           dump_lattice_value (dump_file, "Lattice value changed to ", new_val);
485           fprintf (dump_file, ".  Adding SSA edges to worklist.\n");
486         }
487
488       *old_val = new_val;
489
490       gcc_assert (new_val.lattice_val != UNDEFINED);
491       return true;
492     }
493
494   return false;
495 }
496
497
498 /* Return the likely CCP lattice value for STMT.
499
500    If STMT has no operands, then return CONSTANT.
501
502    Else if undefinedness of operands of STMT cause its value to be
503    undefined, then return UNDEFINED.
504
505    Else if any operands of STMT are constants, then return CONSTANT.
506
507    Else return VARYING.  */
508
509 static ccp_lattice_t
510 likely_value (gimple stmt)
511 {
512   bool has_constant_operand, has_undefined_operand, all_undefined_operands;
513   tree use;
514   ssa_op_iter iter;
515   unsigned i;
516
517   enum gimple_code code = gimple_code (stmt);
518
519   /* This function appears to be called only for assignments, calls,
520      conditionals, and switches, due to the logic in visit_stmt.  */
521   gcc_assert (code == GIMPLE_ASSIGN
522               || code == GIMPLE_CALL
523               || code == GIMPLE_COND
524               || code == GIMPLE_SWITCH);
525
526   /* If the statement has volatile operands, it won't fold to a
527      constant value.  */
528   if (gimple_has_volatile_ops (stmt))
529     return VARYING;
530
531   /* Arrive here for more complex cases.  */
532   has_constant_operand = false;
533   has_undefined_operand = false;
534   all_undefined_operands = true;
535   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
536     {
537       prop_value_t *val = get_value (use);
538
539       if (val->lattice_val == UNDEFINED)
540         has_undefined_operand = true;
541       else
542         all_undefined_operands = false;
543
544       if (val->lattice_val == CONSTANT)
545         has_constant_operand = true;
546     }
547
548   /* There may be constants in regular rhs operands.  For calls we
549      have to ignore lhs, fndecl and static chain, otherwise only
550      the lhs.  */
551   for (i = (is_gimple_call (stmt) ? 2 : 0) + gimple_has_lhs (stmt);
552        i < gimple_num_ops (stmt); ++i)
553     {
554       tree op = gimple_op (stmt, i);
555       if (!op || TREE_CODE (op) == SSA_NAME)
556         continue;
557       if (is_gimple_min_invariant (op))
558         has_constant_operand = true;
559     }
560
561   if (has_constant_operand)
562     all_undefined_operands = false;
563
564   /* If the operation combines operands like COMPLEX_EXPR make sure to
565      not mark the result UNDEFINED if only one part of the result is
566      undefined.  */
567   if (has_undefined_operand && all_undefined_operands)
568     return UNDEFINED;
569   else if (code == GIMPLE_ASSIGN && has_undefined_operand)
570     {
571       switch (gimple_assign_rhs_code (stmt))
572         {
573         /* Unary operators are handled with all_undefined_operands.  */
574         case PLUS_EXPR:
575         case MINUS_EXPR:
576         case POINTER_PLUS_EXPR:
577           /* Not MIN_EXPR, MAX_EXPR.  One VARYING operand may be selected.
578              Not bitwise operators, one VARYING operand may specify the
579              result completely.  Not logical operators for the same reason.
580              Not COMPLEX_EXPR as one VARYING operand makes the result partly
581              not UNDEFINED.  Not *DIV_EXPR, comparisons and shifts because
582              the undefined operand may be promoted.  */
583           return UNDEFINED;
584
585         default:
586           ;
587         }
588     }
589   /* If there was an UNDEFINED operand but the result may be not UNDEFINED
590      fall back to VARYING even if there were CONSTANT operands.  */
591   if (has_undefined_operand)
592     return VARYING;
593
594   /* We do not consider virtual operands here -- load from read-only
595      memory may have only VARYING virtual operands, but still be
596      constant.  */
597   if (has_constant_operand
598       || gimple_references_memory_p (stmt))
599     return CONSTANT;
600
601   return VARYING;
602 }
603
604 /* Returns true if STMT cannot be constant.  */
605
606 static bool
607 surely_varying_stmt_p (gimple stmt)
608 {
609   /* If the statement has operands that we cannot handle, it cannot be
610      constant.  */
611   if (gimple_has_volatile_ops (stmt))
612     return true;
613
614   /* If it is a call and does not return a value or is not a
615      builtin and not an indirect call, it is varying.  */
616   if (is_gimple_call (stmt))
617     {
618       tree fndecl;
619       if (!gimple_call_lhs (stmt)
620           || ((fndecl = gimple_call_fndecl (stmt)) != NULL_TREE
621               && !DECL_BUILT_IN (fndecl)))
622         return true;
623     }
624
625   /* Any other store operation is not interesting.  */
626   else if (gimple_vdef (stmt))
627     return true;
628
629   /* Anything other than assignments and conditional jumps are not
630      interesting for CCP.  */
631   if (gimple_code (stmt) != GIMPLE_ASSIGN
632       && gimple_code (stmt) != GIMPLE_COND
633       && gimple_code (stmt) != GIMPLE_SWITCH
634       && gimple_code (stmt) != GIMPLE_CALL)
635     return true;
636
637   return false;
638 }
639
640 /* Initialize local data structures for CCP.  */
641
642 static void
643 ccp_initialize (void)
644 {
645   basic_block bb;
646
647   const_val = XCNEWVEC (prop_value_t, num_ssa_names);
648
649   /* Initialize simulation flags for PHI nodes and statements.  */
650   FOR_EACH_BB (bb)
651     {
652       gimple_stmt_iterator i;
653
654       for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
655         {
656           gimple stmt = gsi_stmt (i);
657           bool is_varying;
658
659           /* If the statement is a control insn, then we do not
660              want to avoid simulating the statement once.  Failure
661              to do so means that those edges will never get added.  */
662           if (stmt_ends_bb_p (stmt))
663             is_varying = false;
664           else
665             is_varying = surely_varying_stmt_p (stmt);
666
667           if (is_varying)
668             {
669               tree def;
670               ssa_op_iter iter;
671
672               /* If the statement will not produce a constant, mark
673                  all its outputs VARYING.  */
674               FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
675                 set_value_varying (def);
676             }
677           prop_set_simulate_again (stmt, !is_varying);
678         }
679     }
680
681   /* Now process PHI nodes.  We never clear the simulate_again flag on
682      phi nodes, since we do not know which edges are executable yet,
683      except for phi nodes for virtual operands when we do not do store ccp.  */
684   FOR_EACH_BB (bb)
685     {
686       gimple_stmt_iterator i;
687
688       for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
689         {
690           gimple phi = gsi_stmt (i);
691
692           if (!is_gimple_reg (gimple_phi_result (phi)))
693             prop_set_simulate_again (phi, false);
694           else
695             prop_set_simulate_again (phi, true);
696         }
697     }
698 }
699
700 /* Debug count support. Reset the values of ssa names
701    VARYING when the total number ssa names analyzed is
702    beyond the debug count specified.  */
703
704 static void
705 do_dbg_cnt (void)
706 {
707   unsigned i;
708   for (i = 0; i < num_ssa_names; i++)
709     {
710       if (!dbg_cnt (ccp))
711         {
712           const_val[i].lattice_val = VARYING;
713           const_val[i].value = NULL_TREE;
714         }
715     }
716 }
717
718
719 /* Do final substitution of propagated values, cleanup the flowgraph and
720    free allocated storage.
721
722    Return TRUE when something was optimized.  */
723
724 static bool
725 ccp_finalize (void)
726 {
727   bool something_changed;
728
729   do_dbg_cnt ();
730   /* Perform substitutions based on the known constant values.  */
731   something_changed = substitute_and_fold (const_val, ccp_fold_stmt);
732
733   free (const_val);
734   const_val = NULL;
735   return something_changed;;
736 }
737
738
739 /* Compute the meet operator between *VAL1 and *VAL2.  Store the result
740    in VAL1.
741
742                 any  M UNDEFINED   = any
743                 any  M VARYING     = VARYING
744                 Ci   M Cj          = Ci         if (i == j)
745                 Ci   M Cj          = VARYING    if (i != j)
746    */
747
748 static void
749 ccp_lattice_meet (prop_value_t *val1, prop_value_t *val2)
750 {
751   if (val1->lattice_val == UNDEFINED)
752     {
753       /* UNDEFINED M any = any   */
754       *val1 = *val2;
755     }
756   else if (val2->lattice_val == UNDEFINED)
757     {
758       /* any M UNDEFINED = any
759          Nothing to do.  VAL1 already contains the value we want.  */
760       ;
761     }
762   else if (val1->lattice_val == VARYING
763            || val2->lattice_val == VARYING)
764     {
765       /* any M VARYING = VARYING.  */
766       val1->lattice_val = VARYING;
767       val1->value = NULL_TREE;
768     }
769   else if (val1->lattice_val == CONSTANT
770            && val2->lattice_val == CONSTANT
771            && simple_cst_equal (val1->value, val2->value) == 1)
772     {
773       /* Ci M Cj = Ci           if (i == j)
774          Ci M Cj = VARYING      if (i != j)
775
776          If these two values come from memory stores, make sure that
777          they come from the same memory reference.  */
778       val1->lattice_val = CONSTANT;
779       val1->value = val1->value;
780     }
781   else
782     {
783       /* Any other combination is VARYING.  */
784       val1->lattice_val = VARYING;
785       val1->value = NULL_TREE;
786     }
787 }
788
789
790 /* Loop through the PHI_NODE's parameters for BLOCK and compare their
791    lattice values to determine PHI_NODE's lattice value.  The value of a
792    PHI node is determined calling ccp_lattice_meet with all the arguments
793    of the PHI node that are incoming via executable edges.  */
794
795 static enum ssa_prop_result
796 ccp_visit_phi_node (gimple phi)
797 {
798   unsigned i;
799   prop_value_t *old_val, new_val;
800
801   if (dump_file && (dump_flags & TDF_DETAILS))
802     {
803       fprintf (dump_file, "\nVisiting PHI node: ");
804       print_gimple_stmt (dump_file, phi, 0, dump_flags);
805     }
806
807   old_val = get_value (gimple_phi_result (phi));
808   switch (old_val->lattice_val)
809     {
810     case VARYING:
811       return SSA_PROP_VARYING;
812
813     case CONSTANT:
814       new_val = *old_val;
815       break;
816
817     case UNDEFINED:
818       new_val.lattice_val = UNDEFINED;
819       new_val.value = NULL_TREE;
820       break;
821
822     default:
823       gcc_unreachable ();
824     }
825
826   for (i = 0; i < gimple_phi_num_args (phi); i++)
827     {
828       /* Compute the meet operator over all the PHI arguments flowing
829          through executable edges.  */
830       edge e = gimple_phi_arg_edge (phi, i);
831
832       if (dump_file && (dump_flags & TDF_DETAILS))
833         {
834           fprintf (dump_file,
835               "\n    Argument #%d (%d -> %d %sexecutable)\n",
836               i, e->src->index, e->dest->index,
837               (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
838         }
839
840       /* If the incoming edge is executable, Compute the meet operator for
841          the existing value of the PHI node and the current PHI argument.  */
842       if (e->flags & EDGE_EXECUTABLE)
843         {
844           tree arg = gimple_phi_arg (phi, i)->def;
845           prop_value_t arg_val;
846
847           if (is_gimple_min_invariant (arg))
848             {
849               arg_val.lattice_val = CONSTANT;
850               arg_val.value = arg;
851             }
852           else
853             arg_val = *(get_value (arg));
854
855           ccp_lattice_meet (&new_val, &arg_val);
856
857           if (dump_file && (dump_flags & TDF_DETAILS))
858             {
859               fprintf (dump_file, "\t");
860               print_generic_expr (dump_file, arg, dump_flags);
861               dump_lattice_value (dump_file, "\tValue: ", arg_val);
862               fprintf (dump_file, "\n");
863             }
864
865           if (new_val.lattice_val == VARYING)
866             break;
867         }
868     }
869
870   if (dump_file && (dump_flags & TDF_DETAILS))
871     {
872       dump_lattice_value (dump_file, "\n    PHI node value: ", new_val);
873       fprintf (dump_file, "\n\n");
874     }
875
876   /* Make the transition to the new value.  */
877   if (set_lattice_value (gimple_phi_result (phi), new_val))
878     {
879       if (new_val.lattice_val == VARYING)
880         return SSA_PROP_VARYING;
881       else
882         return SSA_PROP_INTERESTING;
883     }
884   else
885     return SSA_PROP_NOT_INTERESTING;
886 }
887
888 /* Return true if we may propagate the address expression ADDR into the
889    dereference DEREF and cancel them.  */
890
891 bool
892 may_propagate_address_into_dereference (tree addr, tree deref)
893 {
894   gcc_assert (INDIRECT_REF_P (deref)
895               && TREE_CODE (addr) == ADDR_EXPR);
896
897   /* Don't propagate if ADDR's operand has incomplete type.  */
898   if (!COMPLETE_TYPE_P (TREE_TYPE (TREE_OPERAND (addr, 0))))
899     return false;
900
901   /* If the address is invariant then we do not need to preserve restrict
902      qualifications.  But we do need to preserve volatile qualifiers until
903      we can annotate the folded dereference itself properly.  */
904   if (is_gimple_min_invariant (addr)
905       && (!TREE_THIS_VOLATILE (deref)
906           || TYPE_VOLATILE (TREE_TYPE (addr))))
907     return useless_type_conversion_p (TREE_TYPE (deref),
908                                       TREE_TYPE (TREE_OPERAND (addr, 0)));
909
910   /* Else both the address substitution and the folding must result in
911      a valid useless type conversion sequence.  */
912   return (useless_type_conversion_p (TREE_TYPE (TREE_OPERAND (deref, 0)),
913                                      TREE_TYPE (addr))
914           && useless_type_conversion_p (TREE_TYPE (deref),
915                                         TREE_TYPE (TREE_OPERAND (addr, 0))));
916 }
917
918 /* CCP specific front-end to the non-destructive constant folding
919    routines.
920
921    Attempt to simplify the RHS of STMT knowing that one or more
922    operands are constants.
923
924    If simplification is possible, return the simplified RHS,
925    otherwise return the original RHS or NULL_TREE.  */
926
927 static tree
928 ccp_fold (gimple stmt)
929 {
930   location_t loc = gimple_location (stmt);
931   switch (gimple_code (stmt))
932     {
933     case GIMPLE_ASSIGN:
934       {
935         enum tree_code subcode = gimple_assign_rhs_code (stmt);
936
937         switch (get_gimple_rhs_class (subcode))
938           {
939           case GIMPLE_SINGLE_RHS:
940             {
941               tree rhs = gimple_assign_rhs1 (stmt);
942               enum tree_code_class kind = TREE_CODE_CLASS (subcode);
943
944               if (TREE_CODE (rhs) == SSA_NAME)
945                 {
946                   /* If the RHS is an SSA_NAME, return its known constant value,
947                      if any.  */
948                   return get_value (rhs)->value;
949                 }
950               /* Handle propagating invariant addresses into address operations.
951                  The folding we do here matches that in tree-ssa-forwprop.c.  */
952               else if (TREE_CODE (rhs) == ADDR_EXPR)
953                 {
954                   tree *base;
955                   base = &TREE_OPERAND (rhs, 0);
956                   while (handled_component_p (*base))
957                     base = &TREE_OPERAND (*base, 0);
958                   if (TREE_CODE (*base) == INDIRECT_REF
959                       && TREE_CODE (TREE_OPERAND (*base, 0)) == SSA_NAME)
960                     {
961                       prop_value_t *val = get_value (TREE_OPERAND (*base, 0));
962                       if (val->lattice_val == CONSTANT
963                           && TREE_CODE (val->value) == ADDR_EXPR
964                           && may_propagate_address_into_dereference
965                                (val->value, *base))
966                         {
967                           /* We need to return a new tree, not modify the IL
968                              or share parts of it.  So play some tricks to
969                              avoid manually building it.  */
970                           tree ret, save = *base;
971                           *base = TREE_OPERAND (val->value, 0);
972                           ret = unshare_expr (rhs);
973                           recompute_tree_invariant_for_addr_expr (ret);
974                           *base = save;
975                           return ret;
976                         }
977                     }
978                 }
979               else if (TREE_CODE (rhs) == CONSTRUCTOR
980                        && TREE_CODE (TREE_TYPE (rhs)) == VECTOR_TYPE
981                        && (CONSTRUCTOR_NELTS (rhs)
982                            == TYPE_VECTOR_SUBPARTS (TREE_TYPE (rhs))))
983                 {
984                   unsigned i;
985                   tree val, list;
986
987                   list = NULL_TREE;
988                   FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (rhs), i, val)
989                     {
990                       if (TREE_CODE (val) == SSA_NAME
991                           && get_value (val)->lattice_val == CONSTANT)
992                         val = get_value (val)->value;
993                       if (TREE_CODE (val) == INTEGER_CST
994                           || TREE_CODE (val) == REAL_CST
995                           || TREE_CODE (val) == FIXED_CST)
996                         list = tree_cons (NULL_TREE, val, list);
997                       else
998                         return NULL_TREE;
999                     }
1000
1001                   return build_vector (TREE_TYPE (rhs), nreverse (list));
1002                 }
1003
1004               if (kind == tcc_reference)
1005                 {
1006                   if ((TREE_CODE (rhs) == VIEW_CONVERT_EXPR
1007                        || TREE_CODE (rhs) == REALPART_EXPR
1008                        || TREE_CODE (rhs) == IMAGPART_EXPR)
1009                       && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
1010                     {
1011                       prop_value_t *val = get_value (TREE_OPERAND (rhs, 0));
1012                       if (val->lattice_val == CONSTANT)
1013                         return fold_unary_loc (EXPR_LOCATION (rhs),
1014                                            TREE_CODE (rhs),
1015                                            TREE_TYPE (rhs), val->value);
1016                     }
1017                   else if (TREE_CODE (rhs) == INDIRECT_REF
1018                            && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
1019                     {
1020                       prop_value_t *val = get_value (TREE_OPERAND (rhs, 0));
1021                       if (val->lattice_val == CONSTANT
1022                           && TREE_CODE (val->value) == ADDR_EXPR
1023                           && useless_type_conversion_p (TREE_TYPE (rhs),
1024                                                         TREE_TYPE (TREE_TYPE (val->value))))
1025                         rhs = TREE_OPERAND (val->value, 0);
1026                     }
1027                   return fold_const_aggregate_ref (rhs);
1028                 }
1029               else if (kind == tcc_declaration)
1030                 return get_symbol_constant_value (rhs);
1031               return rhs;
1032             }
1033
1034           case GIMPLE_UNARY_RHS:
1035             {
1036               /* Handle unary operators that can appear in GIMPLE form.
1037                  Note that we know the single operand must be a constant,
1038                  so this should almost always return a simplified RHS.  */
1039               tree lhs = gimple_assign_lhs (stmt);
1040               tree op0 = gimple_assign_rhs1 (stmt);
1041
1042               /* Simplify the operand down to a constant.  */
1043               if (TREE_CODE (op0) == SSA_NAME)
1044                 {
1045                   prop_value_t *val = get_value (op0);
1046                   if (val->lattice_val == CONSTANT)
1047                     op0 = get_value (op0)->value;
1048                 }
1049
1050               /* Conversions are useless for CCP purposes if they are
1051                  value-preserving.  Thus the restrictions that
1052                  useless_type_conversion_p places for pointer type conversions
1053                  do not apply here.  Substitution later will only substitute to
1054                  allowed places.  */
1055               if (CONVERT_EXPR_CODE_P (subcode)
1056                   && POINTER_TYPE_P (TREE_TYPE (lhs))
1057                   && POINTER_TYPE_P (TREE_TYPE (op0))
1058                   /* Do not allow differences in volatile qualification
1059                      as this might get us confused as to whether a
1060                      propagation destination statement is volatile
1061                      or not.  See PR36988.  */
1062                   && (TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (lhs)))
1063                       == TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (op0)))))
1064                 {
1065                   tree tem;
1066                   /* Still try to generate a constant of correct type.  */
1067                   if (!useless_type_conversion_p (TREE_TYPE (lhs),
1068                                                   TREE_TYPE (op0))
1069                       && ((tem = maybe_fold_offset_to_address
1070                            (loc,
1071                             op0, integer_zero_node, TREE_TYPE (lhs)))
1072                           != NULL_TREE))
1073                     return tem;
1074                   return op0;
1075                 }
1076
1077               return
1078                 fold_unary_ignore_overflow_loc (loc, subcode,
1079                                                 gimple_expr_type (stmt), op0);
1080             }
1081
1082           case GIMPLE_BINARY_RHS:
1083             {
1084               /* Handle binary operators that can appear in GIMPLE form.  */
1085               tree op0 = gimple_assign_rhs1 (stmt);
1086               tree op1 = gimple_assign_rhs2 (stmt);
1087
1088               /* Simplify the operands down to constants when appropriate.  */
1089               if (TREE_CODE (op0) == SSA_NAME)
1090                 {
1091                   prop_value_t *val = get_value (op0);
1092                   if (val->lattice_val == CONSTANT)
1093                     op0 = val->value;
1094                 }
1095
1096               if (TREE_CODE (op1) == SSA_NAME)
1097                 {
1098                   prop_value_t *val = get_value (op1);
1099                   if (val->lattice_val == CONSTANT)
1100                     op1 = val->value;
1101                 }
1102
1103               /* Fold &foo + CST into an invariant reference if possible.  */
1104               if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR
1105                   && TREE_CODE (op0) == ADDR_EXPR
1106                   && TREE_CODE (op1) == INTEGER_CST)
1107                 {
1108                   tree tem = maybe_fold_offset_to_address
1109                     (loc, op0, op1, TREE_TYPE (op0));
1110                   if (tem != NULL_TREE)
1111                     return tem;
1112                 }
1113
1114               return fold_binary_loc (loc, subcode,
1115                                   gimple_expr_type (stmt), op0, op1);
1116             }
1117
1118           default:
1119             gcc_unreachable ();
1120           }
1121       }
1122       break;
1123
1124     case GIMPLE_CALL:
1125       {
1126         tree fn = gimple_call_fn (stmt);
1127         prop_value_t *val;
1128
1129         if (TREE_CODE (fn) == SSA_NAME)
1130           {
1131             val = get_value (fn);
1132             if (val->lattice_val == CONSTANT)
1133               fn = val->value;
1134           }
1135         if (TREE_CODE (fn) == ADDR_EXPR
1136             && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL
1137             && DECL_BUILT_IN (TREE_OPERAND (fn, 0)))
1138           {
1139             tree *args = XALLOCAVEC (tree, gimple_call_num_args (stmt));
1140             tree call, retval;
1141             unsigned i;
1142             for (i = 0; i < gimple_call_num_args (stmt); ++i)
1143               {
1144                 args[i] = gimple_call_arg (stmt, i);
1145                 if (TREE_CODE (args[i]) == SSA_NAME)
1146                   {
1147                     val = get_value (args[i]);
1148                     if (val->lattice_val == CONSTANT)
1149                       args[i] = val->value;
1150                   }
1151               }
1152             call = build_call_array_loc (loc,
1153                                          gimple_call_return_type (stmt),
1154                                          fn, gimple_call_num_args (stmt), args);
1155             retval = fold_call_expr (EXPR_LOCATION (call), call, false);
1156             if (retval)
1157               /* fold_call_expr wraps the result inside a NOP_EXPR.  */
1158               STRIP_NOPS (retval);
1159             return retval;
1160           }
1161         return NULL_TREE;
1162       }
1163
1164     case GIMPLE_COND:
1165       {
1166         /* Handle comparison operators that can appear in GIMPLE form.  */
1167         tree op0 = gimple_cond_lhs (stmt);
1168         tree op1 = gimple_cond_rhs (stmt);
1169         enum tree_code code = gimple_cond_code (stmt);
1170
1171         /* Simplify the operands down to constants when appropriate.  */
1172         if (TREE_CODE (op0) == SSA_NAME)
1173           {
1174             prop_value_t *val = get_value (op0);
1175             if (val->lattice_val == CONSTANT)
1176               op0 = val->value;
1177           }
1178
1179         if (TREE_CODE (op1) == SSA_NAME)
1180           {
1181             prop_value_t *val = get_value (op1);
1182             if (val->lattice_val == CONSTANT)
1183               op1 = val->value;
1184           }
1185
1186         return fold_binary_loc (loc, code, boolean_type_node, op0, op1);
1187       }
1188
1189     case GIMPLE_SWITCH:
1190       {
1191         tree rhs = gimple_switch_index (stmt);
1192
1193         if (TREE_CODE (rhs) == SSA_NAME)
1194           {
1195             /* If the RHS is an SSA_NAME, return its known constant value,
1196                if any.  */
1197             return get_value (rhs)->value;
1198           }
1199
1200         return rhs;
1201       }
1202
1203     default:
1204       gcc_unreachable ();
1205     }
1206 }
1207
1208
1209 /* Return the tree representing the element referenced by T if T is an
1210    ARRAY_REF or COMPONENT_REF into constant aggregates.  Return
1211    NULL_TREE otherwise.  */
1212
1213 tree
1214 fold_const_aggregate_ref (tree t)
1215 {
1216   prop_value_t *value;
1217   tree base, ctor, idx, field;
1218   unsigned HOST_WIDE_INT cnt;
1219   tree cfield, cval;
1220
1221   if (TREE_CODE_CLASS (TREE_CODE (t)) == tcc_declaration)
1222     return get_symbol_constant_value (t);
1223
1224   switch (TREE_CODE (t))
1225     {
1226     case ARRAY_REF:
1227       /* Get a CONSTRUCTOR.  If BASE is a VAR_DECL, get its
1228          DECL_INITIAL.  If BASE is a nested reference into another
1229          ARRAY_REF or COMPONENT_REF, make a recursive call to resolve
1230          the inner reference.  */
1231       base = TREE_OPERAND (t, 0);
1232       switch (TREE_CODE (base))
1233         {
1234         case VAR_DECL:
1235           if (!TREE_READONLY (base)
1236               || TREE_CODE (TREE_TYPE (base)) != ARRAY_TYPE
1237               || !targetm.binds_local_p (base))
1238             return NULL_TREE;
1239
1240           ctor = DECL_INITIAL (base);
1241           break;
1242
1243         case ARRAY_REF:
1244         case COMPONENT_REF:
1245           ctor = fold_const_aggregate_ref (base);
1246           break;
1247
1248         case STRING_CST:
1249         case CONSTRUCTOR:
1250           ctor = base;
1251           break;
1252
1253         default:
1254           return NULL_TREE;
1255         }
1256
1257       if (ctor == NULL_TREE
1258           || (TREE_CODE (ctor) != CONSTRUCTOR
1259               && TREE_CODE (ctor) != STRING_CST)
1260           || !TREE_STATIC (ctor))
1261         return NULL_TREE;
1262
1263       /* Get the index.  If we have an SSA_NAME, try to resolve it
1264          with the current lattice value for the SSA_NAME.  */
1265       idx = TREE_OPERAND (t, 1);
1266       switch (TREE_CODE (idx))
1267         {
1268         case SSA_NAME:
1269           if ((value = get_value (idx))
1270               && value->lattice_val == CONSTANT
1271               && TREE_CODE (value->value) == INTEGER_CST)
1272             idx = value->value;
1273           else
1274             return NULL_TREE;
1275           break;
1276
1277         case INTEGER_CST:
1278           break;
1279
1280         default:
1281           return NULL_TREE;
1282         }
1283
1284       /* Fold read from constant string.  */
1285       if (TREE_CODE (ctor) == STRING_CST)
1286         {
1287           if ((TYPE_MODE (TREE_TYPE (t))
1288                == TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
1289               && (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
1290                   == MODE_INT)
1291               && GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor)))) == 1
1292               && compare_tree_int (idx, TREE_STRING_LENGTH (ctor)) < 0)
1293             return build_int_cst_type (TREE_TYPE (t),
1294                                        (TREE_STRING_POINTER (ctor)
1295                                         [TREE_INT_CST_LOW (idx)]));
1296           return NULL_TREE;
1297         }
1298
1299       /* Whoo-hoo!  I'll fold ya baby.  Yeah!  */
1300       FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
1301         if (tree_int_cst_equal (cfield, idx))
1302           {
1303             STRIP_NOPS (cval);
1304             if (TREE_CODE (cval) == ADDR_EXPR)
1305               {
1306                 tree base = get_base_address (TREE_OPERAND (cval, 0));
1307                 if (base && TREE_CODE (base) == VAR_DECL)
1308                   add_referenced_var (base);
1309               }
1310             return cval;
1311           }
1312       break;
1313
1314     case COMPONENT_REF:
1315       /* Get a CONSTRUCTOR.  If BASE is a VAR_DECL, get its
1316          DECL_INITIAL.  If BASE is a nested reference into another
1317          ARRAY_REF or COMPONENT_REF, make a recursive call to resolve
1318          the inner reference.  */
1319       base = TREE_OPERAND (t, 0);
1320       switch (TREE_CODE (base))
1321         {
1322         case VAR_DECL:
1323           if (!TREE_READONLY (base)
1324               || TREE_CODE (TREE_TYPE (base)) != RECORD_TYPE
1325               || !targetm.binds_local_p (base))
1326             return NULL_TREE;
1327
1328           ctor = DECL_INITIAL (base);
1329           break;
1330
1331         case ARRAY_REF:
1332         case COMPONENT_REF:
1333           ctor = fold_const_aggregate_ref (base);
1334           break;
1335
1336         default:
1337           return NULL_TREE;
1338         }
1339
1340       if (ctor == NULL_TREE
1341           || TREE_CODE (ctor) != CONSTRUCTOR
1342           || !TREE_STATIC (ctor))
1343         return NULL_TREE;
1344
1345       field = TREE_OPERAND (t, 1);
1346
1347       FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
1348         if (cfield == field
1349             /* FIXME: Handle bit-fields.  */
1350             && ! DECL_BIT_FIELD (cfield))
1351           {
1352             STRIP_NOPS (cval);
1353             if (TREE_CODE (cval) == ADDR_EXPR)
1354               {
1355                 tree base = get_base_address (TREE_OPERAND (cval, 0));
1356                 if (base && TREE_CODE (base) == VAR_DECL)
1357                   add_referenced_var (base);
1358               }
1359             return cval;
1360           }
1361       break;
1362
1363     case REALPART_EXPR:
1364     case IMAGPART_EXPR:
1365       {
1366         tree c = fold_const_aggregate_ref (TREE_OPERAND (t, 0));
1367         if (c && TREE_CODE (c) == COMPLEX_CST)
1368           return fold_build1_loc (EXPR_LOCATION (t),
1369                               TREE_CODE (t), TREE_TYPE (t), c);
1370         break;
1371       }
1372
1373     case INDIRECT_REF:
1374       {
1375         tree base = TREE_OPERAND (t, 0);
1376         if (TREE_CODE (base) == SSA_NAME
1377             && (value = get_value (base))
1378             && value->lattice_val == CONSTANT
1379             && TREE_CODE (value->value) == ADDR_EXPR
1380             && useless_type_conversion_p (TREE_TYPE (t),
1381                                           TREE_TYPE (TREE_TYPE (value->value))))
1382           return fold_const_aggregate_ref (TREE_OPERAND (value->value, 0));
1383         break;
1384       }
1385
1386     default:
1387       break;
1388     }
1389
1390   return NULL_TREE;
1391 }
1392
1393 /* Evaluate statement STMT.
1394    Valid only for assignments, calls, conditionals, and switches. */
1395
1396 static prop_value_t
1397 evaluate_stmt (gimple stmt)
1398 {
1399   prop_value_t val;
1400   tree simplified = NULL_TREE;
1401   ccp_lattice_t likelyvalue = likely_value (stmt);
1402   bool is_constant;
1403
1404   fold_defer_overflow_warnings ();
1405
1406   /* If the statement is likely to have a CONSTANT result, then try
1407      to fold the statement to determine the constant value.  */
1408   /* FIXME.  This is the only place that we call ccp_fold.
1409      Since likely_value never returns CONSTANT for calls, we will
1410      not attempt to fold them, including builtins that may profit.  */
1411   if (likelyvalue == CONSTANT)
1412     simplified = ccp_fold (stmt);
1413   /* If the statement is likely to have a VARYING result, then do not
1414      bother folding the statement.  */
1415   else if (likelyvalue == VARYING)
1416     {
1417       enum gimple_code code = gimple_code (stmt);
1418       if (code == GIMPLE_ASSIGN)
1419         {
1420           enum tree_code subcode = gimple_assign_rhs_code (stmt);
1421
1422           /* Other cases cannot satisfy is_gimple_min_invariant
1423              without folding.  */
1424           if (get_gimple_rhs_class (subcode) == GIMPLE_SINGLE_RHS)
1425             simplified = gimple_assign_rhs1 (stmt);
1426         }
1427       else if (code == GIMPLE_SWITCH)
1428         simplified = gimple_switch_index (stmt);
1429       else
1430         /* These cannot satisfy is_gimple_min_invariant without folding.  */
1431         gcc_assert (code == GIMPLE_CALL || code == GIMPLE_COND);
1432     }
1433
1434   is_constant = simplified && is_gimple_min_invariant (simplified);
1435
1436   fold_undefer_overflow_warnings (is_constant, stmt, 0);
1437
1438   if (dump_file && (dump_flags & TDF_DETAILS))
1439     {
1440       fprintf (dump_file, "which is likely ");
1441       switch (likelyvalue)
1442         {
1443         case CONSTANT:
1444           fprintf (dump_file, "CONSTANT");
1445           break;
1446         case UNDEFINED:
1447           fprintf (dump_file, "UNDEFINED");
1448           break;
1449         case VARYING:
1450           fprintf (dump_file, "VARYING");
1451           break;
1452         default:;
1453         }
1454       fprintf (dump_file, "\n");
1455     }
1456
1457   if (is_constant)
1458     {
1459       /* The statement produced a constant value.  */
1460       val.lattice_val = CONSTANT;
1461       val.value = simplified;
1462     }
1463   else
1464     {
1465       /* The statement produced a nonconstant value.  If the statement
1466          had UNDEFINED operands, then the result of the statement
1467          should be UNDEFINED.  Otherwise, the statement is VARYING.  */
1468       if (likelyvalue == UNDEFINED)
1469         val.lattice_val = likelyvalue;
1470       else
1471         val.lattice_val = VARYING;
1472
1473       val.value = NULL_TREE;
1474     }
1475
1476   return val;
1477 }
1478
1479 /* Fold the stmt at *GSI with CCP specific information that propagating
1480    and regular folding does not catch.  */
1481
1482 static bool
1483 ccp_fold_stmt (gimple_stmt_iterator *gsi)
1484 {
1485   gimple stmt = gsi_stmt (*gsi);
1486
1487   switch (gimple_code (stmt))
1488     {
1489     case GIMPLE_COND:
1490       {
1491         prop_value_t val;
1492         /* Statement evaluation will handle type mismatches in constants
1493            more gracefully than the final propagation.  This allows us to
1494            fold more conditionals here.  */
1495         val = evaluate_stmt (stmt);
1496         if (val.lattice_val != CONSTANT
1497             || TREE_CODE (val.value) != INTEGER_CST)
1498           return false;
1499
1500         if (integer_zerop (val.value))
1501           gimple_cond_make_false (stmt);
1502         else
1503           gimple_cond_make_true (stmt);
1504
1505         return true;
1506       }
1507
1508     case GIMPLE_CALL:
1509       {
1510         tree lhs = gimple_call_lhs (stmt);
1511         prop_value_t *val;
1512         tree argt;
1513         bool changed = false;
1514         unsigned i;
1515
1516         /* If the call was folded into a constant make sure it goes
1517            away even if we cannot propagate into all uses because of
1518            type issues.  */
1519         if (lhs
1520             && TREE_CODE (lhs) == SSA_NAME
1521             && (val = get_value (lhs))
1522             && val->lattice_val == CONSTANT)
1523           {
1524             tree new_rhs = unshare_expr (val->value);
1525             bool res;
1526             if (!useless_type_conversion_p (TREE_TYPE (lhs),
1527                                             TREE_TYPE (new_rhs)))
1528               new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs);
1529             res = update_call_from_tree (gsi, new_rhs);
1530             gcc_assert (res);
1531             return true;
1532           }
1533
1534         /* Propagate into the call arguments.  Compared to replace_uses_in
1535            this can use the argument slot types for type verification
1536            instead of the current argument type.  We also can safely
1537            drop qualifiers here as we are dealing with constants anyway.  */
1538         argt = TYPE_ARG_TYPES (TREE_TYPE (TREE_TYPE (gimple_call_fn (stmt))));
1539         for (i = 0; i < gimple_call_num_args (stmt) && argt;
1540              ++i, argt = TREE_CHAIN (argt))
1541           {
1542             tree arg = gimple_call_arg (stmt, i);
1543             if (TREE_CODE (arg) == SSA_NAME
1544                 && (val = get_value (arg))
1545                 && val->lattice_val == CONSTANT
1546                 && useless_type_conversion_p
1547                      (TYPE_MAIN_VARIANT (TREE_VALUE (argt)),
1548                       TYPE_MAIN_VARIANT (TREE_TYPE (val->value))))
1549               {
1550                 gimple_call_set_arg (stmt, i, unshare_expr (val->value));
1551                 changed = true;
1552               }
1553           }
1554
1555         return changed;
1556       }
1557
1558     case GIMPLE_ASSIGN:
1559       {
1560         tree lhs = gimple_assign_lhs (stmt);
1561         prop_value_t *val;
1562
1563         /* If we have a load that turned out to be constant replace it
1564            as we cannot propagate into all uses in all cases.  */
1565         if (gimple_assign_single_p (stmt)
1566             && TREE_CODE (lhs) == SSA_NAME
1567             && (val = get_value (lhs))
1568             && val->lattice_val == CONSTANT)
1569           {
1570             tree rhs = unshare_expr (val->value);
1571             if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
1572               rhs = fold_convert (TREE_TYPE (lhs), rhs);
1573             gimple_assign_set_rhs_from_tree (gsi, rhs);
1574             return true;
1575           }
1576
1577         return false;
1578       }
1579
1580     default:
1581       return false;
1582     }
1583 }
1584
1585 /* Visit the assignment statement STMT.  Set the value of its LHS to the
1586    value computed by the RHS and store LHS in *OUTPUT_P.  If STMT
1587    creates virtual definitions, set the value of each new name to that
1588    of the RHS (if we can derive a constant out of the RHS).
1589    Value-returning call statements also perform an assignment, and
1590    are handled here.  */
1591
1592 static enum ssa_prop_result
1593 visit_assignment (gimple stmt, tree *output_p)
1594 {
1595   prop_value_t val;
1596   enum ssa_prop_result retval;
1597
1598   tree lhs = gimple_get_lhs (stmt);
1599
1600   gcc_assert (gimple_code (stmt) != GIMPLE_CALL
1601               || gimple_call_lhs (stmt) != NULL_TREE);
1602
1603   if (gimple_assign_copy_p (stmt))
1604     {
1605       tree rhs = gimple_assign_rhs1 (stmt);
1606
1607       if  (TREE_CODE (rhs) == SSA_NAME)
1608         {
1609           /* For a simple copy operation, we copy the lattice values.  */
1610           prop_value_t *nval = get_value (rhs);
1611           val = *nval;
1612         }
1613       else
1614         val = evaluate_stmt (stmt);
1615     }
1616   else
1617     /* Evaluate the statement, which could be
1618        either a GIMPLE_ASSIGN or a GIMPLE_CALL.  */
1619     val = evaluate_stmt (stmt);
1620
1621   retval = SSA_PROP_NOT_INTERESTING;
1622
1623   /* Set the lattice value of the statement's output.  */
1624   if (TREE_CODE (lhs) == SSA_NAME)
1625     {
1626       /* If STMT is an assignment to an SSA_NAME, we only have one
1627          value to set.  */
1628       if (set_lattice_value (lhs, val))
1629         {
1630           *output_p = lhs;
1631           if (val.lattice_val == VARYING)
1632             retval = SSA_PROP_VARYING;
1633           else
1634             retval = SSA_PROP_INTERESTING;
1635         }
1636     }
1637
1638   return retval;
1639 }
1640
1641
1642 /* Visit the conditional statement STMT.  Return SSA_PROP_INTERESTING
1643    if it can determine which edge will be taken.  Otherwise, return
1644    SSA_PROP_VARYING.  */
1645
1646 static enum ssa_prop_result
1647 visit_cond_stmt (gimple stmt, edge *taken_edge_p)
1648 {
1649   prop_value_t val;
1650   basic_block block;
1651
1652   block = gimple_bb (stmt);
1653   val = evaluate_stmt (stmt);
1654
1655   /* Find which edge out of the conditional block will be taken and add it
1656      to the worklist.  If no single edge can be determined statically,
1657      return SSA_PROP_VARYING to feed all the outgoing edges to the
1658      propagation engine.  */
1659   *taken_edge_p = val.value ? find_taken_edge (block, val.value) : 0;
1660   if (*taken_edge_p)
1661     return SSA_PROP_INTERESTING;
1662   else
1663     return SSA_PROP_VARYING;
1664 }
1665
1666
1667 /* Evaluate statement STMT.  If the statement produces an output value and
1668    its evaluation changes the lattice value of its output, return
1669    SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the
1670    output value.
1671
1672    If STMT is a conditional branch and we can determine its truth
1673    value, set *TAKEN_EDGE_P accordingly.  If STMT produces a varying
1674    value, return SSA_PROP_VARYING.  */
1675
1676 static enum ssa_prop_result
1677 ccp_visit_stmt (gimple stmt, edge *taken_edge_p, tree *output_p)
1678 {
1679   tree def;
1680   ssa_op_iter iter;
1681
1682   if (dump_file && (dump_flags & TDF_DETAILS))
1683     {
1684       fprintf (dump_file, "\nVisiting statement:\n");
1685       print_gimple_stmt (dump_file, stmt, 0, dump_flags);
1686     }
1687
1688   switch (gimple_code (stmt))
1689     {
1690       case GIMPLE_ASSIGN:
1691         /* If the statement is an assignment that produces a single
1692            output value, evaluate its RHS to see if the lattice value of
1693            its output has changed.  */
1694         return visit_assignment (stmt, output_p);
1695
1696       case GIMPLE_CALL:
1697         /* A value-returning call also performs an assignment.  */
1698         if (gimple_call_lhs (stmt) != NULL_TREE)
1699           return visit_assignment (stmt, output_p);
1700         break;
1701
1702       case GIMPLE_COND:
1703       case GIMPLE_SWITCH:
1704         /* If STMT is a conditional branch, see if we can determine
1705            which branch will be taken.   */
1706         /* FIXME.  It appears that we should be able to optimize
1707            computed GOTOs here as well.  */
1708         return visit_cond_stmt (stmt, taken_edge_p);
1709
1710       default:
1711         break;
1712     }
1713
1714   /* Any other kind of statement is not interesting for constant
1715      propagation and, therefore, not worth simulating.  */
1716   if (dump_file && (dump_flags & TDF_DETAILS))
1717     fprintf (dump_file, "No interesting values produced.  Marked VARYING.\n");
1718
1719   /* Definitions made by statements other than assignments to
1720      SSA_NAMEs represent unknown modifications to their outputs.
1721      Mark them VARYING.  */
1722   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
1723     {
1724       prop_value_t v = { VARYING, NULL_TREE };
1725       set_lattice_value (def, v);
1726     }
1727
1728   return SSA_PROP_VARYING;
1729 }
1730
1731
1732 /* Main entry point for SSA Conditional Constant Propagation.  */
1733
1734 static unsigned int
1735 do_ssa_ccp (void)
1736 {
1737   ccp_initialize ();
1738   ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node);
1739   if (ccp_finalize ())
1740     return (TODO_cleanup_cfg | TODO_update_ssa | TODO_remove_unused_locals);
1741   else
1742     return 0;
1743 }
1744
1745
1746 static bool
1747 gate_ccp (void)
1748 {
1749   return flag_tree_ccp != 0;
1750 }
1751
1752
1753 struct gimple_opt_pass pass_ccp =
1754 {
1755  {
1756   GIMPLE_PASS,
1757   "ccp",                                /* name */
1758   gate_ccp,                             /* gate */
1759   do_ssa_ccp,                           /* execute */
1760   NULL,                                 /* sub */
1761   NULL,                                 /* next */
1762   0,                                    /* static_pass_number */
1763   TV_TREE_CCP,                          /* tv_id */
1764   PROP_cfg | PROP_ssa,                  /* properties_required */
1765   0,                                    /* properties_provided */
1766   0,                                    /* properties_destroyed */
1767   0,                                    /* todo_flags_start */
1768   TODO_dump_func | TODO_verify_ssa
1769   | TODO_verify_stmts | TODO_ggc_collect/* todo_flags_finish */
1770  }
1771 };
1772
1773
1774 /* A subroutine of fold_stmt.  Attempts to fold *(A+O) to A[X].
1775    BASE is an array type.  OFFSET is a byte displacement.  ORIG_TYPE
1776    is the desired result type.
1777
1778    LOC is the location of the original expression.  */
1779
1780 static tree
1781 maybe_fold_offset_to_array_ref (location_t loc, tree base, tree offset,
1782                                 tree orig_type,
1783                                 bool allow_negative_idx)
1784 {
1785   tree min_idx, idx, idx_type, elt_offset = integer_zero_node;
1786   tree array_type, elt_type, elt_size;
1787   tree domain_type;
1788
1789   /* If BASE is an ARRAY_REF, we can pick up another offset (this time
1790      measured in units of the size of elements type) from that ARRAY_REF).
1791      We can't do anything if either is variable.
1792
1793      The case we handle here is *(&A[N]+O).  */
1794   if (TREE_CODE (base) == ARRAY_REF)
1795     {
1796       tree low_bound = array_ref_low_bound (base);
1797
1798       elt_offset = TREE_OPERAND (base, 1);
1799       if (TREE_CODE (low_bound) != INTEGER_CST
1800           || TREE_CODE (elt_offset) != INTEGER_CST)
1801         return NULL_TREE;
1802
1803       elt_offset = int_const_binop (MINUS_EXPR, elt_offset, low_bound, 0);
1804       base = TREE_OPERAND (base, 0);
1805     }
1806
1807   /* Ignore stupid user tricks of indexing non-array variables.  */
1808   array_type = TREE_TYPE (base);
1809   if (TREE_CODE (array_type) != ARRAY_TYPE)
1810     return NULL_TREE;
1811   elt_type = TREE_TYPE (array_type);
1812   if (!useless_type_conversion_p (orig_type, elt_type))
1813     return NULL_TREE;
1814
1815   /* Use signed size type for intermediate computation on the index.  */
1816   idx_type = signed_type_for (size_type_node);
1817
1818   /* If OFFSET and ELT_OFFSET are zero, we don't care about the size of the
1819      element type (so we can use the alignment if it's not constant).
1820      Otherwise, compute the offset as an index by using a division.  If the
1821      division isn't exact, then don't do anything.  */
1822   elt_size = TYPE_SIZE_UNIT (elt_type);
1823   if (!elt_size)
1824     return NULL;
1825   if (integer_zerop (offset))
1826     {
1827       if (TREE_CODE (elt_size) != INTEGER_CST)
1828         elt_size = size_int (TYPE_ALIGN (elt_type));
1829
1830       idx = build_int_cst (idx_type, 0);
1831     }
1832   else
1833     {
1834       unsigned HOST_WIDE_INT lquo, lrem;
1835       HOST_WIDE_INT hquo, hrem;
1836       double_int soffset;
1837
1838       /* The final array offset should be signed, so we need
1839          to sign-extend the (possibly pointer) offset here
1840          and use signed division.  */
1841       soffset = double_int_sext (tree_to_double_int (offset),
1842                                  TYPE_PRECISION (TREE_TYPE (offset)));
1843       if (TREE_CODE (elt_size) != INTEGER_CST
1844           || div_and_round_double (TRUNC_DIV_EXPR, 0,
1845                                    soffset.low, soffset.high,
1846                                    TREE_INT_CST_LOW (elt_size),
1847                                    TREE_INT_CST_HIGH (elt_size),
1848                                    &lquo, &hquo, &lrem, &hrem)
1849           || lrem || hrem)
1850         return NULL_TREE;
1851
1852       idx = build_int_cst_wide (idx_type, lquo, hquo);
1853     }
1854
1855   /* Assume the low bound is zero.  If there is a domain type, get the
1856      low bound, if any, convert the index into that type, and add the
1857      low bound.  */
1858   min_idx = build_int_cst (idx_type, 0);
1859   domain_type = TYPE_DOMAIN (array_type);
1860   if (domain_type)
1861     {
1862       idx_type = domain_type;
1863       if (TYPE_MIN_VALUE (idx_type))
1864         min_idx = TYPE_MIN_VALUE (idx_type);
1865       else
1866         min_idx = fold_convert (idx_type, min_idx);
1867
1868       if (TREE_CODE (min_idx) != INTEGER_CST)
1869         return NULL_TREE;
1870
1871       elt_offset = fold_convert (idx_type, elt_offset);
1872     }
1873
1874   if (!integer_zerop (min_idx))
1875     idx = int_const_binop (PLUS_EXPR, idx, min_idx, 0);
1876   if (!integer_zerop (elt_offset))
1877     idx = int_const_binop (PLUS_EXPR, idx, elt_offset, 0);
1878
1879   /* Make sure to possibly truncate late after offsetting.  */
1880   idx = fold_convert (idx_type, idx);
1881
1882   /* We don't want to construct access past array bounds. For example
1883        char *(c[4]);
1884        c[3][2];
1885      should not be simplified into (*c)[14] or tree-vrp will
1886      give false warnings.  The same is true for
1887        struct A { long x; char d[0]; } *a;
1888        (char *)a - 4;
1889      which should be not folded to &a->d[-8].  */
1890   if (domain_type
1891       && TYPE_MAX_VALUE (domain_type)
1892       && TREE_CODE (TYPE_MAX_VALUE (domain_type)) == INTEGER_CST)
1893     {
1894       tree up_bound = TYPE_MAX_VALUE (domain_type);
1895
1896       if (tree_int_cst_lt (up_bound, idx)
1897           /* Accesses after the end of arrays of size 0 (gcc
1898              extension) and 1 are likely intentional ("struct
1899              hack").  */
1900           && compare_tree_int (up_bound, 1) > 0)
1901         return NULL_TREE;
1902     }
1903   if (domain_type
1904       && TYPE_MIN_VALUE (domain_type))
1905     {
1906       if (!allow_negative_idx
1907           && TREE_CODE (TYPE_MIN_VALUE (domain_type)) == INTEGER_CST
1908           && tree_int_cst_lt (idx, TYPE_MIN_VALUE (domain_type)))
1909         return NULL_TREE;
1910     }
1911   else if (!allow_negative_idx
1912            && compare_tree_int (idx, 0) < 0)
1913     return NULL_TREE;
1914
1915   {
1916     tree t = build4 (ARRAY_REF, elt_type, base, idx, NULL_TREE, NULL_TREE);
1917     SET_EXPR_LOCATION (t, loc);
1918     return t;
1919   }
1920 }
1921
1922
1923 /* Attempt to fold *(S+O) to S.X.
1924    BASE is a record type.  OFFSET is a byte displacement.  ORIG_TYPE
1925    is the desired result type.
1926
1927    LOC is the location of the original expression.  */
1928
1929 static tree
1930 maybe_fold_offset_to_component_ref (location_t loc, tree record_type,
1931                                     tree base, tree offset, tree orig_type)
1932 {
1933   tree f, t, field_type, tail_array_field, field_offset;
1934   tree ret;
1935   tree new_base;
1936
1937   if (TREE_CODE (record_type) != RECORD_TYPE
1938       && TREE_CODE (record_type) != UNION_TYPE
1939       && TREE_CODE (record_type) != QUAL_UNION_TYPE)
1940     return NULL_TREE;
1941
1942   /* Short-circuit silly cases.  */
1943   if (useless_type_conversion_p (record_type, orig_type))
1944     return NULL_TREE;
1945
1946   tail_array_field = NULL_TREE;
1947   for (f = TYPE_FIELDS (record_type); f ; f = TREE_CHAIN (f))
1948     {
1949       int cmp;
1950
1951       if (TREE_CODE (f) != FIELD_DECL)
1952         continue;
1953       if (DECL_BIT_FIELD (f))
1954         continue;
1955
1956       if (!DECL_FIELD_OFFSET (f))
1957         continue;
1958       field_offset = byte_position (f);
1959       if (TREE_CODE (field_offset) != INTEGER_CST)
1960         continue;
1961
1962       /* ??? Java creates "interesting" fields for representing base classes.
1963          They have no name, and have no context.  With no context, we get into
1964          trouble with nonoverlapping_component_refs_p.  Skip them.  */
1965       if (!DECL_FIELD_CONTEXT (f))
1966         continue;
1967
1968       /* The previous array field isn't at the end.  */
1969       tail_array_field = NULL_TREE;
1970
1971       /* Check to see if this offset overlaps with the field.  */
1972       cmp = tree_int_cst_compare (field_offset, offset);
1973       if (cmp > 0)
1974         continue;
1975
1976       field_type = TREE_TYPE (f);
1977
1978       /* Here we exactly match the offset being checked.  If the types match,
1979          then we can return that field.  */
1980       if (cmp == 0
1981           && useless_type_conversion_p (orig_type, field_type))
1982         {
1983           t = build3 (COMPONENT_REF, field_type, base, f, NULL_TREE);
1984           return t;
1985         }
1986
1987       /* Don't care about offsets into the middle of scalars.  */
1988       if (!AGGREGATE_TYPE_P (field_type))
1989         continue;
1990
1991       /* Check for array at the end of the struct.  This is often
1992          used as for flexible array members.  We should be able to
1993          turn this into an array access anyway.  */
1994       if (TREE_CODE (field_type) == ARRAY_TYPE)
1995         tail_array_field = f;
1996
1997       /* Check the end of the field against the offset.  */
1998       if (!DECL_SIZE_UNIT (f)
1999           || TREE_CODE (DECL_SIZE_UNIT (f)) != INTEGER_CST)
2000         continue;
2001       t = int_const_binop (MINUS_EXPR, offset, field_offset, 1);
2002       if (!tree_int_cst_lt (t, DECL_SIZE_UNIT (f)))
2003         continue;
2004
2005       /* If we matched, then set offset to the displacement into
2006          this field.  */
2007       new_base = build3 (COMPONENT_REF, field_type, base, f, NULL_TREE);
2008       SET_EXPR_LOCATION (new_base, loc);
2009
2010       /* Recurse to possibly find the match.  */
2011       ret = maybe_fold_offset_to_array_ref (loc, new_base, t, orig_type,
2012                                             f == TYPE_FIELDS (record_type));
2013       if (ret)
2014         return ret;
2015       ret = maybe_fold_offset_to_component_ref (loc, field_type, new_base, t,
2016                                                 orig_type);
2017       if (ret)
2018         return ret;
2019     }
2020
2021   if (!tail_array_field)
2022     return NULL_TREE;
2023
2024   f = tail_array_field;
2025   field_type = TREE_TYPE (f);
2026   offset = int_const_binop (MINUS_EXPR, offset, byte_position (f), 1);
2027
2028   /* If we get here, we've got an aggregate field, and a possibly
2029      nonzero offset into them.  Recurse and hope for a valid match.  */
2030   base = build3 (COMPONENT_REF, field_type, base, f, NULL_TREE);
2031   SET_EXPR_LOCATION (base, loc);
2032
2033   t = maybe_fold_offset_to_array_ref (loc, base, offset, orig_type,
2034                                       f == TYPE_FIELDS (record_type));
2035   if (t)
2036     return t;
2037   return maybe_fold_offset_to_component_ref (loc, field_type, base, offset,
2038                                              orig_type);
2039 }
2040
2041 /* Attempt to express (ORIG_TYPE)BASE+OFFSET as BASE->field_of_orig_type
2042    or BASE[index] or by combination of those.
2043
2044    LOC is the location of original expression.
2045
2046    Before attempting the conversion strip off existing ADDR_EXPRs and
2047    handled component refs.  */
2048
2049 tree
2050 maybe_fold_offset_to_reference (location_t loc, tree base, tree offset,
2051                                 tree orig_type)
2052 {
2053   tree ret;
2054   tree type;
2055
2056   STRIP_NOPS (base);
2057   if (TREE_CODE (base) != ADDR_EXPR)
2058     return NULL_TREE;
2059
2060   base = TREE_OPERAND (base, 0);
2061
2062   /* Handle case where existing COMPONENT_REF pick e.g. wrong field of union,
2063      so it needs to be removed and new COMPONENT_REF constructed.
2064      The wrong COMPONENT_REF are often constructed by folding the
2065      (type *)&object within the expression (type *)&object+offset  */
2066   if (handled_component_p (base))
2067     {
2068       HOST_WIDE_INT sub_offset, size, maxsize;
2069       tree newbase;
2070       newbase = get_ref_base_and_extent (base, &sub_offset,
2071                                          &size, &maxsize);
2072       gcc_assert (newbase);
2073       if (size == maxsize
2074           && size != -1
2075           && !(sub_offset & (BITS_PER_UNIT - 1)))
2076         {
2077           base = newbase;
2078           if (sub_offset)
2079             offset = int_const_binop (PLUS_EXPR, offset,
2080                                       build_int_cst (TREE_TYPE (offset),
2081                                                      sub_offset / BITS_PER_UNIT), 1);
2082         }
2083     }
2084   if (useless_type_conversion_p (orig_type, TREE_TYPE (base))
2085       && integer_zerop (offset))
2086     return base;
2087   type = TREE_TYPE (base);
2088
2089   ret = maybe_fold_offset_to_component_ref (loc, type, base, offset, orig_type);
2090   if (!ret)
2091     ret = maybe_fold_offset_to_array_ref (loc, base, offset, orig_type, true);
2092
2093   return ret;
2094 }
2095
2096 /* Attempt to express (ORIG_TYPE)&BASE+OFFSET as &BASE->field_of_orig_type
2097    or &BASE[index] or by combination of those.
2098
2099    LOC is the location of the original expression.
2100
2101    Before attempting the conversion strip off existing component refs.  */
2102
2103 tree
2104 maybe_fold_offset_to_address (location_t loc, tree addr, tree offset,
2105                               tree orig_type)
2106 {
2107   tree t;
2108
2109   gcc_assert (POINTER_TYPE_P (TREE_TYPE (addr))
2110               && POINTER_TYPE_P (orig_type));
2111
2112   t = maybe_fold_offset_to_reference (loc, addr, offset,
2113                                       TREE_TYPE (orig_type));
2114   if (t != NULL_TREE)
2115     {
2116       tree orig = addr;
2117       tree ptr_type;
2118
2119       /* For __builtin_object_size to function correctly we need to
2120          make sure not to fold address arithmetic so that we change
2121          reference from one array to another.  This would happen for
2122          example for
2123
2124            struct X { char s1[10]; char s2[10] } s;
2125            char *foo (void) { return &s.s2[-4]; }
2126
2127          where we need to avoid generating &s.s1[6].  As the C and
2128          C++ frontends create different initial trees
2129          (char *) &s.s1 + -4  vs.  &s.s1[-4]  we have to do some
2130          sophisticated comparisons here.  Note that checking for the
2131          condition after the fact is easier than trying to avoid doing
2132          the folding.  */
2133       STRIP_NOPS (orig);
2134       if (TREE_CODE (orig) == ADDR_EXPR)
2135         orig = TREE_OPERAND (orig, 0);
2136       if ((TREE_CODE (orig) == ARRAY_REF
2137            || (TREE_CODE (orig) == COMPONENT_REF
2138                && TREE_CODE (TREE_TYPE (TREE_OPERAND (orig, 1))) == ARRAY_TYPE))
2139           && (TREE_CODE (t) == ARRAY_REF
2140               || TREE_CODE (t) == COMPONENT_REF)
2141           && !operand_equal_p (TREE_CODE (orig) == ARRAY_REF
2142                                ? TREE_OPERAND (orig, 0) : orig,
2143                                TREE_CODE (t) == ARRAY_REF
2144                                ? TREE_OPERAND (t, 0) : t, 0))
2145         return NULL_TREE;
2146
2147       ptr_type = build_pointer_type (TREE_TYPE (t));
2148       if (!useless_type_conversion_p (orig_type, ptr_type))
2149         return NULL_TREE;
2150       return build_fold_addr_expr_with_type_loc (loc, t, ptr_type);
2151     }
2152
2153   return NULL_TREE;
2154 }
2155
2156 /* A subroutine of fold_stmt.  Attempt to simplify *(BASE+OFFSET).
2157    Return the simplified expression, or NULL if nothing could be done.  */
2158
2159 static tree
2160 maybe_fold_stmt_indirect (tree expr, tree base, tree offset)
2161 {
2162   tree t;
2163   bool volatile_p = TREE_THIS_VOLATILE (expr);
2164   location_t loc = EXPR_LOCATION (expr);
2165
2166   /* We may well have constructed a double-nested PLUS_EXPR via multiple
2167      substitutions.  Fold that down to one.  Remove NON_LVALUE_EXPRs that
2168      are sometimes added.  */
2169   base = fold (base);
2170   STRIP_TYPE_NOPS (base);
2171   TREE_OPERAND (expr, 0) = base;
2172
2173   /* One possibility is that the address reduces to a string constant.  */
2174   t = fold_read_from_constant_string (expr);
2175   if (t)
2176     return t;
2177
2178   /* Add in any offset from a POINTER_PLUS_EXPR.  */
2179   if (TREE_CODE (base) == POINTER_PLUS_EXPR)
2180     {
2181       tree offset2;
2182
2183       offset2 = TREE_OPERAND (base, 1);
2184       if (TREE_CODE (offset2) != INTEGER_CST)
2185         return NULL_TREE;
2186       base = TREE_OPERAND (base, 0);
2187
2188       offset = fold_convert (sizetype,
2189                              int_const_binop (PLUS_EXPR, offset, offset2, 1));
2190     }
2191
2192   if (TREE_CODE (base) == ADDR_EXPR)
2193     {
2194       tree base_addr = base;
2195
2196       /* Strip the ADDR_EXPR.  */
2197       base = TREE_OPERAND (base, 0);
2198
2199       /* Fold away CONST_DECL to its value, if the type is scalar.  */
2200       if (TREE_CODE (base) == CONST_DECL
2201           && is_gimple_min_invariant (DECL_INITIAL (base)))
2202         return DECL_INITIAL (base);
2203
2204       /* If there is no offset involved simply return the folded base.  */
2205       if (integer_zerop (offset))
2206         return base;
2207
2208       /* Try folding *(&B+O) to B.X.  */
2209       t = maybe_fold_offset_to_reference (loc, base_addr, offset,
2210                                           TREE_TYPE (expr));
2211       if (t)
2212         {
2213           /* Preserve volatileness of the original expression.
2214              We can end up with a plain decl here which is shared
2215              and we shouldn't mess with its flags.  */
2216           if (!SSA_VAR_P (t))
2217             TREE_THIS_VOLATILE (t) = volatile_p;
2218           return t;
2219         }
2220     }
2221   else
2222     {
2223       /* We can get here for out-of-range string constant accesses,
2224          such as "_"[3].  Bail out of the entire substitution search
2225          and arrange for the entire statement to be replaced by a
2226          call to __builtin_trap.  In all likelihood this will all be
2227          constant-folded away, but in the meantime we can't leave with
2228          something that get_expr_operands can't understand.  */
2229
2230       t = base;
2231       STRIP_NOPS (t);
2232       if (TREE_CODE (t) == ADDR_EXPR
2233           && TREE_CODE (TREE_OPERAND (t, 0)) == STRING_CST)
2234         {
2235           /* FIXME: Except that this causes problems elsewhere with dead
2236              code not being deleted, and we die in the rtl expanders
2237              because we failed to remove some ssa_name.  In the meantime,
2238              just return zero.  */
2239           /* FIXME2: This condition should be signaled by
2240              fold_read_from_constant_string directly, rather than
2241              re-checking for it here.  */
2242           return integer_zero_node;
2243         }
2244
2245       /* Try folding *(B+O) to B->X.  Still an improvement.  */
2246       if (POINTER_TYPE_P (TREE_TYPE (base)))
2247         {
2248           t = maybe_fold_offset_to_reference (loc, base, offset,
2249                                               TREE_TYPE (expr));
2250           if (t)
2251             return t;
2252         }
2253     }
2254
2255   /* Otherwise we had an offset that we could not simplify.  */
2256   return NULL_TREE;
2257 }
2258
2259
2260 /* A quaint feature extant in our address arithmetic is that there
2261    can be hidden type changes here.  The type of the result need
2262    not be the same as the type of the input pointer.
2263
2264    What we're after here is an expression of the form
2265         (T *)(&array + const)
2266    where array is OP0, const is OP1, RES_TYPE is T and
2267    the cast doesn't actually exist, but is implicit in the
2268    type of the POINTER_PLUS_EXPR.  We'd like to turn this into
2269         &array[x]
2270    which may be able to propagate further.  */
2271
2272 tree
2273 maybe_fold_stmt_addition (location_t loc, tree res_type, tree op0, tree op1)
2274 {
2275   tree ptd_type;
2276   tree t;
2277
2278   /* The first operand should be an ADDR_EXPR.  */
2279   if (TREE_CODE (op0) != ADDR_EXPR)
2280     return NULL_TREE;
2281   op0 = TREE_OPERAND (op0, 0);
2282
2283   /* It had better be a constant.  */
2284   if (TREE_CODE (op1) != INTEGER_CST)
2285     {
2286       /* Or op0 should now be A[0] and the non-constant offset defined
2287          via a multiplication by the array element size.  */
2288       if (TREE_CODE (op0) == ARRAY_REF
2289           && integer_zerop (TREE_OPERAND (op0, 1))
2290           && TREE_CODE (op1) == SSA_NAME
2291           && host_integerp (TYPE_SIZE_UNIT (TREE_TYPE (op0)), 1))
2292         {
2293           gimple offset_def = SSA_NAME_DEF_STMT (op1);
2294           if (!is_gimple_assign (offset_def))
2295             return NULL_TREE;
2296
2297           if (gimple_assign_rhs_code (offset_def) == MULT_EXPR
2298               && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
2299               && tree_int_cst_equal (gimple_assign_rhs2 (offset_def),
2300                                      TYPE_SIZE_UNIT (TREE_TYPE (op0))))
2301             return build_fold_addr_expr
2302                           (build4 (ARRAY_REF, TREE_TYPE (op0),
2303                                    TREE_OPERAND (op0, 0),
2304                                    gimple_assign_rhs1 (offset_def),
2305                                    TREE_OPERAND (op0, 2),
2306                                    TREE_OPERAND (op0, 3)));
2307           else if (integer_onep (TYPE_SIZE_UNIT (TREE_TYPE (op0)))
2308                    && gimple_assign_rhs_code (offset_def) != MULT_EXPR)
2309             return build_fold_addr_expr
2310                           (build4 (ARRAY_REF, TREE_TYPE (op0),
2311                                    TREE_OPERAND (op0, 0),
2312                                    op1,
2313                                    TREE_OPERAND (op0, 2),
2314                                    TREE_OPERAND (op0, 3)));
2315         }
2316       return NULL_TREE;
2317     }
2318
2319   /* If the first operand is an ARRAY_REF, expand it so that we can fold
2320      the offset into it.  */
2321   while (TREE_CODE (op0) == ARRAY_REF)
2322     {
2323       tree array_obj = TREE_OPERAND (op0, 0);
2324       tree array_idx = TREE_OPERAND (op0, 1);
2325       tree elt_type = TREE_TYPE (op0);
2326       tree elt_size = TYPE_SIZE_UNIT (elt_type);
2327       tree min_idx;
2328
2329       if (TREE_CODE (array_idx) != INTEGER_CST)
2330         break;
2331       if (TREE_CODE (elt_size) != INTEGER_CST)
2332         break;
2333
2334       /* Un-bias the index by the min index of the array type.  */
2335       min_idx = TYPE_DOMAIN (TREE_TYPE (array_obj));
2336       if (min_idx)
2337         {
2338           min_idx = TYPE_MIN_VALUE (min_idx);
2339           if (min_idx)
2340             {
2341               if (TREE_CODE (min_idx) != INTEGER_CST)
2342                 break;
2343
2344               array_idx = fold_convert (TREE_TYPE (min_idx), array_idx);
2345               if (!integer_zerop (min_idx))
2346                 array_idx = int_const_binop (MINUS_EXPR, array_idx,
2347                                              min_idx, 0);
2348             }
2349         }
2350
2351       /* Convert the index to a byte offset.  */
2352       array_idx = fold_convert (sizetype, array_idx);
2353       array_idx = int_const_binop (MULT_EXPR, array_idx, elt_size, 0);
2354
2355       /* Update the operands for the next round, or for folding.  */
2356       op1 = int_const_binop (PLUS_EXPR,
2357                              array_idx, op1, 0);
2358       op0 = array_obj;
2359     }
2360
2361   ptd_type = TREE_TYPE (res_type);
2362   /* If we want a pointer to void, reconstruct the reference from the
2363      array element type.  A pointer to that can be trivially converted
2364      to void *.  This happens as we fold (void *)(ptr p+ off).  */
2365   if (VOID_TYPE_P (ptd_type)
2366       && TREE_CODE (TREE_TYPE (op0)) == ARRAY_TYPE)
2367     ptd_type = TREE_TYPE (TREE_TYPE (op0));
2368
2369   /* At which point we can try some of the same things as for indirects.  */
2370   t = maybe_fold_offset_to_array_ref (loc, op0, op1, ptd_type, true);
2371   if (!t)
2372     t = maybe_fold_offset_to_component_ref (loc, TREE_TYPE (op0), op0, op1,
2373                                             ptd_type);
2374   if (t)
2375     {
2376       t = build1 (ADDR_EXPR, res_type, t);
2377       SET_EXPR_LOCATION (t, loc);
2378     }
2379
2380   return t;
2381 }
2382
2383 /* Subroutine of fold_stmt.  We perform several simplifications of the
2384    memory reference tree EXPR and make sure to re-gimplify them properly
2385    after propagation of constant addresses.  IS_LHS is true if the
2386    reference is supposed to be an lvalue.  */
2387
2388 static tree
2389 maybe_fold_reference (tree expr, bool is_lhs)
2390 {
2391   tree *t = &expr;
2392
2393   if (TREE_CODE (expr) == ARRAY_REF
2394       && !is_lhs)
2395     {
2396       tree tem = fold_read_from_constant_string (expr);
2397       if (tem)
2398         return tem;
2399     }
2400
2401   /* ???  We might want to open-code the relevant remaining cases
2402      to avoid using the generic fold.  */
2403   if (handled_component_p (*t)
2404       && CONSTANT_CLASS_P (TREE_OPERAND (*t, 0)))
2405     {
2406       tree tem = fold (*t);
2407       if (tem != *t)
2408         return tem;
2409     }
2410
2411   while (handled_component_p (*t))
2412     t = &TREE_OPERAND (*t, 0);
2413
2414   if (TREE_CODE (*t) == INDIRECT_REF)
2415     {
2416       tree tem = maybe_fold_stmt_indirect (*t, TREE_OPERAND (*t, 0),
2417                                            integer_zero_node);
2418       /* Avoid folding *"abc" = 5 into 'a' = 5.  */
2419       if (is_lhs && tem && CONSTANT_CLASS_P (tem))
2420         tem = NULL_TREE;
2421       if (!tem
2422           && TREE_CODE (TREE_OPERAND (*t, 0)) == ADDR_EXPR)
2423         /* If we had a good reason for propagating the address here,
2424            make sure we end up with valid gimple.  See PR34989.  */
2425         tem = TREE_OPERAND (TREE_OPERAND (*t, 0), 0);
2426
2427       if (tem)
2428         {
2429           *t = tem;
2430           tem = maybe_fold_reference (expr, is_lhs);
2431           if (tem)
2432             return tem;
2433           return expr;
2434         }
2435     }
2436   else if (!is_lhs
2437            && DECL_P (*t))
2438     {
2439       tree tem = get_symbol_constant_value (*t);
2440       if (tem
2441           && useless_type_conversion_p (TREE_TYPE (*t), TREE_TYPE (tem)))
2442         {
2443           *t = unshare_expr (tem);
2444           tem = maybe_fold_reference (expr, is_lhs);
2445           if (tem)
2446             return tem;
2447           return expr;
2448         }
2449     }
2450
2451   return NULL_TREE;
2452 }
2453
2454
2455 /* Return the string length, maximum string length or maximum value of
2456    ARG in LENGTH.
2457    If ARG is an SSA name variable, follow its use-def chains.  If LENGTH
2458    is not NULL and, for TYPE == 0, its value is not equal to the length
2459    we determine or if we are unable to determine the length or value,
2460    return false.  VISITED is a bitmap of visited variables.
2461    TYPE is 0 if string length should be returned, 1 for maximum string
2462    length and 2 for maximum value ARG can have.  */
2463
2464 static bool
2465 get_maxval_strlen (tree arg, tree *length, bitmap visited, int type)
2466 {
2467   tree var, val;
2468   gimple def_stmt;
2469
2470   if (TREE_CODE (arg) != SSA_NAME)
2471     {
2472       if (TREE_CODE (arg) == COND_EXPR)
2473         return get_maxval_strlen (COND_EXPR_THEN (arg), length, visited, type)
2474                && get_maxval_strlen (COND_EXPR_ELSE (arg), length, visited, type);
2475       /* We can end up with &(*iftmp_1)[0] here as well, so handle it.  */
2476       else if (TREE_CODE (arg) == ADDR_EXPR
2477                && TREE_CODE (TREE_OPERAND (arg, 0)) == ARRAY_REF
2478                && integer_zerop (TREE_OPERAND (TREE_OPERAND (arg, 0), 1)))
2479         {
2480           tree aop0 = TREE_OPERAND (TREE_OPERAND (arg, 0), 0);
2481           if (TREE_CODE (aop0) == INDIRECT_REF
2482               && TREE_CODE (TREE_OPERAND (aop0, 0)) == SSA_NAME)
2483             return get_maxval_strlen (TREE_OPERAND (aop0, 0),
2484                                       length, visited, type);
2485         }
2486
2487       if (type == 2)
2488         {
2489           val = arg;
2490           if (TREE_CODE (val) != INTEGER_CST
2491               || tree_int_cst_sgn (val) < 0)
2492             return false;
2493         }
2494       else
2495         val = c_strlen (arg, 1);
2496       if (!val)
2497         return false;
2498
2499       if (*length)
2500         {
2501           if (type > 0)
2502             {
2503               if (TREE_CODE (*length) != INTEGER_CST
2504                   || TREE_CODE (val) != INTEGER_CST)
2505                 return false;
2506
2507               if (tree_int_cst_lt (*length, val))
2508                 *length = val;
2509               return true;
2510             }
2511           else if (simple_cst_equal (val, *length) != 1)
2512             return false;
2513         }
2514
2515       *length = val;
2516       return true;
2517     }
2518
2519   /* If we were already here, break the infinite cycle.  */
2520   if (bitmap_bit_p (visited, SSA_NAME_VERSION (arg)))
2521     return true;
2522   bitmap_set_bit (visited, SSA_NAME_VERSION (arg));
2523
2524   var = arg;
2525   def_stmt = SSA_NAME_DEF_STMT (var);
2526
2527   switch (gimple_code (def_stmt))
2528     {
2529       case GIMPLE_ASSIGN:
2530         /* The RHS of the statement defining VAR must either have a
2531            constant length or come from another SSA_NAME with a constant
2532            length.  */
2533         if (gimple_assign_single_p (def_stmt)
2534             || gimple_assign_unary_nop_p (def_stmt))
2535           {
2536             tree rhs = gimple_assign_rhs1 (def_stmt);
2537             return get_maxval_strlen (rhs, length, visited, type);
2538           }
2539         return false;
2540
2541       case GIMPLE_PHI:
2542         {
2543           /* All the arguments of the PHI node must have the same constant
2544              length.  */
2545           unsigned i;
2546
2547           for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
2548           {
2549             tree arg = gimple_phi_arg (def_stmt, i)->def;
2550
2551             /* If this PHI has itself as an argument, we cannot
2552                determine the string length of this argument.  However,
2553                if we can find a constant string length for the other
2554                PHI args then we can still be sure that this is a
2555                constant string length.  So be optimistic and just
2556                continue with the next argument.  */
2557             if (arg == gimple_phi_result (def_stmt))
2558               continue;
2559
2560             if (!get_maxval_strlen (arg, length, visited, type))
2561               return false;
2562           }
2563         }
2564         return true;
2565
2566       default:
2567         return false;
2568     }
2569 }
2570
2571
2572 /* Fold builtin call in statement STMT.  Returns a simplified tree.
2573    We may return a non-constant expression, including another call
2574    to a different function and with different arguments, e.g.,
2575    substituting memcpy for strcpy when the string length is known.
2576    Note that some builtins expand into inline code that may not
2577    be valid in GIMPLE.  Callers must take care.  */
2578
2579 static tree
2580 ccp_fold_builtin (gimple stmt)
2581 {
2582   tree result, val[3];
2583   tree callee, a;
2584   int arg_idx, type;
2585   bitmap visited;
2586   bool ignore;
2587   int nargs;
2588   location_t loc = gimple_location (stmt);
2589
2590   gcc_assert (is_gimple_call (stmt));
2591
2592   ignore = (gimple_call_lhs (stmt) == NULL);
2593
2594   /* First try the generic builtin folder.  If that succeeds, return the
2595      result directly.  */
2596   result = fold_call_stmt (stmt, ignore);
2597   if (result)
2598     {
2599       if (ignore)
2600         STRIP_NOPS (result);
2601       return result;
2602     }
2603
2604   /* Ignore MD builtins.  */
2605   callee = gimple_call_fndecl (stmt);
2606   if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_MD)
2607     return NULL_TREE;
2608
2609   /* If the builtin could not be folded, and it has no argument list,
2610      we're done.  */
2611   nargs = gimple_call_num_args (stmt);
2612   if (nargs == 0)
2613     return NULL_TREE;
2614
2615   /* Limit the work only for builtins we know how to simplify.  */
2616   switch (DECL_FUNCTION_CODE (callee))
2617     {
2618     case BUILT_IN_STRLEN:
2619     case BUILT_IN_FPUTS:
2620     case BUILT_IN_FPUTS_UNLOCKED:
2621       arg_idx = 0;
2622       type = 0;
2623       break;
2624     case BUILT_IN_STRCPY:
2625     case BUILT_IN_STRNCPY:
2626       arg_idx = 1;
2627       type = 0;
2628       break;
2629     case BUILT_IN_MEMCPY_CHK:
2630     case BUILT_IN_MEMPCPY_CHK:
2631     case BUILT_IN_MEMMOVE_CHK:
2632     case BUILT_IN_MEMSET_CHK:
2633     case BUILT_IN_STRNCPY_CHK:
2634       arg_idx = 2;
2635       type = 2;
2636       break;
2637     case BUILT_IN_STRCPY_CHK:
2638     case BUILT_IN_STPCPY_CHK:
2639       arg_idx = 1;
2640       type = 1;
2641       break;
2642     case BUILT_IN_SNPRINTF_CHK:
2643     case BUILT_IN_VSNPRINTF_CHK:
2644       arg_idx = 1;
2645       type = 2;
2646       break;
2647     default:
2648       return NULL_TREE;
2649     }
2650
2651   if (arg_idx >= nargs)
2652     return NULL_TREE;
2653
2654   /* Try to use the dataflow information gathered by the CCP process.  */
2655   visited = BITMAP_ALLOC (NULL);
2656   bitmap_clear (visited);
2657
2658   memset (val, 0, sizeof (val));
2659   a = gimple_call_arg (stmt, arg_idx);
2660   if (!get_maxval_strlen (a, &val[arg_idx], visited, type))
2661     val[arg_idx] = NULL_TREE;
2662
2663   BITMAP_FREE (visited);
2664
2665   result = NULL_TREE;
2666   switch (DECL_FUNCTION_CODE (callee))
2667     {
2668     case BUILT_IN_STRLEN:
2669       if (val[0] && nargs == 1)
2670         {
2671           tree new_val =
2672               fold_convert (TREE_TYPE (gimple_call_lhs (stmt)), val[0]);
2673
2674           /* If the result is not a valid gimple value, or not a cast
2675              of a valid gimple value, then we can not use the result.  */
2676           if (is_gimple_val (new_val)
2677               || (is_gimple_cast (new_val)
2678                   && is_gimple_val (TREE_OPERAND (new_val, 0))))
2679             return new_val;
2680         }
2681       break;
2682
2683     case BUILT_IN_STRCPY:
2684       if (val[1] && is_gimple_val (val[1]) && nargs == 2)
2685         result = fold_builtin_strcpy (loc, callee,
2686                                       gimple_call_arg (stmt, 0),
2687                                       gimple_call_arg (stmt, 1),
2688                                       val[1]);
2689       break;
2690
2691     case BUILT_IN_STRNCPY:
2692       if (val[1] && is_gimple_val (val[1]) && nargs == 3)
2693         result = fold_builtin_strncpy (loc, callee,
2694                                        gimple_call_arg (stmt, 0),
2695                                        gimple_call_arg (stmt, 1),
2696                                        gimple_call_arg (stmt, 2),
2697                                        val[1]);
2698       break;
2699
2700     case BUILT_IN_FPUTS:
2701       if (nargs == 2)
2702         result = fold_builtin_fputs (loc, gimple_call_arg (stmt, 0),
2703                                      gimple_call_arg (stmt, 1),
2704                                      ignore, false, val[0]);
2705       break;
2706
2707     case BUILT_IN_FPUTS_UNLOCKED:
2708       if (nargs == 2)
2709         result = fold_builtin_fputs (loc, gimple_call_arg (stmt, 0),
2710                                      gimple_call_arg (stmt, 1),
2711                                      ignore, true, val[0]);
2712       break;
2713
2714     case BUILT_IN_MEMCPY_CHK:
2715     case BUILT_IN_MEMPCPY_CHK:
2716     case BUILT_IN_MEMMOVE_CHK:
2717     case BUILT_IN_MEMSET_CHK:
2718       if (val[2] && is_gimple_val (val[2]) && nargs == 4)
2719         result = fold_builtin_memory_chk (loc, callee,
2720                                           gimple_call_arg (stmt, 0),
2721                                           gimple_call_arg (stmt, 1),
2722                                           gimple_call_arg (stmt, 2),
2723                                           gimple_call_arg (stmt, 3),
2724                                           val[2], ignore,
2725                                           DECL_FUNCTION_CODE (callee));
2726       break;
2727
2728     case BUILT_IN_STRCPY_CHK:
2729     case BUILT_IN_STPCPY_CHK:
2730       if (val[1] && is_gimple_val (val[1]) && nargs == 3)
2731         result = fold_builtin_stxcpy_chk (loc, callee,
2732                                           gimple_call_arg (stmt, 0),
2733                                           gimple_call_arg (stmt, 1),
2734                                           gimple_call_arg (stmt, 2),
2735                                           val[1], ignore,
2736                                           DECL_FUNCTION_CODE (callee));
2737       break;
2738
2739     case BUILT_IN_STRNCPY_CHK:
2740       if (val[2] && is_gimple_val (val[2]) && nargs == 4)
2741         result = fold_builtin_strncpy_chk (loc, gimple_call_arg (stmt, 0),
2742                                            gimple_call_arg (stmt, 1),
2743                                            gimple_call_arg (stmt, 2),
2744                                            gimple_call_arg (stmt, 3),
2745                                            val[2]);
2746       break;
2747
2748     case BUILT_IN_SNPRINTF_CHK:
2749     case BUILT_IN_VSNPRINTF_CHK:
2750       if (val[1] && is_gimple_val (val[1]))
2751         result = gimple_fold_builtin_snprintf_chk (stmt, val[1],
2752                                                    DECL_FUNCTION_CODE (callee));
2753       break;
2754
2755     default:
2756       gcc_unreachable ();
2757     }
2758
2759   if (result && ignore)
2760     result = fold_ignored_result (result);
2761   return result;
2762 }
2763
2764 /* Attempt to fold an assignment statement pointed-to by SI.  Returns a
2765    replacement rhs for the statement or NULL_TREE if no simplification
2766    could be made.  It is assumed that the operands have been previously
2767    folded.  */
2768
2769 static tree
2770 fold_gimple_assign (gimple_stmt_iterator *si)
2771 {
2772   gimple stmt = gsi_stmt (*si);
2773   enum tree_code subcode = gimple_assign_rhs_code (stmt);
2774   location_t loc = gimple_location (stmt);
2775
2776   tree result = NULL_TREE;
2777
2778   switch (get_gimple_rhs_class (subcode))
2779     {
2780     case GIMPLE_SINGLE_RHS:
2781       {
2782         tree rhs = gimple_assign_rhs1 (stmt);
2783
2784         /* Try to fold a conditional expression.  */
2785         if (TREE_CODE (rhs) == COND_EXPR)
2786           {
2787             tree op0 = COND_EXPR_COND (rhs);
2788             tree tem;
2789             bool set = false;
2790             location_t cond_loc = EXPR_LOCATION (rhs);
2791
2792             if (COMPARISON_CLASS_P (op0))
2793               {
2794                 fold_defer_overflow_warnings ();
2795                 tem = fold_binary_loc (cond_loc,
2796                                    TREE_CODE (op0), TREE_TYPE (op0),
2797                                    TREE_OPERAND (op0, 0),
2798                                    TREE_OPERAND (op0, 1));
2799                 /* This is actually a conditional expression, not a GIMPLE
2800                    conditional statement, however, the valid_gimple_rhs_p
2801                    test still applies.  */
2802                 set = (tem && is_gimple_condexpr (tem)
2803                        && valid_gimple_rhs_p (tem));
2804                 fold_undefer_overflow_warnings (set, stmt, 0);
2805               }
2806             else if (is_gimple_min_invariant (op0))
2807               {
2808                 tem = op0;
2809                 set = true;
2810               }
2811             else
2812               return NULL_TREE;
2813
2814             if (set)
2815               result = fold_build3_loc (cond_loc, COND_EXPR, TREE_TYPE (rhs), tem,
2816                                     COND_EXPR_THEN (rhs), COND_EXPR_ELSE (rhs));
2817           }
2818
2819         else if (TREE_CODE (rhs) == TARGET_MEM_REF)
2820           return maybe_fold_tmr (rhs);
2821
2822         else if (REFERENCE_CLASS_P (rhs))
2823           return maybe_fold_reference (rhs, false);
2824
2825         else if (TREE_CODE (rhs) == ADDR_EXPR)
2826           {
2827             tree tem = maybe_fold_reference (TREE_OPERAND (rhs, 0), true);
2828             if (tem)
2829               result = fold_convert (TREE_TYPE (rhs),
2830                                      build_fold_addr_expr_loc (loc, tem));
2831           }
2832
2833         else if (TREE_CODE (rhs) == CONSTRUCTOR
2834                  && TREE_CODE (TREE_TYPE (rhs)) == VECTOR_TYPE
2835                  && (CONSTRUCTOR_NELTS (rhs)
2836                      == TYPE_VECTOR_SUBPARTS (TREE_TYPE (rhs))))
2837           {
2838             /* Fold a constant vector CONSTRUCTOR to VECTOR_CST.  */
2839             unsigned i;
2840             tree val;
2841
2842             FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (rhs), i, val)
2843               if (TREE_CODE (val) != INTEGER_CST
2844                   && TREE_CODE (val) != REAL_CST
2845                   && TREE_CODE (val) != FIXED_CST)
2846                 return NULL_TREE;
2847
2848             return build_vector_from_ctor (TREE_TYPE (rhs),
2849                                            CONSTRUCTOR_ELTS (rhs));
2850           }
2851
2852         else if (DECL_P (rhs))
2853           return unshare_expr (get_symbol_constant_value (rhs));
2854
2855         /* If we couldn't fold the RHS, hand over to the generic
2856            fold routines.  */
2857         if (result == NULL_TREE)
2858           result = fold (rhs);
2859
2860         /* Strip away useless type conversions.  Both the NON_LVALUE_EXPR
2861            that may have been added by fold, and "useless" type
2862            conversions that might now be apparent due to propagation.  */
2863         STRIP_USELESS_TYPE_CONVERSION (result);
2864
2865         if (result != rhs && valid_gimple_rhs_p (result))
2866           return result;
2867
2868         return NULL_TREE;
2869       }
2870       break;
2871
2872     case GIMPLE_UNARY_RHS:
2873       {
2874         tree rhs = gimple_assign_rhs1 (stmt);
2875
2876         result = fold_unary_loc (loc, subcode, gimple_expr_type (stmt), rhs);
2877         if (result)
2878           {
2879             /* If the operation was a conversion do _not_ mark a
2880                resulting constant with TREE_OVERFLOW if the original
2881                constant was not.  These conversions have implementation
2882                defined behavior and retaining the TREE_OVERFLOW flag
2883                here would confuse later passes such as VRP.  */
2884             if (CONVERT_EXPR_CODE_P (subcode)
2885                 && TREE_CODE (result) == INTEGER_CST
2886                 && TREE_CODE (rhs) == INTEGER_CST)
2887               TREE_OVERFLOW (result) = TREE_OVERFLOW (rhs);
2888
2889             STRIP_USELESS_TYPE_CONVERSION (result);
2890             if (valid_gimple_rhs_p (result))
2891               return result;
2892           }
2893         else if (CONVERT_EXPR_CODE_P (subcode)
2894                  && POINTER_TYPE_P (gimple_expr_type (stmt))
2895                  && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt))))
2896           {
2897             tree type = gimple_expr_type (stmt);
2898             tree t = maybe_fold_offset_to_address (loc,
2899                                                    gimple_assign_rhs1 (stmt),
2900                                                    integer_zero_node, type);
2901             if (t)
2902               return t;
2903           }
2904       }
2905       break;
2906
2907     case GIMPLE_BINARY_RHS:
2908       /* Try to fold pointer addition.  */
2909       if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
2910         {
2911           tree type = TREE_TYPE (gimple_assign_rhs1 (stmt));
2912           if (TREE_CODE (TREE_TYPE (type)) == ARRAY_TYPE)
2913             {
2914               type = build_pointer_type (TREE_TYPE (TREE_TYPE (type)));
2915               if (!useless_type_conversion_p
2916                     (TREE_TYPE (gimple_assign_lhs (stmt)), type))
2917                 type = TREE_TYPE (gimple_assign_rhs1 (stmt));
2918             }
2919           result = maybe_fold_stmt_addition (gimple_location (stmt),
2920                                              type,
2921                                              gimple_assign_rhs1 (stmt),
2922                                              gimple_assign_rhs2 (stmt));
2923         }
2924
2925       if (!result)
2926         result = fold_binary_loc (loc, subcode,
2927                               TREE_TYPE (gimple_assign_lhs (stmt)),
2928                               gimple_assign_rhs1 (stmt),
2929                               gimple_assign_rhs2 (stmt));
2930
2931       if (result)
2932         {
2933           STRIP_USELESS_TYPE_CONVERSION (result);
2934           if (valid_gimple_rhs_p (result))
2935             return result;
2936
2937           /* Fold might have produced non-GIMPLE, so if we trust it blindly
2938              we lose canonicalization opportunities.  Do not go again
2939              through fold here though, or the same non-GIMPLE will be
2940              produced.  */
2941           if (commutative_tree_code (subcode)
2942               && tree_swap_operands_p (gimple_assign_rhs1 (stmt),
2943                                        gimple_assign_rhs2 (stmt), false))
2944             return build2 (subcode, TREE_TYPE (gimple_assign_lhs (stmt)),
2945                            gimple_assign_rhs2 (stmt),
2946                            gimple_assign_rhs1 (stmt));
2947         }
2948       break;
2949
2950     case GIMPLE_INVALID_RHS:
2951       gcc_unreachable ();
2952     }
2953
2954   return NULL_TREE;
2955 }
2956
2957 /* Attempt to fold a conditional statement. Return true if any changes were
2958    made. We only attempt to fold the condition expression, and do not perform
2959    any transformation that would require alteration of the cfg.  It is
2960    assumed that the operands have been previously folded.  */
2961
2962 static bool
2963 fold_gimple_cond (gimple stmt)
2964 {
2965   tree result = fold_binary_loc (gimple_location (stmt),
2966                              gimple_cond_code (stmt),
2967                              boolean_type_node,
2968                              gimple_cond_lhs (stmt),
2969                              gimple_cond_rhs (stmt));
2970
2971   if (result)
2972     {
2973       STRIP_USELESS_TYPE_CONVERSION (result);
2974       if (is_gimple_condexpr (result) && valid_gimple_rhs_p (result))
2975         {
2976           gimple_cond_set_condition_from_tree (stmt, result);
2977           return true;
2978         }
2979     }
2980
2981   return false;
2982 }
2983
2984 static void gimplify_and_update_call_from_tree (gimple_stmt_iterator *, tree);
2985
2986 /* Attempt to fold a call statement referenced by the statement iterator GSI.
2987    The statement may be replaced by another statement, e.g., if the call
2988    simplifies to a constant value. Return true if any changes were made.
2989    It is assumed that the operands have been previously folded.  */
2990
2991 static bool
2992 fold_gimple_call (gimple_stmt_iterator *gsi)
2993 {
2994   gimple stmt = gsi_stmt (*gsi);
2995
2996   tree callee = gimple_call_fndecl (stmt);
2997
2998   /* Check for builtins that CCP can handle using information not
2999      available in the generic fold routines.  */
3000   if (callee && DECL_BUILT_IN (callee))
3001     {
3002       tree result = ccp_fold_builtin (stmt);
3003
3004       if (result)
3005         {
3006           if (!update_call_from_tree (gsi, result))
3007             gimplify_and_update_call_from_tree (gsi, result);
3008           return true;
3009         }
3010     }
3011   else
3012     {
3013       /* Check for resolvable OBJ_TYPE_REF.  The only sorts we can resolve
3014          here are when we've propagated the address of a decl into the
3015          object slot.  */
3016       /* ??? Should perhaps do this in fold proper.  However, doing it
3017          there requires that we create a new CALL_EXPR, and that requires
3018          copying EH region info to the new node.  Easier to just do it
3019          here where we can just smash the call operand.  */
3020       /* ??? Is there a good reason not to do this in fold_stmt_inplace?  */
3021       callee = gimple_call_fn (stmt);
3022       if (TREE_CODE (callee) == OBJ_TYPE_REF
3023           && lang_hooks.fold_obj_type_ref
3024           && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR
3025           && DECL_P (TREE_OPERAND
3026                      (OBJ_TYPE_REF_OBJECT (callee), 0)))
3027         {
3028           tree t;
3029
3030           /* ??? Caution: Broken ADDR_EXPR semantics means that
3031              looking at the type of the operand of the addr_expr
3032              can yield an array type.  See silly exception in
3033              check_pointer_types_r.  */
3034           t = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (callee)));
3035           t = lang_hooks.fold_obj_type_ref (callee, t);
3036           if (t)
3037             {
3038               gimple_call_set_fn (stmt, t);
3039               return true;
3040             }
3041         }
3042     }
3043
3044   return false;
3045 }
3046
3047 /* Worker for both fold_stmt and fold_stmt_inplace.  The INPLACE argument
3048    distinguishes both cases.  */
3049
3050 static bool
3051 fold_stmt_1 (gimple_stmt_iterator *gsi, bool inplace)
3052 {
3053   bool changed = false;
3054   gimple stmt = gsi_stmt (*gsi);
3055   unsigned i;
3056
3057   /* Fold the main computation performed by the statement.  */
3058   switch (gimple_code (stmt))
3059     {
3060     case GIMPLE_ASSIGN:
3061       {
3062         unsigned old_num_ops = gimple_num_ops (stmt);
3063         tree new_rhs = fold_gimple_assign (gsi);
3064         tree lhs = gimple_assign_lhs (stmt);
3065         if (new_rhs
3066             && !useless_type_conversion_p (TREE_TYPE (lhs),
3067                                            TREE_TYPE (new_rhs)))
3068           new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs);
3069         if (new_rhs
3070             && (!inplace
3071                 || get_gimple_rhs_num_ops (TREE_CODE (new_rhs)) < old_num_ops))
3072           {
3073             gimple_assign_set_rhs_from_tree (gsi, new_rhs);
3074             changed = true;
3075           }
3076         break;
3077       }
3078
3079     case GIMPLE_COND:
3080       changed |= fold_gimple_cond (stmt);
3081       break;
3082
3083     case GIMPLE_CALL:
3084       /* Fold *& in call arguments.  */
3085       for (i = 0; i < gimple_call_num_args (stmt); ++i)
3086         if (REFERENCE_CLASS_P (gimple_call_arg (stmt, i)))
3087           {
3088             tree tmp = maybe_fold_reference (gimple_call_arg (stmt, i), false);
3089             if (tmp)
3090               {
3091                 gimple_call_set_arg (stmt, i, tmp);
3092                 changed = true;
3093               }
3094           }
3095       /* The entire statement may be replaced in this case.  */
3096       if (!inplace)
3097         changed |= fold_gimple_call (gsi);
3098       break;
3099
3100     case GIMPLE_ASM:
3101       /* Fold *& in asm operands.  */
3102       for (i = 0; i < gimple_asm_noutputs (stmt); ++i)
3103         {
3104           tree link = gimple_asm_output_op (stmt, i);
3105           tree op = TREE_VALUE (link);
3106           if (REFERENCE_CLASS_P (op)
3107               && (op = maybe_fold_reference (op, true)) != NULL_TREE)
3108             {
3109               TREE_VALUE (link) = op;
3110               changed = true;
3111             }
3112         }
3113       for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
3114         {
3115           tree link = gimple_asm_input_op (stmt, i);
3116           tree op = TREE_VALUE (link);
3117           if (REFERENCE_CLASS_P (op)
3118               && (op = maybe_fold_reference (op, false)) != NULL_TREE)
3119             {
3120               TREE_VALUE (link) = op;
3121               changed = true;
3122             }
3123         }
3124       break;
3125
3126     default:;
3127     }
3128
3129   stmt = gsi_stmt (*gsi);
3130
3131   /* Fold *& on the lhs.  */
3132   if (gimple_has_lhs (stmt))
3133     {
3134       tree lhs = gimple_get_lhs (stmt);
3135       if (lhs && REFERENCE_CLASS_P (lhs))
3136         {
3137           tree new_lhs = maybe_fold_reference (lhs, true);
3138           if (new_lhs)
3139             {
3140               gimple_set_lhs (stmt, new_lhs);
3141               changed = true;
3142             }
3143         }
3144     }
3145
3146   return changed;
3147 }
3148
3149 /* Fold the statement pointed to by GSI.  In some cases, this function may
3150    replace the whole statement with a new one.  Returns true iff folding
3151    makes any changes.
3152    The statement pointed to by GSI should be in valid gimple form but may
3153    be in unfolded state as resulting from for example constant propagation
3154    which can produce *&x = 0.  */
3155
3156 bool
3157 fold_stmt (gimple_stmt_iterator *gsi)
3158 {
3159   return fold_stmt_1 (gsi, false);
3160 }
3161
3162 /* Perform the minimal folding on statement STMT.  Only operations like
3163    *&x created by constant propagation are handled.  The statement cannot
3164    be replaced with a new one.  Return true if the statement was
3165    changed, false otherwise.
3166    The statement STMT should be in valid gimple form but may
3167    be in unfolded state as resulting from for example constant propagation
3168    which can produce *&x = 0.  */
3169
3170 bool
3171 fold_stmt_inplace (gimple stmt)
3172 {
3173   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
3174   bool changed = fold_stmt_1 (&gsi, true);
3175   gcc_assert (gsi_stmt (gsi) == stmt);
3176   return changed;
3177 }
3178
3179 /* Try to optimize out __builtin_stack_restore.  Optimize it out
3180    if there is another __builtin_stack_restore in the same basic
3181    block and no calls or ASM_EXPRs are in between, or if this block's
3182    only outgoing edge is to EXIT_BLOCK and there are no calls or
3183    ASM_EXPRs after this __builtin_stack_restore.  */
3184
3185 static tree
3186 optimize_stack_restore (gimple_stmt_iterator i)
3187 {
3188   tree callee;
3189   gimple stmt;
3190
3191   basic_block bb = gsi_bb (i);
3192   gimple call = gsi_stmt (i);
3193
3194   if (gimple_code (call) != GIMPLE_CALL
3195       || gimple_call_num_args (call) != 1
3196       || TREE_CODE (gimple_call_arg (call, 0)) != SSA_NAME
3197       || !POINTER_TYPE_P (TREE_TYPE (gimple_call_arg (call, 0))))
3198     return NULL_TREE;
3199
3200   for (gsi_next (&i); !gsi_end_p (i); gsi_next (&i))
3201     {
3202       stmt = gsi_stmt (i);
3203       if (gimple_code (stmt) == GIMPLE_ASM)
3204         return NULL_TREE;
3205       if (gimple_code (stmt) != GIMPLE_CALL)
3206         continue;
3207
3208       callee = gimple_call_fndecl (stmt);
3209       if (!callee
3210           || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL
3211           /* All regular builtins are ok, just obviously not alloca.  */
3212           || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALLOCA)
3213         return NULL_TREE;
3214
3215       if (DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_RESTORE)
3216         goto second_stack_restore;
3217     }
3218
3219   if (!gsi_end_p (i))
3220     return NULL_TREE;
3221
3222   /* Allow one successor of the exit block, or zero successors.  */
3223   switch (EDGE_COUNT (bb->succs))
3224     {
3225     case 0:
3226       break;
3227     case 1:
3228       if (single_succ_edge (bb)->dest != EXIT_BLOCK_PTR)
3229         return NULL_TREE;
3230       break;
3231     default:
3232       return NULL_TREE;
3233     }
3234  second_stack_restore:
3235
3236   /* If there's exactly one use, then zap the call to __builtin_stack_save.
3237      If there are multiple uses, then the last one should remove the call.
3238      In any case, whether the call to __builtin_stack_save can be removed
3239      or not is irrelevant to removing the call to __builtin_stack_restore.  */
3240   if (has_single_use (gimple_call_arg (call, 0)))
3241     {
3242       gimple stack_save = SSA_NAME_DEF_STMT (gimple_call_arg (call, 0));
3243       if (is_gimple_call (stack_save))
3244         {
3245           callee = gimple_call_fndecl (stack_save);
3246           if (callee
3247               && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
3248               && DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_SAVE)
3249             {
3250               gimple_stmt_iterator stack_save_gsi;
3251               tree rhs;
3252
3253               stack_save_gsi = gsi_for_stmt (stack_save);
3254               rhs = build_int_cst (TREE_TYPE (gimple_call_arg (call, 0)), 0);
3255               update_call_from_tree (&stack_save_gsi, rhs);
3256             }
3257         }
3258     }
3259
3260   /* No effect, so the statement will be deleted.  */
3261   return integer_zero_node;
3262 }
3263
3264 /* If va_list type is a simple pointer and nothing special is needed,
3265    optimize __builtin_va_start (&ap, 0) into ap = __builtin_next_arg (0),
3266    __builtin_va_end (&ap) out as NOP and __builtin_va_copy into a simple
3267    pointer assignment.  */
3268
3269 static tree
3270 optimize_stdarg_builtin (gimple call)
3271 {
3272   tree callee, lhs, rhs, cfun_va_list;
3273   bool va_list_simple_ptr;
3274   location_t loc = gimple_location (call);
3275
3276   if (gimple_code (call) != GIMPLE_CALL)
3277     return NULL_TREE;
3278
3279   callee = gimple_call_fndecl (call);
3280
3281   cfun_va_list = targetm.fn_abi_va_list (callee);
3282   va_list_simple_ptr = POINTER_TYPE_P (cfun_va_list)
3283                        && (TREE_TYPE (cfun_va_list) == void_type_node
3284                            || TREE_TYPE (cfun_va_list) == char_type_node);
3285
3286   switch (DECL_FUNCTION_CODE (callee))
3287     {
3288     case BUILT_IN_VA_START:
3289       if (!va_list_simple_ptr
3290           || targetm.expand_builtin_va_start != NULL
3291           || built_in_decls[BUILT_IN_NEXT_ARG] == NULL)
3292         return NULL_TREE;
3293
3294       if (gimple_call_num_args (call) != 2)
3295         return NULL_TREE;
3296
3297       lhs = gimple_call_arg (call, 0);
3298       if (!POINTER_TYPE_P (TREE_TYPE (lhs))
3299           || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs)))
3300              != TYPE_MAIN_VARIANT (cfun_va_list))
3301         return NULL_TREE;
3302
3303       lhs = build_fold_indirect_ref_loc (loc, lhs);
3304       rhs = build_call_expr_loc (loc, built_in_decls[BUILT_IN_NEXT_ARG],
3305                              1, integer_zero_node);
3306       rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
3307       return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
3308
3309     case BUILT_IN_VA_COPY:
3310       if (!va_list_simple_ptr)
3311         return NULL_TREE;
3312
3313       if (gimple_call_num_args (call) != 2)
3314         return NULL_TREE;
3315
3316       lhs = gimple_call_arg (call, 0);
3317       if (!POINTER_TYPE_P (TREE_TYPE (lhs))
3318           || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs)))
3319              != TYPE_MAIN_VARIANT (cfun_va_list))
3320         return NULL_TREE;
3321
3322       lhs = build_fold_indirect_ref_loc (loc, lhs);
3323       rhs = gimple_call_arg (call, 1);
3324       if (TYPE_MAIN_VARIANT (TREE_TYPE (rhs))
3325           != TYPE_MAIN_VARIANT (cfun_va_list))
3326         return NULL_TREE;
3327
3328       rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
3329       return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
3330
3331     case BUILT_IN_VA_END:
3332       /* No effect, so the statement will be deleted.  */
3333       return integer_zero_node;
3334
3335     default:
3336       gcc_unreachable ();
3337     }
3338 }
3339
3340 /* Convert EXPR into a GIMPLE value suitable for substitution on the
3341    RHS of an assignment.  Insert the necessary statements before
3342    iterator *SI_P.  The statement at *SI_P, which must be a GIMPLE_CALL
3343    is replaced.  If the call is expected to produces a result, then it
3344    is replaced by an assignment of the new RHS to the result variable.
3345    If the result is to be ignored, then the call is replaced by a
3346    GIMPLE_NOP.  */
3347
3348 static void
3349 gimplify_and_update_call_from_tree (gimple_stmt_iterator *si_p, tree expr)
3350 {
3351   tree lhs;
3352   tree tmp = NULL_TREE;  /* Silence warning.  */
3353   gimple stmt, new_stmt;
3354   gimple_stmt_iterator i;
3355   gimple_seq stmts = gimple_seq_alloc();
3356   struct gimplify_ctx gctx;
3357   gimple last = NULL;
3358
3359   stmt = gsi_stmt (*si_p);
3360
3361   gcc_assert (is_gimple_call (stmt));
3362
3363   lhs = gimple_call_lhs (stmt);
3364
3365   push_gimplify_context (&gctx);
3366
3367   if (lhs == NULL_TREE)
3368     gimplify_and_add (expr, &stmts);
3369   else
3370     tmp = get_initialized_tmp_var (expr, &stmts, NULL);
3371
3372   pop_gimplify_context (NULL);
3373
3374   if (gimple_has_location (stmt))
3375     annotate_all_with_location (stmts, gimple_location (stmt));
3376
3377   /* The replacement can expose previously unreferenced variables.  */
3378   for (i = gsi_start (stmts); !gsi_end_p (i); gsi_next (&i))
3379     {
3380       if (last)
3381         {
3382           gsi_insert_before (si_p, last, GSI_NEW_STMT);
3383           gsi_next (si_p);
3384         }
3385       new_stmt = gsi_stmt (i);
3386       find_new_referenced_vars (new_stmt);
3387       mark_symbols_for_renaming (new_stmt);
3388       last = new_stmt;
3389     }
3390
3391   if (lhs == NULL_TREE)
3392     {
3393       unlink_stmt_vdef (stmt);
3394       release_defs (stmt);
3395       new_stmt = last;
3396     }
3397   else
3398     {
3399       if (last)
3400         {
3401           gsi_insert_before (si_p, last, GSI_NEW_STMT);
3402           gsi_next (si_p);
3403         }
3404       new_stmt = gimple_build_assign (lhs, tmp);
3405       gimple_set_vuse (new_stmt, gimple_vuse (stmt));
3406       gimple_set_vdef (new_stmt, gimple_vdef (stmt));
3407       move_ssa_defining_stmt_for_defs (new_stmt, stmt);
3408     }
3409
3410   gimple_set_location (new_stmt, gimple_location (stmt));
3411   gsi_replace (si_p, new_stmt, false);
3412 }