OSDN Git Service

c4fbf8a8ab1f7bb24f92fd191b75cbfaf15fc198
[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, 51 Franklin Street, Fifth Floor,
19 Boston, MA 02110-1301, 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 "expr.h"
35 #include "function.h"
36 #include "diagnostic.h"
37 #include "bitmap.h"
38 #include "pointer-set.h"
39 #include "tree-flow.h"
40 #include "tree-gimple.h"
41 #include "tree-inline.h"
42 #include "varray.h"
43 #include "timevar.h"
44 #include "hashtab.h"
45 #include "tree-dump.h"
46 #include "tree-pass.h"
47 #include "toplev.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;
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 = PHI_CHAIN (phi))
62     {
63       if (PHI_ARG_DEF (phi, e->dest_idx) == NULL_TREE)
64         continue;
65
66       src = PHI_ARG_DEF (phi, e->dest_idx);
67       dst = PHI_RESULT (phi);
68       node = build_tree_list (dst, src);
69       *last = node;
70       last = &TREE_CHAIN (node);
71     }
72
73   e = redirect_edge_succ_nodup (e, dest);
74   PENDING_STMT (e) = list;
75
76   return e;
77 }
78
79 /* Add PHI arguments queued in PENDINT_STMT list on edge E to edge
80    E->dest.  */
81
82 void
83 flush_pending_stmts (edge e)
84 {
85   tree phi, arg;
86
87   if (!PENDING_STMT (e))
88     return;
89
90   for (phi = phi_nodes (e->dest), arg = PENDING_STMT (e);
91        phi;
92        phi = PHI_CHAIN (phi), arg = TREE_CHAIN (arg))
93     {
94       tree def = TREE_VALUE (arg);
95       add_phi_arg (phi, def, e);
96     }
97
98   PENDING_STMT (e) = NULL;
99 }
100
101 /* Return true if SSA_NAME is malformed and mark it visited.
102
103    IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
104       operand.  */
105
106 static bool
107 verify_ssa_name (tree ssa_name, bool is_virtual)
108 {
109   if (TREE_CODE (ssa_name) != SSA_NAME)
110     {
111       error ("Expected an SSA_NAME object");
112       return true;
113     }
114
115   if (TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name)))
116     {
117       error ("Type mismatch between an SSA_NAME and its symbol.");
118       return true;
119     }
120
121   if (SSA_NAME_IN_FREE_LIST (ssa_name))
122     {
123       error ("Found an SSA_NAME that had been released into the free pool");
124       return true;
125     }
126
127   if (is_virtual && is_gimple_reg (ssa_name))
128     {
129       error ("Found a virtual definition for a GIMPLE register");
130       return true;
131     }
132
133   if (!is_virtual && !is_gimple_reg (ssa_name))
134     {
135       error ("Found a real definition for a non-register");
136       return true;
137     }
138
139   if (is_virtual && var_ann (SSA_NAME_VAR (ssa_name)) 
140       && get_subvars_for_var (SSA_NAME_VAR (ssa_name)) != NULL)
141     {
142       error ("Found real variable when subvariables should have appeared");
143       return true;
144     }
145
146   return false;
147 }
148
149
150 /* Return true if the definition of SSA_NAME at block BB is malformed.
151
152    STMT is the statement where SSA_NAME is created.
153
154    DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
155       version numbers.  If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
156       it means that the block in that array slot contains the
157       definition of SSA_NAME.
158
159    IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
160       V_MUST_DEF.  */
161
162 static bool
163 verify_def (basic_block bb, basic_block *definition_block, tree ssa_name,
164             tree stmt, bool is_virtual)
165 {
166   if (verify_ssa_name (ssa_name, is_virtual))
167     goto err;
168
169   if (definition_block[SSA_NAME_VERSION (ssa_name)])
170     {
171       error ("SSA_NAME created in two different blocks %i and %i",
172              definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index);
173       goto err;
174     }
175
176   definition_block[SSA_NAME_VERSION (ssa_name)] = bb;
177
178   if (SSA_NAME_DEF_STMT (ssa_name) != stmt)
179     {
180       error ("SSA_NAME_DEF_STMT is wrong");
181       fprintf (stderr, "Expected definition statement:\n");
182       print_generic_stmt (stderr, SSA_NAME_DEF_STMT (ssa_name), TDF_VOPS);
183       fprintf (stderr, "\nActual definition statement:\n");
184       print_generic_stmt (stderr, stmt, TDF_VOPS);
185       goto err;
186     }
187
188   return false;
189
190 err:
191   fprintf (stderr, "while verifying SSA_NAME ");
192   print_generic_expr (stderr, ssa_name, 0);
193   fprintf (stderr, " in statement\n");
194   print_generic_stmt (stderr, stmt, TDF_VOPS);
195
196   return true;
197 }
198
199
200 /* Return true if the use of SSA_NAME at statement STMT in block BB is
201    malformed.
202
203    DEF_BB is the block where SSA_NAME was found to be created.
204
205    IDOM contains immediate dominator information for the flowgraph.
206
207    CHECK_ABNORMAL is true if the caller wants to check whether this use
208       is flowing through an abnormal edge (only used when checking PHI
209       arguments).
210
211    IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
212       V_MUST_DEF.
213    
214    If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
215      that are defined before STMT in basic block BB.  */
216
217 static bool
218 verify_use (basic_block bb, basic_block def_bb, use_operand_p use_p,
219             tree stmt, bool check_abnormal, bool is_virtual,
220             bitmap names_defined_in_bb)
221 {
222   bool err = false;
223   tree ssa_name = USE_FROM_PTR (use_p);
224
225   err = verify_ssa_name (ssa_name, is_virtual);
226
227   if (!TREE_VISITED (ssa_name))
228     if (verify_imm_links (stderr, ssa_name))
229       err = true;
230
231   TREE_VISITED (ssa_name) = 1;
232
233   if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name))
234       && var_ann (SSA_NAME_VAR (ssa_name))->default_def == ssa_name)
235     ; /* Default definitions have empty statements.  Nothing to do.  */
236   else if (!def_bb)
237     {
238       error ("Missing definition");
239       err = true;
240     }
241   else if (bb != def_bb
242            && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
243     {
244       error ("Definition in block %i does not dominate use in block %i",
245              def_bb->index, bb->index);
246       err = true;
247     }
248   else if (bb == def_bb
249            && names_defined_in_bb != NULL
250            && !bitmap_bit_p (names_defined_in_bb, SSA_NAME_VERSION (ssa_name)))
251     {
252       error ("Definition in block %i follows the use", def_bb->index);
253       err = true;
254     }
255
256   if (check_abnormal
257       && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
258     {
259       error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
260       err = true;
261     }
262
263   /* Make sure the use is in an appropriate list by checking the previous 
264      element to make sure it's the same.  */
265   if (use_p->prev == NULL)
266     {
267       error ("No immediate_use list");
268       err = true;
269     }
270   else
271     {
272       tree listvar ;
273       if (use_p->prev->use == NULL)
274         listvar = use_p->prev->stmt;
275       else
276         listvar = USE_FROM_PTR (use_p->prev);
277       if (listvar != ssa_name)
278         {
279           error ("Wrong immediate use list");
280           err = true;
281         }
282     }
283
284   if (err)
285     {
286       fprintf (stderr, "for SSA_NAME: ");
287       print_generic_expr (stderr, ssa_name, TDF_VOPS);
288       fprintf (stderr, " in statement:\n");
289       print_generic_stmt (stderr, stmt, TDF_VOPS);
290     }
291
292   return err;
293 }
294
295
296 /* Return true if any of the arguments for PHI node PHI at block BB is
297    malformed.
298
299    DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
300       numbers.  If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
301       block in that array slot contains the definition of SSA_NAME.  */
302
303 static bool
304 verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)
305 {
306   edge e;
307   bool err = false;
308   unsigned i, phi_num_args = PHI_NUM_ARGS (phi);
309
310   if (EDGE_COUNT (bb->preds) != phi_num_args)
311     {
312       error ("Incoming edge count does not match number of PHI arguments\n");
313       err = true;
314       goto error;
315     }
316
317   for (i = 0; i < phi_num_args; i++)
318     {
319       use_operand_p op_p = PHI_ARG_DEF_PTR (phi, i);
320       tree op = USE_FROM_PTR (op_p);
321
322
323       e = EDGE_PRED (bb, i);
324
325       if (op == NULL_TREE)
326         {
327           error ("PHI argument is missing for edge %d->%d\n",
328                  e->src->index,
329                  e->dest->index);
330           err = true;
331           goto error;
332         }
333
334       if (TREE_CODE (op) != SSA_NAME && !is_gimple_min_invariant (op))
335         {
336           error ("PHI argument is not SSA_NAME, or invariant");
337           err = true;
338         }
339
340       if (TREE_CODE (op) == SSA_NAME)
341         err = verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op_p,
342                           phi, e->flags & EDGE_ABNORMAL,
343                           !is_gimple_reg (PHI_RESULT (phi)),
344                           NULL);
345
346       if (e->dest != bb)
347         {
348           error ("Wrong edge %d->%d for PHI argument\n",
349                  e->src->index, e->dest->index);
350           err = true;
351         }
352
353       if (err)
354         {
355           fprintf (stderr, "PHI argument\n");
356           print_generic_stmt (stderr, op, TDF_VOPS);
357           goto error;
358         }
359     }
360
361 error:
362   if (err)
363     {
364       fprintf (stderr, "for PHI node\n");
365       print_generic_stmt (stderr, phi, TDF_VOPS);
366     }
367
368
369   return err;
370 }
371
372
373 static void
374 verify_flow_insensitive_alias_info (void)
375 {
376   tree var;
377   bitmap visited = BITMAP_ALLOC (NULL);
378   referenced_var_iterator rvi;
379
380   FOR_EACH_REFERENCED_VAR (var, rvi)
381     {
382       size_t j;
383       var_ann_t ann;
384       varray_type may_aliases;
385
386       ann = var_ann (var);
387       may_aliases = ann->may_aliases;
388
389       for (j = 0; may_aliases && j < VARRAY_ACTIVE_SIZE (may_aliases); j++)
390         {
391           tree alias = VARRAY_TREE (may_aliases, j);
392
393           bitmap_set_bit (visited, DECL_UID (alias));
394
395           if (!may_be_aliased (alias))
396             {
397               error ("Non-addressable variable inside an alias set.");
398               debug_variable (alias);
399               goto err;
400             }
401         }
402     }
403
404   FOR_EACH_REFERENCED_VAR (var, rvi)
405     {
406       var_ann_t ann;
407       ann = var_ann (var);
408
409       if (ann->mem_tag_kind == NOT_A_TAG
410           && ann->is_alias_tag
411           && !bitmap_bit_p (visited, DECL_UID (var)))
412         {
413           error ("Addressable variable that is an alias tag but is not in any alias set.");
414           goto err;
415         }
416     }
417
418   BITMAP_FREE (visited);
419   return;
420
421 err:
422   debug_variable (var);
423   internal_error ("verify_flow_insensitive_alias_info failed.");
424 }
425
426
427 static void
428 verify_flow_sensitive_alias_info (void)
429 {
430   size_t i;
431   tree ptr;
432
433   for (i = 1; i < num_ssa_names; i++)
434     {
435       tree var;
436       var_ann_t ann;
437       struct ptr_info_def *pi;
438  
439
440       ptr = ssa_name (i);
441       if (!ptr)
442         continue;
443
444       /* We only care for pointers that are actually referenced in the
445          program.  */
446       if (!POINTER_TYPE_P (TREE_TYPE (ptr)) || !TREE_VISITED (ptr))
447         continue;
448
449       /* RESULT_DECL is special.  If it's a GIMPLE register, then it
450          is only written-to only once in the return statement.
451          Otherwise, aggregate RESULT_DECLs may be written-to more than
452          once in virtual operands.  */
453       var = SSA_NAME_VAR (ptr);
454       if (TREE_CODE (var) == RESULT_DECL
455           && is_gimple_reg (ptr))
456         continue;
457
458       pi = SSA_NAME_PTR_INFO (ptr);
459       if (pi == NULL)
460         continue;
461
462       ann = var_ann (var);
463       if (pi->is_dereferenced && !pi->name_mem_tag && !ann->type_mem_tag)
464         {
465           error ("Dereferenced pointers should have a name or a type tag");
466           goto err;
467         }
468
469       if (pi->name_mem_tag
470           && !pi->pt_malloc
471           && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars)))
472         {
473           error ("Pointers with a memory tag, should have points-to sets or point to malloc");
474           goto err;
475         }
476
477       if (pi->value_escapes_p
478           && pi->name_mem_tag
479           && !is_call_clobbered (pi->name_mem_tag))
480         {
481           error ("Pointer escapes but its name tag is not call-clobbered.");
482           goto err;
483         }
484     }
485
486   return;
487
488 err:
489   debug_variable (ptr);
490   internal_error ("verify_flow_sensitive_alias_info failed.");
491 }
492
493 DEF_VEC_P (bitmap);
494 DEF_VEC_ALLOC_P (bitmap,heap);
495
496 /* Verify that all name tags have different points to sets.
497    This algorithm takes advantage of the fact that every variable with the
498    same name tag must have the same points-to set. 
499    So we check a single variable for each name tag, and verify that its
500    points-to set is different from every other points-to set for other name
501    tags.
502
503    Additionally, given a pointer P_i with name tag NMT and type tag
504    TMT, this function verified the alias set of TMT is a superset of
505    the alias set of NMT.  */
506
507 static void
508 verify_name_tags (void)
509 {
510   size_t i;  
511   size_t j;
512   bitmap first, second;  
513   VEC(tree,heap) *name_tag_reps = NULL;
514   VEC(bitmap,heap) *pt_vars_for_reps = NULL;
515   bitmap type_aliases = BITMAP_ALLOC (NULL);
516
517   /* First we compute the name tag representatives and their points-to sets.  */
518   for (i = 0; i < num_ssa_names; i++)
519     {
520       struct ptr_info_def *pi;
521       tree tmt, ptr = ssa_name (i);
522
523       if (ptr == NULL_TREE)
524         continue;
525       
526       pi = SSA_NAME_PTR_INFO (ptr);
527
528       if (!TREE_VISITED (ptr) 
529           || !POINTER_TYPE_P (TREE_TYPE (ptr)) 
530           || !pi
531           || !pi->name_mem_tag 
532           || TREE_VISITED (pi->name_mem_tag))
533         continue;
534
535       TREE_VISITED (pi->name_mem_tag) = 1;
536
537       if (pi->pt_vars == NULL)
538         continue;
539
540       VEC_safe_push (tree, heap, name_tag_reps, ptr);
541       VEC_safe_push (bitmap, heap, pt_vars_for_reps, pi->pt_vars);
542
543       /* Verify that alias set of PTR's type tag is a superset of the
544          alias set of PTR's name tag.  */
545       tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
546       if (tmt)
547         {
548           size_t i;
549           varray_type aliases = var_ann (tmt)->may_aliases;
550           bitmap_clear (type_aliases);
551           for (i = 0; aliases && i < VARRAY_ACTIVE_SIZE (aliases); i++)
552             {
553               tree alias = VARRAY_TREE (aliases, i);
554               bitmap_set_bit (type_aliases, DECL_UID (alias));
555             }
556
557           /* When grouping, we may have added PTR's type tag into the
558              alias set of PTR's name tag.  To prevent a false
559              positive, pretend that TMT is in its own alias set.  */
560           bitmap_set_bit (type_aliases, DECL_UID (tmt));
561
562           if (bitmap_equal_p (type_aliases, pi->pt_vars))
563             continue;
564
565           if (!bitmap_intersect_compl_p (type_aliases, pi->pt_vars))
566             {
567               error ("Alias set of a pointer's type tag should be a superset of the corresponding name tag");
568               debug_variable (tmt);
569               debug_variable (pi->name_mem_tag);
570               goto err;
571             }
572         }
573     }
574   
575   /* Now compare all the representative bitmaps with all other representative
576      bitmaps, to verify that they are all different.  */
577   for (i = 0; VEC_iterate (bitmap, pt_vars_for_reps, i, first); i++)
578     {
579        for (j = i + 1; VEC_iterate (bitmap, pt_vars_for_reps, j, second); j++)
580          { 
581            if (bitmap_equal_p (first, second))
582              {
583                error ("Two different pointers with identical points-to sets but different name tags");
584                debug_variable (VEC_index (tree, name_tag_reps, j));
585                goto err;
586              }
587          }
588     }
589
590   /* Lastly, clear out the visited flags.  */
591   for (i = 0; i < num_ssa_names; i++)
592     {
593       if (ssa_name (i))
594         {
595           tree ptr = ssa_name (i);
596           struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
597           if (!TREE_VISITED (ptr) 
598               || !POINTER_TYPE_P (TREE_TYPE (ptr)) 
599               || !pi
600               || !pi->name_mem_tag)
601             continue;
602           TREE_VISITED (pi->name_mem_tag) = 0;
603         }
604     } 
605
606   /* We do not have to free the bitmaps or trees in the vectors, as
607      they are not owned by us.  */
608   VEC_free (bitmap, heap, pt_vars_for_reps);
609   VEC_free (tree, heap, name_tag_reps);
610   BITMAP_FREE (type_aliases);
611   return;
612   
613 err:
614   debug_variable (VEC_index (tree, name_tag_reps, i));
615   internal_error ("verify_name_tags failed");
616 }
617
618
619 /* Verify the consistency of aliasing information.  */
620
621 static void
622 verify_alias_info (void)
623 {
624   verify_flow_sensitive_alias_info ();
625   verify_name_tags ();
626   verify_flow_insensitive_alias_info ();
627 }
628
629
630 /* Verify common invariants in the SSA web.
631    TODO: verify the variable annotations.  */
632
633 void
634 verify_ssa (bool check_modified_stmt)
635 {
636   size_t i;
637   basic_block bb;
638   basic_block *definition_block = xcalloc (num_ssa_names, sizeof (basic_block));
639   ssa_op_iter iter;
640   tree op;
641   enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS];
642   bitmap names_defined_in_bb = BITMAP_ALLOC (NULL);
643
644   gcc_assert (!need_ssa_update_p ());
645
646   verify_stmts ();
647
648   timevar_push (TV_TREE_SSA_VERIFY);
649
650   /* Keep track of SSA names present in the IL.  */
651   for (i = 1; i < num_ssa_names; i++)
652     {
653       tree name = ssa_name (i);
654       if (name)
655         {
656           tree stmt;
657           TREE_VISITED (name) = 0;
658
659           stmt = SSA_NAME_DEF_STMT (name);
660           if (!IS_EMPTY_STMT (stmt))
661             {
662               basic_block bb = bb_for_stmt (stmt);
663               verify_def (bb, definition_block,
664                           name, stmt, !is_gimple_reg (name));
665
666             }
667         }
668     }
669
670   calculate_dominance_info (CDI_DOMINATORS);
671
672   /* Now verify all the uses and make sure they agree with the definitions
673      found in the previous pass.  */
674   FOR_EACH_BB (bb)
675     {
676       edge e;
677       tree phi;
678       edge_iterator ei;
679       block_stmt_iterator bsi;
680
681       /* Make sure that all edges have a clear 'aux' field.  */
682       FOR_EACH_EDGE (e, ei, bb->preds)
683         {
684           if (e->aux)
685             {
686               error ("AUX pointer initialized for edge %d->%d\n", e->src->index,
687                       e->dest->index);
688               goto err;
689             }
690         }
691
692       /* Verify the arguments for every PHI node in the block.  */
693       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
694         {
695           if (verify_phi_args (phi, bb, definition_block))
696             goto err;
697           bitmap_set_bit (names_defined_in_bb,
698                           SSA_NAME_VERSION (PHI_RESULT (phi)));
699         }
700
701       /* Now verify all the uses and vuses in every statement of the block.  */
702       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
703         {
704           tree stmt = bsi_stmt (bsi);
705           use_operand_p use_p;
706
707           if (check_modified_stmt && stmt_modified_p (stmt))
708             {
709               error ("Stmt (%p) marked modified after optimization pass : ",
710                      (void *)stmt);
711               print_generic_stmt (stderr, stmt, TDF_VOPS);
712               goto err;
713             }
714
715           if (TREE_CODE (stmt) == MODIFY_EXPR
716               && TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
717             {
718               tree lhs, base_address;
719
720               lhs = TREE_OPERAND (stmt, 0);
721               base_address = get_base_address (lhs);
722
723               if (base_address
724                   && SSA_VAR_P (base_address)
725                   && ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF))
726                 {
727                   error ("Statement makes a memory store, but has no "
728                          "V_MAY_DEFS nor V_MUST_DEFS");
729                   print_generic_stmt (stderr, stmt, TDF_VOPS);
730                   goto err;
731                 }
732             }
733
734
735           if (stmt_ann (stmt)->makes_aliased_stores 
736               && ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF))
737             {
738               error ("Statement makes aliased stores, but has no V_MAY_DEFS");
739               print_generic_stmt (stderr, stmt, TDF_VOPS);
740               goto err;
741             }
742
743           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
744                                     SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
745             {
746               op = USE_FROM_PTR (use_p);
747               if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
748                               use_p, stmt, false, !is_gimple_reg (op),
749                               names_defined_in_bb))
750                 goto err;
751             }
752
753           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
754             bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
755         }
756
757       bitmap_clear (names_defined_in_bb);
758     }
759
760   /* Finally, verify alias information.  */
761   verify_alias_info ();
762
763   free (definition_block);
764
765   /* Restore the dominance information to its prior known state, so
766      that we do not perturb the compiler's subsequent behavior.  */
767   if (orig_dom_state == DOM_NONE)
768     free_dominance_info (CDI_DOMINATORS);
769   else
770     dom_computed[CDI_DOMINATORS] = orig_dom_state;
771   
772   BITMAP_FREE (names_defined_in_bb);
773   timevar_pop (TV_TREE_SSA_VERIFY);
774   return;
775
776 err:
777   internal_error ("verify_ssa failed.");
778 }
779
780 /* Return true if the uid in both int tree maps are equal.  */
781
782 int
783 int_tree_map_eq (const void *va, const void *vb)
784 {
785   const struct int_tree_map  *a = va, *b = vb;
786   return (a->uid == b->uid);
787 }
788
789 /* Hash a UID in a int_tree_map.  */
790
791 unsigned int
792 int_tree_map_hash (const void *item)
793 {
794   return ((const struct int_tree_map *)item)->uid;
795 }
796
797
798 /* Initialize global DFA and SSA structures.  */
799
800 void
801 init_tree_ssa (void)
802 {
803   referenced_vars = htab_create_ggc (20, int_tree_map_hash, 
804                                      int_tree_map_eq, NULL);
805   call_clobbered_vars = BITMAP_ALLOC (NULL);
806   addressable_vars = BITMAP_ALLOC (NULL);
807   init_ssanames ();
808   init_phinodes ();
809   global_var = NULL_TREE;
810   aliases_computed_p = false;
811 }
812
813
814 /* Deallocate memory associated with SSA data structures for FNDECL.  */
815
816 void
817 delete_tree_ssa (void)
818 {
819   size_t i;
820   basic_block bb;
821   block_stmt_iterator bsi;
822   referenced_var_iterator rvi;
823   tree var;
824
825   /* Release any ssa_names still in use.  */
826   for (i = 0; i < num_ssa_names; i++)
827     {
828       tree var = ssa_name (i);
829       if (var && TREE_CODE (var) == SSA_NAME)
830         {
831           SSA_NAME_IMM_USE_NODE (var).prev = &(SSA_NAME_IMM_USE_NODE (var));
832           SSA_NAME_IMM_USE_NODE (var).next = &(SSA_NAME_IMM_USE_NODE (var));
833         }
834       release_ssa_name (var);
835     }
836
837   /* Remove annotations from every tree in the function.  */
838   FOR_EACH_BB (bb)
839     {
840       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
841         {
842           tree stmt = bsi_stmt (bsi);
843           stmt_ann_t ann = get_stmt_ann (stmt);
844
845           free_ssa_operands (&ann->operands);
846           ann->addresses_taken = 0;
847           mark_stmt_modified (stmt);
848         }
849       set_phi_nodes (bb, NULL);
850     }
851
852   /* Remove annotations from every referenced variable.  */
853   FOR_EACH_REFERENCED_VAR (var, rvi)
854     {
855       ggc_free (var->common.ann);
856       var->common.ann = NULL;
857     }
858   htab_delete (referenced_vars);
859   referenced_vars = NULL;
860
861   fini_ssanames ();
862   fini_phinodes ();
863
864   global_var = NULL_TREE;
865   BITMAP_FREE (call_clobbered_vars);
866   call_clobbered_vars = NULL;
867   BITMAP_FREE (addressable_vars);
868   addressable_vars = NULL;
869   modified_noreturn_calls = NULL;
870   aliases_computed_p = false;
871   gcc_assert (!need_ssa_update_p ());
872 }
873
874
875 /* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a
876    useless type conversion, otherwise return false.  */
877
878 bool
879 tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
880 {
881   if (inner_type == outer_type)
882     return true;
883
884   /* Changes in machine mode are never useless conversions.  */
885   if (TYPE_MODE (inner_type) != TYPE_MODE (outer_type))
886     return false;
887
888   /* If the inner and outer types are effectively the same, then
889      strip the type conversion and enter the equivalence into
890      the table.  */
891   if (lang_hooks.types_compatible_p (inner_type, outer_type))
892     return true;
893
894   /* If both types are pointers and the outer type is a (void *), then
895      the conversion is not necessary.  The opposite is not true since
896      that conversion would result in a loss of information if the
897      equivalence was used.  Consider an indirect function call where
898      we need to know the exact type of the function to correctly
899      implement the ABI.  */
900   else if (POINTER_TYPE_P (inner_type)
901            && POINTER_TYPE_P (outer_type)
902            && TYPE_REF_CAN_ALIAS_ALL (inner_type)
903               == TYPE_REF_CAN_ALIAS_ALL (outer_type)
904            && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
905     return true;
906
907   /* Pointers/references are equivalent if their pointed to types
908      are effectively the same.  This allows to strip conversions between
909      pointer types with different type qualifiers.  */
910   else if (POINTER_TYPE_P (inner_type)
911            && POINTER_TYPE_P (outer_type)
912            && TYPE_REF_CAN_ALIAS_ALL (inner_type)
913               == TYPE_REF_CAN_ALIAS_ALL (outer_type)
914            && lang_hooks.types_compatible_p (TREE_TYPE (inner_type),
915                                              TREE_TYPE (outer_type)))
916     return true;
917
918   /* If both the inner and outer types are integral types, then the
919      conversion is not necessary if they have the same mode and
920      signedness and precision, and both or neither are boolean.  Some
921      code assumes an invariant that boolean types stay boolean and do
922      not become 1-bit bit-field types.  Note that types with precision
923      not using all bits of the mode (such as bit-field types in C)
924      mean that testing of precision is necessary.  */
925   else if (INTEGRAL_TYPE_P (inner_type)
926            && INTEGRAL_TYPE_P (outer_type)
927            && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
928            && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type)
929            && simple_cst_equal (TYPE_MAX_VALUE (inner_type), TYPE_MAX_VALUE (outer_type))
930            && simple_cst_equal (TYPE_MIN_VALUE (inner_type), TYPE_MIN_VALUE (outer_type)))
931     {
932       bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE);
933       bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE);
934       if (first_boolean == second_boolean)
935         return true;
936     }
937
938   /* Recurse for complex types.  */
939   else if (TREE_CODE (inner_type) == COMPLEX_TYPE
940            && TREE_CODE (outer_type) == COMPLEX_TYPE
941            && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
942                                                   TREE_TYPE (inner_type)))
943     return true;
944
945   return false;
946 }
947
948 /* Return true if EXPR is a useless type conversion, otherwise return
949    false.  */
950
951 bool
952 tree_ssa_useless_type_conversion (tree expr)
953 {
954   /* If we have an assignment that merely uses a NOP_EXPR to change
955      the top of the RHS to the type of the LHS and the type conversion
956      is "safe", then strip away the type conversion so that we can
957      enter LHS = RHS into the const_and_copies table.  */
958   if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR
959       || TREE_CODE (expr) == VIEW_CONVERT_EXPR
960       || TREE_CODE (expr) == NON_LVALUE_EXPR)
961     return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
962                                                TREE_TYPE (TREE_OPERAND (expr,
963                                                                         0)));
964
965
966   return false;
967 }
968
969 /* Returns true if statement STMT may read memory.  */
970
971 bool
972 stmt_references_memory_p (tree stmt)
973 {
974   stmt_ann_t ann = stmt_ann (stmt);
975
976   if (ann->has_volatile_ops)
977     return true;
978
979   return (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS));
980 }
981
982 /* Internal helper for walk_use_def_chains.  VAR, FN and DATA are as
983    described in walk_use_def_chains.
984    
985    VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
986       infinite loops.  We used to have a bitmap for this to just mark
987       SSA versions we had visited.  But non-sparse bitmaps are way too
988       expensive, while sparse bitmaps may cause quadratic behavior.
989
990    IS_DFS is true if the caller wants to perform a depth-first search
991       when visiting PHI nodes.  A DFS will visit each PHI argument and
992       call FN after each one.  Otherwise, all the arguments are
993       visited first and then FN is called with each of the visited
994       arguments in a separate pass.  */
995
996 static bool
997 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
998                        struct pointer_set_t *visited, bool is_dfs)
999 {
1000   tree def_stmt;
1001
1002   if (pointer_set_insert (visited, var))
1003     return false;
1004
1005   def_stmt = SSA_NAME_DEF_STMT (var);
1006
1007   if (TREE_CODE (def_stmt) != PHI_NODE)
1008     {
1009       /* If we reached the end of the use-def chain, call FN.  */
1010       return fn (var, def_stmt, data);
1011     }
1012   else
1013     {
1014       int i;
1015
1016       /* When doing a breadth-first search, call FN before following the
1017          use-def links for each argument.  */
1018       if (!is_dfs)
1019         for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1020           if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
1021             return true;
1022
1023       /* Follow use-def links out of each PHI argument.  */
1024       for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1025         {
1026           tree arg = PHI_ARG_DEF (def_stmt, i);
1027           if (TREE_CODE (arg) == SSA_NAME
1028               && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
1029             return true;
1030         }
1031
1032       /* When doing a depth-first search, call FN after following the
1033          use-def links for each argument.  */
1034       if (is_dfs)
1035         for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1036           if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
1037             return true;
1038     }
1039   
1040   return false;
1041 }
1042   
1043
1044
1045 /* Walk use-def chains starting at the SSA variable VAR.  Call
1046    function FN at each reaching definition found.  FN takes three
1047    arguments: VAR, its defining statement (DEF_STMT) and a generic
1048    pointer to whatever state information that FN may want to maintain
1049    (DATA).  FN is able to stop the walk by returning true, otherwise
1050    in order to continue the walk, FN should return false.  
1051
1052    Note, that if DEF_STMT is a PHI node, the semantics are slightly
1053    different.  The first argument to FN is no longer the original
1054    variable VAR, but the PHI argument currently being examined.  If FN
1055    wants to get at VAR, it should call PHI_RESULT (PHI).
1056
1057    If IS_DFS is true, this function will:
1058
1059         1- walk the use-def chains for all the PHI arguments, and,
1060         2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
1061
1062    If IS_DFS is false, the two steps above are done in reverse order
1063    (i.e., a breadth-first search).  */
1064
1065
1066 void
1067 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
1068                      bool is_dfs)
1069 {
1070   tree def_stmt;
1071
1072   gcc_assert (TREE_CODE (var) == SSA_NAME);
1073
1074   def_stmt = SSA_NAME_DEF_STMT (var);
1075
1076   /* We only need to recurse if the reaching definition comes from a PHI
1077      node.  */
1078   if (TREE_CODE (def_stmt) != PHI_NODE)
1079     (*fn) (var, def_stmt, data);
1080   else
1081     {
1082       struct pointer_set_t *visited = pointer_set_create ();
1083       walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
1084       pointer_set_destroy (visited);
1085     }
1086 }
1087
1088 \f
1089 /* Emit warnings for uninitialized variables.  This is done in two passes.
1090
1091    The first pass notices real uses of SSA names with default definitions.
1092    Such uses are unconditionally uninitialized, and we can be certain that
1093    such a use is a mistake.  This pass is run before most optimizations,
1094    so that we catch as many as we can.
1095
1096    The second pass follows PHI nodes to find uses that are potentially
1097    uninitialized.  In this case we can't necessarily prove that the use
1098    is really uninitialized.  This pass is run after most optimizations,
1099    so that we thread as many jumps and possible, and delete as much dead
1100    code as possible, in order to reduce false positives.  We also look
1101    again for plain uninitialized variables, since optimization may have
1102    changed conditionally uninitialized to unconditionally uninitialized.  */
1103
1104 /* Emit a warning for T, an SSA_NAME, being uninitialized.  The exact
1105    warning text is in MSGID and LOCUS may contain a location or be null.  */
1106
1107 static void
1108 warn_uninit (tree t, const char *gmsgid, void *data)
1109 {
1110   tree var = SSA_NAME_VAR (t);
1111   tree def = SSA_NAME_DEF_STMT (t);
1112   tree context = (tree) data;
1113   location_t * locus;
1114
1115   /* Default uses (indicated by an empty definition statement),
1116      are uninitialized.  */
1117   if (!IS_EMPTY_STMT (def))
1118     return;
1119
1120   /* Except for PARMs of course, which are always initialized.  */
1121   if (TREE_CODE (var) == PARM_DECL)
1122     return;
1123
1124   /* Hard register variables get their initial value from the ether.  */
1125   if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1126     return;
1127
1128   /* TREE_NO_WARNING either means we already warned, or the front end
1129      wishes to suppress the warning.  */
1130   if (TREE_NO_WARNING (var))
1131     return;
1132
1133   locus = (context != NULL && EXPR_HAS_LOCATION (context)
1134            ? EXPR_LOCUS (context)
1135            : &DECL_SOURCE_LOCATION (var));
1136   warning (0, gmsgid, locus, var);
1137   TREE_NO_WARNING (var) = 1;
1138 }
1139    
1140 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1141    and warn about them.  */
1142
1143 static tree
1144 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
1145 {
1146   tree t = *tp;
1147
1148   /* We only do data flow with SSA_NAMEs, so that's all we can warn about.  */
1149   if (TREE_CODE (t) == SSA_NAME)
1150     {
1151       warn_uninit (t, "%H%qD is used uninitialized in this function", data);
1152       *walk_subtrees = 0;
1153     }
1154   else if (IS_TYPE_OR_DECL_P (t))
1155     *walk_subtrees = 0;
1156
1157   return NULL_TREE;
1158 }
1159
1160 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1161    and warn about them.  */
1162
1163 static void
1164 warn_uninitialized_phi (tree phi)
1165 {
1166   int i, n = PHI_NUM_ARGS (phi);
1167
1168   /* Don't look at memory tags.  */
1169   if (!is_gimple_reg (PHI_RESULT (phi)))
1170     return;
1171
1172   for (i = 0; i < n; ++i)
1173     {
1174       tree op = PHI_ARG_DEF (phi, i);
1175       if (TREE_CODE (op) == SSA_NAME)
1176         warn_uninit (op, "%H%qD may be used uninitialized in this function",
1177                      NULL);
1178     }
1179 }
1180
1181 static void
1182 execute_early_warn_uninitialized (void)
1183 {
1184   block_stmt_iterator bsi;
1185   basic_block bb;
1186
1187   FOR_EACH_BB (bb)
1188     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1189       {
1190         tree context = bsi_stmt (bsi);
1191         walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1192                    context, NULL);
1193       }
1194 }
1195
1196 static void
1197 execute_late_warn_uninitialized (void)
1198 {
1199   basic_block bb;
1200   tree phi;
1201
1202   /* Re-do the plain uninitialized variable check, as optimization may have
1203      straightened control flow.  Do this first so that we don't accidentally
1204      get a "may be" warning when we'd have seen an "is" warning later.  */
1205   execute_early_warn_uninitialized ();
1206
1207   FOR_EACH_BB (bb)
1208     for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1209       warn_uninitialized_phi (phi);
1210 }
1211
1212 static bool
1213 gate_warn_uninitialized (void)
1214 {
1215   return warn_uninitialized != 0;
1216 }
1217
1218 struct tree_opt_pass pass_early_warn_uninitialized =
1219 {
1220   NULL,                                 /* name */
1221   gate_warn_uninitialized,              /* gate */
1222   execute_early_warn_uninitialized,     /* execute */
1223   NULL,                                 /* sub */
1224   NULL,                                 /* next */
1225   0,                                    /* static_pass_number */
1226   0,                                    /* tv_id */
1227   PROP_ssa,                             /* properties_required */
1228   0,                                    /* properties_provided */
1229   0,                                    /* properties_destroyed */
1230   0,                                    /* todo_flags_start */
1231   0,                                    /* todo_flags_finish */
1232   0                                     /* letter */
1233 };
1234
1235 struct tree_opt_pass pass_late_warn_uninitialized =
1236 {
1237   NULL,                                 /* name */
1238   gate_warn_uninitialized,              /* gate */
1239   execute_late_warn_uninitialized,      /* execute */
1240   NULL,                                 /* sub */
1241   NULL,                                 /* next */
1242   0,                                    /* static_pass_number */
1243   0,                                    /* tv_id */
1244   PROP_ssa,                             /* properties_required */
1245   0,                                    /* properties_provided */
1246   0,                                    /* properties_destroyed */
1247   0,                                    /* todo_flags_start */
1248   0,                                    /* todo_flags_finish */
1249   0                                     /* letter */
1250 };
1251