1 /* Miscellaneous SSA utility functions.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008 Free Software
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
30 #include "langhooks.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
36 #include "diagnostic.h"
38 #include "pointer-set.h"
39 #include "tree-flow.h"
41 #include "tree-inline.h"
45 #include "tree-dump.h"
46 #include "tree-pass.h"
49 /* Pointer map of variable mappings, keyed by edge. */
50 static struct pointer_map_t *edge_var_maps;
53 /* Add a mapping with PHI RESULT and PHI DEF associated with edge E. */
56 redirect_edge_var_map_add (edge e, tree result, tree def)
59 edge_var_map_vector old_head, head;
60 edge_var_map new_node;
62 if (edge_var_maps == NULL)
63 edge_var_maps = pointer_map_create ();
65 slot = pointer_map_insert (edge_var_maps, e);
66 old_head = head = (edge_var_map_vector) *slot;
69 head = VEC_alloc (edge_var_map, heap, 5);
73 new_node.result = result;
75 VEC_safe_push (edge_var_map, heap, head, &new_node);
78 /* The push did some reallocation. Update the pointer map. */
84 /* Clear the var mappings in edge E. */
87 redirect_edge_var_map_clear (edge e)
90 edge_var_map_vector head;
95 slot = pointer_map_contains (edge_var_maps, e);
99 head = (edge_var_map_vector) *slot;
100 VEC_free (edge_var_map, heap, head);
106 /* Duplicate the redirected var mappings in OLDE in NEWE.
108 Since we can't remove a mapping, let's just duplicate it. This assumes a
109 pointer_map can have multiple edges mapping to the same var_map (many to
110 one mapping), since we don't remove the previous mappings. */
113 redirect_edge_var_map_dup (edge newe, edge olde)
115 void **new_slot, **old_slot; edge_var_map_vector head;
120 new_slot = pointer_map_insert (edge_var_maps, newe);
121 old_slot = pointer_map_contains (edge_var_maps, olde);
124 head = (edge_var_map_vector) *old_slot;
127 *new_slot = VEC_copy (edge_var_map, heap, head);
129 *new_slot = VEC_alloc (edge_var_map, heap, 5);
133 /* Return the variable mappings for a given edge. If there is none, return
137 redirect_edge_var_map_vector (edge e)
141 /* Hey, what kind of idiot would... you'd be surprised. */
145 slot = pointer_map_contains (edge_var_maps, e);
149 return (edge_var_map_vector) *slot;
153 /* Clear the edge variable mappings. */
156 redirect_edge_var_map_destroy (void)
160 pointer_map_destroy (edge_var_maps);
161 edge_var_maps = NULL;
166 /* Remove the corresponding arguments from the PHI nodes in E's
167 destination block and redirect it to DEST. Return redirected edge.
168 The list of removed arguments is stored in a vector accessed
169 through edge_var_maps. */
172 ssa_redirect_edge (edge e, basic_block dest)
174 gimple_stmt_iterator gsi;
177 redirect_edge_var_map_clear (e);
179 /* Remove the appropriate PHI arguments in E's destination block. */
180 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
184 phi = gsi_stmt (gsi);
185 def = gimple_phi_arg_def (phi, e->dest_idx);
187 if (def == NULL_TREE)
190 redirect_edge_var_map_add (e, gimple_phi_result (phi), def);
193 e = redirect_edge_succ_nodup (e, dest);
199 /* Add PHI arguments queued in PENDING_STMT list on edge E to edge
203 flush_pending_stmts (edge e)
206 edge_var_map_vector v;
209 gimple_stmt_iterator gsi;
211 v = redirect_edge_var_map_vector (e);
215 for (gsi = gsi_start_phis (e->dest), i = 0;
216 !gsi_end_p (gsi) && VEC_iterate (edge_var_map, v, i, vm);
217 gsi_next (&gsi), i++)
221 phi = gsi_stmt (gsi);
222 def = redirect_edge_var_map_def (vm);
223 add_phi_arg (phi, def, e);
226 redirect_edge_var_map_clear (e);
229 /* Return true if SSA_NAME is malformed and mark it visited.
231 IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
235 verify_ssa_name (tree ssa_name, bool is_virtual)
237 if (TREE_CODE (ssa_name) != SSA_NAME)
239 error ("expected an SSA_NAME object");
243 if (TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name)))
245 error ("type mismatch between an SSA_NAME and its symbol");
249 if (SSA_NAME_IN_FREE_LIST (ssa_name))
251 error ("found an SSA_NAME that had been released into the free pool");
255 if (is_virtual && is_gimple_reg (ssa_name))
257 error ("found a virtual definition for a GIMPLE register");
261 if (!is_virtual && !is_gimple_reg (ssa_name))
263 error ("found a real definition for a non-register");
267 if (SSA_NAME_IS_DEFAULT_DEF (ssa_name)
268 && !gimple_nop_p (SSA_NAME_DEF_STMT (ssa_name)))
270 error ("found a default name with a non-empty defining statement");
278 /* Return true if the definition of SSA_NAME at block BB is malformed.
280 STMT is the statement where SSA_NAME is created.
282 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
283 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
284 it means that the block in that array slot contains the
285 definition of SSA_NAME.
287 IS_VIRTUAL is true if SSA_NAME is created by a VDEF. */
290 verify_def (basic_block bb, basic_block *definition_block, tree ssa_name,
291 gimple stmt, bool is_virtual)
293 if (verify_ssa_name (ssa_name, is_virtual))
296 if (definition_block[SSA_NAME_VERSION (ssa_name)])
298 error ("SSA_NAME created in two different blocks %i and %i",
299 definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index);
303 definition_block[SSA_NAME_VERSION (ssa_name)] = bb;
305 if (SSA_NAME_DEF_STMT (ssa_name) != stmt)
307 error ("SSA_NAME_DEF_STMT is wrong");
308 fprintf (stderr, "Expected definition statement:\n");
309 print_gimple_stmt (stderr, SSA_NAME_DEF_STMT (ssa_name), 4, TDF_VOPS);
310 fprintf (stderr, "\nActual definition statement:\n");
311 print_gimple_stmt (stderr, stmt, 4, TDF_VOPS);
318 fprintf (stderr, "while verifying SSA_NAME ");
319 print_generic_expr (stderr, ssa_name, 0);
320 fprintf (stderr, " in statement\n");
321 print_gimple_stmt (stderr, stmt, 4, TDF_VOPS);
327 /* Return true if the use of SSA_NAME at statement STMT in block BB is
330 DEF_BB is the block where SSA_NAME was found to be created.
332 IDOM contains immediate dominator information for the flowgraph.
334 CHECK_ABNORMAL is true if the caller wants to check whether this use
335 is flowing through an abnormal edge (only used when checking PHI
338 If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
339 that are defined before STMT in basic block BB. */
342 verify_use (basic_block bb, basic_block def_bb, use_operand_p use_p,
343 gimple stmt, bool check_abnormal, bitmap names_defined_in_bb)
346 tree ssa_name = USE_FROM_PTR (use_p);
348 if (!TREE_VISITED (ssa_name))
349 if (verify_imm_links (stderr, ssa_name))
352 TREE_VISITED (ssa_name) = 1;
354 if (gimple_nop_p (SSA_NAME_DEF_STMT (ssa_name))
355 && SSA_NAME_IS_DEFAULT_DEF (ssa_name))
356 ; /* Default definitions have empty statements. Nothing to do. */
359 error ("missing definition");
362 else if (bb != def_bb
363 && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
365 error ("definition in block %i does not dominate use in block %i",
366 def_bb->index, bb->index);
369 else if (bb == def_bb
370 && names_defined_in_bb != NULL
371 && !bitmap_bit_p (names_defined_in_bb, SSA_NAME_VERSION (ssa_name)))
373 error ("definition in block %i follows the use", def_bb->index);
378 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
380 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
384 /* Make sure the use is in an appropriate list by checking the previous
385 element to make sure it's the same. */
386 if (use_p->prev == NULL)
388 error ("no immediate_use list");
394 if (use_p->prev->use == NULL)
395 listvar = use_p->prev->loc.ssa_name;
397 listvar = USE_FROM_PTR (use_p->prev);
398 if (listvar != ssa_name)
400 error ("wrong immediate use list");
407 fprintf (stderr, "for SSA_NAME: ");
408 print_generic_expr (stderr, ssa_name, TDF_VOPS);
409 fprintf (stderr, " in statement:\n");
410 print_gimple_stmt (stderr, stmt, 0, TDF_VOPS);
417 /* Return true if any of the arguments for PHI node PHI at block BB is
420 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
421 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
422 it means that the block in that array slot contains the
423 definition of SSA_NAME. */
426 verify_phi_args (gimple phi, basic_block bb, basic_block *definition_block)
430 size_t i, phi_num_args = gimple_phi_num_args (phi);
432 if (EDGE_COUNT (bb->preds) != phi_num_args)
434 error ("incoming edge count does not match number of PHI arguments");
439 for (i = 0; i < phi_num_args; i++)
441 use_operand_p op_p = gimple_phi_arg_imm_use_ptr (phi, i);
442 tree op = USE_FROM_PTR (op_p);
444 e = EDGE_PRED (bb, i);
448 error ("PHI argument is missing for edge %d->%d",
455 if (TREE_CODE (op) != SSA_NAME && !is_gimple_min_invariant (op))
457 error ("PHI argument is not SSA_NAME, or invariant");
461 if (TREE_CODE (op) == SSA_NAME)
463 err = verify_ssa_name (op, !is_gimple_reg (gimple_phi_result (phi)));
464 err |= verify_use (e->src, definition_block[SSA_NAME_VERSION (op)],
465 op_p, phi, e->flags & EDGE_ABNORMAL, NULL);
470 error ("wrong edge %d->%d for PHI argument",
471 e->src->index, e->dest->index);
477 fprintf (stderr, "PHI argument\n");
478 print_generic_stmt (stderr, op, TDF_VOPS);
486 fprintf (stderr, "for PHI node\n");
487 print_gimple_stmt (stderr, phi, 0, TDF_VOPS|TDF_MEMSYMS);
496 verify_flow_insensitive_alias_info (void)
499 referenced_var_iterator rvi;
501 FOR_EACH_REFERENCED_VAR (var, rvi)
508 if (!MTAG_P (var) || !MTAG_ALIASES (var))
511 aliases = MTAG_ALIASES (var);
513 EXECUTE_IF_SET_IN_BITMAP (aliases, 0, j, bi)
515 alias = referenced_var (j);
517 if (TREE_CODE (alias) != MEMORY_PARTITION_TAG
518 && !may_be_aliased (alias))
520 error ("non-addressable variable inside an alias set");
521 debug_variable (alias);
530 debug_variable (var);
531 internal_error ("verify_flow_insensitive_alias_info failed");
536 verify_flow_sensitive_alias_info (void)
541 for (i = 1; i < num_ssa_names; i++)
545 struct ptr_info_def *pi;
552 /* We only care for pointers that are actually referenced in the
554 if (!POINTER_TYPE_P (TREE_TYPE (ptr)) || !TREE_VISITED (ptr))
557 /* RESULT_DECL is special. If it's a GIMPLE register, then it
558 is only written-to only once in the return statement.
559 Otherwise, aggregate RESULT_DECLs may be written-to more than
560 once in virtual operands. */
561 var = SSA_NAME_VAR (ptr);
562 if (TREE_CODE (var) == RESULT_DECL
563 && is_gimple_reg (ptr))
566 pi = SSA_NAME_PTR_INFO (ptr);
571 if (pi->memory_tag_needed && !pi->name_mem_tag && !ann->symbol_mem_tag)
573 error ("dereferenced pointers should have a name or a symbol tag");
578 && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars)))
580 error ("pointers with a memory tag, should have points-to sets");
584 if (pi->value_escapes_p
585 && pi->escape_mask & ~ESCAPE_TO_RETURN
588 tree t = memory_partition (pi->name_mem_tag);
590 t = pi->name_mem_tag;
592 if (!is_call_clobbered (t))
594 error ("pointer escapes but its name tag is not call-clobbered");
603 debug_variable (ptr);
604 internal_error ("verify_flow_sensitive_alias_info failed");
608 /* Verify the consistency of call clobbering information. */
611 verify_call_clobbering (void)
616 referenced_var_iterator rvi;
618 /* At all times, the result of the call_clobbered flag should
619 match the result of the call_clobbered_vars bitmap. Verify both
620 that everything in call_clobbered_vars is marked
621 call_clobbered, and that everything marked
622 call_clobbered is in call_clobbered_vars. */
623 EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun), 0, i, bi)
625 var = referenced_var (i);
627 if (memory_partition (var))
628 var = memory_partition (var);
630 if (!MTAG_P (var) && !var_ann (var)->call_clobbered)
632 error ("variable in call_clobbered_vars but not marked "
634 debug_variable (var);
639 FOR_EACH_REFERENCED_VAR (var, rvi)
641 if (is_gimple_reg (var))
644 if (memory_partition (var))
645 var = memory_partition (var);
648 && var_ann (var)->call_clobbered
649 && !bitmap_bit_p (gimple_call_clobbered_vars (cfun), DECL_UID (var)))
651 error ("variable marked call_clobbered but not in "
652 "call_clobbered_vars bitmap.");
653 debug_variable (var);
661 internal_error ("verify_call_clobbering failed");
665 /* Verify invariants in memory partitions. */
668 verify_memory_partitions (void)
672 VEC(tree,heap) *mpt_table = gimple_ssa_operands (cfun)->mpt_table;
673 struct pointer_set_t *partitioned_syms = pointer_set_create ();
675 for (i = 0; VEC_iterate (tree, mpt_table, i, mpt); i++)
680 if (MPT_SYMBOLS (mpt) == NULL)
682 error ("Memory partitions should have at least one symbol");
683 debug_variable (mpt);
687 EXECUTE_IF_SET_IN_BITMAP (MPT_SYMBOLS (mpt), 0, j, bj)
689 tree var = referenced_var (j);
690 if (pointer_set_insert (partitioned_syms, var))
692 error ("Partitioned symbols should belong to exactly one "
694 debug_variable (var);
700 pointer_set_destroy (partitioned_syms);
705 internal_error ("verify_memory_partitions failed");
709 /* Verify the consistency of aliasing information. */
712 verify_alias_info (void)
714 verify_flow_sensitive_alias_info ();
715 verify_call_clobbering ();
716 verify_flow_insensitive_alias_info ();
717 verify_memory_partitions ();
721 /* Verify common invariants in the SSA web.
722 TODO: verify the variable annotations. */
725 verify_ssa (bool check_modified_stmt)
729 basic_block *definition_block = XCNEWVEC (basic_block, num_ssa_names);
732 enum dom_state orig_dom_state = dom_info_state (CDI_DOMINATORS);
733 bitmap names_defined_in_bb = BITMAP_ALLOC (NULL);
735 gcc_assert (!need_ssa_update_p ());
739 timevar_push (TV_TREE_SSA_VERIFY);
741 /* Keep track of SSA names present in the IL. */
742 for (i = 1; i < num_ssa_names; i++)
744 tree name = ssa_name (i);
748 TREE_VISITED (name) = 0;
750 stmt = SSA_NAME_DEF_STMT (name);
751 if (!gimple_nop_p (stmt))
753 basic_block bb = gimple_bb (stmt);
754 verify_def (bb, definition_block,
755 name, stmt, !is_gimple_reg (name));
761 calculate_dominance_info (CDI_DOMINATORS);
763 /* Now verify all the uses and make sure they agree with the definitions
764 found in the previous pass. */
770 gimple_stmt_iterator gsi;
772 /* Make sure that all edges have a clear 'aux' field. */
773 FOR_EACH_EDGE (e, ei, bb->preds)
777 error ("AUX pointer initialized for edge %d->%d", e->src->index,
783 /* Verify the arguments for every PHI node in the block. */
784 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
786 phi = gsi_stmt (gsi);
787 if (verify_phi_args (phi, bb, definition_block))
790 bitmap_set_bit (names_defined_in_bb,
791 SSA_NAME_VERSION (gimple_phi_result (phi)));
794 /* Now verify all the uses and vuses in every statement of the block. */
795 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
797 gimple stmt = gsi_stmt (gsi);
800 if (check_modified_stmt && gimple_modified_p (stmt))
802 error ("stmt (%p) marked modified after optimization pass: ",
804 print_gimple_stmt (stderr, stmt, 0, TDF_VOPS);
808 if (is_gimple_assign (stmt)
809 && TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
811 tree lhs, base_address;
813 lhs = gimple_assign_lhs (stmt);
814 base_address = get_base_address (lhs);
817 && gimple_aliases_computed_p (cfun)
818 && SSA_VAR_P (base_address)
819 && !gimple_has_volatile_ops (stmt)
820 && ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF))
822 error ("statement makes a memory store, but has no VDEFS");
823 print_gimple_stmt (stderr, stmt, 0, TDF_VOPS);
828 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_VIRTUALS)
830 if (verify_ssa_name (op, true))
832 error ("in statement");
833 print_gimple_stmt (stderr, stmt, 0, TDF_VOPS|TDF_MEMSYMS);
838 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE|SSA_OP_DEF)
840 if (verify_ssa_name (op, false))
842 error ("in statement");
843 print_gimple_stmt (stderr, stmt, 0, TDF_VOPS|TDF_MEMSYMS);
848 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE|SSA_OP_VUSE)
850 op = USE_FROM_PTR (use_p);
851 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
852 use_p, stmt, false, names_defined_in_bb))
856 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
857 bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
860 bitmap_clear (names_defined_in_bb);
863 /* Finally, verify alias information. */
864 if (gimple_aliases_computed_p (cfun))
865 verify_alias_info ();
867 free (definition_block);
869 /* Restore the dominance information to its prior known state, so
870 that we do not perturb the compiler's subsequent behavior. */
871 if (orig_dom_state == DOM_NONE)
872 free_dominance_info (CDI_DOMINATORS);
874 set_dom_info_availability (CDI_DOMINATORS, orig_dom_state);
876 BITMAP_FREE (names_defined_in_bb);
877 timevar_pop (TV_TREE_SSA_VERIFY);
881 internal_error ("verify_ssa failed");
884 /* Return true if the uid in both int tree maps are equal. */
887 int_tree_map_eq (const void *va, const void *vb)
889 const struct int_tree_map *a = (const struct int_tree_map *) va;
890 const struct int_tree_map *b = (const struct int_tree_map *) vb;
891 return (a->uid == b->uid);
894 /* Hash a UID in a int_tree_map. */
897 int_tree_map_hash (const void *item)
899 return ((const struct int_tree_map *)item)->uid;
902 /* Return true if the DECL_UID in both trees are equal. */
905 uid_decl_map_eq (const void *va, const void *vb)
907 const_tree a = (const_tree) va;
908 const_tree b = (const_tree) vb;
909 return (a->decl_minimal.uid == b->decl_minimal.uid);
912 /* Hash a tree in a uid_decl_map. */
915 uid_decl_map_hash (const void *item)
917 return ((const_tree)item)->decl_minimal.uid;
920 /* Return true if the DECL_UID in both trees are equal. */
923 uid_ssaname_map_eq (const void *va, const void *vb)
925 const_tree a = (const_tree) va;
926 const_tree b = (const_tree) vb;
927 return (a->ssa_name.var->decl_minimal.uid == b->ssa_name.var->decl_minimal.uid);
930 /* Hash a tree in a uid_decl_map. */
933 uid_ssaname_map_hash (const void *item)
935 return ((const_tree)item)->ssa_name.var->decl_minimal.uid;
939 /* Initialize global DFA and SSA structures. */
942 init_tree_ssa (struct function *fn)
944 fn->gimple_df = GGC_CNEW (struct gimple_df);
945 fn->gimple_df->referenced_vars = htab_create_ggc (20, uid_decl_map_hash,
946 uid_decl_map_eq, NULL);
947 fn->gimple_df->default_defs = htab_create_ggc (20, uid_ssaname_map_hash,
948 uid_ssaname_map_eq, NULL);
949 fn->gimple_df->call_clobbered_vars = BITMAP_GGC_ALLOC ();
950 fn->gimple_df->call_used_vars = BITMAP_GGC_ALLOC ();
951 fn->gimple_df->addressable_vars = BITMAP_GGC_ALLOC ();
952 init_ssanames (fn, 0);
957 /* Deallocate memory associated with SSA data structures for FNDECL. */
960 delete_tree_ssa (void)
964 gimple_stmt_iterator gsi;
965 referenced_var_iterator rvi;
968 /* Release any ssa_names still in use. */
969 for (i = 0; i < num_ssa_names; i++)
971 tree var = ssa_name (i);
972 if (var && TREE_CODE (var) == SSA_NAME)
974 SSA_NAME_IMM_USE_NODE (var).prev = &(SSA_NAME_IMM_USE_NODE (var));
975 SSA_NAME_IMM_USE_NODE (var).next = &(SSA_NAME_IMM_USE_NODE (var));
977 release_ssa_name (var);
980 /* FIXME. This may not be necessary. We will release all this
981 memory en masse in free_ssa_operands. This clearing used to be
982 necessary to avoid problems with the inliner, but it may not be
986 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
988 gimple stmt = gsi_stmt (gsi);
990 if (gimple_has_ops (stmt))
992 gimple_set_def_ops (stmt, NULL);
993 gimple_set_use_ops (stmt, NULL);
994 gimple_set_addresses_taken (stmt, NULL);
997 if (gimple_has_mem_ops (stmt))
999 gimple_set_vdef_ops (stmt, NULL);
1000 gimple_set_vuse_ops (stmt, NULL);
1001 BITMAP_FREE (stmt->gsmem.membase.stores);
1002 BITMAP_FREE (stmt->gsmem.membase.loads);
1005 gimple_set_modified (stmt, true);
1007 set_phi_nodes (bb, NULL);
1010 /* Remove annotations from every referenced local variable. */
1011 FOR_EACH_REFERENCED_VAR (var, rvi)
1014 && (TREE_STATIC (var) || DECL_EXTERNAL (var)))
1016 var_ann (var)->mpt = NULL_TREE;
1017 var_ann (var)->symbol_mem_tag = NULL_TREE;
1021 ggc_free (var->base.ann);
1022 var->base.ann = NULL;
1024 htab_delete (gimple_referenced_vars (cfun));
1025 cfun->gimple_df->referenced_vars = NULL;
1030 /* We no longer maintain the SSA operand cache at this point. */
1031 if (ssa_operands_active ())
1032 fini_ssa_operands ();
1034 cfun->gimple_df->global_var = NULL_TREE;
1036 htab_delete (cfun->gimple_df->default_defs);
1037 cfun->gimple_df->default_defs = NULL;
1038 cfun->gimple_df->call_clobbered_vars = NULL;
1039 cfun->gimple_df->call_used_vars = NULL;
1040 cfun->gimple_df->addressable_vars = NULL;
1041 cfun->gimple_df->modified_noreturn_calls = NULL;
1042 if (gimple_aliases_computed_p (cfun))
1044 delete_alias_heapvars ();
1045 gcc_assert (!need_ssa_update_p ());
1047 cfun->gimple_df->aliases_computed_p = false;
1048 delete_mem_ref_stats (cfun);
1050 cfun->gimple_df = NULL;
1052 /* We no longer need the edge variable maps. */
1053 redirect_edge_var_map_destroy ();
1056 /* Helper function for useless_type_conversion_p. */
1059 useless_type_conversion_p_1 (tree outer_type, tree inner_type)
1061 /* Qualifiers on value types do not matter. */
1062 inner_type = TYPE_MAIN_VARIANT (inner_type);
1063 outer_type = TYPE_MAIN_VARIANT (outer_type);
1065 if (inner_type == outer_type)
1068 /* If we know the canonical types, compare them. */
1069 if (TYPE_CANONICAL (inner_type)
1070 && TYPE_CANONICAL (inner_type) == TYPE_CANONICAL (outer_type))
1073 /* Changes in machine mode are never useless conversions. */
1074 if (TYPE_MODE (inner_type) != TYPE_MODE (outer_type))
1077 /* If both the inner and outer types are integral types, then the
1078 conversion is not necessary if they have the same mode and
1079 signedness and precision, and both or neither are boolean. */
1080 if (INTEGRAL_TYPE_P (inner_type)
1081 && INTEGRAL_TYPE_P (outer_type))
1083 /* Preserve changes in signedness or precision. */
1084 if (TYPE_UNSIGNED (inner_type) != TYPE_UNSIGNED (outer_type)
1085 || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
1088 /* Conversions from a non-base to a base type are not useless.
1089 This way we preserve the invariant to do arithmetic in
1091 if (TREE_TYPE (inner_type)
1092 && TREE_TYPE (inner_type) != inner_type
1093 && (TREE_TYPE (outer_type) == outer_type
1094 || TREE_TYPE (outer_type) == NULL_TREE))
1097 /* We don't need to preserve changes in the types minimum or
1098 maximum value in general as these do not generate code
1099 unless the types precisions are different. */
1104 /* Scalar floating point types with the same mode are compatible. */
1105 else if (SCALAR_FLOAT_TYPE_P (inner_type)
1106 && SCALAR_FLOAT_TYPE_P (outer_type))
1109 /* We need to take special care recursing to pointed-to types. */
1110 else if (POINTER_TYPE_P (inner_type)
1111 && POINTER_TYPE_P (outer_type))
1113 /* Don't lose casts between pointers to volatile and non-volatile
1114 qualified types. Doing so would result in changing the semantics
1115 of later accesses. */
1116 if ((TYPE_VOLATILE (TREE_TYPE (outer_type))
1117 != TYPE_VOLATILE (TREE_TYPE (inner_type)))
1118 && TYPE_VOLATILE (TREE_TYPE (outer_type)))
1121 /* Do not lose casts between pointers with different
1122 TYPE_REF_CAN_ALIAS_ALL setting or alias sets. */
1123 if ((TYPE_REF_CAN_ALIAS_ALL (inner_type)
1124 != TYPE_REF_CAN_ALIAS_ALL (outer_type))
1125 || (get_alias_set (TREE_TYPE (inner_type))
1126 != get_alias_set (TREE_TYPE (outer_type))))
1129 /* We do not care for const qualification of the pointed-to types
1130 as const qualification has no semantic value to the middle-end. */
1132 /* Do not lose casts to restrict qualified pointers. */
1133 if ((TYPE_RESTRICT (outer_type)
1134 != TYPE_RESTRICT (inner_type))
1135 && TYPE_RESTRICT (outer_type))
1138 /* Otherwise pointers/references are equivalent if their pointed
1139 to types are effectively the same. We can strip qualifiers
1140 on pointed-to types for further comparison, which is done in
1142 return useless_type_conversion_p_1 (TREE_TYPE (outer_type),
1143 TREE_TYPE (inner_type));
1146 /* Recurse for complex types. */
1147 else if (TREE_CODE (inner_type) == COMPLEX_TYPE
1148 && TREE_CODE (outer_type) == COMPLEX_TYPE)
1149 return useless_type_conversion_p_1 (TREE_TYPE (outer_type),
1150 TREE_TYPE (inner_type));
1152 /* Recurse for vector types with the same number of subparts. */
1153 else if (TREE_CODE (inner_type) == VECTOR_TYPE
1154 && TREE_CODE (outer_type) == VECTOR_TYPE
1155 && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
1156 return useless_type_conversion_p_1 (TREE_TYPE (outer_type),
1157 TREE_TYPE (inner_type));
1159 /* For aggregates we may need to fall back to structural equality
1161 else if (AGGREGATE_TYPE_P (inner_type)
1162 && AGGREGATE_TYPE_P (outer_type))
1164 /* Different types of aggregates are incompatible. */
1165 if (TREE_CODE (inner_type) != TREE_CODE (outer_type))
1168 /* ??? This seems to be necessary even for aggregates that don't
1169 have TYPE_STRUCTURAL_EQUALITY_P set. */
1171 /* ??? This should eventually just return false. */
1172 return lang_hooks.types_compatible_p (inner_type, outer_type);
1174 /* Also for functions and possibly other types with
1175 TYPE_STRUCTURAL_EQUALITY_P set. */
1176 else if (TYPE_STRUCTURAL_EQUALITY_P (inner_type)
1177 && TYPE_STRUCTURAL_EQUALITY_P (outer_type))
1178 return lang_hooks.types_compatible_p (inner_type, outer_type);
1183 /* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a
1184 useless type conversion, otherwise return false.
1186 This function implicitly defines the middle-end type system. With
1187 the notion of 'a < b' meaning that useless_type_conversion_p (a, b)
1188 holds and 'a > b' meaning that useless_type_conversion_p (b, a) holds,
1189 the following invariants shall be fulfilled:
1191 1) useless_type_conversion_p is transitive.
1192 If a < b and b < c then a < c.
1194 2) useless_type_conversion_p is not symmetric.
1195 From a < b does not follow a > b.
1197 3) Types define the available set of operations applicable to values.
1198 A type conversion is useless if the operations for the target type
1199 is a subset of the operations for the source type. For example
1200 casts to void* are useless, casts from void* are not (void* can't
1201 be dereferenced or offsetted, but copied, hence its set of operations
1202 is a strict subset of that of all other data pointer types). Casts
1203 to const T* are useless (can't be written to), casts from const T*
1207 useless_type_conversion_p (tree outer_type, tree inner_type)
1209 /* If the outer type is (void *), then the conversion is not
1210 necessary. We have to make sure to not apply this while
1211 recursing though. */
1212 if (POINTER_TYPE_P (inner_type)
1213 && POINTER_TYPE_P (outer_type)
1214 && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
1217 return useless_type_conversion_p_1 (outer_type, inner_type);
1220 /* Return true if a conversion from either type of TYPE1 and TYPE2
1221 to the other is not required. Otherwise return false. */
1224 types_compatible_p (tree type1, tree type2)
1226 return (type1 == type2
1227 || (useless_type_conversion_p (type1, type2)
1228 && useless_type_conversion_p (type2, type1)));
1231 /* Return true if EXPR is a useless type conversion, otherwise return
1235 tree_ssa_useless_type_conversion (tree expr)
1237 /* If we have an assignment that merely uses a NOP_EXPR to change
1238 the top of the RHS to the type of the LHS and the type conversion
1239 is "safe", then strip away the type conversion so that we can
1240 enter LHS = RHS into the const_and_copies table. */
1241 if (CONVERT_EXPR_P (expr)
1242 || TREE_CODE (expr) == VIEW_CONVERT_EXPR
1243 || TREE_CODE (expr) == NON_LVALUE_EXPR)
1244 return useless_type_conversion_p
1246 TREE_TYPE (TREE_OPERAND (expr, 0)));
1252 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
1253 described in walk_use_def_chains.
1255 VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
1256 infinite loops. We used to have a bitmap for this to just mark
1257 SSA versions we had visited. But non-sparse bitmaps are way too
1258 expensive, while sparse bitmaps may cause quadratic behavior.
1260 IS_DFS is true if the caller wants to perform a depth-first search
1261 when visiting PHI nodes. A DFS will visit each PHI argument and
1262 call FN after each one. Otherwise, all the arguments are
1263 visited first and then FN is called with each of the visited
1264 arguments in a separate pass. */
1267 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
1268 struct pointer_set_t *visited, bool is_dfs)
1272 if (pointer_set_insert (visited, var))
1275 def_stmt = SSA_NAME_DEF_STMT (var);
1277 if (gimple_code (def_stmt) != GIMPLE_PHI)
1279 /* If we reached the end of the use-def chain, call FN. */
1280 return fn (var, def_stmt, data);
1286 /* When doing a breadth-first search, call FN before following the
1287 use-def links for each argument. */
1289 for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
1290 if (fn (gimple_phi_arg_def (def_stmt, i), def_stmt, data))
1293 /* Follow use-def links out of each PHI argument. */
1294 for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
1296 tree arg = gimple_phi_arg_def (def_stmt, i);
1298 /* ARG may be NULL for newly introduced PHI nodes. */
1300 && TREE_CODE (arg) == SSA_NAME
1301 && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
1305 /* When doing a depth-first search, call FN after following the
1306 use-def links for each argument. */
1308 for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
1309 if (fn (gimple_phi_arg_def (def_stmt, i), def_stmt, data))
1318 /* Walk use-def chains starting at the SSA variable VAR. Call
1319 function FN at each reaching definition found. FN takes three
1320 arguments: VAR, its defining statement (DEF_STMT) and a generic
1321 pointer to whatever state information that FN may want to maintain
1322 (DATA). FN is able to stop the walk by returning true, otherwise
1323 in order to continue the walk, FN should return false.
1325 Note, that if DEF_STMT is a PHI node, the semantics are slightly
1326 different. The first argument to FN is no longer the original
1327 variable VAR, but the PHI argument currently being examined. If FN
1328 wants to get at VAR, it should call PHI_RESULT (PHI).
1330 If IS_DFS is true, this function will:
1332 1- walk the use-def chains for all the PHI arguments, and,
1333 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
1335 If IS_DFS is false, the two steps above are done in reverse order
1336 (i.e., a breadth-first search). */
1339 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
1344 gcc_assert (TREE_CODE (var) == SSA_NAME);
1346 def_stmt = SSA_NAME_DEF_STMT (var);
1348 /* We only need to recurse if the reaching definition comes from a PHI
1350 if (gimple_code (def_stmt) != GIMPLE_PHI)
1351 (*fn) (var, def_stmt, data);
1354 struct pointer_set_t *visited = pointer_set_create ();
1355 walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
1356 pointer_set_destroy (visited);
1361 /* Return true if T, an SSA_NAME, has an undefined value. */
1364 ssa_undefined_value_p (tree t)
1366 tree var = SSA_NAME_VAR (t);
1368 /* Parameters get their initial value from the function entry. */
1369 if (TREE_CODE (var) == PARM_DECL)
1372 /* Hard register variables get their initial value from the ether. */
1373 if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1376 /* The value is undefined iff its definition statement is empty. */
1377 return gimple_nop_p (SSA_NAME_DEF_STMT (t));
1380 /* Emit warnings for uninitialized variables. This is done in two passes.
1382 The first pass notices real uses of SSA names with undefined values.
1383 Such uses are unconditionally uninitialized, and we can be certain that
1384 such a use is a mistake. This pass is run before most optimizations,
1385 so that we catch as many as we can.
1387 The second pass follows PHI nodes to find uses that are potentially
1388 uninitialized. In this case we can't necessarily prove that the use
1389 is really uninitialized. This pass is run after most optimizations,
1390 so that we thread as many jumps and possible, and delete as much dead
1391 code as possible, in order to reduce false positives. We also look
1392 again for plain uninitialized variables, since optimization may have
1393 changed conditionally uninitialized to unconditionally uninitialized. */
1395 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1396 warning text is in MSGID and LOCUS may contain a location or be null. */
1399 warn_uninit (tree t, const char *gmsgid, void *data)
1401 tree var = SSA_NAME_VAR (t);
1402 gimple context = (gimple) data;
1403 location_t location;
1404 expanded_location xloc, floc;
1406 if (!ssa_undefined_value_p (t))
1409 /* TREE_NO_WARNING either means we already warned, or the front end
1410 wishes to suppress the warning. */
1411 if (TREE_NO_WARNING (var))
1414 /* Do not warn if it can be initialized outside this module. */
1415 if (is_global_var (var))
1418 location = (context != NULL && gimple_has_location (context))
1419 ? gimple_location (context)
1420 : DECL_SOURCE_LOCATION (var);
1421 xloc = expand_location (location);
1422 floc = expand_location (DECL_SOURCE_LOCATION (cfun->decl));
1423 if (warning_at (location, OPT_Wuninitialized, gmsgid, var))
1425 TREE_NO_WARNING (var) = 1;
1427 if (xloc.file != floc.file
1428 || xloc.line < floc.line
1429 || xloc.line > LOCATION_LINE (cfun->function_end_locus))
1430 inform (input_location, "%J%qD was declared here", var, var);
1436 bool always_executed;
1437 bool warn_possibly_uninitialized;
1440 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1441 and warn about them. */
1444 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data_)
1446 struct walk_stmt_info *wi = (struct walk_stmt_info *) data_;
1447 struct walk_data *data = (struct walk_data *) wi->info;
1450 /* We do not care about LHS. */
1454 switch (TREE_CODE (t))
1457 /* Taking the address of an uninitialized variable does not
1458 count as using it. */
1464 /* A VAR_DECL in the RHS of a gimple statement may mean that
1465 this variable is loaded from memory. */
1469 /* If there is not gimple stmt,
1470 or alias information has not been computed,
1471 then we cannot check VUSE ops. */
1472 if (data->stmt == NULL
1473 || !gimple_aliases_computed_p (cfun))
1476 vuse = SINGLE_SSA_USE_OPERAND (data->stmt, SSA_OP_VUSE);
1477 if (vuse == NULL_USE_OPERAND_P)
1480 op = USE_FROM_PTR (vuse);
1481 if (t != SSA_NAME_VAR (op)
1482 || !SSA_NAME_IS_DEFAULT_DEF (op))
1484 /* If this is a VUSE of t and it is the default definition,
1485 then warn about op. */
1487 /* Fall through into SSA_NAME. */
1491 /* We only do data flow with SSA_NAMEs, so that's all we
1493 if (data->always_executed)
1494 warn_uninit (t, "%qD is used uninitialized in this function",
1496 else if (data->warn_possibly_uninitialized)
1497 warn_uninit (t, "%qD may be used uninitialized in this function",
1504 /* The total store transformation performed during gimplification
1505 creates uninitialized variable uses. If all is well, these will
1506 be optimized away, so don't warn now. */
1507 if (TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
1512 if (IS_TYPE_OR_DECL_P (t))
1520 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1521 and warn about them. */
1524 warn_uninitialized_phi (gimple phi)
1526 size_t i, n = gimple_phi_num_args (phi);
1528 /* Don't look at memory tags. */
1529 if (!is_gimple_reg (gimple_phi_result (phi)))
1532 for (i = 0; i < n; ++i)
1534 tree op = gimple_phi_arg_def (phi, i);
1535 if (TREE_CODE (op) == SSA_NAME)
1536 warn_uninit (op, "%qD may be used uninitialized in this function",
1542 warn_uninitialized_vars (bool warn_possibly_uninitialized)
1544 gimple_stmt_iterator gsi;
1546 struct walk_data data;
1548 data.warn_possibly_uninitialized = warn_possibly_uninitialized;
1550 calculate_dominance_info (CDI_POST_DOMINATORS);
1554 data.always_executed = dominated_by_p (CDI_POST_DOMINATORS,
1555 single_succ (ENTRY_BLOCK_PTR), bb);
1556 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1558 struct walk_stmt_info wi;
1559 data.stmt = gsi_stmt (gsi);
1560 memset (&wi, 0, sizeof (wi));
1562 walk_gimple_op (gsi_stmt (gsi), warn_uninitialized_var, &wi);
1569 execute_early_warn_uninitialized (void)
1571 /* Currently, this pass runs always but
1572 execute_late_warn_uninitialized only runs with optimization. With
1573 optimization we want to warn about possible uninitialized as late
1574 as possible, thus don't do it here. However, without
1575 optimization we need to warn here about "may be uninitialized".
1577 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize);
1582 execute_late_warn_uninitialized (void)
1585 gimple_stmt_iterator gsi;
1587 /* Re-do the plain uninitialized variable check, as optimization may have
1588 straightened control flow. Do this first so that we don't accidentally
1589 get a "may be" warning when we'd have seen an "is" warning later. */
1590 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
1593 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1594 warn_uninitialized_phi (gsi_stmt (gsi));
1600 gate_warn_uninitialized (void)
1602 return warn_uninitialized != 0;
1605 struct gimple_opt_pass pass_early_warn_uninitialized =
1610 gate_warn_uninitialized, /* gate */
1611 execute_early_warn_uninitialized, /* execute */
1614 0, /* static_pass_number */
1616 PROP_ssa, /* properties_required */
1617 0, /* properties_provided */
1618 0, /* properties_destroyed */
1619 0, /* todo_flags_start */
1620 0 /* todo_flags_finish */
1624 struct gimple_opt_pass pass_late_warn_uninitialized =
1629 gate_warn_uninitialized, /* gate */
1630 execute_late_warn_uninitialized, /* execute */
1633 0, /* static_pass_number */
1635 PROP_ssa, /* properties_required */
1636 0, /* properties_provided */
1637 0, /* properties_destroyed */
1638 0, /* todo_flags_start */
1639 0 /* todo_flags_finish */
1643 /* Compute TREE_ADDRESSABLE for local variables. */
1646 execute_update_addresses_taken (void)
1649 referenced_var_iterator rvi;
1650 gimple_stmt_iterator gsi;
1652 bitmap addresses_taken = BITMAP_ALLOC (NULL);
1653 bitmap vars_updated = BITMAP_ALLOC (NULL);
1654 bool update_vops = false;
1656 /* Collect into ADDRESSES_TAKEN all variables whose address is taken within
1657 the function body. */
1660 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1662 bitmap taken = gimple_addresses_taken (gsi_stmt (gsi));
1664 bitmap_ior_into (addresses_taken, taken);
1667 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1670 gimple phi = gsi_stmt (gsi);
1672 for (i = 0; i < gimple_phi_num_args (phi); i++)
1674 tree op = PHI_ARG_DEF (phi, i), var;
1675 if (TREE_CODE (op) == ADDR_EXPR
1676 && (var = get_base_address (TREE_OPERAND (op, 0))) != NULL
1678 bitmap_set_bit (addresses_taken, DECL_UID (var));
1683 /* When possible, clear ADDRESSABLE bit and mark variable for conversion into
1685 FOR_EACH_REFERENCED_VAR (var, rvi)
1686 if (!is_global_var (var)
1687 && TREE_CODE (var) != RESULT_DECL
1688 && TREE_ADDRESSABLE (var)
1689 && !bitmap_bit_p (addresses_taken, DECL_UID (var)))
1691 TREE_ADDRESSABLE (var) = 0;
1692 if (is_gimple_reg (var))
1693 mark_sym_for_renaming (var);
1695 bitmap_set_bit (vars_updated, DECL_UID (var));
1698 fprintf (dump_file, "No longer having address taken ");
1699 print_generic_expr (dump_file, var, 0);
1700 fprintf (dump_file, "\n");
1704 /* Operand caches needs to be recomputed for operands referencing the updated
1708 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1710 gimple stmt = gsi_stmt (gsi);
1712 if ((gimple_loaded_syms (stmt)
1713 && bitmap_intersect_p (gimple_loaded_syms (stmt), vars_updated))
1714 || (gimple_stored_syms (stmt)
1715 && bitmap_intersect_p (gimple_stored_syms (stmt), vars_updated)))
1718 BITMAP_FREE (addresses_taken);
1719 BITMAP_FREE (vars_updated);
1723 struct gimple_opt_pass pass_update_address_taken =
1727 "addressables", /* name */
1729 execute_update_addresses_taken, /* execute */
1732 0, /* static_pass_number */
1734 PROP_ssa, /* properties_required */
1735 0, /* properties_provided */
1736 0, /* properties_destroyed */
1737 0, /* todo_flags_start */
1738 TODO_update_ssa /* todo_flags_finish */