* testsuite/libgomp.fortran/vla7.f90: Add -w to options.
[official-gcc.git] / gcc / tree-ssa.c
blobf6924b3e634332a6147f136aab36107752e00d86
1 /* Miscellaneous SSA utility functions.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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. */
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"
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). */
53 edge
54 ssa_redirect_edge (edge e, basic_block dest)
56 tree phi;
57 tree list = NULL, *last = &list;
58 tree src, dst, node;
60 /* Remove the appropriate PHI arguments in E's destination block. */
61 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
63 if (PHI_ARG_DEF (phi, e->dest_idx) == NULL_TREE)
64 continue;
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);
73 e = redirect_edge_succ_nodup (e, dest);
74 PENDING_STMT (e) = list;
76 return e;
79 /* Add PHI arguments queued in PENDINT_STMT list on edge E to edge
80 E->dest. */
82 void
83 flush_pending_stmts (edge e)
85 tree phi, arg;
87 if (!PENDING_STMT (e))
88 return;
90 for (phi = phi_nodes (e->dest), arg = PENDING_STMT (e);
91 phi;
92 phi = PHI_CHAIN (phi), arg = TREE_CHAIN (arg))
94 tree def = TREE_VALUE (arg);
95 add_phi_arg (phi, def, e);
98 PENDING_STMT (e) = NULL;
101 /* Return true if SSA_NAME is malformed and mark it visited.
103 IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
104 operand. */
106 static bool
107 verify_ssa_name (tree ssa_name, bool is_virtual)
109 if (TREE_CODE (ssa_name) != SSA_NAME)
111 error ("expected an SSA_NAME object");
112 return true;
115 if (TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name)))
117 error ("type mismatch between an SSA_NAME and its symbol");
118 return true;
121 if (SSA_NAME_IN_FREE_LIST (ssa_name))
123 error ("found an SSA_NAME that had been released into the free pool");
124 return true;
127 if (is_virtual && is_gimple_reg (ssa_name))
129 error ("found a virtual definition for a GIMPLE register");
130 return true;
133 if (!is_virtual && !is_gimple_reg (ssa_name))
135 error ("found a real definition for a non-register");
136 return true;
139 if (is_virtual && var_ann (SSA_NAME_VAR (ssa_name))
140 && get_subvars_for_var (SSA_NAME_VAR (ssa_name)) != NULL)
142 error ("found real variable when subvariables should have appeared");
143 return true;
146 return false;
150 /* Return true if the definition of SSA_NAME at block BB is malformed.
152 STMT is the statement where SSA_NAME is created.
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.
159 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
160 V_MUST_DEF. */
162 static bool
163 verify_def (basic_block bb, basic_block *definition_block, tree ssa_name,
164 tree stmt, bool is_virtual)
166 if (verify_ssa_name (ssa_name, is_virtual))
167 goto err;
169 if (definition_block[SSA_NAME_VERSION (ssa_name)])
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;
176 definition_block[SSA_NAME_VERSION (ssa_name)] = bb;
178 if (SSA_NAME_DEF_STMT (ssa_name) != stmt)
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;
188 return false;
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);
196 return true;
200 /* Return true if the use of SSA_NAME at statement STMT in block BB is
201 malformed.
203 DEF_BB is the block where SSA_NAME was found to be created.
205 IDOM contains immediate dominator information for the flowgraph.
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).
211 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
212 V_MUST_DEF.
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. */
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)
222 bool err = false;
223 tree ssa_name = USE_FROM_PTR (use_p);
225 err = verify_ssa_name (ssa_name, is_virtual);
227 if (!TREE_VISITED (ssa_name))
228 if (verify_imm_links (stderr, ssa_name))
229 err = true;
231 TREE_VISITED (ssa_name) = 1;
233 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name))
234 && default_def (SSA_NAME_VAR (ssa_name)) == ssa_name)
235 ; /* Default definitions have empty statements. Nothing to do. */
236 else if (!def_bb)
238 error ("missing definition");
239 err = true;
241 else if (bb != def_bb
242 && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
244 error ("definition in block %i does not dominate use in block %i",
245 def_bb->index, bb->index);
246 err = true;
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)))
252 error ("definition in block %i follows the use", def_bb->index);
253 err = true;
256 if (check_abnormal
257 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
259 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
260 err = true;
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)
267 error ("no immediate_use list");
268 err = true;
270 else
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)
279 error ("wrong immediate use list");
280 err = true;
284 if (err)
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);
292 return err;
296 /* Return true if any of the arguments for PHI node PHI at block BB is
297 malformed.
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. */
303 static bool
304 verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)
306 edge e;
307 bool err = false;
308 unsigned i, phi_num_args = PHI_NUM_ARGS (phi);
310 if (EDGE_COUNT (bb->preds) != phi_num_args)
312 error ("incoming edge count does not match number of PHI arguments");
313 err = true;
314 goto error;
317 for (i = 0; i < phi_num_args; i++)
319 use_operand_p op_p = PHI_ARG_DEF_PTR (phi, i);
320 tree op = USE_FROM_PTR (op_p);
323 e = EDGE_PRED (bb, i);
325 if (op == NULL_TREE)
327 error ("PHI argument is missing for edge %d->%d",
328 e->src->index,
329 e->dest->index);
330 err = true;
331 goto error;
334 if (TREE_CODE (op) != SSA_NAME && !is_gimple_min_invariant (op))
336 error ("PHI argument is not SSA_NAME, or invariant");
337 err = true;
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);
346 if (e->dest != bb)
348 error ("wrong edge %d->%d for PHI argument",
349 e->src->index, e->dest->index);
350 err = true;
353 if (err)
355 fprintf (stderr, "PHI argument\n");
356 print_generic_stmt (stderr, op, TDF_VOPS);
357 goto error;
361 error:
362 if (err)
364 fprintf (stderr, "for PHI node\n");
365 print_generic_stmt (stderr, phi, TDF_VOPS);
369 return err;
373 static void
374 verify_flow_insensitive_alias_info (void)
376 tree var;
377 bitmap visited = BITMAP_ALLOC (NULL);
378 referenced_var_iterator rvi;
380 FOR_EACH_REFERENCED_VAR (var, rvi)
382 size_t j;
383 var_ann_t ann;
384 VEC(tree,gc) *may_aliases;
385 tree alias;
387 ann = var_ann (var);
388 may_aliases = ann->may_aliases;
390 for (j = 0; VEC_iterate (tree, may_aliases, j, alias); j++)
392 bitmap_set_bit (visited, DECL_UID (alias));
394 if (!may_be_aliased (alias))
396 error ("non-addressable variable inside an alias set");
397 debug_variable (alias);
398 goto err;
403 FOR_EACH_REFERENCED_VAR (var, rvi)
405 var_ann_t ann;
406 ann = var_ann (var);
408 if (!MTAG_P (var)
409 && ann->is_alias_tag
410 && !bitmap_bit_p (visited, DECL_UID (var)))
412 error ("addressable variable that is an alias tag but is not in any alias set");
413 goto err;
417 BITMAP_FREE (visited);
418 return;
420 err:
421 debug_variable (var);
422 internal_error ("verify_flow_insensitive_alias_info failed");
426 static void
427 verify_flow_sensitive_alias_info (void)
429 size_t i;
430 tree ptr;
432 for (i = 1; i < num_ssa_names; i++)
434 tree var;
435 var_ann_t ann;
436 struct ptr_info_def *pi;
439 ptr = ssa_name (i);
440 if (!ptr)
441 continue;
443 /* We only care for pointers that are actually referenced in the
444 program. */
445 if (!POINTER_TYPE_P (TREE_TYPE (ptr)) || !TREE_VISITED (ptr))
446 continue;
448 /* RESULT_DECL is special. If it's a GIMPLE register, then it
449 is only written-to only once in the return statement.
450 Otherwise, aggregate RESULT_DECLs may be written-to more than
451 once in virtual operands. */
452 var = SSA_NAME_VAR (ptr);
453 if (TREE_CODE (var) == RESULT_DECL
454 && is_gimple_reg (ptr))
455 continue;
457 pi = SSA_NAME_PTR_INFO (ptr);
458 if (pi == NULL)
459 continue;
461 ann = var_ann (var);
462 if (pi->is_dereferenced && !pi->name_mem_tag && !ann->type_mem_tag)
464 error ("dereferenced pointers should have a name or a type tag");
465 goto err;
468 if (pi->name_mem_tag
469 && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars)))
471 error ("pointers with a memory tag, should have points-to sets");
472 goto err;
475 if (pi->value_escapes_p
476 && pi->name_mem_tag
477 && !is_call_clobbered (pi->name_mem_tag))
479 error ("pointer escapes but its name tag is not call-clobbered");
480 goto err;
484 return;
486 err:
487 debug_variable (ptr);
488 internal_error ("verify_flow_sensitive_alias_info failed");
491 DEF_VEC_P (bitmap);
492 DEF_VEC_ALLOC_P (bitmap,heap);
494 /* Verify that all name tags have different points to sets.
495 This algorithm takes advantage of the fact that every variable with the
496 same name tag must have the same points-to set.
497 So we check a single variable for each name tag, and verify that its
498 points-to set is different from every other points-to set for other name
499 tags.
501 Additionally, given a pointer P_i with name tag NMT and type tag
502 TMT, this function verified the alias set of TMT is a superset of
503 the alias set of NMT. */
505 static void
506 verify_name_tags (void)
508 size_t i;
509 size_t j;
510 bitmap first, second;
511 VEC(tree,heap) *name_tag_reps = NULL;
512 VEC(bitmap,heap) *pt_vars_for_reps = NULL;
513 bitmap type_aliases = BITMAP_ALLOC (NULL);
515 /* First we compute the name tag representatives and their points-to sets. */
516 for (i = 0; i < num_ssa_names; i++)
518 struct ptr_info_def *pi;
519 tree tmt, ptr = ssa_name (i);
521 if (ptr == NULL_TREE)
522 continue;
524 pi = SSA_NAME_PTR_INFO (ptr);
526 if (!TREE_VISITED (ptr)
527 || !POINTER_TYPE_P (TREE_TYPE (ptr))
528 || !pi
529 || !pi->name_mem_tag
530 || TREE_VISITED (pi->name_mem_tag))
531 continue;
533 TREE_VISITED (pi->name_mem_tag) = 1;
535 if (pi->pt_vars == NULL)
536 continue;
538 VEC_safe_push (tree, heap, name_tag_reps, ptr);
539 VEC_safe_push (bitmap, heap, pt_vars_for_reps, pi->pt_vars);
541 /* Verify that alias set of PTR's type tag is a superset of the
542 alias set of PTR's name tag. */
543 tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
544 if (tmt)
546 size_t i;
547 VEC(tree,gc) *aliases = var_ann (tmt)->may_aliases;
548 tree alias;
550 bitmap_clear (type_aliases);
551 for (i = 0; VEC_iterate (tree, aliases, i, alias); i++)
552 bitmap_set_bit (type_aliases, DECL_UID (alias));
554 /* When grouping, we may have added PTR's type tag into the
555 alias set of PTR's name tag. To prevent a false
556 positive, pretend that TMT is in its own alias set. */
557 bitmap_set_bit (type_aliases, DECL_UID (tmt));
559 if (bitmap_equal_p (type_aliases, pi->pt_vars))
560 continue;
562 if (!bitmap_intersect_compl_p (type_aliases, pi->pt_vars))
564 error ("alias set of a pointer's type tag should be a superset of the corresponding name tag");
565 debug_variable (tmt);
566 debug_variable (pi->name_mem_tag);
567 goto err;
572 /* Now compare all the representative bitmaps with all other representative
573 bitmaps, to verify that they are all different. */
574 for (i = 0; VEC_iterate (bitmap, pt_vars_for_reps, i, first); i++)
576 for (j = i + 1; VEC_iterate (bitmap, pt_vars_for_reps, j, second); j++)
578 if (bitmap_equal_p (first, second))
580 error ("two different pointers with identical points-to sets but different name tags");
581 debug_variable (VEC_index (tree, name_tag_reps, j));
582 goto err;
587 /* Lastly, clear out the visited flags. */
588 for (i = 0; i < num_ssa_names; i++)
590 if (ssa_name (i))
592 tree ptr = ssa_name (i);
593 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
594 if (!TREE_VISITED (ptr)
595 || !POINTER_TYPE_P (TREE_TYPE (ptr))
596 || !pi
597 || !pi->name_mem_tag)
598 continue;
599 TREE_VISITED (pi->name_mem_tag) = 0;
603 /* We do not have to free the bitmaps or trees in the vectors, as
604 they are not owned by us. */
605 VEC_free (bitmap, heap, pt_vars_for_reps);
606 VEC_free (tree, heap, name_tag_reps);
607 BITMAP_FREE (type_aliases);
608 return;
610 err:
611 debug_variable (VEC_index (tree, name_tag_reps, i));
612 internal_error ("verify_name_tags failed");
616 /* Verify the consistency of aliasing information. */
618 static void
619 verify_alias_info (void)
621 verify_flow_sensitive_alias_info ();
622 verify_name_tags ();
623 verify_flow_insensitive_alias_info ();
627 /* Verify common invariants in the SSA web.
628 TODO: verify the variable annotations. */
630 void
631 verify_ssa (bool check_modified_stmt)
633 size_t i;
634 basic_block bb;
635 basic_block *definition_block = XCNEWVEC (basic_block, num_ssa_names);
636 ssa_op_iter iter;
637 tree op;
638 enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS];
639 bitmap names_defined_in_bb = BITMAP_ALLOC (NULL);
641 gcc_assert (!need_ssa_update_p ());
643 verify_stmts ();
645 timevar_push (TV_TREE_SSA_VERIFY);
647 /* Keep track of SSA names present in the IL. */
648 for (i = 1; i < num_ssa_names; i++)
650 tree name = ssa_name (i);
651 if (name)
653 tree stmt;
654 TREE_VISITED (name) = 0;
656 stmt = SSA_NAME_DEF_STMT (name);
657 if (!IS_EMPTY_STMT (stmt))
659 basic_block bb = bb_for_stmt (stmt);
660 verify_def (bb, definition_block,
661 name, stmt, !is_gimple_reg (name));
667 calculate_dominance_info (CDI_DOMINATORS);
669 /* Now verify all the uses and make sure they agree with the definitions
670 found in the previous pass. */
671 FOR_EACH_BB (bb)
673 edge e;
674 tree phi;
675 edge_iterator ei;
676 block_stmt_iterator bsi;
678 /* Make sure that all edges have a clear 'aux' field. */
679 FOR_EACH_EDGE (e, ei, bb->preds)
681 if (e->aux)
683 error ("AUX pointer initialized for edge %d->%d", e->src->index,
684 e->dest->index);
685 goto err;
689 /* Verify the arguments for every PHI node in the block. */
690 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
692 if (verify_phi_args (phi, bb, definition_block))
693 goto err;
694 bitmap_set_bit (names_defined_in_bb,
695 SSA_NAME_VERSION (PHI_RESULT (phi)));
698 /* Now verify all the uses and vuses in every statement of the block. */
699 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
701 tree stmt = bsi_stmt (bsi);
702 use_operand_p use_p;
704 if (check_modified_stmt && stmt_modified_p (stmt))
706 error ("stmt (%p) marked modified after optimization pass : ",
707 (void *)stmt);
708 print_generic_stmt (stderr, stmt, TDF_VOPS);
709 goto err;
712 if (TREE_CODE (stmt) == MODIFY_EXPR
713 && TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
715 tree lhs, base_address;
717 lhs = TREE_OPERAND (stmt, 0);
718 base_address = get_base_address (lhs);
720 if (base_address
721 && SSA_VAR_P (base_address)
722 && ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF))
724 error ("statement makes a memory store, but has no "
725 "V_MAY_DEFS nor V_MUST_DEFS");
726 print_generic_stmt (stderr, stmt, TDF_VOPS);
727 goto err;
731 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
732 SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
734 op = USE_FROM_PTR (use_p);
735 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
736 use_p, stmt, false, !is_gimple_reg (op),
737 names_defined_in_bb))
738 goto err;
741 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
742 bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
745 bitmap_clear (names_defined_in_bb);
748 /* Finally, verify alias information. */
749 verify_alias_info ();
751 free (definition_block);
753 /* Restore the dominance information to its prior known state, so
754 that we do not perturb the compiler's subsequent behavior. */
755 if (orig_dom_state == DOM_NONE)
756 free_dominance_info (CDI_DOMINATORS);
757 else
758 dom_computed[CDI_DOMINATORS] = orig_dom_state;
760 BITMAP_FREE (names_defined_in_bb);
761 timevar_pop (TV_TREE_SSA_VERIFY);
762 return;
764 err:
765 internal_error ("verify_ssa failed");
768 /* Return true if the uid in both int tree maps are equal. */
771 int_tree_map_eq (const void *va, const void *vb)
773 const struct int_tree_map *a = (const struct int_tree_map *) va;
774 const struct int_tree_map *b = (const struct int_tree_map *) vb;
775 return (a->uid == b->uid);
778 /* Hash a UID in a int_tree_map. */
780 unsigned int
781 int_tree_map_hash (const void *item)
783 return ((const struct int_tree_map *)item)->uid;
787 /* Initialize global DFA and SSA structures. */
789 void
790 init_tree_ssa (void)
792 referenced_vars = htab_create_ggc (20, int_tree_map_hash,
793 int_tree_map_eq, NULL);
794 default_defs = htab_create_ggc (20, int_tree_map_hash, int_tree_map_eq, NULL);
795 call_clobbered_vars = BITMAP_ALLOC (NULL);
796 addressable_vars = BITMAP_ALLOC (NULL);
797 init_alias_heapvars ();
798 init_ssanames ();
799 init_phinodes ();
800 global_var = NULL_TREE;
801 aliases_computed_p = false;
805 /* Deallocate memory associated with SSA data structures for FNDECL. */
807 void
808 delete_tree_ssa (void)
810 size_t i;
811 basic_block bb;
812 block_stmt_iterator bsi;
813 referenced_var_iterator rvi;
814 tree var;
816 /* Release any ssa_names still in use. */
817 for (i = 0; i < num_ssa_names; i++)
819 tree var = ssa_name (i);
820 if (var && TREE_CODE (var) == SSA_NAME)
822 SSA_NAME_IMM_USE_NODE (var).prev = &(SSA_NAME_IMM_USE_NODE (var));
823 SSA_NAME_IMM_USE_NODE (var).next = &(SSA_NAME_IMM_USE_NODE (var));
825 release_ssa_name (var);
828 /* Remove annotations from every tree in the function. */
829 FOR_EACH_BB (bb)
831 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
833 tree stmt = bsi_stmt (bsi);
834 stmt_ann_t ann = get_stmt_ann (stmt);
836 free_ssa_operands (&ann->operands);
837 ann->addresses_taken = 0;
838 mark_stmt_modified (stmt);
840 set_phi_nodes (bb, NULL);
843 /* Remove annotations from every referenced variable. */
844 FOR_EACH_REFERENCED_VAR (var, rvi)
846 ggc_free (var->common.ann);
847 var->common.ann = NULL;
849 htab_delete (referenced_vars);
850 referenced_vars = NULL;
852 fini_ssanames ();
853 fini_phinodes ();
855 global_var = NULL_TREE;
857 htab_delete (default_defs);
858 BITMAP_FREE (call_clobbered_vars);
859 call_clobbered_vars = NULL;
860 BITMAP_FREE (addressable_vars);
861 addressable_vars = NULL;
862 modified_noreturn_calls = NULL;
863 aliases_computed_p = false;
864 delete_alias_heapvars ();
865 gcc_assert (!need_ssa_update_p ());
869 /* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a
870 useless type conversion, otherwise return false. */
872 bool
873 tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
875 if (inner_type == outer_type)
876 return true;
878 /* Changes in machine mode are never useless conversions. */
879 if (TYPE_MODE (inner_type) != TYPE_MODE (outer_type))
880 return false;
882 /* If the inner and outer types are effectively the same, then
883 strip the type conversion and enter the equivalence into
884 the table. */
885 if (lang_hooks.types_compatible_p (inner_type, outer_type))
886 return true;
888 /* If both types are pointers and the outer type is a (void *), then
889 the conversion is not necessary. The opposite is not true since
890 that conversion would result in a loss of information if the
891 equivalence was used. Consider an indirect function call where
892 we need to know the exact type of the function to correctly
893 implement the ABI. */
894 else if (POINTER_TYPE_P (inner_type)
895 && POINTER_TYPE_P (outer_type)
896 && TYPE_REF_CAN_ALIAS_ALL (inner_type)
897 == TYPE_REF_CAN_ALIAS_ALL (outer_type)
898 && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
899 return true;
901 /* Don't lose casts between pointers to volatile and non-volatile
902 qualified types. Doing so would result in changing the semantics
903 of later accesses. */
904 else if (POINTER_TYPE_P (inner_type)
905 && POINTER_TYPE_P (outer_type)
906 && TYPE_VOLATILE (TREE_TYPE (outer_type))
907 != TYPE_VOLATILE (TREE_TYPE (inner_type)))
908 return false;
910 /* Pointers/references are equivalent if their pointed to types
911 are effectively the same. This allows to strip conversions between
912 pointer types with different type qualifiers. */
913 else if (POINTER_TYPE_P (inner_type)
914 && POINTER_TYPE_P (outer_type)
915 && TYPE_REF_CAN_ALIAS_ALL (inner_type)
916 == TYPE_REF_CAN_ALIAS_ALL (outer_type)
917 && lang_hooks.types_compatible_p (TREE_TYPE (inner_type),
918 TREE_TYPE (outer_type)))
919 return true;
921 /* If both the inner and outer types are integral types, then the
922 conversion is not necessary if they have the same mode and
923 signedness and precision, and both or neither are boolean. Some
924 code assumes an invariant that boolean types stay boolean and do
925 not become 1-bit bit-field types. Note that types with precision
926 not using all bits of the mode (such as bit-field types in C)
927 mean that testing of precision is necessary. */
928 else if (INTEGRAL_TYPE_P (inner_type)
929 && INTEGRAL_TYPE_P (outer_type)
930 && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
931 && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type)
932 && simple_cst_equal (TYPE_MAX_VALUE (inner_type), TYPE_MAX_VALUE (outer_type))
933 && simple_cst_equal (TYPE_MIN_VALUE (inner_type), TYPE_MIN_VALUE (outer_type)))
935 bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE);
936 bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE);
937 if (first_boolean == second_boolean)
938 return true;
941 /* Recurse for complex types. */
942 else if (TREE_CODE (inner_type) == COMPLEX_TYPE
943 && TREE_CODE (outer_type) == COMPLEX_TYPE
944 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
945 TREE_TYPE (inner_type)))
946 return true;
948 return false;
951 /* Return true if EXPR is a useless type conversion, otherwise return
952 false. */
954 bool
955 tree_ssa_useless_type_conversion (tree expr)
957 /* If we have an assignment that merely uses a NOP_EXPR to change
958 the top of the RHS to the type of the LHS and the type conversion
959 is "safe", then strip away the type conversion so that we can
960 enter LHS = RHS into the const_and_copies table. */
961 if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR
962 || TREE_CODE (expr) == VIEW_CONVERT_EXPR
963 || TREE_CODE (expr) == NON_LVALUE_EXPR)
964 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
965 TREE_TYPE (TREE_OPERAND (expr,
966 0)));
969 return false;
972 /* Returns true if statement STMT may read memory. */
974 bool
975 stmt_references_memory_p (tree stmt)
977 stmt_ann_t ann = stmt_ann (stmt);
979 if (ann->has_volatile_ops)
980 return true;
982 return (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS));
985 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
986 described in walk_use_def_chains.
988 VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
989 infinite loops. We used to have a bitmap for this to just mark
990 SSA versions we had visited. But non-sparse bitmaps are way too
991 expensive, while sparse bitmaps may cause quadratic behavior.
993 IS_DFS is true if the caller wants to perform a depth-first search
994 when visiting PHI nodes. A DFS will visit each PHI argument and
995 call FN after each one. Otherwise, all the arguments are
996 visited first and then FN is called with each of the visited
997 arguments in a separate pass. */
999 static bool
1000 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
1001 struct pointer_set_t *visited, bool is_dfs)
1003 tree def_stmt;
1005 if (pointer_set_insert (visited, var))
1006 return false;
1008 def_stmt = SSA_NAME_DEF_STMT (var);
1010 if (TREE_CODE (def_stmt) != PHI_NODE)
1012 /* If we reached the end of the use-def chain, call FN. */
1013 return fn (var, def_stmt, data);
1015 else
1017 int i;
1019 /* When doing a breadth-first search, call FN before following the
1020 use-def links for each argument. */
1021 if (!is_dfs)
1022 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1023 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
1024 return true;
1026 /* Follow use-def links out of each PHI argument. */
1027 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1029 tree arg = PHI_ARG_DEF (def_stmt, i);
1030 if (TREE_CODE (arg) == SSA_NAME
1031 && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
1032 return true;
1035 /* When doing a depth-first search, call FN after following the
1036 use-def links for each argument. */
1037 if (is_dfs)
1038 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1039 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
1040 return true;
1043 return false;
1048 /* Walk use-def chains starting at the SSA variable VAR. Call
1049 function FN at each reaching definition found. FN takes three
1050 arguments: VAR, its defining statement (DEF_STMT) and a generic
1051 pointer to whatever state information that FN may want to maintain
1052 (DATA). FN is able to stop the walk by returning true, otherwise
1053 in order to continue the walk, FN should return false.
1055 Note, that if DEF_STMT is a PHI node, the semantics are slightly
1056 different. The first argument to FN is no longer the original
1057 variable VAR, but the PHI argument currently being examined. If FN
1058 wants to get at VAR, it should call PHI_RESULT (PHI).
1060 If IS_DFS is true, this function will:
1062 1- walk the use-def chains for all the PHI arguments, and,
1063 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
1065 If IS_DFS is false, the two steps above are done in reverse order
1066 (i.e., a breadth-first search). */
1069 void
1070 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
1071 bool is_dfs)
1073 tree def_stmt;
1075 gcc_assert (TREE_CODE (var) == SSA_NAME);
1077 def_stmt = SSA_NAME_DEF_STMT (var);
1079 /* We only need to recurse if the reaching definition comes from a PHI
1080 node. */
1081 if (TREE_CODE (def_stmt) != PHI_NODE)
1082 (*fn) (var, def_stmt, data);
1083 else
1085 struct pointer_set_t *visited = pointer_set_create ();
1086 walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
1087 pointer_set_destroy (visited);
1092 /* Emit warnings for uninitialized variables. This is done in two passes.
1094 The first pass notices real uses of SSA names with default definitions.
1095 Such uses are unconditionally uninitialized, and we can be certain that
1096 such a use is a mistake. This pass is run before most optimizations,
1097 so that we catch as many as we can.
1099 The second pass follows PHI nodes to find uses that are potentially
1100 uninitialized. In this case we can't necessarily prove that the use
1101 is really uninitialized. This pass is run after most optimizations,
1102 so that we thread as many jumps and possible, and delete as much dead
1103 code as possible, in order to reduce false positives. We also look
1104 again for plain uninitialized variables, since optimization may have
1105 changed conditionally uninitialized to unconditionally uninitialized. */
1107 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1108 warning text is in MSGID and LOCUS may contain a location or be null. */
1110 static void
1111 warn_uninit (tree t, const char *gmsgid, void *data)
1113 tree var = SSA_NAME_VAR (t);
1114 tree def = SSA_NAME_DEF_STMT (t);
1115 tree context = (tree) data;
1116 location_t * locus;
1118 /* Default uses (indicated by an empty definition statement),
1119 are uninitialized. */
1120 if (!IS_EMPTY_STMT (def))
1121 return;
1123 /* Except for PARMs of course, which are always initialized. */
1124 if (TREE_CODE (var) == PARM_DECL)
1125 return;
1127 /* Hard register variables get their initial value from the ether. */
1128 if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1129 return;
1131 /* TREE_NO_WARNING either means we already warned, or the front end
1132 wishes to suppress the warning. */
1133 if (TREE_NO_WARNING (var))
1134 return;
1136 locus = (context != NULL && EXPR_HAS_LOCATION (context)
1137 ? EXPR_LOCUS (context)
1138 : &DECL_SOURCE_LOCATION (var));
1139 warning (0, gmsgid, locus, var);
1140 TREE_NO_WARNING (var) = 1;
1143 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1144 and warn about them. */
1146 static tree
1147 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
1149 tree t = *tp;
1151 switch (TREE_CODE (t))
1153 case SSA_NAME:
1154 /* We only do data flow with SSA_NAMEs, so that's all we
1155 can warn about. */
1156 warn_uninit (t, "%H%qD is used uninitialized in this function", data);
1157 *walk_subtrees = 0;
1158 break;
1160 case REALPART_EXPR:
1161 case IMAGPART_EXPR:
1162 /* The total store transformation performed during gimplification
1163 creates uninitialized variable uses. If all is well, these will
1164 be optimized away, so don't warn now. */
1165 if (TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
1166 *walk_subtrees = 0;
1167 break;
1169 default:
1170 if (IS_TYPE_OR_DECL_P (t))
1171 *walk_subtrees = 0;
1172 break;
1175 return NULL_TREE;
1178 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1179 and warn about them. */
1181 static void
1182 warn_uninitialized_phi (tree phi)
1184 int i, n = PHI_NUM_ARGS (phi);
1186 /* Don't look at memory tags. */
1187 if (!is_gimple_reg (PHI_RESULT (phi)))
1188 return;
1190 for (i = 0; i < n; ++i)
1192 tree op = PHI_ARG_DEF (phi, i);
1193 if (TREE_CODE (op) == SSA_NAME)
1194 warn_uninit (op, "%H%qD may be used uninitialized in this function",
1195 NULL);
1199 static void
1200 execute_early_warn_uninitialized (void)
1202 block_stmt_iterator bsi;
1203 basic_block bb;
1205 FOR_EACH_BB (bb)
1206 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1208 tree context = bsi_stmt (bsi);
1209 walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1210 context, NULL);
1214 static void
1215 execute_late_warn_uninitialized (void)
1217 basic_block bb;
1218 tree phi;
1220 /* Re-do the plain uninitialized variable check, as optimization may have
1221 straightened control flow. Do this first so that we don't accidentally
1222 get a "may be" warning when we'd have seen an "is" warning later. */
1223 execute_early_warn_uninitialized ();
1225 FOR_EACH_BB (bb)
1226 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1227 warn_uninitialized_phi (phi);
1230 static bool
1231 gate_warn_uninitialized (void)
1233 return warn_uninitialized != 0;
1236 struct tree_opt_pass pass_early_warn_uninitialized =
1238 NULL, /* name */
1239 gate_warn_uninitialized, /* gate */
1240 execute_early_warn_uninitialized, /* execute */
1241 NULL, /* sub */
1242 NULL, /* next */
1243 0, /* static_pass_number */
1244 0, /* tv_id */
1245 PROP_ssa, /* properties_required */
1246 0, /* properties_provided */
1247 0, /* properties_destroyed */
1248 0, /* todo_flags_start */
1249 0, /* todo_flags_finish */
1250 0 /* letter */
1253 struct tree_opt_pass pass_late_warn_uninitialized =
1255 NULL, /* name */
1256 gate_warn_uninitialized, /* gate */
1257 execute_late_warn_uninitialized, /* execute */
1258 NULL, /* sub */
1259 NULL, /* next */
1260 0, /* static_pass_number */
1261 0, /* tv_id */
1262 PROP_ssa, /* properties_required */
1263 0, /* properties_provided */
1264 0, /* properties_destroyed */
1265 0, /* todo_flags_start */
1266 0, /* todo_flags_finish */
1267 0 /* letter */