1 /* Miscellaneous SSA utility functions.
2 Copyright (C) 2001, 2002, 2003, 2004 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, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
23 #include "coretypes.h"
30 #include "langhooks.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
37 #include "diagnostic.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 edge E and remove the corresponding arguments from the PHI nodes
50 in E's destination block. */
53 ssa_remove_edge (edge e)
57 /* Remove the appropriate PHI arguments in E's destination block. */
58 for (phi = phi_nodes (e->dest); phi; phi = next)
60 next = PHI_CHAIN (phi);
61 remove_phi_arg (phi, e->src);
67 /* Remove the corresponding arguments from the PHI nodes in E's
68 destination block and redirect it to DEST. Return redirected edge.
69 The list of removed arguments is stored in PENDING_STMT (e). */
72 ssa_redirect_edge (edge e, basic_block dest)
75 tree list = NULL, *last = &list;
79 /* Remove the appropriate PHI arguments in E's destination block. */
80 for (phi = phi_nodes (e->dest); phi; phi = next)
82 next = PHI_CHAIN (phi);
84 i = phi_arg_from_edge (phi, e);
88 src = PHI_ARG_DEF (phi, i);
89 dst = PHI_RESULT (phi);
90 node = build_tree_list (dst, src);
92 last = &TREE_CHAIN (node);
94 remove_phi_arg_num (phi, i);
97 e = redirect_edge_succ_nodup (e, dest);
98 PENDING_STMT (e) = list;
103 /* Add PHI arguments queued in PENDINT_STMT list on edge E to edge
107 flush_pending_stmts (edge e)
111 if (!PENDING_STMT (e))
114 for (phi = phi_nodes (e->dest), arg = PENDING_STMT (e);
116 phi = TREE_CHAIN (phi), arg = TREE_CHAIN (arg))
118 tree def = TREE_VALUE (arg);
119 add_phi_arg (&phi, def, e);
122 PENDING_STMT (e) = NULL;
125 /* Return true if SSA_NAME is malformed and mark it visited.
127 IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
131 verify_ssa_name (tree ssa_name, bool is_virtual)
133 TREE_VISITED (ssa_name) = 1;
135 if (TREE_CODE (ssa_name) != SSA_NAME)
137 error ("Expected an SSA_NAME object");
141 if (TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name)))
143 error ("Type mismatch between an SSA_NAME and its symbol.");
147 if (SSA_NAME_IN_FREE_LIST (ssa_name))
149 error ("Found an SSA_NAME that had been released into the free pool");
153 if (is_virtual && is_gimple_reg (ssa_name))
155 error ("Found a virtual definition for a GIMPLE register");
159 if (!is_virtual && !is_gimple_reg (ssa_name))
161 error ("Found a real definition for a non-register");
169 /* Return true if the definition of SSA_NAME at block BB is malformed.
171 STMT is the statement where SSA_NAME is created.
173 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
174 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
175 it means that the block in that array slot contains the
176 definition of SSA_NAME.
178 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
182 verify_def (basic_block bb, basic_block *definition_block, tree ssa_name,
183 tree stmt, bool is_virtual)
185 if (verify_ssa_name (ssa_name, is_virtual))
188 if (definition_block[SSA_NAME_VERSION (ssa_name)])
190 error ("SSA_NAME created in two different blocks %i and %i",
191 definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index);
195 definition_block[SSA_NAME_VERSION (ssa_name)] = bb;
197 if (SSA_NAME_DEF_STMT (ssa_name) != stmt)
199 error ("SSA_NAME_DEF_STMT is wrong");
200 fprintf (stderr, "Expected definition statement:\n");
201 print_generic_stmt (stderr, SSA_NAME_DEF_STMT (ssa_name), TDF_VOPS);
202 fprintf (stderr, "\nActual definition statement:\n");
203 print_generic_stmt (stderr, stmt, TDF_VOPS);
210 fprintf (stderr, "while verifying SSA_NAME ");
211 print_generic_expr (stderr, ssa_name, 0);
212 fprintf (stderr, " in statement\n");
213 print_generic_stmt (stderr, stmt, TDF_VOPS);
219 /* Return true if the use of SSA_NAME at statement STMT in block BB is
222 DEF_BB is the block where SSA_NAME was found to be created.
224 IDOM contains immediate dominator information for the flowgraph.
226 CHECK_ABNORMAL is true if the caller wants to check whether this use
227 is flowing through an abnormal edge (only used when checking PHI
230 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
233 If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
234 that are defined before STMT in basic block BB. */
237 verify_use (basic_block bb, basic_block def_bb, tree ssa_name,
238 tree stmt, bool check_abnormal, bool is_virtual,
239 bitmap names_defined_in_bb)
243 err = verify_ssa_name (ssa_name, is_virtual);
245 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name))
246 && var_ann (SSA_NAME_VAR (ssa_name))->default_def == ssa_name)
247 ; /* Default definitions have empty statements. Nothing to do. */
250 error ("Missing definition");
253 else if (bb != def_bb
254 && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
256 error ("Definition in block %i does not dominate use in block %i",
257 def_bb->index, bb->index);
260 else if (bb == def_bb
261 && names_defined_in_bb != NULL
262 && !bitmap_bit_p (names_defined_in_bb, SSA_NAME_VERSION (ssa_name)))
264 error ("Definition in block %i follows the use", def_bb->index);
269 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
271 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
277 fprintf (stderr, "for SSA_NAME: ");
278 print_generic_expr (stderr, ssa_name, TDF_VOPS);
279 fprintf (stderr, "in statement:\n");
280 print_generic_stmt (stderr, stmt, TDF_VOPS);
287 /* Return true if any of the arguments for PHI node PHI at block BB is
290 IDOM contains immediate dominator information for the flowgraph.
292 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
293 numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
294 block in that array slot contains the definition of SSA_NAME. */
297 verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)
301 int i, phi_num_args = PHI_NUM_ARGS (phi);
304 /* Mark all the incoming edges. */
305 FOR_EACH_EDGE (e, ei, bb->preds)
308 for (i = 0; i < phi_num_args; i++)
310 tree op = PHI_ARG_DEF (phi, i);
312 e = PHI_ARG_EDGE (phi, i);
314 if (TREE_CODE (op) == SSA_NAME)
315 err = verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op,
316 phi, e->flags & EDGE_ABNORMAL,
317 !is_gimple_reg (PHI_RESULT (phi)),
322 error ("Wrong edge %d->%d for PHI argument\n",
323 e->src->index, e->dest->index, bb->index);
327 if (e->aux == (void *) 0)
329 error ("PHI argument flowing through dead edge %d->%d\n",
330 e->src->index, e->dest->index);
334 if (e->aux == (void *) 2)
336 error ("PHI argument duplicated for edge %d->%d\n", e->src->index,
343 fprintf (stderr, "PHI argument\n");
344 print_generic_stmt (stderr, op, TDF_VOPS);
351 FOR_EACH_EDGE (e, ei, bb->preds)
353 if (e->aux != (void *) 2)
355 error ("No argument flowing through edge %d->%d\n", e->src->index,
366 fprintf (stderr, "for PHI node\n");
367 print_generic_stmt (stderr, phi, TDF_VOPS);
376 verify_flow_insensitive_alias_info (void)
380 bitmap visited = BITMAP_XMALLOC ();
382 for (i = 0; i < num_referenced_vars; i++)
386 varray_type may_aliases;
388 var = referenced_var (i);
390 may_aliases = ann->may_aliases;
392 for (j = 0; may_aliases && j < VARRAY_ACTIVE_SIZE (may_aliases); j++)
394 tree alias = VARRAY_TREE (may_aliases, j);
396 bitmap_set_bit (visited, var_ann (alias)->uid);
398 if (!may_be_aliased (alias))
400 error ("Non-addressable variable inside an alias set.");
401 debug_variable (alias);
407 for (i = 0; i < num_referenced_vars; i++)
411 var = referenced_var (i);
414 if (ann->mem_tag_kind == NOT_A_TAG
416 && !bitmap_bit_p (visited, ann->uid))
418 error ("Addressable variable that is an alias tag but is not in any alias set.");
423 BITMAP_XFREE (visited);
427 debug_variable (var);
428 internal_error ("verify_flow_insensitive_alias_info failed.");
433 verify_flow_sensitive_alias_info (void)
438 for (i = 1; i < num_ssa_names; i++)
441 struct ptr_info_def *pi;
446 ann = var_ann (SSA_NAME_VAR (ptr));
447 pi = SSA_NAME_PTR_INFO (ptr);
449 /* We only care for pointers that are actually referenced in the
451 if (!TREE_VISITED (ptr) || !POINTER_TYPE_P (TREE_TYPE (ptr)))
454 /* RESULT_DECL is special. If it's a GIMPLE register, then it
455 is only written-to only once in the return statement.
456 Otherwise, aggregate RESULT_DECLs may be written-to more than
457 once in virtual operands. */
458 if (TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL
459 && is_gimple_reg (ptr))
465 if (pi->is_dereferenced && !pi->name_mem_tag && !ann->type_mem_tag)
467 error ("Dereferenced pointers should have a name or a type tag");
473 && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars)))
475 error ("Pointers with a memory tag, should have points-to sets or point to malloc");
479 if (pi->value_escapes_p
481 && !is_call_clobbered (pi->name_mem_tag))
483 error ("Pointer escapes but its name tag is not call-clobbered.");
491 debug_variable (ptr);
492 internal_error ("verify_flow_sensitive_alias_info failed.");
495 DEF_VEC_MALLOC_P (bitmap);
497 /* Verify that all name tags have different points to sets.
498 This algorithm takes advantage of the fact that every variable with the
499 same name tag must have the same points-to set.
500 So we check a single variable for each name tag, and verify that its
501 points-to set is different from every other points-to set for other name
505 verify_name_tags (void)
509 bitmap first, second;
510 VEC (tree) *name_tag_reps = NULL;
511 VEC (bitmap) *pt_vars_for_reps = NULL;
513 /* First we compute the name tag representatives and their points-to sets. */
514 for (i = 0; i < num_ssa_names; i++)
518 tree ptr = ssa_name (i);
519 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
520 if (!TREE_VISITED (ptr)
521 || !POINTER_TYPE_P (TREE_TYPE (ptr))
524 || TREE_VISITED (pi->name_mem_tag))
526 TREE_VISITED (pi->name_mem_tag) = 1;
527 if (pi->pt_vars != NULL)
529 VEC_safe_push (tree, name_tag_reps, ptr);
530 VEC_safe_push (bitmap, pt_vars_for_reps, pi->pt_vars);
535 /* Now compare all the representative bitmaps with all other representative
536 bitmaps, to verify that they are all different. */
537 for (i = 0; VEC_iterate (bitmap, pt_vars_for_reps, i, first); i++)
539 for (j = i + 1; VEC_iterate (bitmap, pt_vars_for_reps, j, second); j++)
541 if (bitmap_equal_p (first, second))
543 error ("Two different pointers with identical points-to sets but different name tags");
544 debug_variable (VEC_index (tree, name_tag_reps, j));
550 /* Lastly, clear out the visited flags. */
551 for (i = 0; i < num_ssa_names; i++)
555 tree ptr = ssa_name (i);
556 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
557 if (!TREE_VISITED (ptr)
558 || !POINTER_TYPE_P (TREE_TYPE (ptr))
560 || !pi->name_mem_tag)
562 TREE_VISITED (pi->name_mem_tag) = 0;
565 VEC_free (bitmap, pt_vars_for_reps);
569 debug_variable (VEC_index (tree, name_tag_reps, i));
570 internal_error ("verify_name_tags failed");
572 /* Verify the consistency of aliasing information. */
575 verify_alias_info (void)
577 verify_flow_sensitive_alias_info ();
579 verify_flow_insensitive_alias_info ();
583 /* Verify common invariants in the SSA web.
584 TODO: verify the variable annotations. */
591 basic_block *definition_block = xcalloc (num_ssa_names, sizeof (basic_block));
594 enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS];
595 bitmap names_defined_in_bb = BITMAP_XMALLOC ();
597 timevar_push (TV_TREE_SSA_VERIFY);
599 /* Keep track of SSA names present in the IL. */
600 for (i = 1; i < num_ssa_names; i++)
602 TREE_VISITED (ssa_name (i)) = 0;
604 calculate_dominance_info (CDI_DOMINATORS);
606 /* Verify and register all the SSA_NAME definitions found in the
611 block_stmt_iterator bsi;
613 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
616 if (verify_def (bb, definition_block, PHI_RESULT (phi), phi,
617 !is_gimple_reg (PHI_RESULT (phi))))
619 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
621 tree def = PHI_ARG_DEF (phi, i);
622 if (TREE_CODE (def) != SSA_NAME && !is_gimple_min_invariant (def))
624 error ("PHI argument is not SSA_NAME, or invariant");
625 print_generic_stmt (stderr, phi, TDF_VOPS);
631 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
635 stmt = bsi_stmt (bsi);
636 get_stmt_operands (stmt);
638 if (stmt_ann (stmt)->makes_aliased_stores
639 && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) == 0)
641 error ("Statement makes aliased stores, but has no V_MAY_DEFS");
642 print_generic_stmt (stderr, stmt, TDF_VOPS);
646 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
648 if (verify_def (bb, definition_block, op, stmt, true))
652 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
654 if (verify_def (bb, definition_block, op, stmt, false))
661 /* Now verify all the uses and make sure they agree with the definitions
662 found in the previous pass. */
668 block_stmt_iterator bsi;
670 /* Make sure that all edges have a clear 'aux' field. */
671 FOR_EACH_EDGE (e, ei, bb->preds)
675 error ("AUX pointer initialized for edge %d->%d\n", e->src->index,
681 /* Verify the arguments for every PHI node in the block. */
682 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
684 if (verify_phi_args (phi, bb, definition_block))
686 bitmap_set_bit (names_defined_in_bb,
687 SSA_NAME_VERSION (PHI_RESULT (phi)));
690 /* Now verify all the uses and vuses in every statement of the block. */
691 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
693 tree stmt = bsi_stmt (bsi);
695 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
697 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
698 op, stmt, false, true,
699 names_defined_in_bb))
703 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
705 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
706 op, stmt, false, false,
707 names_defined_in_bb))
711 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
713 bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
717 /* Verify the uses in arguments of PHI nodes at the exits from the
719 FOR_EACH_EDGE (e, ei, bb->succs)
721 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
723 bool virtual = !is_gimple_reg (PHI_RESULT (phi));
724 op = PHI_ARG_DEF_FROM_EDGE (phi, e);
725 if (TREE_CODE (op) != SSA_NAME)
728 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
729 op, phi, false, virtual,
730 names_defined_in_bb))
735 bitmap_clear (names_defined_in_bb);
738 /* Finally, verify alias information. */
739 verify_alias_info ();
741 free (definition_block);
742 /* Restore the dominance information to its prior known state, so
743 that we do not perturb the compiler's subsequent behavior. */
744 if (orig_dom_state == DOM_NONE)
745 free_dominance_info (CDI_DOMINATORS);
747 dom_computed[CDI_DOMINATORS] = orig_dom_state;
749 BITMAP_XFREE (names_defined_in_bb);
750 timevar_pop (TV_TREE_SSA_VERIFY);
754 internal_error ("verify_ssa failed.");
758 /* Initialize global DFA and SSA structures. */
763 VARRAY_TREE_INIT (referenced_vars, 20, "referenced_vars");
764 call_clobbered_vars = BITMAP_XMALLOC ();
765 addressable_vars = BITMAP_XMALLOC ();
766 init_ssa_operands ();
769 global_var = NULL_TREE;
773 /* Deallocate memory associated with SSA data structures for FNDECL. */
776 delete_tree_ssa (void)
780 block_stmt_iterator bsi;
782 /* Remove annotations from every tree in the function. */
784 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
786 tree stmt = bsi_stmt (bsi);
788 ggc_free (stmt->common.ann);
789 stmt->common.ann = NULL;
792 /* Remove annotations from every referenced variable. */
795 for (i = 0; i < num_referenced_vars; i++)
797 tree var = referenced_var (i);
798 ggc_free (var->common.ann);
799 var->common.ann = NULL;
801 referenced_vars = NULL;
806 fini_ssa_operands ();
808 global_var = NULL_TREE;
809 BITMAP_XFREE (call_clobbered_vars);
810 call_clobbered_vars = NULL;
811 BITMAP_XFREE (addressable_vars);
812 addressable_vars = NULL;
816 /* Return true if EXPR is a useless type conversion, otherwise return
820 tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
822 /* If the inner and outer types are effectively the same, then
823 strip the type conversion and enter the equivalence into
825 if (inner_type == outer_type
826 || (lang_hooks.types_compatible_p (inner_type, outer_type)))
829 /* If both types are pointers and the outer type is a (void *), then
830 the conversion is not necessary. The opposite is not true since
831 that conversion would result in a loss of information if the
832 equivalence was used. Consider an indirect function call where
833 we need to know the exact type of the function to correctly
834 implement the ABI. */
835 else if (POINTER_TYPE_P (inner_type)
836 && POINTER_TYPE_P (outer_type)
837 && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
840 /* Pointers and references are equivalent once we get to GENERIC,
841 so strip conversions that just switch between them. */
842 else if (POINTER_TYPE_P (inner_type)
843 && POINTER_TYPE_P (outer_type)
844 && lang_hooks.types_compatible_p (TREE_TYPE (inner_type),
845 TREE_TYPE (outer_type)))
848 /* If both the inner and outer types are integral types, then the
849 conversion is not necessary if they have the same mode and
850 signedness and precision, and both or neither are boolean. Some
851 code assumes an invariant that boolean types stay boolean and do
852 not become 1-bit bit-field types. Note that types with precision
853 not using all bits of the mode (such as bit-field types in C)
854 mean that testing of precision is necessary. */
855 else if (INTEGRAL_TYPE_P (inner_type)
856 && INTEGRAL_TYPE_P (outer_type)
857 && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
858 && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
859 && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
861 bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE);
862 bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE);
863 if (first_boolean == second_boolean)
867 /* Recurse for complex types. */
868 else if (TREE_CODE (inner_type) == COMPLEX_TYPE
869 && TREE_CODE (outer_type) == COMPLEX_TYPE
870 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
871 TREE_TYPE (inner_type)))
877 /* Return true if EXPR is a useless type conversion, otherwise return
881 tree_ssa_useless_type_conversion (tree expr)
883 /* If we have an assignment that merely uses a NOP_EXPR to change
884 the top of the RHS to the type of the LHS and the type conversion
885 is "safe", then strip away the type conversion so that we can
886 enter LHS = RHS into the const_and_copies table. */
887 if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR
888 || TREE_CODE (expr) == VIEW_CONVERT_EXPR
889 || TREE_CODE (expr) == NON_LVALUE_EXPR)
890 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
891 TREE_TYPE (TREE_OPERAND (expr,
899 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
900 described in walk_use_def_chains.
902 VISITED is a bitmap used to mark visited SSA_NAMEs to avoid
905 IS_DFS is true if the caller wants to perform a depth-first search
906 when visiting PHI nodes. A DFS will visit each PHI argument and
907 call FN after each one. Otherwise, all the arguments are
908 visited first and then FN is called with each of the visited
909 arguments in a separate pass. */
912 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
913 bitmap visited, bool is_dfs)
917 if (bitmap_bit_p (visited, SSA_NAME_VERSION (var)))
920 bitmap_set_bit (visited, SSA_NAME_VERSION (var));
922 def_stmt = SSA_NAME_DEF_STMT (var);
924 if (TREE_CODE (def_stmt) != PHI_NODE)
926 /* If we reached the end of the use-def chain, call FN. */
927 return fn (var, def_stmt, data);
933 /* When doing a breadth-first search, call FN before following the
934 use-def links for each argument. */
936 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
937 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
940 /* Follow use-def links out of each PHI argument. */
941 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
943 tree arg = PHI_ARG_DEF (def_stmt, i);
944 if (TREE_CODE (arg) == SSA_NAME
945 && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
949 /* When doing a depth-first search, call FN after following the
950 use-def links for each argument. */
952 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
953 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
962 /* Walk use-def chains starting at the SSA variable VAR. Call
963 function FN at each reaching definition found. FN takes three
964 arguments: VAR, its defining statement (DEF_STMT) and a generic
965 pointer to whatever state information that FN may want to maintain
966 (DATA). FN is able to stop the walk by returning true, otherwise
967 in order to continue the walk, FN should return false.
969 Note, that if DEF_STMT is a PHI node, the semantics are slightly
970 different. The first argument to FN is no longer the original
971 variable VAR, but the PHI argument currently being examined. If FN
972 wants to get at VAR, it should call PHI_RESULT (PHI).
974 If IS_DFS is true, this function will:
976 1- walk the use-def chains for all the PHI arguments, and,
977 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
979 If IS_DFS is false, the two steps above are done in reverse order
980 (i.e., a breadth-first search). */
984 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
989 gcc_assert (TREE_CODE (var) == SSA_NAME);
991 def_stmt = SSA_NAME_DEF_STMT (var);
993 /* We only need to recurse if the reaching definition comes from a PHI
995 if (TREE_CODE (def_stmt) != PHI_NODE)
996 (*fn) (var, def_stmt, data);
999 bitmap visited = BITMAP_XMALLOC ();
1000 walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
1001 BITMAP_XFREE (visited);
1006 /* Replaces VAR with REPL in memory reference expression *X in
1010 propagate_into_addr (tree stmt, tree var, tree *x, tree repl)
1012 tree new_var, ass_stmt, addr_var;
1014 block_stmt_iterator bsi;
1016 /* There is nothing special to handle in the other cases. */
1017 if (TREE_CODE (repl) != ADDR_EXPR)
1019 addr_var = TREE_OPERAND (repl, 0);
1021 while (handled_component_p (*x)
1022 || TREE_CODE (*x) == REALPART_EXPR
1023 || TREE_CODE (*x) == IMAGPART_EXPR)
1024 x = &TREE_OPERAND (*x, 0);
1026 if (TREE_CODE (*x) != INDIRECT_REF
1027 || TREE_OPERAND (*x, 0) != var)
1030 if (TREE_TYPE (*x) == TREE_TYPE (addr_var))
1033 mark_new_vars_to_rename (stmt, vars_to_rename);
1038 /* Frontends sometimes produce expressions like *&a instead of a[0].
1039 Create a temporary variable to handle this case. */
1040 ass_stmt = build2 (MODIFY_EXPR, void_type_node, NULL_TREE, repl);
1041 new_var = duplicate_ssa_name (var, ass_stmt);
1042 TREE_OPERAND (*x, 0) = new_var;
1043 TREE_OPERAND (ass_stmt, 0) = new_var;
1045 bb = bb_for_stmt (stmt);
1046 tree_block_label (bb);
1047 bsi = bsi_after_labels (bb);
1048 bsi_insert_after (&bsi, ass_stmt, BSI_NEW_STMT);
1050 mark_new_vars_to_rename (stmt, vars_to_rename);
1053 /* Replaces immediate uses of VAR by REPL. */
1056 replace_immediate_uses (tree var, tree repl)
1063 use_operand_p use_p;
1065 df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
1066 n = num_immediate_uses (df);
1068 for (i = 0; i < n; i++)
1070 stmt = immediate_use (df, i);
1072 if (TREE_CODE (stmt) == PHI_NODE)
1074 for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
1075 if (PHI_ARG_DEF (stmt, j) == var)
1077 SET_PHI_ARG_DEF (stmt, j, repl);
1078 if (TREE_CODE (repl) == SSA_NAME
1079 && PHI_ARG_EDGE (stmt, j)->flags & EDGE_ABNORMAL)
1080 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl) = 1;
1086 get_stmt_operands (stmt);
1087 mark_new_vars = false;
1088 if (is_gimple_reg (SSA_NAME_VAR (var)))
1090 if (TREE_CODE (stmt) == MODIFY_EXPR)
1092 propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 0), repl);
1093 propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 1), repl);
1096 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1097 if (USE_FROM_PTR (use_p) == var)
1099 propagate_value (use_p, repl);
1100 mark_new_vars = POINTER_TYPE_P (TREE_TYPE (repl));
1105 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
1106 SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
1107 if (USE_FROM_PTR (use_p) == var)
1108 propagate_value (use_p, repl);
1111 /* FIXME. If REPL is a constant, we need to fold STMT.
1112 However, fold_stmt wants a pointer to the statement, because
1113 it may happen that it needs to replace the whole statement
1114 with a new expression. Since the current def-use machinery
1115 does not return pointers to statements, we call fold_stmt
1116 with the address of a local temporary, if that call changes
1117 the temporary then we fallback on looking for a proper
1118 pointer to STMT by scanning STMT's basic block.
1120 Note that all this will become unnecessary soon. This
1121 pass is being replaced with a proper copy propagation pass
1122 for 4.1 (dnovillo, 2004-09-17). */
1123 if (TREE_CODE (repl) != SSA_NAME)
1129 block_stmt_iterator si = bsi_for_stmt (stmt);
1130 bsi_replace (&si, tmp, true);
1131 stmt = bsi_stmt (si);
1135 /* If REPL is a pointer, it may have different memory tags associated
1136 with it. For instance, VAR may have had a name tag while REPL
1137 only had a type tag. In these cases, the virtual operands (if
1138 any) in the statement will refer to different symbols which need
1141 mark_new_vars_to_rename (stmt, vars_to_rename);
1147 /* Gets the value VAR is equivalent to according to EQ_TO. */
1150 get_eq_name (tree *eq_to, tree var)
1155 while (TREE_CODE (val) == SSA_NAME)
1157 ver = SSA_NAME_VERSION (val);
1164 while (TREE_CODE (var) == SSA_NAME)
1166 ver = SSA_NAME_VERSION (var);
1177 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1178 its result is redundant to to EQ_TO array. */
1181 check_phi_redundancy (tree phi, tree *eq_to)
1183 tree val = NULL_TREE, def, res = PHI_RESULT (phi), stmt;
1184 unsigned i, ver = SSA_NAME_VERSION (res), n;
1187 /* It is unlikely that such large phi node would be redundant. */
1188 if (PHI_NUM_ARGS (phi) > 16)
1191 for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
1193 def = PHI_ARG_DEF (phi, i);
1195 if (TREE_CODE (def) == SSA_NAME)
1197 def = get_eq_name (eq_to, def);
1203 && !operand_equal_p (val, def, 0))
1209 /* At least one of the arguments should not be equal to the result, or
1210 something strange is happening. */
1213 if (get_eq_name (eq_to, res) == val)
1216 if (!may_propagate_copy (res, val))
1221 df = get_immediate_uses (SSA_NAME_DEF_STMT (res));
1222 n = num_immediate_uses (df);
1224 for (i = 0; i < n; i++)
1226 stmt = immediate_use (df, i);
1228 if (TREE_CODE (stmt) == PHI_NODE)
1229 check_phi_redundancy (stmt, eq_to);
1233 /* Removes redundant phi nodes.
1235 A redundant PHI node is a PHI node where all of its PHI arguments
1236 are the same value, excluding any PHI arguments which are the same
1239 A redundant PHI node is effectively a copy, so we forward copy propagate
1240 which removes all uses of the destination of the PHI node then
1241 finally we delete the redundant PHI node.
1243 Note that if we can not copy propagate the PHI node, then the PHI
1244 will not be removed. Thus we do not have to worry about dependencies
1245 between PHIs and the problems serializing PHIs into copies creates.
1247 The most important effect of this pass is to remove degenerate PHI
1248 nodes created by removing unreachable code. */
1251 kill_redundant_phi_nodes (void)
1254 unsigned i, old_num_ssa_names;
1256 tree phi, var, repl, stmt;
1258 /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1259 replaced. If EQ_TO[VER] is ssa name and it is decided to replace it by
1260 other value, it may be necessary to follow the chain till the final value.
1261 We perform path shortening (replacing the entries of the EQ_TO array with
1262 heads of these chains) whenever we access the field to prevent quadratic
1263 complexity (probably would not occur in practice anyway, but let us play
1265 eq_to = xcalloc (num_ssa_names, sizeof (tree));
1267 /* We have had cases where computing immediate uses takes a
1268 significant amount of compile time. If we run into such
1269 problems here, we may want to only compute immediate uses for
1270 a subset of all the SSA_NAMEs instead of computing it for
1271 all of the SSA_NAMEs. */
1272 compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
1273 old_num_ssa_names = num_ssa_names;
1277 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1279 var = PHI_RESULT (phi);
1280 check_phi_redundancy (phi, eq_to);
1284 /* Now propagate the values. */
1285 for (i = 0; i < old_num_ssa_names; i++)
1290 repl = get_eq_name (eq_to, ssa_name (i));
1291 if (repl != ssa_name (i))
1292 replace_immediate_uses (ssa_name (i), repl);
1295 /* And remove the dead phis. */
1296 for (i = 0; i < old_num_ssa_names; i++)
1301 repl = get_eq_name (eq_to, ssa_name (i));
1302 if (repl != ssa_name (i))
1304 stmt = SSA_NAME_DEF_STMT (ssa_name (i));
1305 remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
1313 struct tree_opt_pass pass_redundant_phi =
1315 "redphi", /* name */
1317 kill_redundant_phi_nodes, /* execute */
1320 0, /* static_pass_number */
1322 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1323 0, /* properties_provided */
1324 0, /* properties_destroyed */
1325 0, /* todo_flags_start */
1326 TODO_dump_func | TODO_rename_vars
1327 | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
1331 /* Emit warnings for uninitialized variables. This is done in two passes.
1333 The first pass notices real uses of SSA names with default definitions.
1334 Such uses are unconditionally uninitialized, and we can be certain that
1335 such a use is a mistake. This pass is run before most optimizations,
1336 so that we catch as many as we can.
1338 The second pass follows PHI nodes to find uses that are potentially
1339 uninitialized. In this case we can't necessarily prove that the use
1340 is really uninitialized. This pass is run after most optimizations,
1341 so that we thread as many jumps and possible, and delete as much dead
1342 code as possible, in order to reduce false positives. We also look
1343 again for plain uninitialized variables, since optimization may have
1344 changed conditionally uninitialized to unconditionally uninitialized. */
1346 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1347 warning text is in MSGID and LOCUS may contain a location or be null. */
1350 warn_uninit (tree t, const char *msgid, location_t *locus)
1352 tree var = SSA_NAME_VAR (t);
1353 tree def = SSA_NAME_DEF_STMT (t);
1355 /* Default uses (indicated by an empty definition statement),
1356 are uninitialized. */
1357 if (!IS_EMPTY_STMT (def))
1360 /* Except for PARMs of course, which are always initialized. */
1361 if (TREE_CODE (var) == PARM_DECL)
1364 /* Hard register variables get their initial value from the ether. */
1365 if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1368 /* TREE_NO_WARNING either means we already warned, or the front end
1369 wishes to suppress the warning. */
1370 if (TREE_NO_WARNING (var))
1374 locus = &DECL_SOURCE_LOCATION (var);
1375 warning (msgid, locus, var);
1376 TREE_NO_WARNING (var) = 1;
1379 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1380 and warn about them. */
1383 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
1385 location_t *locus = data;
1388 /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */
1389 if (TREE_CODE (t) == SSA_NAME)
1391 warn_uninit (t, "%H'%D' is used uninitialized in this function", locus);
1394 else if (IS_TYPE_OR_DECL_P (t))
1400 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1401 and warn about them. */
1404 warn_uninitialized_phi (tree phi)
1406 int i, n = PHI_NUM_ARGS (phi);
1408 /* Don't look at memory tags. */
1409 if (!is_gimple_reg (PHI_RESULT (phi)))
1412 for (i = 0; i < n; ++i)
1414 tree op = PHI_ARG_DEF (phi, i);
1415 if (TREE_CODE (op) == SSA_NAME)
1416 warn_uninit (op, "%H'%D' may be used uninitialized in this function",
1422 execute_early_warn_uninitialized (void)
1424 block_stmt_iterator bsi;
1428 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1429 walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1430 EXPR_LOCUS (bsi_stmt (bsi)), NULL);
1434 execute_late_warn_uninitialized (void)
1439 /* Re-do the plain uninitialized variable check, as optimization may have
1440 straightened control flow. Do this first so that we don't accidentally
1441 get a "may be" warning when we'd have seen an "is" warning later. */
1442 execute_early_warn_uninitialized ();
1445 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1446 warn_uninitialized_phi (phi);
1450 gate_warn_uninitialized (void)
1452 return warn_uninitialized != 0;
1455 struct tree_opt_pass pass_early_warn_uninitialized =
1458 gate_warn_uninitialized, /* gate */
1459 execute_early_warn_uninitialized, /* execute */
1462 0, /* static_pass_number */
1464 PROP_ssa, /* properties_required */
1465 0, /* properties_provided */
1466 0, /* properties_destroyed */
1467 0, /* todo_flags_start */
1468 0, /* todo_flags_finish */
1472 struct tree_opt_pass pass_late_warn_uninitialized =
1475 gate_warn_uninitialized, /* gate */
1476 execute_late_warn_uninitialized, /* execute */
1479 0, /* static_pass_number */
1481 PROP_ssa, /* properties_required */
1482 0, /* properties_provided */
1483 0, /* properties_destroyed */
1484 0, /* todo_flags_start */
1485 0, /* todo_flags_finish */