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;
104 /* Return true if SSA_NAME is malformed and mark it visited.
106 IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
110 verify_ssa_name (tree ssa_name, bool is_virtual)
112 TREE_VISITED (ssa_name) = 1;
114 if (TREE_CODE (ssa_name) != SSA_NAME)
116 error ("Expected an SSA_NAME object");
120 if (TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name)))
122 error ("Type mismatch between an SSA_NAME and its symbol.");
126 if (SSA_NAME_IN_FREE_LIST (ssa_name))
128 error ("Found an SSA_NAME that had been released into the free pool");
132 if (is_virtual && is_gimple_reg (ssa_name))
134 error ("Found a virtual definition for a GIMPLE register");
138 if (!is_virtual && !is_gimple_reg (ssa_name))
140 error ("Found a real definition for a non-register");
148 /* Return true if the definition of SSA_NAME at block BB is malformed.
150 STMT is the statement where SSA_NAME is created.
152 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
153 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
154 it means that the block in that array slot contains the
155 definition of SSA_NAME.
157 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
161 verify_def (basic_block bb, basic_block *definition_block, tree ssa_name,
162 tree stmt, bool is_virtual)
164 if (verify_ssa_name (ssa_name, is_virtual))
167 if (definition_block[SSA_NAME_VERSION (ssa_name)])
169 error ("SSA_NAME created in two different blocks %i and %i",
170 definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index);
174 definition_block[SSA_NAME_VERSION (ssa_name)] = bb;
176 if (SSA_NAME_DEF_STMT (ssa_name) != stmt)
178 error ("SSA_NAME_DEF_STMT is wrong");
179 fprintf (stderr, "Expected definition statement:\n");
180 print_generic_stmt (stderr, SSA_NAME_DEF_STMT (ssa_name), TDF_VOPS);
181 fprintf (stderr, "\nActual definition statement:\n");
182 print_generic_stmt (stderr, stmt, TDF_VOPS);
189 fprintf (stderr, "while verifying SSA_NAME ");
190 print_generic_expr (stderr, ssa_name, 0);
191 fprintf (stderr, " in statement\n");
192 print_generic_stmt (stderr, stmt, TDF_VOPS);
198 /* Return true if the use of SSA_NAME at statement STMT in block BB is
201 DEF_BB is the block where SSA_NAME was found to be created.
203 IDOM contains immediate dominator information for the flowgraph.
205 CHECK_ABNORMAL is true if the caller wants to check whether this use
206 is flowing through an abnormal edge (only used when checking PHI
209 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
212 If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
213 that are defined before STMT in basic block BB. */
216 verify_use (basic_block bb, basic_block def_bb, tree ssa_name,
217 tree stmt, bool check_abnormal, bool is_virtual,
218 bitmap names_defined_in_bb)
222 err = verify_ssa_name (ssa_name, is_virtual);
224 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name))
225 && var_ann (SSA_NAME_VAR (ssa_name))->default_def == ssa_name)
226 ; /* Default definitions have empty statements. Nothing to do. */
229 error ("Missing definition");
232 else if (bb != def_bb
233 && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
235 error ("Definition in block %i does not dominate use in block %i",
236 def_bb->index, bb->index);
239 else if (bb == def_bb
240 && names_defined_in_bb != NULL
241 && !bitmap_bit_p (names_defined_in_bb, SSA_NAME_VERSION (ssa_name)))
243 error ("Definition in block %i follows the use", def_bb->index);
248 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
250 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
256 fprintf (stderr, "for SSA_NAME: ");
257 print_generic_expr (stderr, ssa_name, TDF_VOPS);
258 fprintf (stderr, "in statement:\n");
259 print_generic_stmt (stderr, stmt, TDF_VOPS);
266 /* Return true if any of the arguments for PHI node PHI at block BB is
269 IDOM contains immediate dominator information for the flowgraph.
271 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
272 numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
273 block in that array slot contains the definition of SSA_NAME. */
276 verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)
280 int i, phi_num_args = PHI_NUM_ARGS (phi);
283 /* Mark all the incoming edges. */
284 FOR_EACH_EDGE (e, ei, bb->preds)
287 for (i = 0; i < phi_num_args; i++)
289 tree op = PHI_ARG_DEF (phi, i);
291 e = PHI_ARG_EDGE (phi, i);
293 if (TREE_CODE (op) == SSA_NAME)
294 err = verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op,
295 phi, e->flags & EDGE_ABNORMAL,
296 !is_gimple_reg (PHI_RESULT (phi)),
301 error ("Wrong edge %d->%d for PHI argument\n",
302 e->src->index, e->dest->index, bb->index);
306 if (e->aux == (void *) 0)
308 error ("PHI argument flowing through dead edge %d->%d\n",
309 e->src->index, e->dest->index);
313 if (e->aux == (void *) 2)
315 error ("PHI argument duplicated for edge %d->%d\n", e->src->index,
322 fprintf (stderr, "PHI argument\n");
323 print_generic_stmt (stderr, op, TDF_VOPS);
330 FOR_EACH_EDGE (e, ei, bb->preds)
332 if (e->aux != (void *) 2)
334 error ("No argument flowing through edge %d->%d\n", e->src->index,
345 fprintf (stderr, "for PHI node\n");
346 print_generic_stmt (stderr, phi, TDF_VOPS);
355 verify_flow_insensitive_alias_info (void)
359 bitmap visited = BITMAP_XMALLOC ();
361 for (i = 0; i < num_referenced_vars; i++)
365 varray_type may_aliases;
367 var = referenced_var (i);
369 may_aliases = ann->may_aliases;
371 for (j = 0; may_aliases && j < VARRAY_ACTIVE_SIZE (may_aliases); j++)
373 tree alias = VARRAY_TREE (may_aliases, j);
375 bitmap_set_bit (visited, var_ann (alias)->uid);
377 if (!may_be_aliased (alias))
379 error ("Non-addressable variable inside an alias set.");
380 debug_variable (alias);
386 for (i = 0; i < num_referenced_vars; i++)
390 var = referenced_var (i);
393 if (ann->mem_tag_kind == NOT_A_TAG
395 && !bitmap_bit_p (visited, ann->uid))
397 error ("Addressable variable that is an alias tag but is not in any alias set.");
402 BITMAP_XFREE (visited);
406 debug_variable (var);
407 internal_error ("verify_flow_insensitive_alias_info failed.");
412 verify_flow_sensitive_alias_info (void)
417 for (i = 1; i < num_ssa_names; i++)
420 struct ptr_info_def *pi;
425 ann = var_ann (SSA_NAME_VAR (ptr));
426 pi = SSA_NAME_PTR_INFO (ptr);
428 /* We only care for pointers that are actually referenced in the
430 if (!TREE_VISITED (ptr) || !POINTER_TYPE_P (TREE_TYPE (ptr)))
433 /* RESULT_DECL is special. If it's a GIMPLE register, then it
434 is only written-to only once in the return statement.
435 Otherwise, aggregate RESULT_DECLs may be written-to more than
436 once in virtual operands. */
437 if (TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL
438 && is_gimple_reg (ptr))
444 if (pi->is_dereferenced && !pi->name_mem_tag && !ann->type_mem_tag)
446 error ("Dereferenced pointers should have a name or a type tag");
452 && (pi->pt_vars == NULL
453 || bitmap_first_set_bit (pi->pt_vars) < 0))
455 error ("Pointers with a memory tag, should have points-to sets or point to malloc");
459 if (pi->value_escapes_p
461 && !is_call_clobbered (pi->name_mem_tag))
463 error ("Pointer escapes but its name tag is not call-clobbered.");
471 debug_variable (ptr);
472 internal_error ("verify_flow_sensitive_alias_info failed.");
475 DEF_VEC_MALLOC_P (bitmap);
477 /* Verify that all name tags have different points to sets.
478 This algorithm takes advantage of the fact that every variable with the
479 same name tag must have the same points-to set.
480 So we check a single variable for each name tag, and verify that its
481 points-to set is different from every other points-to set for other name
485 verify_name_tags (void)
489 bitmap first, second;
490 VEC (tree) *name_tag_reps = NULL;
491 VEC (bitmap) *pt_vars_for_reps = NULL;
493 /* First we compute the name tag representatives and their points-to sets. */
494 for (i = 0; i < num_ssa_names; i++)
498 tree ptr = ssa_name (i);
499 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
500 if (!TREE_VISITED (ptr)
501 || !POINTER_TYPE_P (TREE_TYPE (ptr))
504 || TREE_VISITED (pi->name_mem_tag))
506 TREE_VISITED (pi->name_mem_tag) = 1;
507 if (pi->pt_vars != NULL)
509 VEC_safe_push (tree, name_tag_reps, ptr);
510 VEC_safe_push (bitmap, pt_vars_for_reps, pi->pt_vars);
515 /* Now compare all the representative bitmaps with all other representative
516 bitmaps, to verify that they are all different. */
517 for (i = 0; VEC_iterate (bitmap, pt_vars_for_reps, i, first); i++)
519 for (j = i + 1; VEC_iterate (bitmap, pt_vars_for_reps, j, second); j++)
521 if (bitmap_equal_p (first, second))
523 error ("Two different pointers with identical points-to sets but different name tags");
524 debug_variable (VEC_index (tree, name_tag_reps, j));
530 /* Lastly, clear out the visited flags. */
531 for (i = 0; i < num_ssa_names; i++)
535 tree ptr = ssa_name (i);
536 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
537 if (!TREE_VISITED (ptr)
538 || !POINTER_TYPE_P (TREE_TYPE (ptr))
540 || !pi->name_mem_tag)
542 TREE_VISITED (pi->name_mem_tag) = 0;
545 VEC_free (bitmap, pt_vars_for_reps);
549 debug_variable (VEC_index (tree, name_tag_reps, i));
550 internal_error ("verify_name_tags failed");
552 /* Verify the consistency of aliasing information. */
555 verify_alias_info (void)
557 verify_flow_sensitive_alias_info ();
559 verify_flow_insensitive_alias_info ();
563 /* Verify common invariants in the SSA web.
564 TODO: verify the variable annotations. */
571 basic_block *definition_block = xcalloc (num_ssa_names, sizeof (basic_block));
574 enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS];
575 bitmap names_defined_in_bb = BITMAP_XMALLOC ();
577 timevar_push (TV_TREE_SSA_VERIFY);
579 /* Keep track of SSA names present in the IL. */
580 for (i = 1; i < num_ssa_names; i++)
582 TREE_VISITED (ssa_name (i)) = 0;
584 calculate_dominance_info (CDI_DOMINATORS);
586 /* Verify and register all the SSA_NAME definitions found in the
591 block_stmt_iterator bsi;
593 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
596 if (verify_def (bb, definition_block, PHI_RESULT (phi), phi,
597 !is_gimple_reg (PHI_RESULT (phi))))
599 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
601 tree def = PHI_ARG_DEF (phi, i);
602 if (TREE_CODE (def) != SSA_NAME && !is_gimple_min_invariant (def))
604 error ("PHI argument is not SSA_NAME, or invariant");
605 print_generic_stmt (stderr, phi, TDF_VOPS);
611 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
615 stmt = bsi_stmt (bsi);
616 get_stmt_operands (stmt);
618 if (stmt_ann (stmt)->makes_aliased_stores
619 && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) == 0)
621 error ("Statement makes aliased stores, but has no V_MAY_DEFS");
622 print_generic_stmt (stderr, stmt, TDF_VOPS);
626 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
628 if (verify_def (bb, definition_block, op, stmt, true))
632 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
634 if (verify_def (bb, definition_block, op, stmt, false))
641 /* Now verify all the uses and make sure they agree with the definitions
642 found in the previous pass. */
648 block_stmt_iterator bsi;
650 /* Make sure that all edges have a clear 'aux' field. */
651 FOR_EACH_EDGE (e, ei, bb->preds)
655 error ("AUX pointer initialized for edge %d->%d\n", e->src->index,
661 /* Verify the arguments for every PHI node in the block. */
662 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
664 if (verify_phi_args (phi, bb, definition_block))
666 bitmap_set_bit (names_defined_in_bb,
667 SSA_NAME_VERSION (PHI_RESULT (phi)));
670 /* Now verify all the uses and vuses in every statement of the block. */
671 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
673 tree stmt = bsi_stmt (bsi);
675 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
677 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
678 op, stmt, false, true,
679 names_defined_in_bb))
683 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
685 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
686 op, stmt, false, false,
687 names_defined_in_bb))
691 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
693 bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
697 /* Verify the uses in arguments of PHI nodes at the exits from the
699 FOR_EACH_EDGE (e, ei, bb->succs)
701 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
703 bool virtual = !is_gimple_reg (PHI_RESULT (phi));
704 op = PHI_ARG_DEF_FROM_EDGE (phi, e);
705 if (TREE_CODE (op) != SSA_NAME)
708 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
709 op, phi, false, virtual,
710 names_defined_in_bb))
715 bitmap_clear (names_defined_in_bb);
718 /* Finally, verify alias information. */
719 verify_alias_info ();
721 free (definition_block);
722 /* Restore the dominance information to its prior known state, so
723 that we do not perturb the compiler's subsequent behavior. */
724 if (orig_dom_state == DOM_NONE)
725 free_dominance_info (CDI_DOMINATORS);
727 dom_computed[CDI_DOMINATORS] = orig_dom_state;
729 BITMAP_XFREE (names_defined_in_bb);
730 timevar_pop (TV_TREE_SSA_VERIFY);
734 internal_error ("verify_ssa failed.");
738 /* Initialize global DFA and SSA structures. */
743 VARRAY_TREE_INIT (referenced_vars, 20, "referenced_vars");
744 call_clobbered_vars = BITMAP_XMALLOC ();
745 addressable_vars = BITMAP_XMALLOC ();
746 init_ssa_operands ();
749 global_var = NULL_TREE;
753 /* Deallocate memory associated with SSA data structures for FNDECL. */
756 delete_tree_ssa (void)
760 block_stmt_iterator bsi;
762 /* Remove annotations from every tree in the function. */
764 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
766 tree stmt = bsi_stmt (bsi);
768 ggc_free (stmt->common.ann);
769 stmt->common.ann = NULL;
772 /* Remove annotations from every referenced variable. */
775 for (i = 0; i < num_referenced_vars; i++)
777 tree var = referenced_var (i);
778 ggc_free (var->common.ann);
779 var->common.ann = NULL;
781 referenced_vars = NULL;
786 fini_ssa_operands ();
788 global_var = NULL_TREE;
789 BITMAP_XFREE (call_clobbered_vars);
790 call_clobbered_vars = NULL;
791 BITMAP_XFREE (addressable_vars);
792 addressable_vars = NULL;
796 /* Return true if EXPR is a useless type conversion, otherwise return
800 tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
802 /* If the inner and outer types are effectively the same, then
803 strip the type conversion and enter the equivalence into
805 if (inner_type == outer_type
806 || (lang_hooks.types_compatible_p (inner_type, outer_type)))
809 /* If both types are pointers and the outer type is a (void *), then
810 the conversion is not necessary. The opposite is not true since
811 that conversion would result in a loss of information if the
812 equivalence was used. Consider an indirect function call where
813 we need to know the exact type of the function to correctly
814 implement the ABI. */
815 else if (POINTER_TYPE_P (inner_type)
816 && POINTER_TYPE_P (outer_type)
817 && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
820 /* Pointers and references are equivalent once we get to GENERIC,
821 so strip conversions that just switch between them. */
822 else if (POINTER_TYPE_P (inner_type)
823 && POINTER_TYPE_P (outer_type)
824 && lang_hooks.types_compatible_p (TREE_TYPE (inner_type),
825 TREE_TYPE (outer_type)))
828 /* If both the inner and outer types are integral types, then the
829 conversion is not necessary if they have the same mode and
830 signedness and precision, and both or neither are boolean. Some
831 code assumes an invariant that boolean types stay boolean and do
832 not become 1-bit bit-field types. Note that types with precision
833 not using all bits of the mode (such as bit-field types in C)
834 mean that testing of precision is necessary. */
835 else if (INTEGRAL_TYPE_P (inner_type)
836 && INTEGRAL_TYPE_P (outer_type)
837 && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
838 && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
839 && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
841 bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE);
842 bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE);
843 if (first_boolean == second_boolean)
847 /* Recurse for complex types. */
848 else if (TREE_CODE (inner_type) == COMPLEX_TYPE
849 && TREE_CODE (outer_type) == COMPLEX_TYPE
850 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
851 TREE_TYPE (inner_type)))
857 /* Return true if EXPR is a useless type conversion, otherwise return
861 tree_ssa_useless_type_conversion (tree expr)
863 /* If we have an assignment that merely uses a NOP_EXPR to change
864 the top of the RHS to the type of the LHS and the type conversion
865 is "safe", then strip away the type conversion so that we can
866 enter LHS = RHS into the const_and_copies table. */
867 if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR
868 || TREE_CODE (expr) == VIEW_CONVERT_EXPR
869 || TREE_CODE (expr) == NON_LVALUE_EXPR)
870 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
871 TREE_TYPE (TREE_OPERAND (expr,
879 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
880 described in walk_use_def_chains.
882 VISITED is a bitmap used to mark visited SSA_NAMEs to avoid
885 IS_DFS is true if the caller wants to perform a depth-first search
886 when visiting PHI nodes. A DFS will visit each PHI argument and
887 call FN after each one. Otherwise, all the arguments are
888 visited first and then FN is called with each of the visited
889 arguments in a separate pass. */
892 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
893 bitmap visited, bool is_dfs)
897 if (bitmap_bit_p (visited, SSA_NAME_VERSION (var)))
900 bitmap_set_bit (visited, SSA_NAME_VERSION (var));
902 def_stmt = SSA_NAME_DEF_STMT (var);
904 if (TREE_CODE (def_stmt) != PHI_NODE)
906 /* If we reached the end of the use-def chain, call FN. */
907 return fn (var, def_stmt, data);
913 /* When doing a breadth-first search, call FN before following the
914 use-def links for each argument. */
916 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
917 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
920 /* Follow use-def links out of each PHI argument. */
921 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
923 tree arg = PHI_ARG_DEF (def_stmt, i);
924 if (TREE_CODE (arg) == SSA_NAME
925 && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
929 /* When doing a depth-first search, call FN after following the
930 use-def links for each argument. */
932 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
933 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
942 /* Walk use-def chains starting at the SSA variable VAR. Call
943 function FN at each reaching definition found. FN takes three
944 arguments: VAR, its defining statement (DEF_STMT) and a generic
945 pointer to whatever state information that FN may want to maintain
946 (DATA). FN is able to stop the walk by returning true, otherwise
947 in order to continue the walk, FN should return false.
949 Note, that if DEF_STMT is a PHI node, the semantics are slightly
950 different. The first argument to FN is no longer the original
951 variable VAR, but the PHI argument currently being examined. If FN
952 wants to get at VAR, it should call PHI_RESULT (PHI).
954 If IS_DFS is true, this function will:
956 1- walk the use-def chains for all the PHI arguments, and,
957 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
959 If IS_DFS is false, the two steps above are done in reverse order
960 (i.e., a breadth-first search). */
964 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
969 gcc_assert (TREE_CODE (var) == SSA_NAME);
971 def_stmt = SSA_NAME_DEF_STMT (var);
973 /* We only need to recurse if the reaching definition comes from a PHI
975 if (TREE_CODE (def_stmt) != PHI_NODE)
976 (*fn) (var, def_stmt, data);
979 bitmap visited = BITMAP_XMALLOC ();
980 walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
981 BITMAP_XFREE (visited);
986 /* Replaces VAR with REPL in memory reference expression *X in
990 propagate_into_addr (tree stmt, tree var, tree *x, tree repl)
992 tree new_var, ass_stmt, addr_var;
994 block_stmt_iterator bsi;
996 /* There is nothing special to handle in the other cases. */
997 if (TREE_CODE (repl) != ADDR_EXPR)
999 addr_var = TREE_OPERAND (repl, 0);
1001 while (handled_component_p (*x)
1002 || TREE_CODE (*x) == REALPART_EXPR
1003 || TREE_CODE (*x) == IMAGPART_EXPR)
1004 x = &TREE_OPERAND (*x, 0);
1006 if (TREE_CODE (*x) != INDIRECT_REF
1007 || TREE_OPERAND (*x, 0) != var)
1010 if (TREE_TYPE (*x) == TREE_TYPE (addr_var))
1013 mark_new_vars_to_rename (stmt, vars_to_rename);
1018 /* Frontends sometimes produce expressions like *&a instead of a[0].
1019 Create a temporary variable to handle this case. */
1020 ass_stmt = build2 (MODIFY_EXPR, void_type_node, NULL_TREE, repl);
1021 new_var = duplicate_ssa_name (var, ass_stmt);
1022 TREE_OPERAND (*x, 0) = new_var;
1023 TREE_OPERAND (ass_stmt, 0) = new_var;
1025 bb = bb_for_stmt (stmt);
1026 tree_block_label (bb);
1027 bsi = bsi_after_labels (bb);
1028 bsi_insert_after (&bsi, ass_stmt, BSI_NEW_STMT);
1030 mark_new_vars_to_rename (stmt, vars_to_rename);
1033 /* Replaces immediate uses of VAR by REPL. */
1036 replace_immediate_uses (tree var, tree repl)
1043 use_operand_p use_p;
1045 df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
1046 n = num_immediate_uses (df);
1048 for (i = 0; i < n; i++)
1050 stmt = immediate_use (df, i);
1052 if (TREE_CODE (stmt) == PHI_NODE)
1054 for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
1055 if (PHI_ARG_DEF (stmt, j) == var)
1057 SET_PHI_ARG_DEF (stmt, j, repl);
1058 if (TREE_CODE (repl) == SSA_NAME
1059 && PHI_ARG_EDGE (stmt, j)->flags & EDGE_ABNORMAL)
1060 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl) = 1;
1066 get_stmt_operands (stmt);
1067 mark_new_vars = false;
1068 if (is_gimple_reg (SSA_NAME_VAR (var)))
1070 if (TREE_CODE (stmt) == MODIFY_EXPR)
1072 propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 0), repl);
1073 propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 1), repl);
1076 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1077 if (USE_FROM_PTR (use_p) == var)
1079 propagate_value (use_p, repl);
1080 mark_new_vars = POINTER_TYPE_P (TREE_TYPE (repl));
1085 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
1086 SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
1087 if (USE_FROM_PTR (use_p) == var)
1088 propagate_value (use_p, repl);
1091 /* FIXME. If REPL is a constant, we need to fold STMT.
1092 However, fold_stmt wants a pointer to the statement, because
1093 it may happen that it needs to replace the whole statement
1094 with a new expression. Since the current def-use machinery
1095 does not return pointers to statements, we call fold_stmt
1096 with the address of a local temporary, if that call changes
1097 the temporary then we fallback on looking for a proper
1098 pointer to STMT by scanning STMT's basic block.
1100 Note that all this will become unnecessary soon. This
1101 pass is being replaced with a proper copy propagation pass
1102 for 4.1 (dnovillo, 2004-09-17). */
1103 if (TREE_CODE (repl) != SSA_NAME)
1109 block_stmt_iterator si = bsi_for_stmt (stmt);
1110 bsi_replace (&si, tmp, true);
1111 stmt = bsi_stmt (si);
1115 /* If REPL is a pointer, it may have different memory tags associated
1116 with it. For instance, VAR may have had a name tag while REPL
1117 only had a type tag. In these cases, the virtual operands (if
1118 any) in the statement will refer to different symbols which need
1121 mark_new_vars_to_rename (stmt, vars_to_rename);
1127 /* Gets the value VAR is equivalent to according to EQ_TO. */
1130 get_eq_name (tree *eq_to, tree var)
1135 while (TREE_CODE (val) == SSA_NAME)
1137 ver = SSA_NAME_VERSION (val);
1144 while (TREE_CODE (var) == SSA_NAME)
1146 ver = SSA_NAME_VERSION (var);
1157 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1158 its result is redundant to to EQ_TO array. */
1161 check_phi_redundancy (tree phi, tree *eq_to)
1163 tree val = NULL_TREE, def, res = PHI_RESULT (phi), stmt;
1164 unsigned i, ver = SSA_NAME_VERSION (res), n;
1167 /* It is unlikely that such large phi node would be redundant. */
1168 if (PHI_NUM_ARGS (phi) > 16)
1171 for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
1173 def = PHI_ARG_DEF (phi, i);
1175 if (TREE_CODE (def) == SSA_NAME)
1177 def = get_eq_name (eq_to, def);
1183 && !operand_equal_p (val, def, 0))
1189 /* At least one of the arguments should not be equal to the result, or
1190 something strange is happening. */
1193 if (get_eq_name (eq_to, res) == val)
1196 if (!may_propagate_copy (res, val))
1201 df = get_immediate_uses (SSA_NAME_DEF_STMT (res));
1202 n = num_immediate_uses (df);
1204 for (i = 0; i < n; i++)
1206 stmt = immediate_use (df, i);
1208 if (TREE_CODE (stmt) == PHI_NODE)
1209 check_phi_redundancy (stmt, eq_to);
1213 /* Removes redundant phi nodes.
1215 A redundant PHI node is a PHI node where all of its PHI arguments
1216 are the same value, excluding any PHI arguments which are the same
1219 A redundant PHI node is effectively a copy, so we forward copy propagate
1220 which removes all uses of the destination of the PHI node then
1221 finally we delete the redundant PHI node.
1223 Note that if we can not copy propagate the PHI node, then the PHI
1224 will not be removed. Thus we do not have to worry about dependencies
1225 between PHIs and the problems serializing PHIs into copies creates.
1227 The most important effect of this pass is to remove degenerate PHI
1228 nodes created by removing unreachable code. */
1231 kill_redundant_phi_nodes (void)
1234 unsigned i, old_num_ssa_names;
1236 tree phi, var, repl, stmt;
1238 /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1239 replaced. If EQ_TO[VER] is ssa name and it is decided to replace it by
1240 other value, it may be necessary to follow the chain till the final value.
1241 We perform path shortening (replacing the entries of the EQ_TO array with
1242 heads of these chains) whenever we access the field to prevent quadratic
1243 complexity (probably would not occur in practice anyway, but let us play
1245 eq_to = xcalloc (num_ssa_names, sizeof (tree));
1247 /* We have had cases where computing immediate uses takes a
1248 significant amount of compile time. If we run into such
1249 problems here, we may want to only compute immediate uses for
1250 a subset of all the SSA_NAMEs instead of computing it for
1251 all of the SSA_NAMEs. */
1252 compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
1253 old_num_ssa_names = num_ssa_names;
1257 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1259 var = PHI_RESULT (phi);
1260 check_phi_redundancy (phi, eq_to);
1264 /* Now propagate the values. */
1265 for (i = 0; i < old_num_ssa_names; i++)
1270 repl = get_eq_name (eq_to, ssa_name (i));
1271 if (repl != ssa_name (i))
1272 replace_immediate_uses (ssa_name (i), repl);
1275 /* And remove the dead phis. */
1276 for (i = 0; i < old_num_ssa_names; i++)
1281 repl = get_eq_name (eq_to, ssa_name (i));
1282 if (repl != ssa_name (i))
1284 stmt = SSA_NAME_DEF_STMT (ssa_name (i));
1285 remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
1293 struct tree_opt_pass pass_redundant_phi =
1295 "redphi", /* name */
1297 kill_redundant_phi_nodes, /* execute */
1300 0, /* static_pass_number */
1302 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1303 0, /* properties_provided */
1304 0, /* properties_destroyed */
1305 0, /* todo_flags_start */
1306 TODO_dump_func | TODO_rename_vars
1307 | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
1311 /* Emit warnings for uninitialized variables. This is done in two passes.
1313 The first pass notices real uses of SSA names with default definitions.
1314 Such uses are unconditionally uninitialized, and we can be certain that
1315 such a use is a mistake. This pass is run before most optimizations,
1316 so that we catch as many as we can.
1318 The second pass follows PHI nodes to find uses that are potentially
1319 uninitialized. In this case we can't necessarily prove that the use
1320 is really uninitialized. This pass is run after most optimizations,
1321 so that we thread as many jumps and possible, and delete as much dead
1322 code as possible, in order to reduce false positives. We also look
1323 again for plain uninitialized variables, since optimization may have
1324 changed conditionally uninitialized to unconditionally uninitialized. */
1326 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1327 warning text is in MSGID and LOCUS may contain a location or be null. */
1330 warn_uninit (tree t, const char *msgid, location_t *locus)
1332 tree var = SSA_NAME_VAR (t);
1333 tree def = SSA_NAME_DEF_STMT (t);
1335 /* Default uses (indicated by an empty definition statement),
1336 are uninitialized. */
1337 if (!IS_EMPTY_STMT (def))
1340 /* Except for PARMs of course, which are always initialized. */
1341 if (TREE_CODE (var) == PARM_DECL)
1344 /* Hard register variables get their initial value from the ether. */
1345 if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1348 /* TREE_NO_WARNING either means we already warned, or the front end
1349 wishes to suppress the warning. */
1350 if (TREE_NO_WARNING (var))
1354 locus = &DECL_SOURCE_LOCATION (var);
1355 warning (msgid, locus, var);
1356 TREE_NO_WARNING (var) = 1;
1359 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1360 and warn about them. */
1363 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
1365 location_t *locus = data;
1368 /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */
1369 if (TREE_CODE (t) == SSA_NAME)
1371 warn_uninit (t, "%H'%D' is used uninitialized in this function", locus);
1374 else if (IS_TYPE_OR_DECL_P (t))
1380 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1381 and warn about them. */
1384 warn_uninitialized_phi (tree phi)
1386 int i, n = PHI_NUM_ARGS (phi);
1388 /* Don't look at memory tags. */
1389 if (!is_gimple_reg (PHI_RESULT (phi)))
1392 for (i = 0; i < n; ++i)
1394 tree op = PHI_ARG_DEF (phi, i);
1395 if (TREE_CODE (op) == SSA_NAME)
1396 warn_uninit (op, "%H'%D' may be used uninitialized in this function",
1402 execute_early_warn_uninitialized (void)
1404 block_stmt_iterator bsi;
1408 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1409 walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1410 EXPR_LOCUS (bsi_stmt (bsi)), NULL);
1414 execute_late_warn_uninitialized (void)
1419 /* Re-do the plain uninitialized variable check, as optimization may have
1420 straightened control flow. Do this first so that we don't accidentally
1421 get a "may be" warning when we'd have seen an "is" warning later. */
1422 execute_early_warn_uninitialized ();
1425 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1426 warn_uninitialized_phi (phi);
1430 gate_warn_uninitialized (void)
1432 return warn_uninitialized != 0;
1435 struct tree_opt_pass pass_early_warn_uninitialized =
1438 gate_warn_uninitialized, /* gate */
1439 execute_early_warn_uninitialized, /* execute */
1442 0, /* static_pass_number */
1444 PROP_ssa, /* properties_required */
1445 0, /* properties_provided */
1446 0, /* properties_destroyed */
1447 0, /* todo_flags_start */
1448 0, /* todo_flags_finish */
1452 struct tree_opt_pass pass_late_warn_uninitialized =
1455 gate_warn_uninitialized, /* gate */
1456 execute_late_warn_uninitialized, /* execute */
1459 0, /* static_pass_number */
1461 PROP_ssa, /* properties_required */
1462 0, /* properties_provided */
1463 0, /* properties_destroyed */
1464 0, /* todo_flags_start */
1465 0, /* todo_flags_finish */