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"
40 #include "tree-gimple.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 = *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);
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);
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)
176 redirect_edge_var_map_clear (e);
178 /* Remove the appropriate PHI arguments in E's destination block. */
179 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
181 tree def = PHI_ARG_DEF (phi, e->dest_idx);
183 if (def == NULL_TREE)
186 redirect_edge_var_map_add (e, PHI_RESULT (phi), def);
189 e = redirect_edge_succ_nodup (e, dest);
194 /* Add PHI arguments queued in PENDING_STMT list on edge E to edge
198 flush_pending_stmts (edge e)
201 edge_var_map_vector v;
205 v = redirect_edge_var_map_vector (e);
209 for (phi = phi_nodes (e->dest), i = 0;
210 phi && VEC_iterate (edge_var_map, v, i, vm);
211 phi = PHI_CHAIN (phi), i++)
213 tree def = redirect_edge_var_map_def (vm);
214 add_phi_arg (phi, def, e);
217 redirect_edge_var_map_clear (e);
220 /* Return true if SSA_NAME is malformed and mark it visited.
222 IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
226 verify_ssa_name (tree ssa_name, bool is_virtual)
228 if (TREE_CODE (ssa_name) != SSA_NAME)
230 error ("expected an SSA_NAME object");
234 if (TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name)))
236 error ("type mismatch between an SSA_NAME and its symbol");
240 if (SSA_NAME_IN_FREE_LIST (ssa_name))
242 error ("found an SSA_NAME that had been released into the free pool");
246 if (is_virtual && is_gimple_reg (ssa_name))
248 error ("found a virtual definition for a GIMPLE register");
252 if (!is_virtual && !is_gimple_reg (ssa_name))
254 error ("found a real definition for a non-register");
258 if (SSA_NAME_IS_DEFAULT_DEF (ssa_name)
259 && !IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name)))
261 error ("found a default name with a non-empty defining statement");
269 /* Return true if the definition of SSA_NAME at block BB is malformed.
271 STMT is the statement where SSA_NAME is created.
273 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
274 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
275 it means that the block in that array slot contains the
276 definition of SSA_NAME.
278 IS_VIRTUAL is true if SSA_NAME is created by a VDEF. */
281 verify_def (basic_block bb, basic_block *definition_block, tree ssa_name,
282 tree stmt, bool is_virtual)
284 if (verify_ssa_name (ssa_name, is_virtual))
287 if (definition_block[SSA_NAME_VERSION (ssa_name)])
289 error ("SSA_NAME created in two different blocks %i and %i",
290 definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index);
294 definition_block[SSA_NAME_VERSION (ssa_name)] = bb;
296 if (SSA_NAME_DEF_STMT (ssa_name) != stmt)
298 error ("SSA_NAME_DEF_STMT is wrong");
299 fprintf (stderr, "Expected definition statement:\n");
300 print_generic_stmt (stderr, SSA_NAME_DEF_STMT (ssa_name), TDF_VOPS);
301 fprintf (stderr, "\nActual definition statement:\n");
302 print_generic_stmt (stderr, stmt, TDF_VOPS);
309 fprintf (stderr, "while verifying SSA_NAME ");
310 print_generic_expr (stderr, ssa_name, 0);
311 fprintf (stderr, " in statement\n");
312 print_generic_stmt (stderr, stmt, TDF_VOPS);
318 /* Return true if the use of SSA_NAME at statement STMT in block BB is
321 DEF_BB is the block where SSA_NAME was found to be created.
323 IDOM contains immediate dominator information for the flowgraph.
325 CHECK_ABNORMAL is true if the caller wants to check whether this use
326 is flowing through an abnormal edge (only used when checking PHI
329 If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
330 that are defined before STMT in basic block BB. */
333 verify_use (basic_block bb, basic_block def_bb, use_operand_p use_p,
334 tree stmt, bool check_abnormal, bitmap names_defined_in_bb)
337 tree ssa_name = USE_FROM_PTR (use_p);
339 if (!TREE_VISITED (ssa_name))
340 if (verify_imm_links (stderr, ssa_name))
343 TREE_VISITED (ssa_name) = 1;
345 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name))
346 && SSA_NAME_IS_DEFAULT_DEF (ssa_name))
347 ; /* Default definitions have empty statements. Nothing to do. */
350 error ("missing definition");
353 else if (bb != def_bb
354 && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
356 error ("definition in block %i does not dominate use in block %i",
357 def_bb->index, bb->index);
360 else if (bb == def_bb
361 && names_defined_in_bb != NULL
362 && !bitmap_bit_p (names_defined_in_bb, SSA_NAME_VERSION (ssa_name)))
364 error ("definition in block %i follows the use", def_bb->index);
369 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
371 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
375 /* Make sure the use is in an appropriate list by checking the previous
376 element to make sure it's the same. */
377 if (use_p->prev == NULL)
379 error ("no immediate_use list");
385 if (use_p->prev->use == NULL)
386 listvar = use_p->prev->stmt;
388 listvar = USE_FROM_PTR (use_p->prev);
389 if (listvar != ssa_name)
391 error ("wrong immediate use list");
398 fprintf (stderr, "for SSA_NAME: ");
399 print_generic_expr (stderr, ssa_name, TDF_VOPS);
400 fprintf (stderr, " in statement:\n");
401 print_generic_stmt (stderr, stmt, TDF_VOPS);
408 /* Return true if any of the arguments for PHI node PHI at block BB is
411 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
412 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
413 it means that the block in that array slot contains the
414 definition of SSA_NAME. */
417 verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)
421 unsigned i, phi_num_args = PHI_NUM_ARGS (phi);
423 if (EDGE_COUNT (bb->preds) != phi_num_args)
425 error ("incoming edge count does not match number of PHI arguments");
430 for (i = 0; i < phi_num_args; i++)
432 use_operand_p op_p = PHI_ARG_DEF_PTR (phi, i);
433 tree op = USE_FROM_PTR (op_p);
435 e = EDGE_PRED (bb, i);
439 error ("PHI argument is missing for edge %d->%d",
446 if (TREE_CODE (op) != SSA_NAME && !is_gimple_min_invariant (op))
448 error ("PHI argument is not SSA_NAME, or invariant");
452 if (TREE_CODE (op) == SSA_NAME)
454 err = verify_ssa_name (op, !is_gimple_reg (PHI_RESULT (phi)));
455 err |= verify_use (e->src, definition_block[SSA_NAME_VERSION (op)],
456 op_p, phi, e->flags & EDGE_ABNORMAL, NULL);
461 error ("wrong edge %d->%d for PHI argument",
462 e->src->index, e->dest->index);
468 fprintf (stderr, "PHI argument\n");
469 print_generic_stmt (stderr, op, TDF_VOPS);
477 fprintf (stderr, "for PHI node\n");
478 print_generic_stmt (stderr, phi, TDF_VOPS|TDF_MEMSYMS);
487 verify_flow_insensitive_alias_info (void)
490 referenced_var_iterator rvi;
492 FOR_EACH_REFERENCED_VAR (var, rvi)
499 if (!MTAG_P (var) || !MTAG_ALIASES (var))
502 aliases = MTAG_ALIASES (var);
504 EXECUTE_IF_SET_IN_BITMAP (aliases, 0, j, bi)
506 alias = referenced_var (j);
508 if (TREE_CODE (alias) != MEMORY_PARTITION_TAG
509 && !may_be_aliased (alias))
511 error ("non-addressable variable inside an alias set");
512 debug_variable (alias);
521 debug_variable (var);
522 internal_error ("verify_flow_insensitive_alias_info failed");
527 verify_flow_sensitive_alias_info (void)
532 for (i = 1; i < num_ssa_names; i++)
536 struct ptr_info_def *pi;
543 /* We only care for pointers that are actually referenced in the
545 if (!POINTER_TYPE_P (TREE_TYPE (ptr)) || !TREE_VISITED (ptr))
548 /* RESULT_DECL is special. If it's a GIMPLE register, then it
549 is only written-to only once in the return statement.
550 Otherwise, aggregate RESULT_DECLs may be written-to more than
551 once in virtual operands. */
552 var = SSA_NAME_VAR (ptr);
553 if (TREE_CODE (var) == RESULT_DECL
554 && is_gimple_reg (ptr))
557 pi = SSA_NAME_PTR_INFO (ptr);
562 if (pi->is_dereferenced && !pi->name_mem_tag && !ann->symbol_mem_tag)
564 error ("dereferenced pointers should have a name or a symbol tag");
569 && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars)))
571 error ("pointers with a memory tag, should have points-to sets");
575 if (pi->value_escapes_p
576 && pi->escape_mask & ~ESCAPE_TO_RETURN
579 tree t = memory_partition (pi->name_mem_tag);
581 t = pi->name_mem_tag;
583 if (!is_call_clobbered (t))
585 error ("pointer escapes but its name tag is not call-clobbered");
594 debug_variable (ptr);
595 internal_error ("verify_flow_sensitive_alias_info failed");
599 /* Verify the consistency of call clobbering information. */
602 verify_call_clobbering (void)
607 referenced_var_iterator rvi;
609 /* At all times, the result of the call_clobbered flag should
610 match the result of the call_clobbered_vars bitmap. Verify both
611 that everything in call_clobbered_vars is marked
612 call_clobbered, and that everything marked
613 call_clobbered is in call_clobbered_vars. */
614 EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun), 0, i, bi)
616 var = referenced_var (i);
618 if (memory_partition (var))
619 var = memory_partition (var);
621 if (!MTAG_P (var) && !var_ann (var)->call_clobbered)
623 error ("variable in call_clobbered_vars but not marked "
625 debug_variable (var);
630 FOR_EACH_REFERENCED_VAR (var, rvi)
632 if (is_gimple_reg (var))
635 if (memory_partition (var))
636 var = memory_partition (var);
639 && var_ann (var)->call_clobbered
640 && !bitmap_bit_p (gimple_call_clobbered_vars (cfun), DECL_UID (var)))
642 error ("variable marked call_clobbered but not in "
643 "call_clobbered_vars bitmap.");
644 debug_variable (var);
652 internal_error ("verify_call_clobbering failed");
656 /* Verify invariants in memory partitions. */
659 verify_memory_partitions (void)
663 VEC(tree,heap) *mpt_table = gimple_ssa_operands (cfun)->mpt_table;
664 struct pointer_set_t *partitioned_syms = pointer_set_create ();
666 for (i = 0; VEC_iterate (tree, mpt_table, i, mpt); i++)
671 if (MPT_SYMBOLS (mpt) == NULL)
673 error ("Memory partitions should have at least one symbol");
674 debug_variable (mpt);
678 EXECUTE_IF_SET_IN_BITMAP (MPT_SYMBOLS (mpt), 0, j, bj)
680 tree var = referenced_var (j);
681 if (pointer_set_insert (partitioned_syms, var))
683 error ("Partitioned symbols should belong to exactly one "
685 debug_variable (var);
691 pointer_set_destroy (partitioned_syms);
696 internal_error ("verify_memory_partitions failed");
700 /* Verify the consistency of aliasing information. */
703 verify_alias_info (void)
705 verify_flow_sensitive_alias_info ();
706 verify_call_clobbering ();
707 verify_flow_insensitive_alias_info ();
708 verify_memory_partitions ();
712 /* Verify common invariants in the SSA web.
713 TODO: verify the variable annotations. */
716 verify_ssa (bool check_modified_stmt)
720 basic_block *definition_block = XCNEWVEC (basic_block, num_ssa_names);
723 enum dom_state orig_dom_state = dom_info_state (CDI_DOMINATORS);
724 bitmap names_defined_in_bb = BITMAP_ALLOC (NULL);
726 gcc_assert (!need_ssa_update_p ());
730 timevar_push (TV_TREE_SSA_VERIFY);
732 /* Keep track of SSA names present in the IL. */
733 for (i = 1; i < num_ssa_names; i++)
735 tree name = ssa_name (i);
739 TREE_VISITED (name) = 0;
741 stmt = SSA_NAME_DEF_STMT (name);
742 if (!IS_EMPTY_STMT (stmt))
744 basic_block bb = bb_for_stmt (stmt);
745 verify_def (bb, definition_block,
746 name, stmt, !is_gimple_reg (name));
752 calculate_dominance_info (CDI_DOMINATORS);
754 /* Now verify all the uses and make sure they agree with the definitions
755 found in the previous pass. */
761 block_stmt_iterator bsi;
763 /* Make sure that all edges have a clear 'aux' field. */
764 FOR_EACH_EDGE (e, ei, bb->preds)
768 error ("AUX pointer initialized for edge %d->%d", e->src->index,
774 /* Verify the arguments for every PHI node in the block. */
775 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
777 if (verify_phi_args (phi, bb, definition_block))
780 bitmap_set_bit (names_defined_in_bb,
781 SSA_NAME_VERSION (PHI_RESULT (phi)));
784 /* Now verify all the uses and vuses in every statement of the block. */
785 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
787 tree stmt = bsi_stmt (bsi);
790 if (check_modified_stmt && stmt_modified_p (stmt))
792 error ("stmt (%p) marked modified after optimization pass: ",
794 print_generic_stmt (stderr, stmt, TDF_VOPS);
798 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
799 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) != SSA_NAME)
801 tree lhs, base_address;
803 lhs = GIMPLE_STMT_OPERAND (stmt, 0);
804 base_address = get_base_address (lhs);
807 && gimple_aliases_computed_p (cfun)
808 && SSA_VAR_P (base_address)
809 && !stmt_ann (stmt)->has_volatile_ops
810 && ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF))
812 error ("statement makes a memory store, but has no VDEFS");
813 print_generic_stmt (stderr, stmt, TDF_VOPS);
818 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_VIRTUALS)
820 if (verify_ssa_name (op, true))
822 error ("in statement");
823 print_generic_stmt (stderr, stmt, TDF_VOPS|TDF_MEMSYMS);
828 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE|SSA_OP_DEF)
830 if (verify_ssa_name (op, false))
832 error ("in statement");
833 print_generic_stmt (stderr, stmt, TDF_VOPS|TDF_MEMSYMS);
838 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE|SSA_OP_VUSE)
840 op = USE_FROM_PTR (use_p);
841 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
842 use_p, stmt, false, names_defined_in_bb))
846 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
847 bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
850 bitmap_clear (names_defined_in_bb);
853 /* Finally, verify alias information. */
854 if (gimple_aliases_computed_p (cfun))
855 verify_alias_info ();
857 free (definition_block);
859 /* Restore the dominance information to its prior known state, so
860 that we do not perturb the compiler's subsequent behavior. */
861 if (orig_dom_state == DOM_NONE)
862 free_dominance_info (CDI_DOMINATORS);
864 set_dom_info_availability (CDI_DOMINATORS, orig_dom_state);
866 BITMAP_FREE (names_defined_in_bb);
867 timevar_pop (TV_TREE_SSA_VERIFY);
871 internal_error ("verify_ssa failed");
874 /* Return true if the uid in both int tree maps are equal. */
877 int_tree_map_eq (const void *va, const void *vb)
879 const struct int_tree_map *a = (const struct int_tree_map *) va;
880 const struct int_tree_map *b = (const struct int_tree_map *) vb;
881 return (a->uid == b->uid);
884 /* Hash a UID in a int_tree_map. */
887 int_tree_map_hash (const void *item)
889 return ((const struct int_tree_map *)item)->uid;
892 /* Return true if the DECL_UID in both trees are equal. */
895 uid_decl_map_eq (const void *va, const void *vb)
897 const_tree a = (const_tree) va;
898 const_tree b = (const_tree) vb;
899 return (a->decl_minimal.uid == b->decl_minimal.uid);
902 /* Hash a tree in a uid_decl_map. */
905 uid_decl_map_hash (const void *item)
907 return ((const_tree)item)->decl_minimal.uid;
910 /* Return true if the DECL_UID in both trees are equal. */
913 uid_ssaname_map_eq (const void *va, const void *vb)
915 const_tree a = (const_tree) va;
916 const_tree b = (const_tree) vb;
917 return (a->ssa_name.var->decl_minimal.uid == b->ssa_name.var->decl_minimal.uid);
920 /* Hash a tree in a uid_decl_map. */
923 uid_ssaname_map_hash (const void *item)
925 return ((const_tree)item)->ssa_name.var->decl_minimal.uid;
929 /* Initialize global DFA and SSA structures. */
932 init_tree_ssa (struct function *fn)
934 fn->gimple_df = GGC_CNEW (struct gimple_df);
935 fn->gimple_df->referenced_vars = htab_create_ggc (20, uid_decl_map_hash,
936 uid_decl_map_eq, NULL);
937 fn->gimple_df->default_defs = htab_create_ggc (20, uid_ssaname_map_hash,
938 uid_ssaname_map_eq, NULL);
939 fn->gimple_df->call_clobbered_vars = BITMAP_GGC_ALLOC ();
940 fn->gimple_df->addressable_vars = BITMAP_GGC_ALLOC ();
941 init_ssanames (fn, 0);
946 /* Deallocate memory associated with SSA data structures for FNDECL. */
949 delete_tree_ssa (void)
953 block_stmt_iterator bsi;
954 referenced_var_iterator rvi;
957 /* Release any ssa_names still in use. */
958 for (i = 0; i < num_ssa_names; i++)
960 tree var = ssa_name (i);
961 if (var && TREE_CODE (var) == SSA_NAME)
963 SSA_NAME_IMM_USE_NODE (var).prev = &(SSA_NAME_IMM_USE_NODE (var));
964 SSA_NAME_IMM_USE_NODE (var).next = &(SSA_NAME_IMM_USE_NODE (var));
966 release_ssa_name (var);
969 /* Remove annotations from every tree in the function. */
972 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
974 tree stmt = bsi_stmt (bsi);
975 stmt_ann_t ann = get_stmt_ann (stmt);
977 free_ssa_operands (&ann->operands);
978 ann->addresses_taken = 0;
979 mark_stmt_modified (stmt);
981 set_phi_nodes (bb, NULL);
984 /* Remove annotations from every referenced local variable. */
985 FOR_EACH_REFERENCED_VAR (var, rvi)
988 && (TREE_STATIC (var) || DECL_EXTERNAL (var)))
990 var_ann (var)->mpt = NULL_TREE;
991 var_ann (var)->symbol_mem_tag = NULL_TREE;
995 ggc_free (var->base.ann);
996 var->base.ann = NULL;
998 htab_delete (gimple_referenced_vars (cfun));
999 cfun->gimple_df->referenced_vars = NULL;
1003 /* we no longer maintain the SSA operand cache at this point. */
1004 if (ssa_operands_active ())
1005 fini_ssa_operands ();
1007 cfun->gimple_df->global_var = NULL_TREE;
1009 htab_delete (cfun->gimple_df->default_defs);
1010 cfun->gimple_df->default_defs = NULL;
1011 cfun->gimple_df->call_clobbered_vars = NULL;
1012 cfun->gimple_df->addressable_vars = NULL;
1013 cfun->gimple_df->modified_noreturn_calls = NULL;
1014 if (gimple_aliases_computed_p (cfun))
1016 delete_alias_heapvars ();
1017 gcc_assert (!need_ssa_update_p ());
1019 cfun->gimple_df->aliases_computed_p = false;
1020 delete_mem_ref_stats (cfun);
1022 cfun->gimple_df = NULL;
1024 /* We no longer need the edge variable maps. */
1025 redirect_edge_var_map_destroy ();
1028 /* Helper function for useless_type_conversion_p. */
1031 useless_type_conversion_p_1 (tree outer_type, tree inner_type)
1033 /* Qualifiers on value types do not matter. */
1034 inner_type = TYPE_MAIN_VARIANT (inner_type);
1035 outer_type = TYPE_MAIN_VARIANT (outer_type);
1037 if (inner_type == outer_type)
1040 /* If we know the canonical types, compare them. */
1041 if (TYPE_CANONICAL (inner_type)
1042 && TYPE_CANONICAL (inner_type) == TYPE_CANONICAL (outer_type))
1045 /* Changes in machine mode are never useless conversions. */
1046 if (TYPE_MODE (inner_type) != TYPE_MODE (outer_type))
1049 /* If both the inner and outer types are integral types, then the
1050 conversion is not necessary if they have the same mode and
1051 signedness and precision, and both or neither are boolean. */
1052 if (INTEGRAL_TYPE_P (inner_type)
1053 && INTEGRAL_TYPE_P (outer_type))
1055 /* Preserve changes in signedness or precision. */
1056 if (TYPE_UNSIGNED (inner_type) != TYPE_UNSIGNED (outer_type)
1057 || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
1060 /* Conversions from a non-base to a base type are not useless.
1061 This way we preserve the invariant to do arithmetic in
1063 if (TREE_TYPE (inner_type)
1064 && TREE_TYPE (inner_type) != inner_type
1065 && (TREE_TYPE (outer_type) == outer_type
1066 || TREE_TYPE (outer_type) == NULL_TREE))
1069 /* We don't need to preserve changes in the types minimum or
1070 maximum value in general as these do not generate code
1071 unless the types precisions are different. */
1076 /* Scalar floating point types with the same mode are compatible. */
1077 else if (SCALAR_FLOAT_TYPE_P (inner_type)
1078 && SCALAR_FLOAT_TYPE_P (outer_type))
1081 /* We need to take special care recursing to pointed-to types. */
1082 else if (POINTER_TYPE_P (inner_type)
1083 && POINTER_TYPE_P (outer_type))
1085 /* Don't lose casts between pointers to volatile and non-volatile
1086 qualified types. Doing so would result in changing the semantics
1087 of later accesses. */
1088 if ((TYPE_VOLATILE (TREE_TYPE (outer_type))
1089 != TYPE_VOLATILE (TREE_TYPE (inner_type)))
1090 && TYPE_VOLATILE (TREE_TYPE (outer_type)))
1093 /* Do not lose casts between pointers with different
1094 TYPE_REF_CAN_ALIAS_ALL setting or alias sets. */
1095 if ((TYPE_REF_CAN_ALIAS_ALL (inner_type)
1096 != TYPE_REF_CAN_ALIAS_ALL (outer_type))
1097 || (get_alias_set (TREE_TYPE (inner_type))
1098 != get_alias_set (TREE_TYPE (outer_type))))
1101 /* We do not care for const qualification of the pointed-to types
1102 as const qualification has no semantic value to the middle-end. */
1104 /* Do not lose casts to restrict qualified pointers. */
1105 if ((TYPE_RESTRICT (outer_type)
1106 != TYPE_RESTRICT (inner_type))
1107 && TYPE_RESTRICT (outer_type))
1110 /* Otherwise pointers/references are equivalent if their pointed
1111 to types are effectively the same. We can strip qualifiers
1112 on pointed-to types for further comparison, which is done in
1114 return useless_type_conversion_p_1 (TREE_TYPE (outer_type),
1115 TREE_TYPE (inner_type));
1118 /* Recurse for complex types. */
1119 else if (TREE_CODE (inner_type) == COMPLEX_TYPE
1120 && TREE_CODE (outer_type) == COMPLEX_TYPE)
1121 return useless_type_conversion_p_1 (TREE_TYPE (outer_type),
1122 TREE_TYPE (inner_type));
1124 /* Recurse for vector types with the same number of subparts. */
1125 else if (TREE_CODE (inner_type) == VECTOR_TYPE
1126 && TREE_CODE (outer_type) == VECTOR_TYPE
1127 && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
1128 return useless_type_conversion_p_1 (TREE_TYPE (outer_type),
1129 TREE_TYPE (inner_type));
1131 /* For aggregates we may need to fall back to structural equality
1133 else if (AGGREGATE_TYPE_P (inner_type)
1134 && AGGREGATE_TYPE_P (outer_type))
1136 /* Different types of aggregates are incompatible. */
1137 if (TREE_CODE (inner_type) != TREE_CODE (outer_type))
1140 /* ??? Add structural equivalence check. */
1142 /* ??? This should eventually just return false. */
1143 return lang_hooks.types_compatible_p (inner_type, outer_type);
1149 /* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a
1150 useless type conversion, otherwise return false.
1152 This function implicitly defines the middle-end type system. With
1153 the notion of 'a < b' meaning that useless_type_conversion_p (a, b)
1154 holds and 'a > b' meaning that useless_type_conversion_p (b, a) holds,
1155 the following invariants shall be fulfilled:
1157 1) useless_type_conversion_p is transitive.
1158 If a < b and b < c then a < c.
1160 2) useless_type_conversion_p is not symmetric.
1161 From a < b does not follow a > b.
1163 3) Types define the available set of operations applicable to values.
1164 A type conversion is useless if the operations for the target type
1165 is a subset of the operations for the source type. For example
1166 casts to void* are useless, casts from void* are not (void* can't
1167 be dereferenced or offsetted, but copied, hence its set of operations
1168 is a strict subset of that of all other data pointer types). Casts
1169 to const T* are useless (can't be written to), casts from const T*
1173 useless_type_conversion_p (tree outer_type, tree inner_type)
1175 /* If the outer type is (void *), then the conversion is not
1176 necessary. We have to make sure to not apply this while
1177 recursing though. */
1178 if (POINTER_TYPE_P (inner_type)
1179 && POINTER_TYPE_P (outer_type)
1180 && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
1183 return useless_type_conversion_p_1 (outer_type, inner_type);
1186 /* Return true if a conversion from either type of TYPE1 and TYPE2
1187 to the other is not required. Otherwise return false. */
1190 types_compatible_p (tree type1, tree type2)
1192 return (type1 == type2
1193 || (useless_type_conversion_p (type1, type2)
1194 && useless_type_conversion_p (type2, type1)));
1197 /* Return true if EXPR is a useless type conversion, otherwise return
1201 tree_ssa_useless_type_conversion (tree expr)
1203 /* If we have an assignment that merely uses a NOP_EXPR to change
1204 the top of the RHS to the type of the LHS and the type conversion
1205 is "safe", then strip away the type conversion so that we can
1206 enter LHS = RHS into the const_and_copies table. */
1207 if (CONVERT_EXPR_P (expr)
1208 || TREE_CODE (expr) == VIEW_CONVERT_EXPR
1209 || TREE_CODE (expr) == NON_LVALUE_EXPR)
1210 /* FIXME: Use of GENERIC_TREE_TYPE here is a temporary measure to work
1211 around known bugs with GIMPLE_MODIFY_STMTs appearing in places
1212 they shouldn't. See PR 30391. */
1213 return useless_type_conversion_p
1215 GENERIC_TREE_TYPE (TREE_OPERAND (expr, 0)));
1221 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
1222 described in walk_use_def_chains.
1224 VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
1225 infinite loops. We used to have a bitmap for this to just mark
1226 SSA versions we had visited. But non-sparse bitmaps are way too
1227 expensive, while sparse bitmaps may cause quadratic behavior.
1229 IS_DFS is true if the caller wants to perform a depth-first search
1230 when visiting PHI nodes. A DFS will visit each PHI argument and
1231 call FN after each one. Otherwise, all the arguments are
1232 visited first and then FN is called with each of the visited
1233 arguments in a separate pass. */
1236 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
1237 struct pointer_set_t *visited, bool is_dfs)
1241 if (pointer_set_insert (visited, var))
1244 def_stmt = SSA_NAME_DEF_STMT (var);
1246 if (TREE_CODE (def_stmt) != PHI_NODE)
1248 /* If we reached the end of the use-def chain, call FN. */
1249 return fn (var, def_stmt, data);
1255 /* When doing a breadth-first search, call FN before following the
1256 use-def links for each argument. */
1258 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1259 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
1262 /* Follow use-def links out of each PHI argument. */
1263 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1265 tree arg = PHI_ARG_DEF (def_stmt, i);
1267 /* ARG may be NULL for newly introduced PHI nodes. */
1269 && TREE_CODE (arg) == SSA_NAME
1270 && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
1274 /* When doing a depth-first search, call FN after following the
1275 use-def links for each argument. */
1277 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1278 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
1287 /* Walk use-def chains starting at the SSA variable VAR. Call
1288 function FN at each reaching definition found. FN takes three
1289 arguments: VAR, its defining statement (DEF_STMT) and a generic
1290 pointer to whatever state information that FN may want to maintain
1291 (DATA). FN is able to stop the walk by returning true, otherwise
1292 in order to continue the walk, FN should return false.
1294 Note, that if DEF_STMT is a PHI node, the semantics are slightly
1295 different. The first argument to FN is no longer the original
1296 variable VAR, but the PHI argument currently being examined. If FN
1297 wants to get at VAR, it should call PHI_RESULT (PHI).
1299 If IS_DFS is true, this function will:
1301 1- walk the use-def chains for all the PHI arguments, and,
1302 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
1304 If IS_DFS is false, the two steps above are done in reverse order
1305 (i.e., a breadth-first search). */
1308 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
1313 gcc_assert (TREE_CODE (var) == SSA_NAME);
1315 def_stmt = SSA_NAME_DEF_STMT (var);
1317 /* We only need to recurse if the reaching definition comes from a PHI
1319 if (TREE_CODE (def_stmt) != PHI_NODE)
1320 (*fn) (var, def_stmt, data);
1323 struct pointer_set_t *visited = pointer_set_create ();
1324 walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
1325 pointer_set_destroy (visited);
1330 /* Return true if T, an SSA_NAME, has an undefined value. */
1333 ssa_undefined_value_p (tree t)
1335 tree var = SSA_NAME_VAR (t);
1337 /* Parameters get their initial value from the function entry. */
1338 if (TREE_CODE (var) == PARM_DECL)
1341 /* Hard register variables get their initial value from the ether. */
1342 if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1345 /* The value is undefined iff its definition statement is empty. */
1346 return IS_EMPTY_STMT (SSA_NAME_DEF_STMT (t));
1349 /* Emit warnings for uninitialized variables. This is done in two passes.
1351 The first pass notices real uses of SSA names with undefined values.
1352 Such uses are unconditionally uninitialized, and we can be certain that
1353 such a use is a mistake. This pass is run before most optimizations,
1354 so that we catch as many as we can.
1356 The second pass follows PHI nodes to find uses that are potentially
1357 uninitialized. In this case we can't necessarily prove that the use
1358 is really uninitialized. This pass is run after most optimizations,
1359 so that we thread as many jumps and possible, and delete as much dead
1360 code as possible, in order to reduce false positives. We also look
1361 again for plain uninitialized variables, since optimization may have
1362 changed conditionally uninitialized to unconditionally uninitialized. */
1364 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1365 warning text is in MSGID and LOCUS may contain a location or be null. */
1368 warn_uninit (tree t, const char *gmsgid, void *data)
1370 tree var = SSA_NAME_VAR (t);
1371 tree context = (tree) data;
1373 expanded_location xloc, floc;
1375 if (!ssa_undefined_value_p (t))
1378 /* TREE_NO_WARNING either means we already warned, or the front end
1379 wishes to suppress the warning. */
1380 if (TREE_NO_WARNING (var))
1383 locus = (context != NULL && EXPR_HAS_LOCATION (context)
1384 ? EXPR_LOCUS (context)
1385 : &DECL_SOURCE_LOCATION (var));
1386 warning (OPT_Wuninitialized, gmsgid, locus, var);
1387 xloc = expand_location (*locus);
1388 floc = expand_location (DECL_SOURCE_LOCATION (cfun->decl));
1389 if (xloc.file != floc.file
1390 || xloc.line < floc.line
1391 || xloc.line > LOCATION_LINE (cfun->function_end_locus))
1392 inform ("%J%qD was declared here", var, var);
1394 TREE_NO_WARNING (var) = 1;
1399 bool always_executed;
1402 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1403 and warn about them. */
1406 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data_)
1408 struct walk_data *data = (struct walk_data *)data_;
1411 switch (TREE_CODE (t))
1414 /* We only do data flow with SSA_NAMEs, so that's all we
1416 if (data->always_executed)
1417 warn_uninit (t, "%H%qD is used uninitialized in this function",
1420 warn_uninit (t, "%H%qD may be used uninitialized in this function",
1427 /* The total store transformation performed during gimplification
1428 creates uninitialized variable uses. If all is well, these will
1429 be optimized away, so don't warn now. */
1430 if (TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
1435 if (IS_TYPE_OR_DECL_P (t))
1443 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1444 and warn about them. */
1447 warn_uninitialized_phi (tree phi)
1449 int i, n = PHI_NUM_ARGS (phi);
1451 /* Don't look at memory tags. */
1452 if (!is_gimple_reg (PHI_RESULT (phi)))
1455 for (i = 0; i < n; ++i)
1457 tree op = PHI_ARG_DEF (phi, i);
1458 if (TREE_CODE (op) == SSA_NAME)
1459 warn_uninit (op, "%H%qD may be used uninitialized in this function",
1465 execute_early_warn_uninitialized (void)
1467 block_stmt_iterator bsi;
1469 struct walk_data data;
1471 calculate_dominance_info (CDI_POST_DOMINATORS);
1475 data.always_executed = dominated_by_p (CDI_POST_DOMINATORS,
1476 single_succ (ENTRY_BLOCK_PTR), bb);
1477 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1479 data.stmt = bsi_stmt (bsi);
1480 walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1488 execute_late_warn_uninitialized (void)
1493 /* Re-do the plain uninitialized variable check, as optimization may have
1494 straightened control flow. Do this first so that we don't accidentally
1495 get a "may be" warning when we'd have seen an "is" warning later. */
1496 execute_early_warn_uninitialized ();
1499 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1500 warn_uninitialized_phi (phi);
1505 gate_warn_uninitialized (void)
1507 return warn_uninitialized != 0;
1510 struct gimple_opt_pass pass_early_warn_uninitialized =
1515 gate_warn_uninitialized, /* gate */
1516 execute_early_warn_uninitialized, /* execute */
1519 0, /* static_pass_number */
1521 PROP_ssa, /* properties_required */
1522 0, /* properties_provided */
1523 0, /* properties_destroyed */
1524 0, /* todo_flags_start */
1525 0 /* todo_flags_finish */
1529 struct gimple_opt_pass pass_late_warn_uninitialized =
1534 gate_warn_uninitialized, /* gate */
1535 execute_late_warn_uninitialized, /* execute */
1538 0, /* static_pass_number */
1540 PROP_ssa, /* properties_required */
1541 0, /* properties_provided */
1542 0, /* properties_destroyed */
1543 0, /* todo_flags_start */
1544 0 /* todo_flags_finish */
1548 /* Compute TREE_ADDRESSABLE for local variables. */
1551 execute_update_addresses_taken (void)
1554 referenced_var_iterator rvi;
1555 block_stmt_iterator bsi;
1557 bitmap addresses_taken = BITMAP_ALLOC (NULL);
1558 bitmap vars_updated = BITMAP_ALLOC (NULL);
1559 bool update_vops = false;
1562 /* Collect into ADDRESSES_TAKEN all variables whose address is taken within
1563 the function body. */
1566 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1568 stmt_ann_t s_ann = stmt_ann (bsi_stmt (bsi));
1570 if (s_ann->addresses_taken)
1571 bitmap_ior_into (addresses_taken, s_ann->addresses_taken);
1573 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1575 unsigned i, phi_num_args = PHI_NUM_ARGS (phi);
1576 for (i = 0; i < phi_num_args; i++)
1578 tree op = PHI_ARG_DEF (phi, i), var;
1579 if (TREE_CODE (op) == ADDR_EXPR
1580 && (var = get_base_address (TREE_OPERAND (op, 0))) != NULL_TREE
1582 bitmap_set_bit (addresses_taken, DECL_UID (var));
1587 /* When possible, clear ADDRESSABLE bit and mark variable for conversion into
1589 FOR_EACH_REFERENCED_VAR (var, rvi)
1590 if (!is_global_var (var)
1591 && TREE_CODE (var) != RESULT_DECL
1592 && TREE_ADDRESSABLE (var)
1593 && !bitmap_bit_p (addresses_taken, DECL_UID (var)))
1595 TREE_ADDRESSABLE (var) = 0;
1596 if (is_gimple_reg (var))
1597 mark_sym_for_renaming (var);
1599 bitmap_set_bit (vars_updated, DECL_UID (var));
1602 fprintf (dump_file, "No longer having address taken ");
1603 print_generic_expr (dump_file, var, 0);
1604 fprintf (dump_file, "\n");
1608 /* Operand caches needs to be recomputed for operands referencing the updated
1612 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1614 tree stmt = bsi_stmt (bsi);
1616 if ((LOADED_SYMS (stmt)
1617 && bitmap_intersect_p (LOADED_SYMS (stmt), vars_updated))
1618 || (STORED_SYMS (stmt)
1619 && bitmap_intersect_p (STORED_SYMS (stmt), vars_updated)))
1622 BITMAP_FREE (addresses_taken);
1623 BITMAP_FREE (vars_updated);
1627 struct gimple_opt_pass pass_update_address_taken =
1631 "addressables", /* name */
1633 execute_update_addresses_taken, /* execute */
1636 0, /* static_pass_number */
1638 PROP_ssa, /* properties_required */
1639 0, /* properties_provided */
1640 0, /* properties_destroyed */
1641 0, /* todo_flags_start */
1642 TODO_update_ssa /* todo_flags_finish */