OSDN Git Service

56a181a37cd9b9c486ccad650fc90ec98a4a4209
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa.c
1 /* Miscellaneous SSA utility functions.
2    Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
9 any later version.
10
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING.  If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "flags.h"
27 #include "rtl.h"
28 #include "tm_p.h"
29 #include "ggc.h"
30 #include "langhooks.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
33 #include "output.h"
34 #include "errors.h"
35 #include "expr.h"
36 #include "function.h"
37 #include "diagnostic.h"
38 #include "bitmap.h"
39 #include "pointer-set.h"
40 #include "tree-flow.h"
41 #include "tree-gimple.h"
42 #include "tree-inline.h"
43 #include "varray.h"
44 #include "timevar.h"
45 #include "hashtab.h"
46 #include "tree-dump.h"
47 #include "tree-pass.h"
48
49 /* Remove the corresponding arguments from the PHI nodes in E's
50    destination block and redirect it to DEST.  Return redirected edge.
51    The list of removed arguments is stored in PENDING_STMT (e).  */
52
53 edge
54 ssa_redirect_edge (edge e, basic_block dest)
55 {
56   tree phi, next;
57   tree list = NULL, *last = &list;
58   tree src, dst, node;
59
60   /* Remove the appropriate PHI arguments in E's destination block.  */
61   for (phi = phi_nodes (e->dest); phi; phi = next)
62     {
63       next = PHI_CHAIN (phi);
64
65       if (PHI_ARG_DEF (phi, e->dest_idx) == NULL_TREE)
66         continue;
67
68       src = PHI_ARG_DEF (phi, e->dest_idx);
69       dst = PHI_RESULT (phi);
70       node = build_tree_list (dst, src);
71       *last = node;
72       last = &TREE_CHAIN (node);
73     }
74
75   e = redirect_edge_succ_nodup (e, dest);
76   PENDING_STMT (e) = list;
77
78   return e;
79 }
80
81 /* Add PHI arguments queued in PENDINT_STMT list on edge E to edge
82    E->dest.  */
83
84 void
85 flush_pending_stmts (edge e)
86 {
87   tree phi, arg;
88
89   if (!PENDING_STMT (e))
90     return;
91
92   for (phi = phi_nodes (e->dest), arg = PENDING_STMT (e);
93        phi;
94        phi = PHI_CHAIN (phi), arg = TREE_CHAIN (arg))
95     {
96       tree def = TREE_VALUE (arg);
97       add_phi_arg (phi, def, e);
98     }
99
100   PENDING_STMT (e) = NULL;
101 }
102
103 /* Return true if SSA_NAME is malformed and mark it visited.
104
105    IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
106       operand.  */
107
108 static bool
109 verify_ssa_name (tree ssa_name, bool is_virtual)
110 {
111   if (TREE_CODE (ssa_name) != SSA_NAME)
112     {
113       error ("Expected an SSA_NAME object");
114       return true;
115     }
116
117   if (TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name)))
118     {
119       error ("Type mismatch between an SSA_NAME and its symbol.");
120       return true;
121     }
122
123   if (SSA_NAME_IN_FREE_LIST (ssa_name))
124     {
125       error ("Found an SSA_NAME that had been released into the free pool");
126       return true;
127     }
128
129   if (is_virtual && is_gimple_reg (ssa_name))
130     {
131       error ("Found a virtual definition for a GIMPLE register");
132       return true;
133     }
134
135   if (!is_virtual && !is_gimple_reg (ssa_name))
136     {
137       error ("Found a real definition for a non-register");
138       return true;
139     }
140
141   return false;
142 }
143
144
145 /* Return true if the definition of SSA_NAME at block BB is malformed.
146
147    STMT is the statement where SSA_NAME is created.
148
149    DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
150       version numbers.  If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
151       it means that the block in that array slot contains the
152       definition of SSA_NAME.
153
154    IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
155       V_MUST_DEF.  */
156
157 static bool
158 verify_def (basic_block bb, basic_block *definition_block, tree ssa_name,
159             tree stmt, bool is_virtual)
160 {
161   if (verify_ssa_name (ssa_name, is_virtual))
162     goto err;
163
164   if (definition_block[SSA_NAME_VERSION (ssa_name)])
165     {
166       error ("SSA_NAME created in two different blocks %i and %i",
167              definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index);
168       goto err;
169     }
170
171   definition_block[SSA_NAME_VERSION (ssa_name)] = bb;
172
173   if (SSA_NAME_DEF_STMT (ssa_name) != stmt)
174     {
175       error ("SSA_NAME_DEF_STMT is wrong");
176       fprintf (stderr, "Expected definition statement:\n");
177       print_generic_stmt (stderr, SSA_NAME_DEF_STMT (ssa_name), TDF_VOPS);
178       fprintf (stderr, "\nActual definition statement:\n");
179       print_generic_stmt (stderr, stmt, TDF_VOPS);
180       goto err;
181     }
182
183   return false;
184
185 err:
186   fprintf (stderr, "while verifying SSA_NAME ");
187   print_generic_expr (stderr, ssa_name, 0);
188   fprintf (stderr, " in statement\n");
189   print_generic_stmt (stderr, stmt, TDF_VOPS);
190
191   return true;
192 }
193
194
195 /* Return true if the use of SSA_NAME at statement STMT in block BB is
196    malformed.
197
198    DEF_BB is the block where SSA_NAME was found to be created.
199
200    IDOM contains immediate dominator information for the flowgraph.
201
202    CHECK_ABNORMAL is true if the caller wants to check whether this use
203       is flowing through an abnormal edge (only used when checking PHI
204       arguments).
205
206    IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
207       V_MUST_DEF.
208    
209    If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
210      that are defined before STMT in basic block BB.  */
211
212 static bool
213 verify_use (basic_block bb, basic_block def_bb, tree ssa_name,
214             tree stmt, bool check_abnormal, bool is_virtual,
215             bitmap names_defined_in_bb)
216 {
217   bool err = false;
218
219   err = verify_ssa_name (ssa_name, is_virtual);
220   TREE_VISITED (ssa_name) = 1;
221
222   if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name))
223       && var_ann (SSA_NAME_VAR (ssa_name))->default_def == ssa_name)
224     ; /* Default definitions have empty statements.  Nothing to do.  */
225   else if (!def_bb)
226     {
227       error ("Missing definition");
228       err = true;
229     }
230   else if (bb != def_bb
231            && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
232     {
233       error ("Definition in block %i does not dominate use in block %i",
234              def_bb->index, bb->index);
235       err = true;
236     }
237   else if (bb == def_bb
238            && names_defined_in_bb != NULL
239            && !bitmap_bit_p (names_defined_in_bb, SSA_NAME_VERSION (ssa_name)))
240     {
241       error ("Definition in block %i follows the use", def_bb->index);
242       err = true;
243     }
244
245   if (check_abnormal
246       && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
247     {
248       error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
249       err = true;
250     }
251
252   if (err)
253     {
254       fprintf (stderr, "for SSA_NAME: ");
255       print_generic_expr (stderr, ssa_name, TDF_VOPS);
256       fprintf (stderr, "in statement:\n");
257       print_generic_stmt (stderr, stmt, TDF_VOPS);
258     }
259
260   return err;
261 }
262
263
264 /* Return true if any of the arguments for PHI node PHI at block BB is
265    malformed.
266
267    DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
268       numbers.  If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
269       block in that array slot contains the definition of SSA_NAME.  */
270
271 static bool
272 verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)
273 {
274   edge e;
275   bool err = false;
276   unsigned i, phi_num_args = PHI_NUM_ARGS (phi);
277
278   if (EDGE_COUNT (bb->preds) != phi_num_args)
279     {
280       error ("Incoming edge count does not match number of PHI arguments\n");
281       err = true;
282       goto error;
283     }
284
285   for (i = 0; i < phi_num_args; i++)
286     {
287       tree op = PHI_ARG_DEF (phi, i);
288
289       e = EDGE_PRED (bb, i);
290
291       if (op == NULL_TREE)
292         {
293           error ("PHI argument is missing for edge %d->%d\n",
294                  e->src->index,
295                  e->dest->index);
296           err = true;
297           goto error;
298         }
299
300       if (TREE_CODE (op) != SSA_NAME && !is_gimple_min_invariant (op))
301         {
302           error ("PHI argument is not SSA_NAME, or invariant");
303           err = true;
304         }
305
306       if (TREE_CODE (op) == SSA_NAME)
307         err = verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op,
308                           phi, e->flags & EDGE_ABNORMAL,
309                           !is_gimple_reg (PHI_RESULT (phi)),
310                           NULL);
311
312       if (e->dest != bb)
313         {
314           error ("Wrong edge %d->%d for PHI argument\n",
315                  e->src->index, e->dest->index, bb->index);
316           err = true;
317         }
318
319       if (err)
320         {
321           fprintf (stderr, "PHI argument\n");
322           print_generic_stmt (stderr, op, TDF_VOPS);
323           goto error;
324         }
325     }
326
327 error:
328   if (err)
329     {
330       fprintf (stderr, "for PHI node\n");
331       print_generic_stmt (stderr, phi, TDF_VOPS);
332     }
333
334
335   return err;
336 }
337
338
339 static void
340 verify_flow_insensitive_alias_info (void)
341 {
342   size_t i;
343   tree var;
344   bitmap visited = BITMAP_ALLOC (NULL);
345
346   for (i = 0; i < num_referenced_vars; i++)
347     {
348       size_t j;
349       var_ann_t ann;
350       varray_type may_aliases;
351
352       var = referenced_var (i);
353       ann = var_ann (var);
354       may_aliases = ann->may_aliases;
355
356       for (j = 0; may_aliases && j < VARRAY_ACTIVE_SIZE (may_aliases); j++)
357         {
358           tree alias = VARRAY_TREE (may_aliases, j);
359
360           bitmap_set_bit (visited, var_ann (alias)->uid);
361
362           if (!may_be_aliased (alias))
363             {
364               error ("Non-addressable variable inside an alias set.");
365               debug_variable (alias);
366               goto err;
367             }
368         }
369     }
370
371   for (i = 0; i < num_referenced_vars; i++)
372     {
373       var_ann_t ann;
374
375       var = referenced_var (i);
376       ann = var_ann (var);
377
378       if (ann->mem_tag_kind == NOT_A_TAG
379           && ann->is_alias_tag
380           && !bitmap_bit_p (visited, ann->uid))
381         {
382           error ("Addressable variable that is an alias tag but is not in any alias set.");
383           goto err;
384         }
385     }
386
387   BITMAP_FREE (visited);
388   return;
389
390 err:
391   debug_variable (var);
392   internal_error ("verify_flow_insensitive_alias_info failed.");
393 }
394
395
396 static void
397 verify_flow_sensitive_alias_info (void)
398 {
399   size_t i;
400   tree ptr;
401
402   for (i = 1; i < num_ssa_names; i++)
403     {
404       tree var;
405       var_ann_t ann;
406       struct ptr_info_def *pi;
407  
408
409       ptr = ssa_name (i);
410       if (!ptr)
411         continue;
412
413       /* We only care for pointers that are actually referenced in the
414          program.  */
415       if (!POINTER_TYPE_P (TREE_TYPE (ptr)) || !TREE_VISITED (ptr))
416         continue;
417
418       /* RESULT_DECL is special.  If it's a GIMPLE register, then it
419          is only written-to only once in the return statement.
420          Otherwise, aggregate RESULT_DECLs may be written-to more than
421          once in virtual operands.  */
422       var = SSA_NAME_VAR (ptr);
423       if (TREE_CODE (var) == RESULT_DECL
424           && is_gimple_reg (ptr))
425         continue;
426
427       pi = SSA_NAME_PTR_INFO (ptr);
428       if (pi == NULL)
429         continue;
430
431       ann = var_ann (var);
432       if (pi->is_dereferenced && !pi->name_mem_tag && !ann->type_mem_tag)
433         {
434           error ("Dereferenced pointers should have a name or a type tag");
435           goto err;
436         }
437
438       if (pi->name_mem_tag
439           && !pi->pt_malloc
440           && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars)))
441         {
442           error ("Pointers with a memory tag, should have points-to sets or point to malloc");
443           goto err;
444         }
445
446       if (pi->value_escapes_p
447           && pi->name_mem_tag
448           && !is_call_clobbered (pi->name_mem_tag))
449         {
450           error ("Pointer escapes but its name tag is not call-clobbered.");
451           goto err;
452         }
453     }
454
455   return;
456
457 err:
458   debug_variable (ptr);
459   internal_error ("verify_flow_sensitive_alias_info failed.");
460 }
461
462 DEF_VEC_MALLOC_P (bitmap);
463
464 /* Verify that all name tags have different points to sets.
465    This algorithm takes advantage of the fact that every variable with the
466    same name tag must have the same points-to set. 
467    So we check a single variable for each name tag, and verify that its
468    points-to set is different from every other points-to set for other name
469    tags.
470
471    Additionally, given a pointer P_i with name tag NMT and type tag
472    TMT, this function verified the alias set of TMT is a superset of
473    the alias set of NMT.  */
474
475 static void
476 verify_name_tags (void)
477 {
478   size_t i;  
479   size_t j;
480   bitmap first, second;  
481   VEC (tree) *name_tag_reps = NULL;
482   VEC (bitmap) *pt_vars_for_reps = NULL;
483   bitmap type_aliases = BITMAP_ALLOC (NULL);
484
485   /* First we compute the name tag representatives and their points-to sets.  */
486   for (i = 0; i < num_ssa_names; i++)
487     {
488       struct ptr_info_def *pi;
489       tree tmt, ptr = ssa_name (i);
490
491       if (ptr == NULL_TREE)
492         continue;
493       
494       pi = SSA_NAME_PTR_INFO (ptr);
495
496       if (!TREE_VISITED (ptr) 
497           || !POINTER_TYPE_P (TREE_TYPE (ptr)) 
498           || !pi
499           || !pi->name_mem_tag 
500           || TREE_VISITED (pi->name_mem_tag))
501         continue;
502
503       TREE_VISITED (pi->name_mem_tag) = 1;
504
505       if (pi->pt_vars == NULL)
506         continue;
507
508       VEC_safe_push (tree, name_tag_reps, ptr);
509       VEC_safe_push (bitmap, pt_vars_for_reps, pi->pt_vars);
510
511       /* Verify that alias set of PTR's type tag is a superset of the
512          alias set of PTR's name tag.  */
513       tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
514       if (tmt)
515         {
516           size_t i;
517           varray_type aliases = var_ann (tmt)->may_aliases;
518           bitmap_clear (type_aliases);
519           for (i = 0; aliases && i < VARRAY_ACTIVE_SIZE (aliases); i++)
520             {
521               tree alias = VARRAY_TREE (aliases, i);
522               bitmap_set_bit (type_aliases, var_ann (alias)->uid);
523             }
524
525           /* When grouping, we may have added PTR's type tag into the
526              alias set of PTR's name tag.  To prevent a false
527              positive, pretend that TMT is in its own alias set.  */
528           bitmap_set_bit (type_aliases, var_ann (tmt)->uid);
529
530           if (bitmap_equal_p (type_aliases, pi->pt_vars))
531             continue;
532
533           if (!bitmap_intersect_compl_p (type_aliases, pi->pt_vars))
534             {
535               error ("Alias set of a pointer's type tag should be a superset of the corresponding name tag");
536               debug_variable (tmt);
537               debug_variable (pi->name_mem_tag);
538               goto err;
539             }
540         }
541     }
542   
543   /* Now compare all the representative bitmaps with all other representative
544      bitmaps, to verify that they are all different.  */
545   for (i = 0; VEC_iterate (bitmap, pt_vars_for_reps, i, first); i++)
546     {
547        for (j = i + 1; VEC_iterate (bitmap, pt_vars_for_reps, j, second); j++)
548          { 
549            if (bitmap_equal_p (first, second))
550              {
551                error ("Two different pointers with identical points-to sets but different name tags");
552                debug_variable (VEC_index (tree, name_tag_reps, j));
553                goto err;
554              }
555          }
556     }
557
558   /* Lastly, clear out the visited flags.  */
559   for (i = 0; i < num_ssa_names; i++)
560     {
561       if (ssa_name (i))
562         {
563           tree ptr = ssa_name (i);
564           struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
565           if (!TREE_VISITED (ptr) 
566               || !POINTER_TYPE_P (TREE_TYPE (ptr)) 
567               || !pi
568               || !pi->name_mem_tag)
569             continue;
570           TREE_VISITED (pi->name_mem_tag) = 0;
571         }
572     } 
573
574   VEC_free (bitmap, pt_vars_for_reps);
575   BITMAP_FREE (type_aliases);
576   return;
577   
578 err:
579   debug_variable (VEC_index (tree, name_tag_reps, i));
580   internal_error ("verify_name_tags failed");
581 }
582
583
584 /* Verify the consistency of aliasing information.  */
585
586 static void
587 verify_alias_info (void)
588 {
589   verify_flow_sensitive_alias_info ();
590   verify_name_tags ();
591   verify_flow_insensitive_alias_info ();
592 }
593
594
595 /* Verify common invariants in the SSA web.
596    TODO: verify the variable annotations.  */
597
598 void
599 verify_ssa (void)
600 {
601   size_t i;
602   basic_block bb;
603   basic_block *definition_block = xcalloc (num_ssa_names, sizeof (basic_block));
604   ssa_op_iter iter;
605   tree op;
606   enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS];
607   bitmap names_defined_in_bb = BITMAP_ALLOC (NULL);
608
609   timevar_push (TV_TREE_SSA_VERIFY);
610
611   /* Keep track of SSA names present in the IL.  */
612   for (i = 1; i < num_ssa_names; i++)
613     {
614       tree name = ssa_name (i);
615       if (name)
616         {
617           tree stmt;
618           TREE_VISITED (name) = 0;
619
620           stmt = SSA_NAME_DEF_STMT (name);
621           if (!IS_EMPTY_STMT (stmt))
622             {
623               basic_block bb = bb_for_stmt (stmt);
624               verify_def (bb, definition_block,
625                           name, stmt, !is_gimple_reg (name));
626
627             }
628         }
629     }
630
631   calculate_dominance_info (CDI_DOMINATORS);
632
633   /* Now verify all the uses and make sure they agree with the definitions
634      found in the previous pass.  */
635   FOR_EACH_BB (bb)
636     {
637       edge e;
638       tree phi;
639       edge_iterator ei;
640       block_stmt_iterator bsi;
641
642       /* Make sure that all edges have a clear 'aux' field.  */
643       FOR_EACH_EDGE (e, ei, bb->preds)
644         {
645           if (e->aux)
646             {
647               error ("AUX pointer initialized for edge %d->%d\n", e->src->index,
648                       e->dest->index);
649               goto err;
650             }
651         }
652
653       /* Verify the arguments for every PHI node in the block.  */
654       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
655         {
656           if (verify_phi_args (phi, bb, definition_block))
657             goto err;
658           bitmap_set_bit (names_defined_in_bb,
659                           SSA_NAME_VERSION (PHI_RESULT (phi)));
660         }
661
662       /* Now verify all the uses and vuses in every statement of the block.  */
663       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
664         {
665           tree stmt = bsi_stmt (bsi);
666
667               get_stmt_operands (stmt);
668
669               if (stmt_ann (stmt)->makes_aliased_stores 
670                   && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) == 0)
671                 {
672                   error ("Statement makes aliased stores, but has no V_MAY_DEFS");
673                   print_generic_stmt (stderr, stmt, TDF_VOPS);
674                   goto err;
675                 }
676
677           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
678             {
679               if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
680                               op, stmt, false, !is_gimple_reg (op),
681                               names_defined_in_bb))
682                 goto err;
683             }
684
685           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
686             {
687               bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
688             }
689         }
690
691       bitmap_clear (names_defined_in_bb);
692     }
693
694   /* Finally, verify alias information.  */
695   verify_alias_info ();
696
697   free (definition_block);
698   /* Restore the dominance information to its prior known state, so
699      that we do not perturb the compiler's subsequent behavior.  */
700   if (orig_dom_state == DOM_NONE)
701     free_dominance_info (CDI_DOMINATORS);
702   else
703     dom_computed[CDI_DOMINATORS] = orig_dom_state;
704   
705   BITMAP_FREE (names_defined_in_bb);
706   timevar_pop (TV_TREE_SSA_VERIFY);
707   return;
708
709 err:
710   internal_error ("verify_ssa failed.");
711 }
712
713
714 /* Initialize global DFA and SSA structures.  */
715
716 void
717 init_tree_ssa (void)
718 {
719   VARRAY_TREE_INIT (referenced_vars, 20, "referenced_vars");
720   call_clobbered_vars = BITMAP_ALLOC (NULL);
721   addressable_vars = BITMAP_ALLOC (NULL);
722   init_ssa_operands ();
723   init_ssanames ();
724   init_phinodes ();
725   global_var = NULL_TREE;
726 }
727
728
729 /* Deallocate memory associated with SSA data structures for FNDECL.  */
730
731 void
732 delete_tree_ssa (void)
733 {
734   size_t i;
735   basic_block bb;
736   block_stmt_iterator bsi;
737
738   /* Remove annotations from every tree in the function.  */
739   FOR_EACH_BB (bb)
740     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
741       {
742         tree stmt = bsi_stmt (bsi);
743         release_defs (stmt);
744         ggc_free (stmt->common.ann);
745         stmt->common.ann = NULL;
746       }
747
748   /* Remove annotations from every referenced variable.  */
749   if (referenced_vars)
750     {
751       for (i = 0; i < num_referenced_vars; i++)
752         {
753           tree var = referenced_var (i);
754           ggc_free (var->common.ann);
755           var->common.ann = NULL;
756         }
757       referenced_vars = NULL;
758     }
759
760   fini_ssanames ();
761   fini_phinodes ();
762   fini_ssa_operands ();
763
764   global_var = NULL_TREE;
765   BITMAP_FREE (call_clobbered_vars);
766   call_clobbered_vars = NULL;
767   BITMAP_FREE (addressable_vars);
768   addressable_vars = NULL;
769   modified_noreturn_calls = NULL;
770 }
771
772
773 /* Return true if EXPR is a useless type conversion, otherwise return
774    false.  */
775
776 bool
777 tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
778 {
779   /* If the inner and outer types are effectively the same, then
780      strip the type conversion and enter the equivalence into
781      the table.  */
782   if (inner_type == outer_type
783      || (lang_hooks.types_compatible_p (inner_type, outer_type)))
784     return true;
785
786   /* If both types are pointers and the outer type is a (void *), then
787      the conversion is not necessary.  The opposite is not true since
788      that conversion would result in a loss of information if the
789      equivalence was used.  Consider an indirect function call where
790      we need to know the exact type of the function to correctly
791      implement the ABI.  */
792   else if (POINTER_TYPE_P (inner_type)
793            && POINTER_TYPE_P (outer_type)
794            && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
795            && TYPE_REF_CAN_ALIAS_ALL (inner_type)
796               == TYPE_REF_CAN_ALIAS_ALL (outer_type)
797            && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
798     return true;
799
800   /* Pointers and references are equivalent once we get to GENERIC,
801      so strip conversions that just switch between them.  */
802   else if (POINTER_TYPE_P (inner_type)
803            && POINTER_TYPE_P (outer_type)
804            && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
805            && TYPE_REF_CAN_ALIAS_ALL (inner_type)
806               == TYPE_REF_CAN_ALIAS_ALL (outer_type)
807            && lang_hooks.types_compatible_p (TREE_TYPE (inner_type),
808                                              TREE_TYPE (outer_type)))
809     return true;
810
811   /* If both the inner and outer types are integral types, then the
812      conversion is not necessary if they have the same mode and
813      signedness and precision, and both or neither are boolean.  Some
814      code assumes an invariant that boolean types stay boolean and do
815      not become 1-bit bit-field types.  Note that types with precision
816      not using all bits of the mode (such as bit-field types in C)
817      mean that testing of precision is necessary.  */
818   else if (INTEGRAL_TYPE_P (inner_type)
819            && INTEGRAL_TYPE_P (outer_type)
820            && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
821            && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
822            && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
823     {
824       bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE);
825       bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE);
826       if (first_boolean == second_boolean)
827         return true;
828     }
829
830   /* Recurse for complex types.  */
831   else if (TREE_CODE (inner_type) == COMPLEX_TYPE
832            && TREE_CODE (outer_type) == COMPLEX_TYPE
833            && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
834                                                   TREE_TYPE (inner_type)))
835     return true;
836
837   return false;
838 }
839
840 /* Return true if EXPR is a useless type conversion, otherwise return
841    false.  */
842
843 bool
844 tree_ssa_useless_type_conversion (tree expr)
845 {
846   /* If we have an assignment that merely uses a NOP_EXPR to change
847      the top of the RHS to the type of the LHS and the type conversion
848      is "safe", then strip away the type conversion so that we can
849      enter LHS = RHS into the const_and_copies table.  */
850   if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR
851       || TREE_CODE (expr) == VIEW_CONVERT_EXPR
852       || TREE_CODE (expr) == NON_LVALUE_EXPR)
853     return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
854                                                TREE_TYPE (TREE_OPERAND (expr,
855                                                                         0)));
856
857
858   return false;
859 }
860
861 /* Returns true if statement STMT may read memory.  */
862
863 bool
864 stmt_references_memory_p (tree stmt)
865 {
866   stmt_ann_t ann;
867
868   get_stmt_operands (stmt);
869   ann = stmt_ann (stmt);
870
871   if (ann->has_volatile_ops)
872     return true;
873
874   return (NUM_VUSES (VUSE_OPS (ann)) > 0
875           || NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) > 0
876           || NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) > 0);
877 }
878
879 /* Internal helper for walk_use_def_chains.  VAR, FN and DATA are as
880    described in walk_use_def_chains.
881    
882    VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
883       infinite loops.  We used to have a bitmap for this to just mark
884       SSA versions we had visited.  But non-sparse bitmaps are way too
885       expensive, while sparse bitmaps may cause quadratic behavior.
886
887    IS_DFS is true if the caller wants to perform a depth-first search
888       when visiting PHI nodes.  A DFS will visit each PHI argument and
889       call FN after each one.  Otherwise, all the arguments are
890       visited first and then FN is called with each of the visited
891       arguments in a separate pass.  */
892
893 static bool
894 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
895                        struct pointer_set_t *visited, bool is_dfs)
896 {
897   tree def_stmt;
898
899   if (pointer_set_insert (visited, var))
900     return false;
901
902   def_stmt = SSA_NAME_DEF_STMT (var);
903
904   if (TREE_CODE (def_stmt) != PHI_NODE)
905     {
906       /* If we reached the end of the use-def chain, call FN.  */
907       return fn (var, def_stmt, data);
908     }
909   else
910     {
911       int i;
912
913       /* When doing a breadth-first search, call FN before following the
914          use-def links for each argument.  */
915       if (!is_dfs)
916         for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
917           if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
918             return true;
919
920       /* Follow use-def links out of each PHI argument.  */
921       for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
922         {
923           tree arg = PHI_ARG_DEF (def_stmt, i);
924           if (TREE_CODE (arg) == SSA_NAME
925               && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
926             return true;
927         }
928
929       /* When doing a depth-first search, call FN after following the
930          use-def links for each argument.  */
931       if (is_dfs)
932         for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
933           if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
934             return true;
935     }
936   
937   return false;
938 }
939   
940
941
942 /* Walk use-def chains starting at the SSA variable VAR.  Call
943    function FN at each reaching definition found.  FN takes three
944    arguments: VAR, its defining statement (DEF_STMT) and a generic
945    pointer to whatever state information that FN may want to maintain
946    (DATA).  FN is able to stop the walk by returning true, otherwise
947    in order to continue the walk, FN should return false.  
948
949    Note, that if DEF_STMT is a PHI node, the semantics are slightly
950    different.  The first argument to FN is no longer the original
951    variable VAR, but the PHI argument currently being examined.  If FN
952    wants to get at VAR, it should call PHI_RESULT (PHI).
953
954    If IS_DFS is true, this function will:
955
956         1- walk the use-def chains for all the PHI arguments, and,
957         2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
958
959    If IS_DFS is false, the two steps above are done in reverse order
960    (i.e., a breadth-first search).  */
961
962
963 void
964 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
965                      bool is_dfs)
966 {
967   tree def_stmt;
968
969   gcc_assert (TREE_CODE (var) == SSA_NAME);
970
971   def_stmt = SSA_NAME_DEF_STMT (var);
972
973   /* We only need to recurse if the reaching definition comes from a PHI
974      node.  */
975   if (TREE_CODE (def_stmt) != PHI_NODE)
976     (*fn) (var, def_stmt, data);
977   else
978     {
979       struct pointer_set_t *visited = pointer_set_create ();
980       walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
981       pointer_set_destroy (visited);
982     }
983 }
984
985
986 /* Replaces VAR with REPL in memory reference expression *X in
987    statement STMT.  */
988
989 static void
990 propagate_into_addr (tree stmt, tree var, tree *x, tree repl)
991 {
992   tree new_var, ass_stmt, addr_var;
993   basic_block bb;
994   block_stmt_iterator bsi;
995
996   /* There is nothing special to handle in the other cases.  */
997   if (TREE_CODE (repl) != ADDR_EXPR)
998     return;
999   addr_var = TREE_OPERAND (repl, 0);
1000
1001   while (handled_component_p (*x)
1002          || TREE_CODE (*x) == REALPART_EXPR
1003          || TREE_CODE (*x) == IMAGPART_EXPR)
1004     x = &TREE_OPERAND (*x, 0);
1005
1006   if (TREE_CODE (*x) != INDIRECT_REF
1007       || TREE_OPERAND (*x, 0) != var)
1008     return;
1009
1010   if (TREE_TYPE (*x) == TREE_TYPE (addr_var))
1011     {
1012       *x = addr_var;
1013       mark_new_vars_to_rename (stmt, vars_to_rename);
1014       return;
1015     }
1016
1017
1018   /* Frontends sometimes produce expressions like *&a instead of a[0].
1019      Create a temporary variable to handle this case.  */
1020   ass_stmt = build2 (MODIFY_EXPR, void_type_node, NULL_TREE, repl);
1021   new_var = duplicate_ssa_name (var, ass_stmt);
1022   TREE_OPERAND (*x, 0) = new_var;
1023   TREE_OPERAND (ass_stmt, 0) = new_var;
1024
1025   bb = bb_for_stmt (stmt);
1026   tree_block_label (bb);
1027   bsi = bsi_after_labels (bb);
1028   bsi_insert_after (&bsi, ass_stmt, BSI_NEW_STMT);
1029
1030   mark_new_vars_to_rename (stmt, vars_to_rename);
1031 }
1032
1033 /* Replaces immediate uses of VAR by REPL.  */
1034
1035 static void
1036 replace_immediate_uses (tree var, tree repl)
1037 {
1038   int i, j, n;
1039   dataflow_t df;
1040   tree stmt;
1041   bool mark_new_vars;
1042   ssa_op_iter iter;
1043   use_operand_p use_p;
1044
1045   df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
1046   n = num_immediate_uses (df);
1047
1048   for (i = 0; i < n; i++)
1049     {
1050       stmt = immediate_use (df, i);
1051
1052       if (TREE_CODE (stmt) == PHI_NODE)
1053         {
1054           for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
1055             if (PHI_ARG_DEF (stmt, j) == var)
1056               {
1057                 SET_PHI_ARG_DEF (stmt, j, repl);
1058                 if (TREE_CODE (repl) == SSA_NAME
1059                     && PHI_ARG_EDGE (stmt, j)->flags & EDGE_ABNORMAL)
1060                   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl) = 1;
1061               }
1062
1063           continue;
1064         }
1065
1066       get_stmt_operands (stmt);
1067       mark_new_vars = false;
1068       if (is_gimple_reg (SSA_NAME_VAR (var)))
1069         {
1070           if (TREE_CODE (stmt) == MODIFY_EXPR)
1071             {
1072               propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 0), repl);
1073               propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 1), repl);
1074             }
1075
1076           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1077             if (USE_FROM_PTR (use_p) == var)
1078               {
1079                 propagate_value (use_p, repl);
1080                 mark_new_vars = POINTER_TYPE_P (TREE_TYPE (repl));
1081               }
1082         }
1083       else
1084         {
1085           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, 
1086                                     SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
1087             if (USE_FROM_PTR (use_p) == var)
1088               propagate_value (use_p, repl);
1089         }
1090
1091       /* FIXME.  If REPL is a constant, we need to fold STMT.
1092          However, fold_stmt wants a pointer to the statement, because
1093          it may happen that it needs to replace the whole statement
1094          with a new expression.  Since the current def-use machinery
1095          does not return pointers to statements, we call fold_stmt
1096          with the address of a local temporary, if that call changes
1097          the temporary then we fallback on looking for a proper
1098          pointer to STMT by scanning STMT's basic block.
1099
1100          Note that all this will become unnecessary soon.  This
1101          pass is being replaced with a proper copy propagation pass
1102          for 4.1 (dnovillo, 2004-09-17).  */
1103       if (TREE_CODE (repl) != SSA_NAME)
1104         {
1105           tree tmp = stmt;
1106           fold_stmt (&tmp);
1107           mark_new_vars = true;
1108           if (tmp != stmt)
1109             {
1110               block_stmt_iterator si = bsi_for_stmt (stmt);
1111               mark_new_vars_to_rename (tmp, vars_to_rename);
1112               redirect_immediate_uses (stmt, tmp);
1113               bsi_replace (&si, tmp, true);
1114               stmt = bsi_stmt (si);
1115             }
1116         }
1117
1118       /* If REPL is a pointer, it may have different memory tags associated
1119          with it.  For instance, VAR may have had a name tag while REPL
1120          only had a type tag.  In these cases, the virtual operands (if
1121          any) in the statement will refer to different symbols which need
1122          to be renamed.  */
1123       if (mark_new_vars)
1124         mark_new_vars_to_rename (stmt, vars_to_rename);
1125       else
1126         modify_stmt (stmt);
1127     }
1128 }
1129
1130 /* Gets the value VAR is equivalent to according to EQ_TO.  */
1131
1132 static tree
1133 get_eq_name (tree *eq_to, tree var)
1134 {
1135   unsigned ver;
1136   tree val = var;
1137
1138   while (TREE_CODE (val) == SSA_NAME)
1139     {
1140       ver = SSA_NAME_VERSION (val);
1141       if (!eq_to[ver])
1142         break;
1143
1144       val = eq_to[ver];
1145     }
1146
1147   while (TREE_CODE (var) == SSA_NAME)
1148     {
1149       ver = SSA_NAME_VERSION (var);
1150       if (!eq_to[ver])
1151         break;
1152
1153       var = eq_to[ver];
1154       eq_to[ver] = val;
1155     }
1156
1157   return val;
1158 }
1159
1160 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1161    its result is redundant to to EQ_TO array.  */
1162
1163 static void
1164 check_phi_redundancy (tree phi, tree *eq_to)
1165 {
1166   tree val = NULL_TREE, def, res = PHI_RESULT (phi), stmt;
1167   unsigned i, ver = SSA_NAME_VERSION (res), n;
1168   dataflow_t df;
1169
1170   /* It is unlikely that such large phi node would be redundant.  */
1171   if (PHI_NUM_ARGS (phi) > 16)
1172     return;
1173
1174   for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
1175     {
1176       def = PHI_ARG_DEF (phi, i);
1177
1178       if (TREE_CODE (def) == SSA_NAME)
1179         {
1180           def = get_eq_name (eq_to, def);
1181           if (def == res)
1182             continue;
1183         }
1184
1185       if (val
1186           && !operand_equal_for_phi_arg_p (val, def))
1187         return;
1188
1189       val = def;
1190     }
1191
1192   /* At least one of the arguments should not be equal to the result, or
1193      something strange is happening.  */
1194   gcc_assert (val);
1195
1196   if (get_eq_name (eq_to, res) == val)
1197     return;
1198
1199   if (!may_propagate_copy (res, val))
1200     return;
1201
1202   eq_to[ver] = val;
1203
1204   df = get_immediate_uses (SSA_NAME_DEF_STMT (res));
1205   n = num_immediate_uses (df);
1206
1207   for (i = 0; i < n; i++)
1208     {
1209       stmt = immediate_use (df, i);
1210
1211       if (TREE_CODE (stmt) == PHI_NODE)
1212         check_phi_redundancy (stmt, eq_to);
1213     }
1214 }
1215
1216 /* Removes redundant phi nodes.
1217
1218    A redundant PHI node is a PHI node where all of its PHI arguments
1219    are the same value, excluding any PHI arguments which are the same
1220    as the PHI result.
1221
1222    A redundant PHI node is effectively a copy, so we forward copy propagate
1223    which removes all uses of the destination of the PHI node then
1224    finally we delete the redundant PHI node.
1225
1226    Note that if we can not copy propagate the PHI node, then the PHI
1227    will not be removed.  Thus we do not have to worry about dependencies
1228    between PHIs and the problems serializing PHIs into copies creates. 
1229    
1230    The most important effect of this pass is to remove degenerate PHI
1231    nodes created by removing unreachable code.  */
1232
1233 void
1234 kill_redundant_phi_nodes (void)
1235 {
1236   tree *eq_to;
1237   unsigned i, old_num_ssa_names;
1238   basic_block bb;
1239   tree phi, var, repl, stmt;
1240
1241   /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1242      replaced.  If EQ_TO[VER] is ssa name and it is decided to replace it by
1243      other value, it may be necessary to follow the chain till the final value.
1244      We perform path shortening (replacing the entries of the EQ_TO array with
1245      heads of these chains) whenever we access the field to prevent quadratic
1246      complexity (probably would not occur in practice anyway, but let us play
1247      it safe).  */
1248   eq_to = xcalloc (num_ssa_names, sizeof (tree));
1249
1250   /* We have had cases where computing immediate uses takes a
1251      significant amount of compile time.  If we run into such
1252      problems here, we may want to only compute immediate uses for
1253      a subset of all the SSA_NAMEs instead of computing it for
1254      all of the SSA_NAMEs.  */
1255   compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
1256   old_num_ssa_names = num_ssa_names;
1257
1258   FOR_EACH_BB (bb)
1259     {
1260       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1261         {
1262           var = PHI_RESULT (phi);
1263           check_phi_redundancy (phi, eq_to);
1264         }
1265     }
1266
1267   /* Now propagate the values.  */
1268   for (i = 0; i < old_num_ssa_names; i++)
1269     {
1270       if (!ssa_name (i))
1271         continue;
1272
1273       repl = get_eq_name (eq_to, ssa_name (i));
1274       if (repl != ssa_name (i))
1275         replace_immediate_uses (ssa_name (i), repl);
1276     }
1277
1278   /* And remove the dead phis.  */
1279   for (i = 0; i < old_num_ssa_names; i++)
1280     {
1281       if (!ssa_name (i))
1282         continue;
1283
1284       repl = get_eq_name (eq_to, ssa_name (i));
1285       if (repl != ssa_name (i))
1286         {
1287           stmt = SSA_NAME_DEF_STMT (ssa_name (i));
1288           remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
1289         }
1290     }
1291
1292   free_df ();
1293   free (eq_to);
1294 }
1295
1296 struct tree_opt_pass pass_redundant_phi =
1297 {
1298   "redphi",                             /* name */
1299   NULL,                                 /* gate */
1300   kill_redundant_phi_nodes,             /* execute */
1301   NULL,                                 /* sub */
1302   NULL,                                 /* next */
1303   0,                                    /* static_pass_number */
1304   TV_TREE_REDPHI,                       /* tv_id */
1305   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1306   0,                                    /* properties_provided */
1307   0,                                    /* properties_destroyed */
1308   0,                                    /* todo_flags_start */
1309   TODO_dump_func | TODO_rename_vars 
1310     | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
1311   0                                     /* letter */
1312 };
1313 \f
1314 /* Emit warnings for uninitialized variables.  This is done in two passes.
1315
1316    The first pass notices real uses of SSA names with default definitions.
1317    Such uses are unconditionally uninitialized, and we can be certain that
1318    such a use is a mistake.  This pass is run before most optimizations,
1319    so that we catch as many as we can.
1320
1321    The second pass follows PHI nodes to find uses that are potentially
1322    uninitialized.  In this case we can't necessarily prove that the use
1323    is really uninitialized.  This pass is run after most optimizations,
1324    so that we thread as many jumps and possible, and delete as much dead
1325    code as possible, in order to reduce false positives.  We also look
1326    again for plain uninitialized variables, since optimization may have
1327    changed conditionally uninitialized to unconditionally uninitialized.  */
1328
1329 /* Emit a warning for T, an SSA_NAME, being uninitialized.  The exact
1330    warning text is in MSGID and LOCUS may contain a location or be null.  */
1331
1332 static void
1333 warn_uninit (tree t, const char *msgid, location_t *locus)
1334 {
1335   tree var = SSA_NAME_VAR (t);
1336   tree def = SSA_NAME_DEF_STMT (t);
1337
1338   /* Default uses (indicated by an empty definition statement),
1339      are uninitialized.  */
1340   if (!IS_EMPTY_STMT (def))
1341     return;
1342
1343   /* Except for PARMs of course, which are always initialized.  */
1344   if (TREE_CODE (var) == PARM_DECL)
1345     return;
1346
1347   /* Hard register variables get their initial value from the ether.  */
1348   if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1349     return;
1350
1351   /* TREE_NO_WARNING either means we already warned, or the front end
1352      wishes to suppress the warning.  */
1353   if (TREE_NO_WARNING (var))
1354     return;
1355
1356   if (!locus)
1357     locus = &DECL_SOURCE_LOCATION (var);
1358   warning (msgid, locus, var);
1359   TREE_NO_WARNING (var) = 1;
1360 }
1361    
1362 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1363    and warn about them.  */
1364
1365 static tree
1366 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
1367 {
1368   location_t *locus = data;
1369   tree t = *tp;
1370
1371   /* We only do data flow with SSA_NAMEs, so that's all we can warn about.  */
1372   if (TREE_CODE (t) == SSA_NAME)
1373     {
1374       warn_uninit (t, "%H%qD is used uninitialized in this function", locus);
1375       *walk_subtrees = 0;
1376     }
1377   else if (IS_TYPE_OR_DECL_P (t))
1378     *walk_subtrees = 0;
1379
1380   return NULL_TREE;
1381 }
1382
1383 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1384    and warn about them.  */
1385
1386 static void
1387 warn_uninitialized_phi (tree phi)
1388 {
1389   int i, n = PHI_NUM_ARGS (phi);
1390
1391   /* Don't look at memory tags.  */
1392   if (!is_gimple_reg (PHI_RESULT (phi)))
1393     return;
1394
1395   for (i = 0; i < n; ++i)
1396     {
1397       tree op = PHI_ARG_DEF (phi, i);
1398       if (TREE_CODE (op) == SSA_NAME)
1399         warn_uninit (op, "%H%qD may be used uninitialized in this function",
1400                      NULL);
1401     }
1402 }
1403
1404 static void
1405 execute_early_warn_uninitialized (void)
1406 {
1407   block_stmt_iterator bsi;
1408   basic_block bb;
1409
1410   FOR_EACH_BB (bb)
1411     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1412       walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1413                  EXPR_LOCUS (bsi_stmt (bsi)), NULL);
1414 }
1415
1416 static void
1417 execute_late_warn_uninitialized (void)
1418 {
1419   basic_block bb;
1420   tree phi;
1421
1422   /* Re-do the plain uninitialized variable check, as optimization may have
1423      straightened control flow.  Do this first so that we don't accidentally
1424      get a "may be" warning when we'd have seen an "is" warning later.  */
1425   execute_early_warn_uninitialized ();
1426
1427   FOR_EACH_BB (bb)
1428     for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1429       warn_uninitialized_phi (phi);
1430 }
1431
1432 static bool
1433 gate_warn_uninitialized (void)
1434 {
1435   return warn_uninitialized != 0;
1436 }
1437
1438 struct tree_opt_pass pass_early_warn_uninitialized =
1439 {
1440   NULL,                                 /* name */
1441   gate_warn_uninitialized,              /* gate */
1442   execute_early_warn_uninitialized,     /* execute */
1443   NULL,                                 /* sub */
1444   NULL,                                 /* next */
1445   0,                                    /* static_pass_number */
1446   0,                                    /* tv_id */
1447   PROP_ssa,                             /* properties_required */
1448   0,                                    /* properties_provided */
1449   0,                                    /* properties_destroyed */
1450   0,                                    /* todo_flags_start */
1451   0,                                    /* todo_flags_finish */
1452   0                                     /* letter */
1453 };
1454
1455 struct tree_opt_pass pass_late_warn_uninitialized =
1456 {
1457   NULL,                                 /* name */
1458   gate_warn_uninitialized,              /* gate */
1459   execute_late_warn_uninitialized,      /* execute */
1460   NULL,                                 /* sub */
1461   NULL,                                 /* next */
1462   0,                                    /* static_pass_number */
1463   0,                                    /* tv_id */
1464   PROP_ssa,                             /* properties_required */
1465   0,                                    /* properties_provided */
1466   0,                                    /* properties_destroyed */
1467   0,                                    /* todo_flags_start */
1468   0,                                    /* todo_flags_finish */
1469   0                                     /* letter */
1470 };
1471