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)
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. */
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 /* 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). */
54 ssa_redirect_edge (edge e, basic_block dest)
57 tree list = NULL, *last = &list;
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)
66 src = PHI_ARG_DEF (phi, e->dest_idx);
67 dst = PHI_RESULT (phi);
68 node = build_tree_list (dst, src);
70 last = &TREE_CHAIN (node);
73 e = redirect_edge_succ_nodup (e, dest);
74 PENDING_STMT (e) = list;
79 /* Add PHI arguments queued in PENDINT_STMT list on edge E to edge
83 flush_pending_stmts (edge e)
87 if (!PENDING_STMT (e))
90 for (phi = phi_nodes (e->dest), arg = PENDING_STMT (e);
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
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");
115 if (TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name)))
117 error ("type mismatch between an SSA_NAME and its symbol");
121 if (SSA_NAME_IN_FREE_LIST (ssa_name))
123 error ("found an SSA_NAME that had been released into the free pool");
127 if (is_virtual && is_gimple_reg (ssa_name))
129 error ("found a virtual definition for a GIMPLE register");
133 if (!is_virtual && !is_gimple_reg (ssa_name))
135 error ("found a real definition for a non-register");
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");
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
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))
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);
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);
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);
200 /* Return true if the use of SSA_NAME at statement STMT in block BB is
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
211 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
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. */
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)
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))
231 TREE_VISITED (ssa_name) = 1;
233 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name))
234 && gimple_default_def (cfun, SSA_NAME_VAR (ssa_name)) == ssa_name)
235 ; /* Default definitions have empty statements. Nothing to do. */
238 error ("missing definition");
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);
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);
257 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
259 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
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");
273 if (use_p->prev->use == NULL)
274 listvar = use_p->prev->stmt;
276 listvar = USE_FROM_PTR (use_p->prev);
277 if (listvar != ssa_name)
279 error ("wrong immediate use list");
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);
296 /* Return true if any of the arguments for PHI node PHI at block BB is
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. */
304 verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)
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");
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);
327 error ("PHI argument is missing for edge %d->%d",
334 if (TREE_CODE (op) != SSA_NAME && !is_gimple_min_invariant (op))
336 error ("PHI argument is not SSA_NAME, or invariant");
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)),
348 error ("wrong edge %d->%d for PHI argument",
349 e->src->index, e->dest->index);
355 fprintf (stderr, "PHI argument\n");
356 print_generic_stmt (stderr, op, TDF_VOPS);
364 fprintf (stderr, "for PHI node\n");
365 print_generic_stmt (stderr, phi, TDF_VOPS);
374 verify_flow_insensitive_alias_info (void)
377 bitmap visited = BITMAP_ALLOC (NULL);
378 referenced_var_iterator rvi;
380 FOR_EACH_REFERENCED_VAR (var, rvi)
384 VEC(tree,gc) *may_aliases;
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);
403 FOR_EACH_REFERENCED_VAR (var, rvi)
410 && !bitmap_bit_p (visited, DECL_UID (var)))
412 error ("addressable variable that is aliased but is not in any alias set");
417 BITMAP_FREE (visited);
421 debug_variable (var);
422 internal_error ("verify_flow_insensitive_alias_info failed");
427 verify_flow_sensitive_alias_info (void)
432 for (i = 1; i < num_ssa_names; i++)
436 struct ptr_info_def *pi;
443 /* We only care for pointers that are actually referenced in the
445 if (!POINTER_TYPE_P (TREE_TYPE (ptr)) || !TREE_VISITED (ptr))
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))
457 pi = SSA_NAME_PTR_INFO (ptr);
462 if (pi->is_dereferenced && !pi->name_mem_tag && !ann->symbol_mem_tag)
464 error ("dereferenced pointers should have a name or a symbol tag");
469 && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars)))
471 error ("pointers with a memory tag, should have points-to sets");
475 if (pi->value_escapes_p
477 && !is_call_clobbered (pi->name_mem_tag))
479 error ("pointer escapes but its name tag is not call-clobbered");
487 debug_variable (ptr);
488 internal_error ("verify_flow_sensitive_alias_info failed");
491 /* Verify the consistency of call clobbering information. */
493 verify_call_clobbering (void)
498 referenced_var_iterator rvi;
500 /* At all times, the result of the DECL_CALL_CLOBBERED flag should
501 match the result of the call_clobbered_vars bitmap. Verify both
502 that everything in call_clobbered_vars is marked
503 DECL_CALL_CLOBBERED, and that everything marked
504 DECL_CALL_CLOBBERED is in call_clobbered_vars. */
505 EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun), 0, i, bi)
507 var = referenced_var (i);
508 if (!MTAG_P (var) && !DECL_CALL_CLOBBERED (var))
510 error ("variable in call_clobbered_vars but not marked DECL_CALL_CLOBBERED");
511 debug_variable (var);
515 FOR_EACH_REFERENCED_VAR (var, rvi)
517 if (!MTAG_P (var) && DECL_CALL_CLOBBERED (var)
518 && !bitmap_bit_p (gimple_call_clobbered_vars (cfun), DECL_UID (var)))
520 error ("variable marked DECL_CALL_CLOBBERED but not in call_clobbered_vars bitmap.");
521 debug_variable (var);
528 internal_error ("verify_call_clobbering failed");
531 /* Verify the consistency of aliasing information. */
534 verify_alias_info (void)
536 verify_flow_sensitive_alias_info ();
537 verify_call_clobbering ();
538 verify_flow_insensitive_alias_info ();
542 /* Verify common invariants in the SSA web.
543 TODO: verify the variable annotations. */
546 verify_ssa (bool check_modified_stmt)
550 basic_block *definition_block = XCNEWVEC (basic_block, num_ssa_names);
553 enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS];
554 bitmap names_defined_in_bb = BITMAP_ALLOC (NULL);
556 gcc_assert (!need_ssa_update_p ());
560 timevar_push (TV_TREE_SSA_VERIFY);
562 /* Keep track of SSA names present in the IL. */
563 for (i = 1; i < num_ssa_names; i++)
565 tree name = ssa_name (i);
569 TREE_VISITED (name) = 0;
571 stmt = SSA_NAME_DEF_STMT (name);
572 if (!IS_EMPTY_STMT (stmt))
574 basic_block bb = bb_for_stmt (stmt);
575 verify_def (bb, definition_block,
576 name, stmt, !is_gimple_reg (name));
582 calculate_dominance_info (CDI_DOMINATORS);
584 /* Now verify all the uses and make sure they agree with the definitions
585 found in the previous pass. */
591 block_stmt_iterator bsi;
593 /* Make sure that all edges have a clear 'aux' field. */
594 FOR_EACH_EDGE (e, ei, bb->preds)
598 error ("AUX pointer initialized for edge %d->%d", e->src->index,
604 /* Verify the arguments for every PHI node in the block. */
605 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
607 if (verify_phi_args (phi, bb, definition_block))
609 bitmap_set_bit (names_defined_in_bb,
610 SSA_NAME_VERSION (PHI_RESULT (phi)));
613 /* Now verify all the uses and vuses in every statement of the block. */
614 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
616 tree stmt = bsi_stmt (bsi);
619 if (check_modified_stmt && stmt_modified_p (stmt))
621 error ("stmt (%p) marked modified after optimization pass : ",
623 print_generic_stmt (stderr, stmt, TDF_VOPS);
627 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
628 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) != SSA_NAME)
630 tree lhs, base_address;
632 lhs = GIMPLE_STMT_OPERAND (stmt, 0);
633 base_address = get_base_address (lhs);
636 && SSA_VAR_P (base_address)
637 && ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF))
639 error ("statement makes a memory store, but has no "
640 "V_MAY_DEFS nor V_MUST_DEFS");
641 print_generic_stmt (stderr, stmt, TDF_VOPS);
646 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
647 SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
649 op = USE_FROM_PTR (use_p);
650 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
651 use_p, stmt, false, !is_gimple_reg (op),
652 names_defined_in_bb))
656 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
657 bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
660 bitmap_clear (names_defined_in_bb);
663 /* Finally, verify alias information. */
664 verify_alias_info ();
666 free (definition_block);
668 /* Restore the dominance information to its prior known state, so
669 that we do not perturb the compiler's subsequent behavior. */
670 if (orig_dom_state == DOM_NONE)
671 free_dominance_info (CDI_DOMINATORS);
673 dom_computed[CDI_DOMINATORS] = orig_dom_state;
675 BITMAP_FREE (names_defined_in_bb);
676 timevar_pop (TV_TREE_SSA_VERIFY);
680 internal_error ("verify_ssa failed");
683 /* Return true if the uid in both int tree maps are equal. */
686 int_tree_map_eq (const void *va, const void *vb)
688 const struct int_tree_map *a = (const struct int_tree_map *) va;
689 const struct int_tree_map *b = (const struct int_tree_map *) vb;
690 return (a->uid == b->uid);
693 /* Hash a UID in a int_tree_map. */
696 int_tree_map_hash (const void *item)
698 return ((const struct int_tree_map *)item)->uid;
702 /* Initialize global DFA and SSA structures. */
707 cfun->gimple_df = ggc_alloc_cleared (sizeof (struct gimple_df));
708 cfun->gimple_df->referenced_vars = htab_create_ggc (20, int_tree_map_hash,
709 int_tree_map_eq, NULL);
710 cfun->gimple_df->default_defs = htab_create_ggc (20, int_tree_map_hash,
711 int_tree_map_eq, NULL);
712 cfun->gimple_df->call_clobbered_vars = BITMAP_GGC_ALLOC ();
713 cfun->gimple_df->addressable_vars = BITMAP_GGC_ALLOC ();
714 init_alias_heapvars ();
720 /* Deallocate memory associated with SSA data structures for FNDECL. */
723 delete_tree_ssa (void)
727 block_stmt_iterator bsi;
728 referenced_var_iterator rvi;
731 /* Release any ssa_names still in use. */
732 for (i = 0; i < num_ssa_names; i++)
734 tree var = ssa_name (i);
735 if (var && TREE_CODE (var) == SSA_NAME)
737 SSA_NAME_IMM_USE_NODE (var).prev = &(SSA_NAME_IMM_USE_NODE (var));
738 SSA_NAME_IMM_USE_NODE (var).next = &(SSA_NAME_IMM_USE_NODE (var));
740 release_ssa_name (var);
743 /* Remove annotations from every tree in the function. */
746 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
748 tree stmt = bsi_stmt (bsi);
749 stmt_ann_t ann = get_stmt_ann (stmt);
751 free_ssa_operands (&ann->operands);
752 ann->addresses_taken = 0;
753 mark_stmt_modified (stmt);
755 set_phi_nodes (bb, NULL);
758 /* Remove annotations from every referenced variable. */
759 FOR_EACH_REFERENCED_VAR (var, rvi)
761 ggc_free (var->base.ann);
762 var->base.ann = NULL;
764 htab_delete (gimple_referenced_vars (cfun));
765 cfun->gimple_df->referenced_vars = NULL;
770 cfun->gimple_df->global_var = NULL_TREE;
772 htab_delete (cfun->gimple_df->default_defs);
773 cfun->gimple_df->call_clobbered_vars = NULL;
774 cfun->gimple_df->addressable_vars = NULL;
775 cfun->gimple_df->modified_noreturn_calls = NULL;
776 cfun->gimple_df->aliases_computed_p = false;
777 delete_alias_heapvars ();
778 gcc_assert (!need_ssa_update_p ());
782 /* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a
783 useless type conversion, otherwise return false. */
786 tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
788 if (inner_type == outer_type)
791 /* Changes in machine mode are never useless conversions. */
792 if (TYPE_MODE (inner_type) != TYPE_MODE (outer_type))
795 /* If the inner and outer types are effectively the same, then
796 strip the type conversion and enter the equivalence into
798 if (lang_hooks.types_compatible_p (inner_type, outer_type))
801 /* If both types are pointers and the outer type is a (void *), then
802 the conversion is not necessary. The opposite is not true since
803 that conversion would result in a loss of information if the
804 equivalence was used. Consider an indirect function call where
805 we need to know the exact type of the function to correctly
806 implement the ABI. */
807 else if (POINTER_TYPE_P (inner_type)
808 && POINTER_TYPE_P (outer_type)
809 && TYPE_REF_CAN_ALIAS_ALL (inner_type)
810 == TYPE_REF_CAN_ALIAS_ALL (outer_type)
811 && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
814 /* Don't lose casts between pointers to volatile and non-volatile
815 qualified types. Doing so would result in changing the semantics
816 of later accesses. */
817 else if (POINTER_TYPE_P (inner_type)
818 && POINTER_TYPE_P (outer_type)
819 && TYPE_VOLATILE (TREE_TYPE (outer_type))
820 != TYPE_VOLATILE (TREE_TYPE (inner_type)))
823 /* Pointers/references are equivalent if their pointed to types
824 are effectively the same. This allows to strip conversions between
825 pointer types with different type qualifiers. */
826 else if (POINTER_TYPE_P (inner_type)
827 && POINTER_TYPE_P (outer_type)
828 && TYPE_REF_CAN_ALIAS_ALL (inner_type)
829 == TYPE_REF_CAN_ALIAS_ALL (outer_type)
830 && lang_hooks.types_compatible_p (TREE_TYPE (inner_type),
831 TREE_TYPE (outer_type)))
834 /* If both the inner and outer types are integral types, then the
835 conversion is not necessary if they have the same mode and
836 signedness and precision, and both or neither are boolean. Some
837 code assumes an invariant that boolean types stay boolean and do
838 not become 1-bit bit-field types. Note that types with precision
839 not using all bits of the mode (such as bit-field types in C)
840 mean that testing of precision is necessary. */
841 else if (INTEGRAL_TYPE_P (inner_type)
842 && INTEGRAL_TYPE_P (outer_type)
843 && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
844 && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type)
845 && simple_cst_equal (TYPE_MAX_VALUE (inner_type), TYPE_MAX_VALUE (outer_type))
846 && simple_cst_equal (TYPE_MIN_VALUE (inner_type), TYPE_MIN_VALUE (outer_type)))
848 bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE);
849 bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE);
850 if (first_boolean == second_boolean)
854 /* Recurse for complex types. */
855 else if (TREE_CODE (inner_type) == COMPLEX_TYPE
856 && TREE_CODE (outer_type) == COMPLEX_TYPE
857 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
858 TREE_TYPE (inner_type)))
864 /* Return true if EXPR is a useless type conversion, otherwise return
868 tree_ssa_useless_type_conversion (tree expr)
870 /* If we have an assignment that merely uses a NOP_EXPR to change
871 the top of the RHS to the type of the LHS and the type conversion
872 is "safe", then strip away the type conversion so that we can
873 enter LHS = RHS into the const_and_copies table. */
874 if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR
875 || TREE_CODE (expr) == VIEW_CONVERT_EXPR
876 || TREE_CODE (expr) == NON_LVALUE_EXPR)
877 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
878 TREE_TYPE (TREE_OPERAND (expr,
885 /* Returns true if statement STMT may read memory. */
888 stmt_references_memory_p (tree stmt)
890 stmt_ann_t ann = stmt_ann (stmt);
892 if (ann->has_volatile_ops)
895 return (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS));
898 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
899 described in walk_use_def_chains.
901 VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
902 infinite loops. We used to have a bitmap for this to just mark
903 SSA versions we had visited. But non-sparse bitmaps are way too
904 expensive, while sparse bitmaps may cause quadratic behavior.
906 IS_DFS is true if the caller wants to perform a depth-first search
907 when visiting PHI nodes. A DFS will visit each PHI argument and
908 call FN after each one. Otherwise, all the arguments are
909 visited first and then FN is called with each of the visited
910 arguments in a separate pass. */
913 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
914 struct pointer_set_t *visited, bool is_dfs)
918 if (pointer_set_insert (visited, var))
921 def_stmt = SSA_NAME_DEF_STMT (var);
923 if (TREE_CODE (def_stmt) != PHI_NODE)
925 /* If we reached the end of the use-def chain, call FN. */
926 return fn (var, def_stmt, data);
932 /* When doing a breadth-first search, call FN before following the
933 use-def links for each argument. */
935 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
936 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
939 /* Follow use-def links out of each PHI argument. */
940 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
942 tree arg = PHI_ARG_DEF (def_stmt, i);
943 if (TREE_CODE (arg) == SSA_NAME
944 && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
948 /* When doing a depth-first search, call FN after following the
949 use-def links for each argument. */
951 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
952 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
961 /* Walk use-def chains starting at the SSA variable VAR. Call
962 function FN at each reaching definition found. FN takes three
963 arguments: VAR, its defining statement (DEF_STMT) and a generic
964 pointer to whatever state information that FN may want to maintain
965 (DATA). FN is able to stop the walk by returning true, otherwise
966 in order to continue the walk, FN should return false.
968 Note, that if DEF_STMT is a PHI node, the semantics are slightly
969 different. The first argument to FN is no longer the original
970 variable VAR, but the PHI argument currently being examined. If FN
971 wants to get at VAR, it should call PHI_RESULT (PHI).
973 If IS_DFS is true, this function will:
975 1- walk the use-def chains for all the PHI arguments, and,
976 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
978 If IS_DFS is false, the two steps above are done in reverse order
979 (i.e., a breadth-first search). */
983 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
988 gcc_assert (TREE_CODE (var) == SSA_NAME);
990 def_stmt = SSA_NAME_DEF_STMT (var);
992 /* We only need to recurse if the reaching definition comes from a PHI
994 if (TREE_CODE (def_stmt) != PHI_NODE)
995 (*fn) (var, def_stmt, data);
998 struct pointer_set_t *visited = pointer_set_create ();
999 walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
1000 pointer_set_destroy (visited);
1005 /* Emit warnings for uninitialized variables. This is done in two passes.
1007 The first pass notices real uses of SSA names with default definitions.
1008 Such uses are unconditionally uninitialized, and we can be certain that
1009 such a use is a mistake. This pass is run before most optimizations,
1010 so that we catch as many as we can.
1012 The second pass follows PHI nodes to find uses that are potentially
1013 uninitialized. In this case we can't necessarily prove that the use
1014 is really uninitialized. This pass is run after most optimizations,
1015 so that we thread as many jumps and possible, and delete as much dead
1016 code as possible, in order to reduce false positives. We also look
1017 again for plain uninitialized variables, since optimization may have
1018 changed conditionally uninitialized to unconditionally uninitialized. */
1020 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1021 warning text is in MSGID and LOCUS may contain a location or be null. */
1024 warn_uninit (tree t, const char *gmsgid, void *data)
1026 tree var = SSA_NAME_VAR (t);
1027 tree def = SSA_NAME_DEF_STMT (t);
1028 tree context = (tree) data;
1030 expanded_location xloc, floc;
1032 /* Default uses (indicated by an empty definition statement),
1033 are uninitialized. */
1034 if (!IS_EMPTY_STMT (def))
1037 /* Except for PARMs of course, which are always initialized. */
1038 if (TREE_CODE (var) == PARM_DECL)
1041 /* Hard register variables get their initial value from the ether. */
1042 if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1045 /* TREE_NO_WARNING either means we already warned, or the front end
1046 wishes to suppress the warning. */
1047 if (TREE_NO_WARNING (var))
1050 locus = (context != NULL && EXPR_HAS_LOCATION (context)
1051 ? EXPR_LOCUS (context)
1052 : &DECL_SOURCE_LOCATION (var));
1053 warning (0, gmsgid, locus, var);
1054 xloc = expand_location (*locus);
1055 floc = expand_location (DECL_SOURCE_LOCATION (cfun->decl));
1056 if (xloc.file != floc.file
1057 || xloc.line < floc.line
1058 || xloc.line > LOCATION_LINE (cfun->function_end_locus))
1059 inform ("%J%qD was declared here", var, var);
1061 TREE_NO_WARNING (var) = 1;
1064 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1065 and warn about them. */
1068 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
1072 switch (TREE_CODE (t))
1075 /* We only do data flow with SSA_NAMEs, so that's all we
1077 warn_uninit (t, "%H%qD is used uninitialized in this function", data);
1083 /* The total store transformation performed during gimplification
1084 creates uninitialized variable uses. If all is well, these will
1085 be optimized away, so don't warn now. */
1086 if (TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
1091 if (IS_TYPE_OR_DECL_P (t))
1099 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1100 and warn about them. */
1103 warn_uninitialized_phi (tree phi)
1105 int i, n = PHI_NUM_ARGS (phi);
1107 /* Don't look at memory tags. */
1108 if (!is_gimple_reg (PHI_RESULT (phi)))
1111 for (i = 0; i < n; ++i)
1113 tree op = PHI_ARG_DEF (phi, i);
1114 if (TREE_CODE (op) == SSA_NAME)
1115 warn_uninit (op, "%H%qD may be used uninitialized in this function",
1121 execute_early_warn_uninitialized (void)
1123 block_stmt_iterator bsi;
1127 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1129 tree context = bsi_stmt (bsi);
1130 walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1137 execute_late_warn_uninitialized (void)
1142 /* Re-do the plain uninitialized variable check, as optimization may have
1143 straightened control flow. Do this first so that we don't accidentally
1144 get a "may be" warning when we'd have seen an "is" warning later. */
1145 execute_early_warn_uninitialized ();
1148 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1149 warn_uninitialized_phi (phi);
1154 gate_warn_uninitialized (void)
1156 return warn_uninitialized != 0;
1159 struct tree_opt_pass pass_early_warn_uninitialized =
1162 gate_warn_uninitialized, /* gate */
1163 execute_early_warn_uninitialized, /* execute */
1166 0, /* static_pass_number */
1168 PROP_ssa, /* properties_required */
1169 0, /* properties_provided */
1170 0, /* properties_destroyed */
1171 0, /* todo_flags_start */
1172 0, /* todo_flags_finish */
1176 struct tree_opt_pass pass_late_warn_uninitialized =
1179 gate_warn_uninitialized, /* gate */
1180 execute_late_warn_uninitialized, /* execute */
1183 0, /* static_pass_number */
1185 PROP_ssa, /* properties_required */
1186 0, /* properties_provided */
1187 0, /* properties_destroyed */
1188 0, /* todo_flags_start */
1189 0, /* todo_flags_finish */