OSDN Git Service

b1b74b1e68f562e9499052899f47966a082fa362
[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 Free Software Foundation, Inc.
3    Adapted from original RTL SSA-CCP by Daniel Berlin <dberlin@dberlin.org>
4    Adapted to GIMPLE trees by Diego Novillo <dnovillo@redhat.com>
5
6 This file is part of GCC.
7    
8 GCC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by the
10 Free Software Foundation; either version 2, or (at your option) any
11 later version.
12    
13 GCC is distributed in the hope that it will be useful, but WITHOUT
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17    
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING.  If not, write to the Free
20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
21 02111-1307, USA.  */
22
23 /* Conditional constant propagation.
24
25    References:
26
27      Constant propagation with conditional branches,
28      Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
29
30      Building an Optimizing Compiler,
31      Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
32
33      Advanced Compiler Design and Implementation,
34      Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6  */
35
36 #include "config.h"
37 #include "system.h"
38 #include "coretypes.h"
39 #include "tm.h"
40 #include "tree.h"
41 #include "flags.h"
42 #include "rtl.h"
43 #include "tm_p.h"
44 #include "ggc.h"
45 #include "basic-block.h"
46 #include "output.h"
47 #include "errors.h"
48 #include "expr.h"
49 #include "function.h"
50 #include "diagnostic.h"
51 #include "timevar.h"
52 #include "tree-dump.h"
53 #include "tree-flow.h"
54 #include "tree-pass.h"
55 #include "tree-ssa-propagate.h"
56 #include "langhooks.h"
57
58
59 /* Possible lattice values.  */
60 typedef enum
61 {
62   UNINITIALIZED = 0,
63   UNDEFINED,
64   UNKNOWN_VAL,
65   CONSTANT,
66   VARYING
67 } latticevalue;
68
69 /* Main structure for CCP.  Contains the lattice value and, if it's a
70     constant, the constant value.  */
71 typedef struct
72 {
73   latticevalue lattice_val;
74   tree const_val;
75 } value;
76
77 /* This is used to track the current value of each variable.  */
78 static value *value_vector;
79
80
81 /* Dump lattice value VAL to file OUTF prefixed by PREFIX.  */
82
83 static void
84 dump_lattice_value (FILE *outf, const char *prefix, value val)
85 {
86   switch (val.lattice_val)
87     {
88     case UNDEFINED:
89       fprintf (outf, "%sUNDEFINED", prefix);
90       break;
91     case VARYING:
92       fprintf (outf, "%sVARYING", prefix);
93       break;
94     case UNKNOWN_VAL:
95       fprintf (outf, "%sUNKNOWN_VAL", prefix);
96       break;
97     case CONSTANT:
98       fprintf (outf, "%sCONSTANT ", prefix);
99       print_generic_expr (outf, val.const_val, dump_flags);
100       break;
101     default:
102       abort ();
103     }
104 }
105
106
107 /* Return a default value for variable VAR using the following rules:
108
109    1- Function arguments are considered VARYING.
110    
111    2- Global and static variables that are declared constant are
112       considered CONSTANT.
113
114    3- Any other virtually defined variable is considered UNKNOWN_VAL.
115
116    4- Any other value is considered UNDEFINED.  This is useful when
117       considering PHI nodes.  PHI arguments that are undefined do not
118       change the constant value of the PHI node, which allows for more
119       constants to be propagated.  */
120
121 static value
122 get_default_value (tree var)
123 {
124   value val;
125   tree sym;
126
127   if (TREE_CODE (var) == SSA_NAME)
128     sym = SSA_NAME_VAR (var);
129   else
130     {
131 #ifdef ENABLE_CHECKING
132       if (!DECL_P (var))
133         abort ();
134 #endif
135       sym = var;
136     }
137
138   val.lattice_val = UNDEFINED;
139   val.const_val = NULL_TREE;
140
141   if (TREE_CODE (sym) == PARM_DECL || TREE_THIS_VOLATILE (sym))
142     {
143       /* Function arguments and volatile variables are considered VARYING.  */
144       val.lattice_val = VARYING;
145     }
146   else if (TREE_STATIC (sym))
147     {
148       /* Globals and static variables are considered UNKNOWN_VAL,
149          unless they are declared 'const'.  */
150       if (TREE_READONLY (sym)
151           && DECL_INITIAL (sym)
152           && is_gimple_min_invariant (DECL_INITIAL (sym)))
153         {
154           val.lattice_val = CONSTANT;
155           val.const_val = DECL_INITIAL (sym);
156         }
157       else
158         {
159           val.const_val = NULL_TREE;
160           val.lattice_val = UNKNOWN_VAL;
161         }
162     }
163   else if (!is_gimple_reg (sym))
164     {
165       val.const_val = NULL_TREE;
166       val.lattice_val = UNKNOWN_VAL;
167     }
168   else
169     {
170       enum tree_code code;
171       tree stmt = SSA_NAME_DEF_STMT (var);
172
173       if (!IS_EMPTY_STMT (stmt))
174         {
175           code = TREE_CODE (stmt);
176           if (code != MODIFY_EXPR && code != PHI_NODE)
177             val.lattice_val = VARYING;
178         }
179     }
180
181   return val;
182 }
183
184 /* Get the constant value associated with variable VAR.  */
185
186 static value *
187 get_value (tree var)
188 {
189   value *val;
190
191 #if defined ENABLE_CHECKING
192   if (TREE_CODE (var) != SSA_NAME)
193     abort ();
194 #endif
195
196   val = &value_vector[SSA_NAME_VERSION (var)];
197   if (val->lattice_val == UNINITIALIZED)
198     *val = get_default_value (var);
199
200   return val;
201 }
202
203
204 /* Set the lattice value for variable VAR to VAL.  Return true if VAL
205    is different from VAR's previous value.  */
206
207 static bool
208 set_lattice_value (tree var, value val)
209 {
210   value *old = get_value (var);
211
212 #ifdef ENABLE_CHECKING
213   if (val.lattice_val == UNDEFINED)
214     {
215       /* CONSTANT->UNDEFINED is never a valid state transition.  */
216       if (old->lattice_val == CONSTANT)
217         abort ();
218         
219       /* UNKNOWN_VAL->UNDEFINED is never a valid state transition.  */
220       if (old->lattice_val == UNKNOWN_VAL)
221         abort ();
222
223       /* VARYING->UNDEFINED is generally not a valid state transition,
224          except for values which are initialized to VARYING.  */
225       if (old->lattice_val == VARYING
226           && get_default_value (var).lattice_val != VARYING)
227         abort ();
228     }
229   else if (val.lattice_val == CONSTANT)
230     {
231       /* VARYING -> CONSTANT is an invalid state transition, except
232          for objects which start off in a VARYING state.  */
233       if (old->lattice_val == VARYING
234           && get_default_value (var).lattice_val != VARYING)
235         abort ();
236     }
237 #endif
238
239   /* If the constant for VAR has changed, then this VAR is really varying.  */
240   if (old->lattice_val == CONSTANT
241       && val.lattice_val == CONSTANT
242       && !simple_cst_equal (old->const_val, val.const_val))
243     {
244       val.lattice_val = VARYING;
245       val.const_val = NULL_TREE;
246     }
247
248   if (old->lattice_val != val.lattice_val)
249     {
250       if (dump_file && (dump_flags & TDF_DETAILS))
251         {
252           dump_lattice_value (dump_file, "Lattice value changed to ", val);
253           fprintf (dump_file, ".  Adding definition to SSA edges.\n");
254         }
255
256       *old = val;
257       return true;
258     }
259
260   return false;
261 }
262
263
264 /* Set the lattice value for the variable VAR to VARYING.  */
265
266 static void
267 def_to_varying (tree var)
268 {
269   value val;
270   val.lattice_val = VARYING;
271   val.const_val = NULL_TREE;
272   set_lattice_value (var, val);
273 }
274
275
276 /* Return the likely latticevalue for STMT.
277
278    If STMT has no operands, then return CONSTANT.
279
280    Else if any operands of STMT are undefined, then return UNDEFINED.
281
282    Else if any operands of STMT are constants, then return CONSTANT.
283
284    Else return VARYING.  */
285
286 static latticevalue
287 likely_value (tree stmt)
288 {
289   vuse_optype vuses;
290   int found_constant = 0;
291   stmt_ann_t ann;
292   tree use;
293   ssa_op_iter iter;
294
295   /* If the statement makes aliased loads or has volatile operands, it
296      won't fold to a constant value.  */
297   ann = stmt_ann (stmt);
298   if (ann->makes_aliased_loads || ann->has_volatile_ops)
299     return VARYING;
300
301   /* A CALL_EXPR is assumed to be varying.  This may be overly conservative,
302      in the presence of const and pure calls.  */
303   if (get_call_expr_in (stmt) != NULL_TREE)
304     return VARYING;
305
306   get_stmt_operands (stmt);
307
308   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
309     {
310       value *val = get_value (use);
311
312       if (val->lattice_val == UNDEFINED)
313         return UNDEFINED;
314
315       if (val->lattice_val == CONSTANT)
316         found_constant = 1;
317     }
318     
319   vuses = VUSE_OPS (ann);
320   
321   if (NUM_VUSES (vuses))
322     {
323       tree vuse = VUSE_OP (vuses, 0);
324       value *val = get_value (vuse);
325       
326       if (val->lattice_val == UNKNOWN_VAL)
327         return UNKNOWN_VAL;
328         
329 #ifdef ENABLE_CHECKING
330   /* There should be no VUSE operands that are UNDEFINED.  */
331   if (val->lattice_val == UNDEFINED)
332     abort ();
333 #endif
334         
335       if (val->lattice_val == CONSTANT)
336         found_constant = 1;
337     }
338
339   return ((found_constant || (!USE_OPS (ann) && !vuses)) ? CONSTANT : VARYING);
340 }
341
342
343 /* Function indicating whether we ought to include information for VAR
344    when calculating immediate uses.  */
345
346 static bool
347 need_imm_uses_for (tree var)
348 {
349   return get_value (var)->lattice_val != VARYING;
350 }
351
352
353 /* Initialize local data structures for CCP.  */
354
355 static void
356 ccp_initialize (void)
357 {
358   basic_block bb;
359   sbitmap is_may_def;
360
361   value_vector = (value *) xmalloc (num_ssa_names * sizeof (value));
362   memset (value_vector, 0, num_ssa_names * sizeof (value));
363
364   /* Set of SSA_NAMEs that are defined by a V_MAY_DEF.  */
365   is_may_def = sbitmap_alloc (num_ssa_names);
366   sbitmap_zero (is_may_def);
367
368   /* Initialize simulation flags for PHI nodes and statements.  */
369   FOR_EACH_BB (bb)
370     {
371       block_stmt_iterator i;
372
373       /* Mark all V_MAY_DEF operands VARYING.  */
374       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
375         {
376           bool is_varying = false;
377           tree stmt = bsi_stmt (i);
378           ssa_op_iter iter;
379           tree def;
380
381           get_stmt_operands (stmt);
382
383           /* Get the default value for each DEF and V_MUST_DEF.  */
384           FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, 
385                                      (SSA_OP_DEF | SSA_OP_VMUSTDEF))
386             {
387               if (get_value (def)->lattice_val == VARYING)
388                 is_varying = true;
389             }
390
391           /* Mark all V_MAY_DEF operands VARYING.  */
392           FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_VMAYDEF)
393             {
394               get_value (def)->lattice_val = VARYING;
395               SET_BIT (is_may_def, SSA_NAME_VERSION (def));
396             }
397
398           /* Statements other than MODIFY_EXPR, COND_EXPR and
399              SWITCH_EXPR are not interesting for constant propagation.
400              Mark them VARYING.  */
401           if (TREE_CODE (stmt) != MODIFY_EXPR
402               && TREE_CODE (stmt) != COND_EXPR
403               && TREE_CODE (stmt) != SWITCH_EXPR)
404             is_varying = true;
405
406           DONT_SIMULATE_AGAIN (stmt) = is_varying;
407         }
408     }
409
410   /* Now process PHI nodes.  */
411   FOR_EACH_BB (bb)
412     {
413       tree phi, var;
414       int x;
415
416       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
417         {
418           value *val = get_value (PHI_RESULT (phi));
419
420           for (x = 0; x < PHI_NUM_ARGS (phi); x++)
421             {
422               var = PHI_ARG_DEF (phi, x);
423
424               /* If one argument has a V_MAY_DEF, the result is
425                  VARYING.  */
426               if (TREE_CODE (var) == SSA_NAME)
427                 {
428                   if (TEST_BIT (is_may_def, SSA_NAME_VERSION (var)))
429                     {
430                       val->lattice_val = VARYING;
431                       SET_BIT (is_may_def, SSA_NAME_VERSION (PHI_RESULT (phi)));
432                       break;
433                     }
434                 }
435             }
436
437           DONT_SIMULATE_AGAIN (phi) = (val->lattice_val == VARYING);
438         }
439     }
440
441   sbitmap_free (is_may_def);
442
443   /* Compute immediate uses for variables we care about.  */
444   compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, need_imm_uses_for);
445 }
446
447
448 /* Replace USE references in statement STMT with their immediate reaching
449    definition.  Return true if at least one reference was replaced.  If
450    REPLACED_ADDRESSES_P is given, it will be set to true if an address
451    constant was replaced.  */
452
453 static bool
454 replace_uses_in (tree stmt, bool *replaced_addresses_p)
455 {
456   bool replaced = false;
457   use_operand_p use;
458   ssa_op_iter iter;
459
460   if (replaced_addresses_p)
461     *replaced_addresses_p = false;
462
463   get_stmt_operands (stmt);
464
465   FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
466     {
467       value *val = get_value (USE_FROM_PTR (use));
468
469       if (val->lattice_val == CONSTANT)
470         {
471           SET_USE (use, val->const_val);
472           replaced = true;
473           if (POINTER_TYPE_P (TREE_TYPE (USE_FROM_PTR (use))) 
474               && replaced_addresses_p)
475             *replaced_addresses_p = true;
476         }
477     }
478
479   return replaced;
480 }
481
482
483 /* Replace the VUSE references in statement STMT with its immediate reaching
484    definition.  Return true if the reference was replaced.  If
485    REPLACED_ADDRESSES_P is given, it will be set to true if an address
486    constant was replaced.  */
487
488 static bool
489 replace_vuse_in (tree stmt, bool *replaced_addresses_p)
490 {
491   bool replaced = false;
492   vuse_optype vuses;
493   use_operand_p vuse;
494   value *val;
495
496   if (replaced_addresses_p)
497     *replaced_addresses_p = false;
498
499   get_stmt_operands (stmt);
500
501   vuses = STMT_VUSE_OPS (stmt);
502
503   if (NUM_VUSES (vuses) != 1)
504     return false;
505
506   vuse = VUSE_OP_PTR (vuses, 0);
507   val = get_value (USE_FROM_PTR (vuse));
508
509   if (val->lattice_val == CONSTANT
510       && TREE_CODE (stmt) == MODIFY_EXPR
511       && DECL_P (TREE_OPERAND (stmt, 1))
512       && TREE_OPERAND (stmt, 1) == SSA_NAME_VAR (USE_FROM_PTR (vuse)))
513     {
514       TREE_OPERAND (stmt, 1) = val->const_val;
515       replaced = true;
516       if (POINTER_TYPE_P (TREE_TYPE (USE_FROM_PTR (vuse))) 
517           && replaced_addresses_p)
518         *replaced_addresses_p = true;
519     }
520
521   return replaced;
522 }
523
524
525 /* Perform final substitution and folding.  After this pass the program
526    should still be in SSA form.  */
527
528 static void
529 substitute_and_fold (void)
530 {
531   basic_block bb;
532
533   if (dump_file && (dump_flags & TDF_DETAILS))
534     fprintf (dump_file,
535              "\nSubstituing constants and folding statements\n\n");
536
537   /* Substitute constants in every statement of every basic block.  */
538   FOR_EACH_BB (bb)
539     {
540       block_stmt_iterator i;
541       tree phi;
542
543       /* Propagate our known constants into PHI nodes.  */
544       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
545         {
546           int i;
547
548           for (i = 0; i < PHI_NUM_ARGS (phi); i++)
549             {
550               value *new_val;
551               use_operand_p orig_p = PHI_ARG_DEF_PTR (phi, i);
552               tree orig = USE_FROM_PTR (orig_p);
553
554               if (! SSA_VAR_P (orig))
555                 break;
556
557               new_val = get_value (orig);
558               if (new_val->lattice_val == CONSTANT
559                   && may_propagate_copy (orig, new_val->const_val))
560                 SET_USE (orig_p, new_val->const_val);
561             }
562         }
563
564       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
565         {
566           bool replaced_address;
567           tree stmt = bsi_stmt (i);
568
569           /* Skip statements that have been folded already.  */
570           if (stmt_modified_p (stmt) || !is_exec_stmt (stmt))
571             continue;
572
573           /* Replace the statement with its folded version and mark it
574              folded.  */
575           if (dump_file && (dump_flags & TDF_DETAILS))
576             {
577               fprintf (dump_file, "Line %d: replaced ", get_lineno (stmt));
578               print_generic_stmt (dump_file, stmt, TDF_SLIM);
579             }
580
581           if (replace_uses_in (stmt, &replaced_address)
582               || replace_vuse_in (stmt, &replaced_address))
583             {
584               bool changed = fold_stmt (bsi_stmt_ptr (i));
585               stmt = bsi_stmt(i);
586               /* If we folded a builtin function, we'll likely
587                  need to rename VDEFs.  */
588               if (replaced_address || changed)
589                 {
590                   mark_new_vars_to_rename (stmt, vars_to_rename);
591                   if (maybe_clean_eh_stmt (stmt))
592                     tree_purge_dead_eh_edges (bb);
593                 }
594               else
595                 modify_stmt (stmt);
596             }
597
598           if (dump_file && (dump_flags & TDF_DETAILS))
599             {
600               fprintf (dump_file, " with ");
601               print_generic_stmt (dump_file, stmt, TDF_SLIM);
602               fprintf (dump_file, "\n");
603             }
604         }
605     }
606 }
607
608
609 /* Free allocated storage.  */
610
611 static void
612 ccp_finalize (void)
613 {
614   /* Perform substitutions based on the known constant values.  */
615   substitute_and_fold ();
616
617   /* Now cleanup any unreachable code.  */
618   cleanup_tree_cfg ();
619
620   free (value_vector);
621 }
622
623
624
625 /* Compute the meet operator between VAL1 and VAL2:
626
627                 any  M UNDEFINED     = any
628                 any  M VARYING       = VARYING
629                 any  M UNKNOWN_VAL   = UNKNOWN_VAL
630                 Ci   M Cj            = Ci       if (i == j)
631                 Ci   M Cj            = VARYING  if (i != j)  */
632 static value
633 ccp_lattice_meet (value val1, value val2)
634 {
635   value result;
636
637   /* any M UNDEFINED = any.  */
638   if (val1.lattice_val == UNDEFINED)
639     return val2;
640   else if (val2.lattice_val == UNDEFINED)
641     return val1;
642
643   /* any M VARYING = VARYING.  */
644   if (val1.lattice_val == VARYING || val2.lattice_val == VARYING)
645     {
646       result.lattice_val = VARYING;
647       result.const_val = NULL_TREE;
648       return result;
649     }
650
651   /* any M UNKNOWN_VAL = UNKNOWN_VAL.  */
652   if (val1.lattice_val == UNKNOWN_VAL 
653       || val2.lattice_val == UNKNOWN_VAL)
654     {
655       result.lattice_val = UNKNOWN_VAL;
656       result.const_val = NULL_TREE;
657       return result;
658     }
659
660   /* Ci M Cj = Ci       if (i == j)
661      Ci M Cj = VARYING  if (i != j)  */
662   if (simple_cst_equal (val1.const_val, val2.const_val) == 1)
663     {
664       result.lattice_val = CONSTANT;
665       result.const_val = val1.const_val;
666     }
667   else
668     {
669       result.lattice_val = VARYING;
670       result.const_val = NULL_TREE;
671     }
672
673   return result;
674 }
675
676
677 /* Loop through the PHI_NODE's parameters for BLOCK and compare their
678    lattice values to determine PHI_NODE's lattice value.  The value of a
679    PHI node is determined calling ccp_lattice_meet() with all the arguments
680    of the PHI node that are incoming via executable edges.  */
681
682 static enum ssa_prop_result
683 ccp_visit_phi_node (tree phi)
684 {
685   value new_val, *old_val;
686   int i;
687
688   if (dump_file && (dump_flags & TDF_DETAILS))
689     {
690       fprintf (dump_file, "\nVisiting PHI node: ");
691       print_generic_expr (dump_file, phi, dump_flags);
692     }
693
694   old_val = get_value (PHI_RESULT (phi));
695   switch (old_val->lattice_val)
696     {
697     case VARYING:
698       return SSA_PROP_NOT_INTERESTING;
699
700     case CONSTANT:
701       new_val = *old_val;
702       break;
703
704     case UNKNOWN_VAL:
705       /* To avoid the default value of UNKNOWN_VAL overriding
706          that of its possible constant arguments, temporarily
707          set the PHI node's default lattice value to be 
708          UNDEFINED.  If the PHI node's old value was UNKNOWN_VAL and
709          the new value is UNDEFINED, then we prevent the invalid
710          transition by not calling set_lattice_value.  */
711       new_val.lattice_val = UNDEFINED;
712       new_val.const_val = NULL_TREE;
713       break;
714
715     case UNDEFINED:
716     case UNINITIALIZED:
717       new_val.lattice_val = UNDEFINED;
718       new_val.const_val = NULL_TREE;
719       break;
720
721     default:
722       abort ();
723     }
724
725   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
726     {
727       /* Compute the meet operator over all the PHI arguments.  */
728       edge e = PHI_ARG_EDGE (phi, i);
729
730       if (dump_file && (dump_flags & TDF_DETAILS))
731         {
732           fprintf (dump_file,
733               "\n    Argument #%d (%d -> %d %sexecutable)\n",
734               i, e->src->index, e->dest->index,
735               (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
736         }
737
738       /* If the incoming edge is executable, Compute the meet operator for
739          the existing value of the PHI node and the current PHI argument.  */
740       if (e->flags & EDGE_EXECUTABLE)
741         {
742           tree rdef = PHI_ARG_DEF (phi, i);
743           value *rdef_val, val;
744
745           if (is_gimple_min_invariant (rdef))
746             {
747               val.lattice_val = CONSTANT;
748               val.const_val = rdef;
749               rdef_val = &val;
750             }
751           else
752             rdef_val = get_value (rdef);
753
754           new_val = ccp_lattice_meet (new_val, *rdef_val);
755
756           if (dump_file && (dump_flags & TDF_DETAILS))
757             {
758               fprintf (dump_file, "\t");
759               print_generic_expr (dump_file, rdef, dump_flags);
760               dump_lattice_value (dump_file, "\tValue: ", *rdef_val);
761               fprintf (dump_file, "\n");
762             }
763
764           if (new_val.lattice_val == VARYING)
765             break;
766         }
767     }
768
769   if (dump_file && (dump_flags & TDF_DETAILS))
770     {
771       dump_lattice_value (dump_file, "\n    PHI node value: ", new_val);
772       fprintf (dump_file, "\n\n");
773     }
774
775   /* Check for an invalid change from UNKNOWN_VAL to UNDEFINED.  */
776   if (old_val->lattice_val == UNKNOWN_VAL
777       && new_val.lattice_val == UNDEFINED)
778     return SSA_PROP_NOT_INTERESTING;
779
780   /* Otherwise, make the transition to the new value.  */
781   if (set_lattice_value (PHI_RESULT (phi), new_val))
782     {
783       if (new_val.lattice_val == VARYING)
784         return SSA_PROP_VARYING;
785       else
786         return SSA_PROP_INTERESTING;
787     }
788   else
789     return SSA_PROP_NOT_INTERESTING;
790 }
791
792
793 /* CCP specific front-end to the non-destructive constant folding
794    routines.
795
796    Attempt to simplify the RHS of STMT knowing that one or more
797    operands are constants.
798
799    If simplification is possible, return the simplified RHS,
800    otherwise return the original RHS.  */
801
802 static tree
803 ccp_fold (tree stmt)
804 {
805   tree rhs = get_rhs (stmt);
806   enum tree_code code = TREE_CODE (rhs);
807   int kind = TREE_CODE_CLASS (code);
808   tree retval = NULL_TREE;
809   vuse_optype vuses;
810   
811   vuses = STMT_VUSE_OPS (stmt);
812
813   /* If the RHS is just a variable, then that variable must now have
814      a constant value that we can return directly.  */
815   if (TREE_CODE (rhs) == SSA_NAME)
816     return get_value (rhs)->const_val;
817   else if (DECL_P (rhs) 
818            && NUM_VUSES (vuses) == 1
819            && rhs == SSA_NAME_VAR (VUSE_OP (vuses, 0)))
820     return get_value (VUSE_OP (vuses, 0))->const_val;
821
822   /* Unary operators.  Note that we know the single operand must
823      be a constant.  So this should almost always return a
824      simplified RHS.  */
825   if (kind == '1')
826     {
827       /* Handle unary operators which can appear in GIMPLE form.  */
828       tree op0 = TREE_OPERAND (rhs, 0);
829
830       /* Simplify the operand down to a constant.  */
831       if (TREE_CODE (op0) == SSA_NAME)
832         {
833           value *val = get_value (op0);
834           if (val->lattice_val == CONSTANT)
835             op0 = get_value (op0)->const_val;
836         }
837
838       retval = nondestructive_fold_unary_to_constant (code,
839                                                       TREE_TYPE (rhs),
840                                                       op0);
841
842       /* If we folded, but did not create an invariant, then we can not
843          use this expression.  */
844       if (retval && ! is_gimple_min_invariant (retval))
845         return NULL;
846
847       /* If we could not fold the expression, but the arguments are all
848          constants and gimple values, then build and return the new
849          expression. 
850
851          In some cases the new expression is still something we can
852          use as a replacement for an argument.  This happens with
853          NOP conversions of types for example.
854
855          In other cases the new expression can not be used as a
856          replacement for an argument (as it would create non-gimple
857          code).  But the new expression can still be used to derive
858          other constants.  */
859       if (! retval && is_gimple_min_invariant (op0))
860         return build1 (code, TREE_TYPE (rhs), op0);
861     }
862
863   /* Binary and comparison operators.  We know one or both of the
864      operands are constants.  */
865   else if (kind == '2'
866            || kind == '<'
867            || code == TRUTH_AND_EXPR
868            || code == TRUTH_OR_EXPR
869            || code == TRUTH_XOR_EXPR)
870     {
871       /* Handle binary and comparison operators that can appear in
872          GIMPLE form.  */
873       tree op0 = TREE_OPERAND (rhs, 0);
874       tree op1 = TREE_OPERAND (rhs, 1);
875
876       /* Simplify the operands down to constants when appropriate.  */
877       if (TREE_CODE (op0) == SSA_NAME)
878         {
879           value *val = get_value (op0);
880           if (val->lattice_val == CONSTANT)
881             op0 = val->const_val;
882         }
883
884       if (TREE_CODE (op1) == SSA_NAME)
885         {
886           value *val = get_value (op1);
887           if (val->lattice_val == CONSTANT)
888             op1 = val->const_val;
889         }
890
891       retval = nondestructive_fold_binary_to_constant (code,
892                                                        TREE_TYPE (rhs),
893                                                        op0, op1);
894
895       /* If we folded, but did not create an invariant, then we can not
896          use this expression.  */
897       if (retval && ! is_gimple_min_invariant (retval))
898         return NULL;
899       
900       /* If we could not fold the expression, but the arguments are all
901          constants and gimple values, then build and return the new
902          expression. 
903
904          In some cases the new expression is still something we can
905          use as a replacement for an argument.  This happens with
906          NOP conversions of types for example.
907
908          In other cases the new expression can not be used as a
909          replacement for an argument (as it would create non-gimple
910          code).  But the new expression can still be used to derive
911          other constants.  */
912       if (! retval
913           && is_gimple_min_invariant (op0)
914           && is_gimple_min_invariant (op1))
915         return build (code, TREE_TYPE (rhs), op0, op1);
916     }
917
918   /* We may be able to fold away calls to builtin functions if their
919      arguments are constants.  */
920   else if (code == CALL_EXPR
921            && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR
922            && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))
923                == FUNCTION_DECL)
924            && DECL_BUILT_IN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)))
925     {
926       use_optype uses = STMT_USE_OPS (stmt);
927       if (NUM_USES (uses) != 0)
928         {
929           tree *orig;
930           size_t i;
931
932           /* Preserve the original values of every operand.  */
933           orig = xmalloc (sizeof (tree) * NUM_USES (uses));
934           for (i = 0; i < NUM_USES (uses); i++)
935             orig[i] = USE_OP (uses, i);
936
937           /* Substitute operands with their values and try to fold.  */
938           replace_uses_in (stmt, NULL);
939           retval = fold_builtin (rhs, false);
940
941           /* Restore operands to their original form.  */
942           for (i = 0; i < NUM_USES (uses); i++)
943             SET_USE_OP (uses, i, orig[i]);
944           free (orig);
945         }
946     }
947   else
948     return rhs;
949
950   /* If we got a simplified form, see if we need to convert its type.  */
951   if (retval)
952     return fold_convert (TREE_TYPE (rhs), retval);
953
954   /* No simplification was possible.  */
955   return rhs;
956 }
957
958
959 /* Evaluate statement STMT.  */
960
961 static value
962 evaluate_stmt (tree stmt)
963 {
964   value val;
965   tree simplified;
966   latticevalue likelyvalue = likely_value (stmt);
967
968   /* If the statement is likely to have a CONSTANT result, then try
969      to fold the statement to determine the constant value.  */
970   if (likelyvalue == CONSTANT)
971     simplified = ccp_fold (stmt);
972   /* If the statement is likely to have a VARYING result, then do not
973      bother folding the statement.  */
974   else if (likelyvalue == VARYING)
975     simplified = get_rhs (stmt);
976   /* Otherwise the statement is likely to have an UNDEFINED value and
977      there will be nothing to do.  */
978   else
979     simplified = NULL_TREE;
980
981   if (simplified && is_gimple_min_invariant (simplified))
982     {
983       /* The statement produced a constant value.  */
984       val.lattice_val = CONSTANT;
985       val.const_val = simplified;
986     }
987   else
988     {
989       /* The statement produced a nonconstant value.  If the statement
990          had undefined or virtual operands, then the result of the 
991          statement should be undefined or virtual respectively.  
992          Else the result of the statement is VARYING.  */
993       val.lattice_val = (likelyvalue == UNDEFINED ? UNDEFINED : VARYING);
994       val.lattice_val = (likelyvalue == UNKNOWN_VAL 
995                            ? UNKNOWN_VAL : val.lattice_val);
996       val.const_val = NULL_TREE;
997     }
998
999   return val;
1000 }
1001
1002
1003 /* Visit the assignment statement STMT.  Set the value of its LHS to the
1004    value computed by the RHS and store LHS in *OUTPUT_P.  */
1005
1006 static enum ssa_prop_result
1007 visit_assignment (tree stmt, tree *output_p)
1008 {
1009   value val;
1010   tree lhs, rhs;
1011   vuse_optype vuses;
1012   v_must_def_optype v_must_defs;
1013
1014   lhs = TREE_OPERAND (stmt, 0);
1015   rhs = TREE_OPERAND (stmt, 1);
1016   vuses = STMT_VUSE_OPS (stmt);
1017   v_must_defs = STMT_V_MUST_DEF_OPS (stmt);
1018
1019 #if defined ENABLE_CHECKING
1020   if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0
1021       || (NUM_V_MUST_DEFS (v_must_defs) != 1
1022           && TREE_CODE (lhs) != SSA_NAME))
1023     abort ();
1024 #endif
1025
1026   /* We require the SSA version number of the lhs for the value_vector.
1027      Make sure we have it.  */
1028   if (TREE_CODE (lhs) != SSA_NAME)
1029     {
1030       /* If we make it here, then stmt only has one definition:
1031          a V_MUST_DEF.  */
1032       lhs = V_MUST_DEF_OP (v_must_defs, 0);
1033     }
1034
1035   if (TREE_CODE (rhs) == SSA_NAME)
1036     {
1037       /* For a simple copy operation, we copy the lattice values.  */
1038       value *nval = get_value (rhs);
1039       val = *nval;
1040     }
1041   else if (DECL_P (rhs) 
1042            && NUM_VUSES (vuses) == 1
1043            && rhs == SSA_NAME_VAR (VUSE_OP (vuses, 0)))
1044     {
1045       /* Same as above, but the rhs is not a gimple register and yet
1046         has a known VUSE.  */
1047       value *nval = get_value (VUSE_OP (vuses, 0));
1048       val = *nval;
1049     }
1050   else
1051     {
1052       /* Evaluate the statement.  */
1053       val = evaluate_stmt (stmt);
1054     }
1055
1056   /* FIXME: Hack.  If this was a definition of a bitfield, we need to widen
1057      the constant value into the type of the destination variable.  This
1058      should not be necessary if GCC represented bitfields properly.  */
1059   {
1060     tree lhs = TREE_OPERAND (stmt, 0);
1061     if (val.lattice_val == CONSTANT
1062         && TREE_CODE (lhs) == COMPONENT_REF
1063         && DECL_BIT_FIELD (TREE_OPERAND (lhs, 1)))
1064       {
1065         tree w = widen_bitfield (val.const_val, TREE_OPERAND (lhs, 1), lhs);
1066
1067         if (w && is_gimple_min_invariant (w))
1068           val.const_val = w;
1069         else
1070           {
1071             val.lattice_val = VARYING;
1072             val.const_val = NULL;
1073           }
1074       }
1075   }
1076
1077   /* If LHS is not a gimple register, then it cannot take on an
1078      UNDEFINED value.  */
1079   if (!is_gimple_reg (SSA_NAME_VAR (lhs)) 
1080       && val.lattice_val == UNDEFINED)
1081     val.lattice_val = UNKNOWN_VAL;      
1082
1083   /* Set the lattice value of the statement's output.  */
1084   if (set_lattice_value (lhs, val))
1085     {
1086       *output_p = lhs;
1087       if (val.lattice_val == VARYING)
1088         return SSA_PROP_VARYING;
1089       else
1090         return SSA_PROP_INTERESTING;
1091     }
1092   else
1093     return SSA_PROP_NOT_INTERESTING;
1094 }
1095
1096
1097 /* Visit the conditional statement STMT.  Return SSA_PROP_INTERESTING
1098    if it can determine which edge will be taken.  Otherwise, return
1099    SSA_PROP_VARYING.  */
1100
1101 static enum ssa_prop_result
1102 visit_cond_stmt (tree stmt, edge *taken_edge_p)
1103 {
1104   value val;
1105   basic_block block;
1106
1107   block = bb_for_stmt (stmt);
1108   val = evaluate_stmt (stmt);
1109
1110   /* Find which edge out of the conditional block will be taken and add it
1111      to the worklist.  If no single edge can be determined statically,
1112      return SSA_PROP_VARYING to feed all the outgoing edges to the
1113      propagation engine.  */
1114   *taken_edge_p = find_taken_edge (block, val.const_val);
1115   if (*taken_edge_p)
1116     return SSA_PROP_INTERESTING;
1117   else
1118     return SSA_PROP_VARYING;
1119 }
1120
1121
1122 /* Evaluate statement STMT.  If the statement produces an output value and
1123    its evaluation changes the lattice value of its output, return
1124    SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the
1125    output value.
1126    
1127    If STMT is a conditional branch and we can determine its truth
1128    value, set *TAKEN_EDGE_P accordingly.  If STMT produces a varying
1129    value, return SSA_PROP_VARYING.  */
1130
1131 static enum ssa_prop_result
1132 ccp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
1133 {
1134   stmt_ann_t ann;
1135   v_may_def_optype v_may_defs;
1136   v_must_def_optype v_must_defs;
1137   tree def;
1138   ssa_op_iter iter;
1139
1140   if (dump_file && (dump_flags & TDF_DETAILS))
1141     {
1142       fprintf (dump_file, "\nVisiting statement: ");
1143       print_generic_stmt (dump_file, stmt, TDF_SLIM);
1144       fprintf (dump_file, "\n");
1145     }
1146
1147   ann = stmt_ann (stmt);
1148
1149   v_must_defs = V_MUST_DEF_OPS (ann);
1150   v_may_defs = V_MAY_DEF_OPS (ann);
1151   if (TREE_CODE (stmt) == MODIFY_EXPR
1152       && NUM_V_MAY_DEFS (v_may_defs) == 0
1153       && (NUM_V_MUST_DEFS (v_must_defs) == 1
1154           || TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME))
1155     {
1156       /* If the statement is an assignment that produces a single
1157          output value, evaluate its RHS to see if the lattice value of
1158          its output has changed.  */
1159       return visit_assignment (stmt, output_p);
1160     }
1161   else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
1162     {
1163       /* If STMT is a conditional branch, see if we can determine
1164          which branch will be taken.  */
1165       return visit_cond_stmt (stmt, taken_edge_p);
1166     }
1167
1168   /* Any other kind of statement is not interesting for constant
1169      propagation and, therefore, not worth simulating.  */
1170   if (dump_file && (dump_flags & TDF_DETAILS))
1171     fprintf (dump_file, "No interesting values produced.  Marked VARYING.\n");
1172
1173   /* Definitions made by statements other than assignments to
1174      SSA_NAMEs represent unknown modifications to their outputs.
1175      Mark them VARYING.  */
1176   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1177     def_to_varying (def);
1178
1179   /* Mark all V_MAY_DEF operands VARYING.  */
1180   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_VMAYDEF)
1181     def_to_varying (def);
1182
1183   return SSA_PROP_VARYING;
1184 }
1185
1186
1187 /* Main entry point for SSA Conditional Constant Propagation.
1188
1189    [ DESCRIBE MAIN ALGORITHM HERE ]  */
1190
1191 static void
1192 execute_ssa_ccp (void)
1193 {
1194   ccp_initialize ();
1195   ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node);
1196   ccp_finalize ();
1197 }
1198
1199
1200 static bool
1201 gate_ccp (void)
1202 {
1203   return flag_tree_ccp != 0;
1204 }
1205
1206
1207 struct tree_opt_pass pass_ccp = 
1208 {
1209   "ccp",                                /* name */
1210   gate_ccp,                             /* gate */
1211   execute_ssa_ccp,                      /* execute */
1212   NULL,                                 /* sub */
1213   NULL,                                 /* next */
1214   0,                                    /* static_pass_number */
1215   TV_TREE_CCP,                          /* tv_id */
1216   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1217   0,                                    /* properties_provided */
1218   0,                                    /* properties_destroyed */
1219   0,                                    /* todo_flags_start */
1220   TODO_dump_func | TODO_rename_vars
1221     | TODO_ggc_collect | TODO_verify_ssa
1222     | TODO_verify_stmts,                /* todo_flags_finish */
1223   0                                     /* letter */
1224 };
1225
1226
1227 /* Given a constant value VAL for bitfield FIELD, and a destination
1228    variable VAR, return VAL appropriately widened to fit into VAR.  If
1229    FIELD is wider than HOST_WIDE_INT, NULL is returned.  */
1230
1231 tree
1232 widen_bitfield (tree val, tree field, tree var)
1233 {
1234   unsigned HOST_WIDE_INT var_size, field_size;
1235   tree wide_val;
1236   unsigned HOST_WIDE_INT mask;
1237   unsigned int i;
1238
1239   /* We can only do this if the size of the type and field and VAL are
1240      all constants representable in HOST_WIDE_INT.  */
1241   if (!host_integerp (TYPE_SIZE (TREE_TYPE (var)), 1)
1242       || !host_integerp (DECL_SIZE (field), 1)
1243       || !host_integerp (val, 0))
1244     return NULL_TREE;
1245
1246   var_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (var)), 1);
1247   field_size = tree_low_cst (DECL_SIZE (field), 1);
1248
1249   /* Give up if either the bitfield or the variable are too wide.  */
1250   if (field_size > HOST_BITS_PER_WIDE_INT || var_size > HOST_BITS_PER_WIDE_INT)
1251     return NULL_TREE;
1252
1253 #if defined ENABLE_CHECKING
1254   if (var_size < field_size)
1255     abort ();
1256 #endif
1257
1258   /* If the sign bit of the value is not set or the field's type is unsigned,
1259      just mask off the high order bits of the value.  */
1260   if (DECL_UNSIGNED (field)
1261       || !(tree_low_cst (val, 0) & (((HOST_WIDE_INT)1) << (field_size - 1))))
1262     {
1263       /* Zero extension.  Build a mask with the lower 'field_size' bits
1264          set and a BIT_AND_EXPR node to clear the high order bits of
1265          the value.  */
1266       for (i = 0, mask = 0; i < field_size; i++)
1267         mask |= ((HOST_WIDE_INT) 1) << i;
1268
1269       wide_val = build (BIT_AND_EXPR, TREE_TYPE (var), val, 
1270                         fold_convert (TREE_TYPE (var),
1271                                       build_int_cst (NULL_TREE, mask)));
1272     }
1273   else
1274     {
1275       /* Sign extension.  Create a mask with the upper 'field_size'
1276          bits set and a BIT_IOR_EXPR to set the high order bits of the
1277          value.  */
1278       for (i = 0, mask = 0; i < (var_size - field_size); i++)
1279         mask |= ((HOST_WIDE_INT) 1) << (var_size - i - 1);
1280
1281       wide_val = build (BIT_IOR_EXPR, TREE_TYPE (var), val,
1282                         fold_convert (TREE_TYPE (var),
1283                                       build_int_cst (NULL_TREE, mask)));
1284     }
1285
1286   return fold (wide_val);
1287 }
1288
1289
1290 /* A subroutine of fold_stmt_r.  Attempts to fold *(A+O) to A[X].
1291    BASE is an array type.  OFFSET is a byte displacement.  ORIG_TYPE
1292    is the desired result type.  */
1293
1294 static tree
1295 maybe_fold_offset_to_array_ref (tree base, tree offset, tree orig_type)
1296 {
1297   tree min_idx, idx, elt_offset = integer_zero_node;
1298   tree array_type, elt_type, elt_size;
1299
1300   /* If BASE is an ARRAY_REF, we can pick up another offset (this time
1301      measured in units of the size of elements type) from that ARRAY_REF).
1302      We can't do anything if either is variable.
1303
1304      The case we handle here is *(&A[N]+O).  */
1305   if (TREE_CODE (base) == ARRAY_REF)
1306     {
1307       tree low_bound = array_ref_low_bound (base);
1308
1309       elt_offset = TREE_OPERAND (base, 1);
1310       if (TREE_CODE (low_bound) != INTEGER_CST
1311           || TREE_CODE (elt_offset) != INTEGER_CST)
1312         return NULL_TREE;
1313
1314       elt_offset = int_const_binop (MINUS_EXPR, elt_offset, low_bound, 0);
1315       base = TREE_OPERAND (base, 0);
1316     }
1317
1318   /* Ignore stupid user tricks of indexing non-array variables.  */
1319   array_type = TREE_TYPE (base);
1320   if (TREE_CODE (array_type) != ARRAY_TYPE)
1321     return NULL_TREE;
1322   elt_type = TREE_TYPE (array_type);
1323   if (!lang_hooks.types_compatible_p (orig_type, elt_type))
1324     return NULL_TREE;
1325         
1326   /* If OFFSET and ELT_OFFSET are zero, we don't care about the size of the
1327      element type (so we can use the alignment if it's not constant).
1328      Otherwise, compute the offset as an index by using a division.  If the
1329      division isn't exact, then don't do anything.  */
1330   elt_size = TYPE_SIZE_UNIT (elt_type);
1331   if (integer_zerop (offset))
1332     {
1333       if (TREE_CODE (elt_size) != INTEGER_CST)
1334         elt_size = size_int (TYPE_ALIGN (elt_type));
1335
1336       idx = integer_zero_node;
1337     }
1338   else
1339     {
1340       unsigned HOST_WIDE_INT lquo, lrem;
1341       HOST_WIDE_INT hquo, hrem;
1342
1343       if (TREE_CODE (elt_size) != INTEGER_CST
1344           || div_and_round_double (TRUNC_DIV_EXPR, 1,
1345                                    TREE_INT_CST_LOW (offset),
1346                                    TREE_INT_CST_HIGH (offset),
1347                                    TREE_INT_CST_LOW (elt_size),
1348                                    TREE_INT_CST_HIGH (elt_size),
1349                                    &lquo, &hquo, &lrem, &hrem)
1350           || lrem || hrem)
1351         return NULL_TREE;
1352
1353       idx = build_int_cst_wide (NULL_TREE, lquo, hquo);
1354     }
1355
1356   /* Assume the low bound is zero.  If there is a domain type, get the
1357      low bound, if any, convert the index into that type, and add the
1358      low bound.  */
1359   min_idx = integer_zero_node;
1360   if (TYPE_DOMAIN (array_type))
1361     {
1362       if (TYPE_MIN_VALUE (TYPE_DOMAIN (array_type)))
1363         min_idx = TYPE_MIN_VALUE (TYPE_DOMAIN (array_type));
1364       else
1365         min_idx = fold_convert (TYPE_DOMAIN (array_type), min_idx);
1366
1367       if (TREE_CODE (min_idx) != INTEGER_CST)
1368         return NULL_TREE;
1369
1370       idx = fold_convert (TYPE_DOMAIN (array_type), idx);
1371       elt_offset = fold_convert (TYPE_DOMAIN (array_type), elt_offset);
1372     }
1373
1374   if (!integer_zerop (min_idx))
1375     idx = int_const_binop (PLUS_EXPR, idx, min_idx, 0);
1376   if (!integer_zerop (elt_offset))
1377     idx = int_const_binop (PLUS_EXPR, idx, elt_offset, 0);
1378
1379   return build (ARRAY_REF, orig_type, base, idx, min_idx,
1380                 size_int (tree_low_cst (elt_size, 1)
1381                           / (TYPE_ALIGN_UNIT (elt_type))));
1382 }
1383
1384
1385 /* A subroutine of fold_stmt_r.  Attempts to fold *(S+O) to S.X.
1386    BASE is a record type.  OFFSET is a byte displacement.  ORIG_TYPE
1387    is the desired result type.  */
1388 /* ??? This doesn't handle class inheritance.  */
1389
1390 static tree
1391 maybe_fold_offset_to_component_ref (tree record_type, tree base, tree offset,
1392                                     tree orig_type, bool base_is_ptr)
1393 {
1394   tree f, t, field_type, tail_array_field;
1395
1396   if (TREE_CODE (record_type) != RECORD_TYPE
1397       && TREE_CODE (record_type) != UNION_TYPE
1398       && TREE_CODE (record_type) != QUAL_UNION_TYPE)
1399     return NULL_TREE;
1400
1401   /* Short-circuit silly cases.  */
1402   if (lang_hooks.types_compatible_p (record_type, orig_type))
1403     return NULL_TREE;
1404
1405   tail_array_field = NULL_TREE;
1406   for (f = TYPE_FIELDS (record_type); f ; f = TREE_CHAIN (f))
1407     {
1408       int cmp;
1409
1410       if (TREE_CODE (f) != FIELD_DECL)
1411         continue;
1412       if (DECL_BIT_FIELD (f))
1413         continue;
1414       if (TREE_CODE (DECL_FIELD_OFFSET (f)) != INTEGER_CST)
1415         continue;
1416
1417       /* ??? Java creates "interesting" fields for representing base classes.
1418          They have no name, and have no context.  With no context, we get into
1419          trouble with nonoverlapping_component_refs_p.  Skip them.  */
1420       if (!DECL_FIELD_CONTEXT (f))
1421         continue;
1422
1423       /* The previous array field isn't at the end.  */
1424       tail_array_field = NULL_TREE;
1425
1426       /* Check to see if this offset overlaps with the field.  */
1427       cmp = tree_int_cst_compare (DECL_FIELD_OFFSET (f), offset);
1428       if (cmp > 0)
1429         continue;
1430
1431       field_type = TREE_TYPE (f);
1432       if (cmp < 0)
1433         {
1434           /* Don't care about offsets into the middle of scalars.  */
1435           if (!AGGREGATE_TYPE_P (field_type))
1436             continue;
1437
1438           /* Check for array at the end of the struct.  This is often
1439              used as for flexible array members.  We should be able to
1440              turn this into an array access anyway.  */
1441           if (TREE_CODE (field_type) == ARRAY_TYPE)
1442             tail_array_field = f;
1443
1444           /* Check the end of the field against the offset.  */
1445           if (!DECL_SIZE_UNIT (f)
1446               || TREE_CODE (DECL_SIZE_UNIT (f)) != INTEGER_CST)
1447             continue;
1448           t = int_const_binop (MINUS_EXPR, offset, DECL_FIELD_OFFSET (f), 1);
1449           if (!tree_int_cst_lt (t, DECL_SIZE_UNIT (f)))
1450             continue;
1451
1452           /* If we matched, then set offset to the displacement into
1453              this field.  */
1454           offset = t;
1455         }
1456
1457       /* Here we exactly match the offset being checked.  If the types match,
1458          then we can return that field.  */
1459       else if (lang_hooks.types_compatible_p (orig_type, field_type))
1460         {
1461           if (base_is_ptr)
1462             base = build1 (INDIRECT_REF, record_type, base);
1463           t = build (COMPONENT_REF, field_type, base, f, NULL_TREE);
1464           return t;
1465         }
1466
1467       /* Don't care about type-punning of scalars.  */
1468       else if (!AGGREGATE_TYPE_P (field_type))
1469         return NULL_TREE;
1470
1471       goto found;
1472     }
1473
1474   if (!tail_array_field)
1475     return NULL_TREE;
1476
1477   f = tail_array_field;
1478   field_type = TREE_TYPE (f);
1479
1480  found:
1481   /* If we get here, we've got an aggregate field, and a possibly 
1482      nonzero offset into them.  Recurse and hope for a valid match.  */
1483   if (base_is_ptr)
1484     base = build1 (INDIRECT_REF, record_type, base);
1485   base = build (COMPONENT_REF, field_type, base, f, NULL_TREE);
1486
1487   t = maybe_fold_offset_to_array_ref (base, offset, orig_type);
1488   if (t)
1489     return t;
1490   return maybe_fold_offset_to_component_ref (field_type, base, offset,
1491                                              orig_type, false);
1492 }
1493
1494
1495 /* A subroutine of fold_stmt_r.  Attempt to simplify *(BASE+OFFSET).
1496    Return the simplified expression, or NULL if nothing could be done.  */
1497
1498 static tree
1499 maybe_fold_stmt_indirect (tree expr, tree base, tree offset)
1500 {
1501   tree t;
1502
1503   /* We may well have constructed a double-nested PLUS_EXPR via multiple
1504      substitutions.  Fold that down to one.  Remove NON_LVALUE_EXPRs that
1505      are sometimes added.  */
1506   base = fold (base);
1507   STRIP_NOPS (base);
1508   TREE_OPERAND (expr, 0) = base;
1509
1510   /* One possibility is that the address reduces to a string constant.  */
1511   t = fold_read_from_constant_string (expr);
1512   if (t)
1513     return t;
1514
1515   /* Add in any offset from a PLUS_EXPR.  */
1516   if (TREE_CODE (base) == PLUS_EXPR)
1517     {
1518       tree offset2;
1519
1520       offset2 = TREE_OPERAND (base, 1);
1521       if (TREE_CODE (offset2) != INTEGER_CST)
1522         return NULL_TREE;
1523       base = TREE_OPERAND (base, 0);
1524
1525       offset = int_const_binop (PLUS_EXPR, offset, offset2, 1);
1526     }
1527
1528   if (TREE_CODE (base) == ADDR_EXPR)
1529     {
1530       /* Strip the ADDR_EXPR.  */
1531       base = TREE_OPERAND (base, 0);
1532
1533       /* Fold away CONST_DECL to its value, if the type is scalar.  */
1534       if (TREE_CODE (base) == CONST_DECL
1535           && is_gimple_min_invariant (DECL_INITIAL (base)))
1536         return DECL_INITIAL (base);
1537
1538       /* Try folding *(&B+O) to B[X].  */
1539       t = maybe_fold_offset_to_array_ref (base, offset, TREE_TYPE (expr));
1540       if (t)
1541         return t;
1542
1543       /* Try folding *(&B+O) to B.X.  */
1544       t = maybe_fold_offset_to_component_ref (TREE_TYPE (base), base, offset,
1545                                               TREE_TYPE (expr), false);
1546       if (t)
1547         return t;
1548
1549       /* Fold *&B to B.  We can only do this if EXPR is the same type
1550          as BASE.  We can't do this if EXPR is the element type of an array
1551          and BASE is the array.  */
1552       if (integer_zerop (offset)
1553           && lang_hooks.types_compatible_p (TREE_TYPE (base),
1554                                             TREE_TYPE (expr)))
1555         return base;
1556     }
1557   else
1558     {
1559       /* We can get here for out-of-range string constant accesses, 
1560          such as "_"[3].  Bail out of the entire substitution search
1561          and arrange for the entire statement to be replaced by a
1562          call to __builtin_trap.  In all likelyhood this will all be
1563          constant-folded away, but in the meantime we can't leave with
1564          something that get_expr_operands can't understand.  */
1565
1566       t = base;
1567       STRIP_NOPS (t);
1568       if (TREE_CODE (t) == ADDR_EXPR
1569           && TREE_CODE (TREE_OPERAND (t, 0)) == STRING_CST)
1570         {
1571           /* FIXME: Except that this causes problems elsewhere with dead
1572              code not being deleted, and we abort in the rtl expanders 
1573              because we failed to remove some ssa_name.  In the meantime,
1574              just return zero.  */
1575           /* FIXME2: This condition should be signaled by
1576              fold_read_from_constant_string directly, rather than 
1577              re-checking for it here.  */
1578           return integer_zero_node;
1579         }
1580
1581       /* Try folding *(B+O) to B->X.  Still an improvement.  */
1582       if (POINTER_TYPE_P (TREE_TYPE (base)))
1583         {
1584           t = maybe_fold_offset_to_component_ref (TREE_TYPE (TREE_TYPE (base)),
1585                                                   base, offset,
1586                                                   TREE_TYPE (expr), true);
1587           if (t)
1588             return t;
1589         }
1590     }
1591
1592   /* Otherwise we had an offset that we could not simplify.  */
1593   return NULL_TREE;
1594 }
1595
1596
1597 /* A subroutine of fold_stmt_r.  EXPR is a PLUS_EXPR.
1598
1599    A quaint feature extant in our address arithmetic is that there
1600    can be hidden type changes here.  The type of the result need
1601    not be the same as the type of the input pointer.
1602
1603    What we're after here is an expression of the form
1604         (T *)(&array + const)
1605    where the cast doesn't actually exist, but is implicit in the
1606    type of the PLUS_EXPR.  We'd like to turn this into
1607         &array[x]
1608    which may be able to propagate further.  */
1609
1610 static tree
1611 maybe_fold_stmt_addition (tree expr)
1612 {
1613   tree op0 = TREE_OPERAND (expr, 0);
1614   tree op1 = TREE_OPERAND (expr, 1);
1615   tree ptr_type = TREE_TYPE (expr);
1616   tree ptd_type;
1617   tree t;
1618   bool subtract = (TREE_CODE (expr) == MINUS_EXPR);
1619
1620   /* We're only interested in pointer arithmetic.  */
1621   if (!POINTER_TYPE_P (ptr_type))
1622     return NULL_TREE;
1623   /* Canonicalize the integral operand to op1.  */
1624   if (INTEGRAL_TYPE_P (TREE_TYPE (op0)))
1625     {
1626       if (subtract)
1627         return NULL_TREE;
1628       t = op0, op0 = op1, op1 = t;
1629     }
1630   /* It had better be a constant.  */
1631   if (TREE_CODE (op1) != INTEGER_CST)
1632     return NULL_TREE;
1633   /* The first operand should be an ADDR_EXPR.  */
1634   if (TREE_CODE (op0) != ADDR_EXPR)
1635     return NULL_TREE;
1636   op0 = TREE_OPERAND (op0, 0);
1637
1638   /* If the first operand is an ARRAY_REF, expand it so that we can fold
1639      the offset into it.  */
1640   while (TREE_CODE (op0) == ARRAY_REF)
1641     {
1642       tree array_obj = TREE_OPERAND (op0, 0);
1643       tree array_idx = TREE_OPERAND (op0, 1);
1644       tree elt_type = TREE_TYPE (op0);
1645       tree elt_size = TYPE_SIZE_UNIT (elt_type);
1646       tree min_idx;
1647
1648       if (TREE_CODE (array_idx) != INTEGER_CST)
1649         break;
1650       if (TREE_CODE (elt_size) != INTEGER_CST)
1651         break;
1652
1653       /* Un-bias the index by the min index of the array type.  */
1654       min_idx = TYPE_DOMAIN (TREE_TYPE (array_obj));
1655       if (min_idx)
1656         {
1657           min_idx = TYPE_MIN_VALUE (min_idx);
1658           if (min_idx)
1659             {
1660               if (TREE_CODE (min_idx) != INTEGER_CST)
1661                 break;
1662
1663               array_idx = convert (TREE_TYPE (min_idx), array_idx);
1664               if (!integer_zerop (min_idx))
1665                 array_idx = int_const_binop (MINUS_EXPR, array_idx,
1666                                              min_idx, 0);
1667             }
1668         }
1669
1670       /* Convert the index to a byte offset.  */
1671       array_idx = convert (sizetype, array_idx);
1672       array_idx = int_const_binop (MULT_EXPR, array_idx, elt_size, 0);
1673
1674       /* Update the operands for the next round, or for folding.  */
1675       /* If we're manipulating unsigned types, then folding into negative
1676          values can produce incorrect results.  Particularly if the type
1677          is smaller than the width of the pointer.  */
1678       if (subtract
1679           && TYPE_UNSIGNED (TREE_TYPE (op1))
1680           && tree_int_cst_lt (array_idx, op1))
1681         return NULL;
1682       op1 = int_const_binop (subtract ? MINUS_EXPR : PLUS_EXPR,
1683                              array_idx, op1, 0);
1684       subtract = false;
1685       op0 = array_obj;
1686     }
1687
1688   /* If we weren't able to fold the subtraction into another array reference,
1689      canonicalize the integer for passing to the array and component ref
1690      simplification functions.  */
1691   if (subtract)
1692     {
1693       if (TYPE_UNSIGNED (TREE_TYPE (op1)))
1694         return NULL;
1695       op1 = fold (build1 (NEGATE_EXPR, TREE_TYPE (op1), op1));
1696       /* ??? In theory fold should always produce another integer.  */
1697       if (TREE_CODE (op1) != INTEGER_CST)
1698         return NULL;
1699     }
1700
1701   ptd_type = TREE_TYPE (ptr_type);
1702
1703   /* At which point we can try some of the same things as for indirects.  */
1704   t = maybe_fold_offset_to_array_ref (op0, op1, ptd_type);
1705   if (!t)
1706     t = maybe_fold_offset_to_component_ref (TREE_TYPE (op0), op0, op1,
1707                                             ptd_type, false);
1708   if (t)
1709     t = build1 (ADDR_EXPR, ptr_type, t);
1710
1711   return t;
1712 }
1713
1714
1715 /* Subroutine of fold_stmt called via walk_tree.  We perform several
1716    simplifications of EXPR_P, mostly having to do with pointer arithmetic.  */
1717
1718 static tree
1719 fold_stmt_r (tree *expr_p, int *walk_subtrees, void *data)
1720 {
1721   bool *changed_p = data;
1722   tree expr = *expr_p, t;
1723
1724   /* ??? It'd be nice if walk_tree had a pre-order option.  */
1725   switch (TREE_CODE (expr))
1726     {
1727     case INDIRECT_REF:
1728       t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
1729       if (t)
1730         return t;
1731       *walk_subtrees = 0;
1732
1733       t = maybe_fold_stmt_indirect (expr, TREE_OPERAND (expr, 0),
1734                                     integer_zero_node);
1735       break;
1736
1737       /* ??? Could handle ARRAY_REF here, as a variant of INDIRECT_REF.
1738          We'd only want to bother decomposing an existing ARRAY_REF if
1739          the base array is found to have another offset contained within.
1740          Otherwise we'd be wasting time.  */
1741
1742     case ADDR_EXPR:
1743       t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
1744       if (t)
1745         return t;
1746       *walk_subtrees = 0;
1747
1748       /* Set TREE_INVARIANT properly so that the value is properly
1749          considered constant, and so gets propagated as expected.  */
1750       if (*changed_p)
1751         recompute_tree_invarant_for_addr_expr (expr);
1752       return NULL_TREE;
1753
1754     case PLUS_EXPR:
1755     case MINUS_EXPR:
1756       t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
1757       if (t)
1758         return t;
1759       t = walk_tree (&TREE_OPERAND (expr, 1), fold_stmt_r, data, NULL);
1760       if (t)
1761         return t;
1762       *walk_subtrees = 0;
1763
1764       t = maybe_fold_stmt_addition (expr);
1765       break;
1766
1767     case COMPONENT_REF:
1768       t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
1769       if (t)
1770         return t;
1771       *walk_subtrees = 0;
1772
1773       /* Make sure the FIELD_DECL is actually a field in the type on the lhs.
1774          We've already checked that the records are compatible, so we should
1775          come up with a set of compatible fields.  */
1776       {
1777         tree expr_record = TREE_TYPE (TREE_OPERAND (expr, 0));
1778         tree expr_field = TREE_OPERAND (expr, 1);
1779
1780         if (DECL_FIELD_CONTEXT (expr_field) != TYPE_MAIN_VARIANT (expr_record))
1781           {
1782             expr_field = find_compatible_field (expr_record, expr_field);
1783             TREE_OPERAND (expr, 1) = expr_field;
1784           }
1785       }
1786       break;
1787
1788     default:
1789       return NULL_TREE;
1790     }
1791
1792   if (t)
1793     {
1794       *expr_p = t;
1795       *changed_p = true;
1796     }
1797
1798   return NULL_TREE;
1799 }
1800
1801
1802 /* Return the string length of ARG in LENGTH.  If ARG is an SSA name variable,
1803    follow its use-def chains.  If LENGTH is not NULL and its value is not
1804    equal to the length we determine, or if we are unable to determine the
1805    length, return false.  VISITED is a bitmap of visited variables.  */
1806
1807 static bool
1808 get_strlen (tree arg, tree *length, bitmap visited)
1809 {
1810   tree var, def_stmt, val;
1811   
1812   if (TREE_CODE (arg) != SSA_NAME)
1813     {
1814       val = c_strlen (arg, 1);
1815       if (!val)
1816         return false;
1817
1818       if (*length && simple_cst_equal (val, *length) != 1)
1819         return false;
1820
1821       *length = val;
1822       return true;
1823     }
1824
1825   /* If we were already here, break the infinite cycle.  */
1826   if (bitmap_bit_p (visited, SSA_NAME_VERSION (arg)))
1827     return true;
1828   bitmap_set_bit (visited, SSA_NAME_VERSION (arg));
1829
1830   var = arg;
1831   def_stmt = SSA_NAME_DEF_STMT (var);
1832
1833   switch (TREE_CODE (def_stmt))
1834     {
1835       case MODIFY_EXPR:
1836         {
1837           tree len, rhs;
1838           
1839           /* The RHS of the statement defining VAR must either have a
1840              constant length or come from another SSA_NAME with a constant
1841              length.  */
1842           rhs = TREE_OPERAND (def_stmt, 1);
1843           STRIP_NOPS (rhs);
1844           if (TREE_CODE (rhs) == SSA_NAME)
1845             return get_strlen (rhs, length, visited);
1846
1847           /* See if the RHS is a constant length.  */
1848           len = c_strlen (rhs, 1);
1849           if (len)
1850             {
1851               if (*length && simple_cst_equal (len, *length) != 1)
1852                 return false;
1853
1854               *length = len;
1855               return true;
1856             }
1857
1858           break;
1859         }
1860
1861       case PHI_NODE:
1862         {
1863           /* All the arguments of the PHI node must have the same constant
1864              length.  */
1865           int i;
1866
1867           for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1868             {
1869               tree arg = PHI_ARG_DEF (def_stmt, i);
1870
1871               /* If this PHI has itself as an argument, we cannot
1872                  determine the string length of this argument.  However,
1873                  if we can find a constant string length for the other
1874                  PHI args then we can still be sure that this is a
1875                  constant string length.  So be optimistic and just
1876                  continue with the next argument.  */
1877               if (arg == PHI_RESULT (def_stmt))
1878                 continue;
1879
1880               if (!get_strlen (arg, length, visited))
1881                 return false;
1882             }
1883
1884           return true;
1885         }
1886
1887       default:
1888         break;
1889     }
1890
1891
1892   return false;
1893 }
1894
1895
1896 /* Fold builtin call FN in statement STMT.  If it cannot be folded into a
1897    constant, return NULL_TREE.  Otherwise, return its constant value.  */
1898
1899 static tree
1900 ccp_fold_builtin (tree stmt, tree fn)
1901 {
1902   tree result, strlen_val[2];
1903   tree callee, arglist, a;
1904   int strlen_arg, i;
1905   bitmap visited;
1906   bool ignore;
1907
1908   ignore = TREE_CODE (stmt) != MODIFY_EXPR;
1909
1910   /* First try the generic builtin folder.  If that succeeds, return the
1911      result directly.  */
1912   result = fold_builtin (fn, ignore);
1913   if (result)
1914   {
1915     if (ignore)
1916       STRIP_NOPS (result);
1917     return result;
1918   }
1919
1920   /* Ignore MD builtins.  */
1921   callee = get_callee_fndecl (fn);
1922   if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_MD)
1923     return NULL_TREE;
1924
1925   /* If the builtin could not be folded, and it has no argument list,
1926      we're done.  */
1927   arglist = TREE_OPERAND (fn, 1);
1928   if (!arglist)
1929     return NULL_TREE;
1930
1931   /* Limit the work only for builtins we know how to simplify.  */
1932   switch (DECL_FUNCTION_CODE (callee))
1933     {
1934     case BUILT_IN_STRLEN:
1935     case BUILT_IN_FPUTS:
1936     case BUILT_IN_FPUTS_UNLOCKED:
1937       strlen_arg = 1;
1938       break;
1939     case BUILT_IN_STRCPY:
1940     case BUILT_IN_STRNCPY:
1941       strlen_arg = 2;
1942       break;
1943     default:
1944       return NULL_TREE;
1945     }
1946
1947   /* Try to use the dataflow information gathered by the CCP process.  */
1948   visited = BITMAP_XMALLOC ();
1949
1950   memset (strlen_val, 0, sizeof (strlen_val));
1951   for (i = 0, a = arglist;
1952        strlen_arg;
1953        i++, strlen_arg >>= 1, a = TREE_CHAIN (a))
1954     if (strlen_arg & 1)
1955       {
1956         bitmap_clear (visited);
1957         if (!get_strlen (TREE_VALUE (a), &strlen_val[i], visited))
1958           strlen_val[i] = NULL_TREE;
1959       }
1960
1961   BITMAP_XFREE (visited);
1962
1963   result = NULL_TREE;
1964   switch (DECL_FUNCTION_CODE (callee))
1965     {
1966     case BUILT_IN_STRLEN:
1967       if (strlen_val[0])
1968         {
1969           tree new = fold_convert (TREE_TYPE (fn), strlen_val[0]);
1970
1971           /* If the result is not a valid gimple value, or not a cast
1972              of a valid gimple value, then we can not use the result.  */
1973           if (is_gimple_val (new)
1974               || (is_gimple_cast (new)
1975                   && is_gimple_val (TREE_OPERAND (new, 0))))
1976             return new;
1977         }
1978       break;
1979
1980     case BUILT_IN_STRCPY:
1981       if (strlen_val[1] && is_gimple_val (strlen_val[1]))
1982         result = fold_builtin_strcpy (fn, strlen_val[1]);
1983       break;
1984
1985     case BUILT_IN_STRNCPY:
1986       if (strlen_val[1] && is_gimple_val (strlen_val[1]))
1987         result = fold_builtin_strncpy (fn, strlen_val[1]);
1988       break;
1989
1990     case BUILT_IN_FPUTS:
1991       result = fold_builtin_fputs (arglist,
1992                                    TREE_CODE (stmt) != MODIFY_EXPR, 0,
1993                                    strlen_val[0]);
1994       break;
1995
1996     case BUILT_IN_FPUTS_UNLOCKED:
1997       result = fold_builtin_fputs (arglist,
1998                                    TREE_CODE (stmt) != MODIFY_EXPR, 1,
1999                                    strlen_val[0]);
2000       break;
2001
2002     default:
2003       abort ();
2004     }
2005
2006   if (result && ignore)
2007     result = fold_ignored_result (result);
2008   return result;
2009 }
2010
2011
2012 /* Fold the statement pointed by STMT_P.  In some cases, this function may
2013    replace the whole statement with a new one.  Returns true iff folding
2014    makes any changes.  */
2015
2016 bool
2017 fold_stmt (tree *stmt_p)
2018 {
2019   tree rhs, result, stmt;
2020   bool changed = false;
2021
2022   stmt = *stmt_p;
2023
2024   /* If we replaced constants and the statement makes pointer dereferences,
2025      then we may need to fold instances of *&VAR into VAR, etc.  */
2026   if (walk_tree (stmt_p, fold_stmt_r, &changed, NULL))
2027     {
2028       *stmt_p
2029         = build_function_call_expr (implicit_built_in_decls[BUILT_IN_TRAP],
2030                                     NULL);
2031       return true;
2032     }
2033
2034   rhs = get_rhs (stmt);
2035   if (!rhs)
2036     return changed;
2037   result = NULL_TREE;
2038
2039   if (TREE_CODE (rhs) == CALL_EXPR)
2040     {
2041       tree callee;
2042
2043       /* Check for builtins that CCP can handle using information not
2044          available in the generic fold routines.  */
2045       callee = get_callee_fndecl (rhs);
2046       if (callee && DECL_BUILT_IN (callee))
2047         result = ccp_fold_builtin (stmt, rhs);
2048       else
2049         {
2050           /* Check for resolvable OBJ_TYPE_REF.  The only sorts we can resolve
2051              here are when we've propagated the address of a decl into the
2052              object slot.  */
2053           /* ??? Should perhaps do this in fold proper.  However, doing it
2054              there requires that we create a new CALL_EXPR, and that requires
2055              copying EH region info to the new node.  Easier to just do it
2056              here where we can just smash the call operand.  */
2057           callee = TREE_OPERAND (rhs, 0);
2058           if (TREE_CODE (callee) == OBJ_TYPE_REF
2059               && lang_hooks.fold_obj_type_ref
2060               && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR
2061               && DECL_P (TREE_OPERAND (OBJ_TYPE_REF_OBJECT (callee), 0)))
2062             {
2063               tree t;
2064
2065               /* ??? Caution: Broken ADDR_EXPR semantics means that
2066                  looking at the type of the operand of the addr_expr
2067                  can yield an array type.  See silly exception in
2068                  check_pointer_types_r.  */
2069
2070               t = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (callee)));
2071               t = lang_hooks.fold_obj_type_ref (callee, t);
2072               if (t)
2073                 {
2074                   TREE_OPERAND (rhs, 0) = t;
2075                   changed = true;
2076                 }
2077             }
2078         }
2079     }
2080
2081   /* If we couldn't fold the RHS, hand over to the generic fold routines.  */
2082   if (result == NULL_TREE)
2083     result = fold (rhs);
2084
2085   /* Strip away useless type conversions.  Both the NON_LVALUE_EXPR that
2086      may have been added by fold, and "useless" type conversions that might
2087      now be apparent due to propagation.  */
2088   STRIP_USELESS_TYPE_CONVERSION (result);
2089
2090   if (result != rhs)
2091     changed |= set_rhs (stmt_p, result);
2092
2093   return changed;
2094 }
2095
2096 \f
2097 /* A simple pass that attempts to fold all builtin functions.  This pass
2098    is run after we've propagated as many constants as we can.  */
2099
2100 static void
2101 execute_fold_all_builtins (void)
2102 {
2103   basic_block bb;
2104   FOR_EACH_BB (bb)
2105     {
2106       block_stmt_iterator i;
2107       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
2108         {
2109           tree *stmtp = bsi_stmt_ptr (i);
2110           tree call = get_rhs (*stmtp);
2111           tree callee, result;
2112
2113           if (!call || TREE_CODE (call) != CALL_EXPR)
2114             continue;
2115           callee = get_callee_fndecl (call);
2116           if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
2117             continue;
2118
2119           result = ccp_fold_builtin (*stmtp, call);
2120           if (!result)
2121             switch (DECL_FUNCTION_CODE (callee))
2122               {
2123               case BUILT_IN_CONSTANT_P:
2124                 /* Resolve __builtin_constant_p.  If it hasn't been
2125                    folded to integer_one_node by now, it's fairly
2126                    certain that the value simply isn't constant.  */
2127                 result = integer_zero_node;
2128                 break;
2129
2130               default:
2131                 continue;
2132               }
2133
2134           if (dump_file && (dump_flags & TDF_DETAILS))
2135             {
2136               fprintf (dump_file, "Simplified\n  ");
2137               print_generic_stmt (dump_file, *stmtp, dump_flags);
2138             }
2139
2140           if (set_rhs (stmtp, result))
2141             modify_stmt (*stmtp);
2142
2143           if (dump_file && (dump_flags & TDF_DETAILS))
2144             {
2145               fprintf (dump_file, "to\n  ");
2146               print_generic_stmt (dump_file, *stmtp, dump_flags);
2147               fprintf (dump_file, "\n");
2148             }
2149         }
2150     }
2151 }
2152
2153
2154 struct tree_opt_pass pass_fold_builtins = 
2155 {
2156   "fab",                                /* name */
2157   NULL,                                 /* gate */
2158   execute_fold_all_builtins,            /* execute */
2159   NULL,                                 /* sub */
2160   NULL,                                 /* next */
2161   0,                                    /* static_pass_number */
2162   0,                                    /* tv_id */
2163   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
2164   0,                                    /* properties_provided */
2165   0,                                    /* properties_destroyed */
2166   0,                                    /* todo_flags_start */
2167   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
2168   0                                     /* letter */
2169 };