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, 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 "pointer-set.h"
40 #include "tree-flow.h"
41 #include "tree-gimple.h"
42 #include "tree-inline.h"
46 #include "tree-dump.h"
47 #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, tree ssa_name,
219 tree stmt, bool check_abnormal, bool is_virtual,
220 bitmap names_defined_in_bb)
224 err = verify_ssa_name (ssa_name, is_virtual);
225 TREE_VISITED (ssa_name) = 1;
227 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name))
228 && var_ann (SSA_NAME_VAR (ssa_name))->default_def == ssa_name)
229 ; /* Default definitions have empty statements. Nothing to do. */
232 error ("Missing definition");
235 else if (bb != def_bb
236 && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
238 error ("Definition in block %i does not dominate use in block %i",
239 def_bb->index, bb->index);
242 else if (bb == def_bb
243 && names_defined_in_bb != NULL
244 && !bitmap_bit_p (names_defined_in_bb, SSA_NAME_VERSION (ssa_name)))
246 error ("Definition in block %i follows the use", def_bb->index);
251 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
253 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
259 fprintf (stderr, "for SSA_NAME: ");
260 print_generic_expr (stderr, ssa_name, TDF_VOPS);
261 fprintf (stderr, "in statement:\n");
262 print_generic_stmt (stderr, stmt, TDF_VOPS);
269 /* Return true if any of the arguments for PHI node PHI at block BB is
272 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
273 numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
274 block in that array slot contains the definition of SSA_NAME. */
277 verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)
281 unsigned i, phi_num_args = PHI_NUM_ARGS (phi);
283 if (EDGE_COUNT (bb->preds) != phi_num_args)
285 error ("Incoming edge count does not match number of PHI arguments\n");
290 for (i = 0; i < phi_num_args; i++)
292 tree op = PHI_ARG_DEF (phi, i);
294 e = EDGE_PRED (bb, i);
298 error ("PHI argument is missing for edge %d->%d\n",
305 if (TREE_CODE (op) != SSA_NAME && !is_gimple_min_invariant (op))
307 error ("PHI argument is not SSA_NAME, or invariant");
311 if (TREE_CODE (op) == SSA_NAME)
312 err = verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op,
313 phi, e->flags & EDGE_ABNORMAL,
314 !is_gimple_reg (PHI_RESULT (phi)),
319 error ("Wrong edge %d->%d for PHI argument\n",
320 e->src->index, e->dest->index, bb->index);
326 fprintf (stderr, "PHI argument\n");
327 print_generic_stmt (stderr, op, TDF_VOPS);
335 fprintf (stderr, "for PHI node\n");
336 print_generic_stmt (stderr, phi, TDF_VOPS);
345 verify_flow_insensitive_alias_info (void)
349 bitmap visited = BITMAP_ALLOC (NULL);
351 for (i = 0; i < num_referenced_vars; i++)
355 varray_type may_aliases;
357 var = referenced_var (i);
359 may_aliases = ann->may_aliases;
361 for (j = 0; may_aliases && j < VARRAY_ACTIVE_SIZE (may_aliases); j++)
363 tree alias = VARRAY_TREE (may_aliases, j);
365 bitmap_set_bit (visited, var_ann (alias)->uid);
367 if (!may_be_aliased (alias))
369 error ("Non-addressable variable inside an alias set.");
370 debug_variable (alias);
376 for (i = 0; i < num_referenced_vars; i++)
380 var = referenced_var (i);
383 if (ann->mem_tag_kind == NOT_A_TAG
385 && !bitmap_bit_p (visited, ann->uid))
387 error ("Addressable variable that is an alias tag but is not in any alias set.");
392 BITMAP_FREE (visited);
396 debug_variable (var);
397 internal_error ("verify_flow_insensitive_alias_info failed.");
402 verify_flow_sensitive_alias_info (void)
407 for (i = 1; i < num_ssa_names; i++)
411 struct ptr_info_def *pi;
418 /* We only care for pointers that are actually referenced in the
420 if (!POINTER_TYPE_P (TREE_TYPE (ptr)) || !TREE_VISITED (ptr))
423 /* RESULT_DECL is special. If it's a GIMPLE register, then it
424 is only written-to only once in the return statement.
425 Otherwise, aggregate RESULT_DECLs may be written-to more than
426 once in virtual operands. */
427 var = SSA_NAME_VAR (ptr);
428 if (TREE_CODE (var) == RESULT_DECL
429 && is_gimple_reg (ptr))
432 pi = SSA_NAME_PTR_INFO (ptr);
437 if (pi->is_dereferenced && !pi->name_mem_tag && !ann->type_mem_tag)
439 error ("Dereferenced pointers should have a name or a type tag");
445 && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars)))
447 error ("Pointers with a memory tag, should have points-to sets or point to malloc");
451 if (pi->value_escapes_p
453 && !is_call_clobbered (pi->name_mem_tag))
455 error ("Pointer escapes but its name tag is not call-clobbered.");
463 debug_variable (ptr);
464 internal_error ("verify_flow_sensitive_alias_info failed.");
467 DEF_VEC_MALLOC_P (bitmap);
469 /* Verify that all name tags have different points to sets.
470 This algorithm takes advantage of the fact that every variable with the
471 same name tag must have the same points-to set.
472 So we check a single variable for each name tag, and verify that its
473 points-to set is different from every other points-to set for other name
476 Additionally, given a pointer P_i with name tag NMT and type tag
477 TMT, this function verified the alias set of TMT is a superset of
478 the alias set of NMT. */
481 verify_name_tags (void)
485 bitmap first, second;
486 VEC (tree) *name_tag_reps = NULL;
487 VEC (bitmap) *pt_vars_for_reps = NULL;
488 bitmap type_aliases = BITMAP_ALLOC (NULL);
490 /* First we compute the name tag representatives and their points-to sets. */
491 for (i = 0; i < num_ssa_names; i++)
493 struct ptr_info_def *pi;
494 tree tmt, ptr = ssa_name (i);
496 if (ptr == NULL_TREE)
499 pi = SSA_NAME_PTR_INFO (ptr);
501 if (!TREE_VISITED (ptr)
502 || !POINTER_TYPE_P (TREE_TYPE (ptr))
505 || TREE_VISITED (pi->name_mem_tag))
508 TREE_VISITED (pi->name_mem_tag) = 1;
510 if (pi->pt_vars == NULL)
513 VEC_safe_push (tree, name_tag_reps, ptr);
514 VEC_safe_push (bitmap, pt_vars_for_reps, pi->pt_vars);
516 /* Verify that alias set of PTR's type tag is a superset of the
517 alias set of PTR's name tag. */
518 tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
522 varray_type aliases = var_ann (tmt)->may_aliases;
523 bitmap_clear (type_aliases);
524 for (i = 0; aliases && i < VARRAY_ACTIVE_SIZE (aliases); i++)
526 tree alias = VARRAY_TREE (aliases, i);
527 bitmap_set_bit (type_aliases, var_ann (alias)->uid);
530 /* When grouping, we may have added PTR's type tag into the
531 alias set of PTR's name tag. To prevent a false
532 positive, pretend that TMT is in its own alias set. */
533 bitmap_set_bit (type_aliases, var_ann (tmt)->uid);
535 if (bitmap_equal_p (type_aliases, pi->pt_vars))
538 if (!bitmap_intersect_compl_p (type_aliases, pi->pt_vars))
540 error ("Alias set of a pointer's type tag should be a superset of the corresponding name tag");
541 debug_variable (tmt);
542 debug_variable (pi->name_mem_tag);
548 /* Now compare all the representative bitmaps with all other representative
549 bitmaps, to verify that they are all different. */
550 for (i = 0; VEC_iterate (bitmap, pt_vars_for_reps, i, first); i++)
552 for (j = i + 1; VEC_iterate (bitmap, pt_vars_for_reps, j, second); j++)
554 if (bitmap_equal_p (first, second))
556 error ("Two different pointers with identical points-to sets but different name tags");
557 debug_variable (VEC_index (tree, name_tag_reps, j));
563 /* Lastly, clear out the visited flags. */
564 for (i = 0; i < num_ssa_names; i++)
568 tree ptr = ssa_name (i);
569 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
570 if (!TREE_VISITED (ptr)
571 || !POINTER_TYPE_P (TREE_TYPE (ptr))
573 || !pi->name_mem_tag)
575 TREE_VISITED (pi->name_mem_tag) = 0;
579 VEC_free (bitmap, pt_vars_for_reps);
580 BITMAP_FREE (type_aliases);
584 debug_variable (VEC_index (tree, name_tag_reps, i));
585 internal_error ("verify_name_tags failed");
589 /* Verify the consistency of aliasing information. */
592 verify_alias_info (void)
594 verify_flow_sensitive_alias_info ();
596 verify_flow_insensitive_alias_info ();
600 /* Verify common invariants in the SSA web.
601 TODO: verify the variable annotations. */
608 basic_block *definition_block = xcalloc (num_ssa_names, sizeof (basic_block));
611 enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS];
612 bitmap names_defined_in_bb = BITMAP_ALLOC (NULL);
614 timevar_push (TV_TREE_SSA_VERIFY);
616 /* Keep track of SSA names present in the IL. */
617 for (i = 1; i < num_ssa_names; i++)
619 tree name = ssa_name (i);
623 TREE_VISITED (name) = 0;
625 stmt = SSA_NAME_DEF_STMT (name);
626 if (!IS_EMPTY_STMT (stmt))
628 basic_block bb = bb_for_stmt (stmt);
629 verify_def (bb, definition_block,
630 name, stmt, !is_gimple_reg (name));
636 calculate_dominance_info (CDI_DOMINATORS);
638 /* Now verify all the uses and make sure they agree with the definitions
639 found in the previous pass. */
645 block_stmt_iterator bsi;
647 /* Make sure that all edges have a clear 'aux' field. */
648 FOR_EACH_EDGE (e, ei, bb->preds)
652 error ("AUX pointer initialized for edge %d->%d\n", e->src->index,
658 /* Verify the arguments for every PHI node in the block. */
659 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
661 if (verify_phi_args (phi, bb, definition_block))
663 bitmap_set_bit (names_defined_in_bb,
664 SSA_NAME_VERSION (PHI_RESULT (phi)));
667 /* Now verify all the uses and vuses in every statement of the block. */
668 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
670 tree stmt = bsi_stmt (bsi);
672 get_stmt_operands (stmt);
674 if (stmt_ann (stmt)->makes_aliased_stores
675 && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) == 0)
677 error ("Statement makes aliased stores, but has no V_MAY_DEFS");
678 print_generic_stmt (stderr, stmt, TDF_VOPS);
682 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
684 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
685 op, stmt, false, !is_gimple_reg (op),
686 names_defined_in_bb))
690 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
692 bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
696 bitmap_clear (names_defined_in_bb);
699 /* Finally, verify alias information. */
700 verify_alias_info ();
702 free (definition_block);
703 /* Restore the dominance information to its prior known state, so
704 that we do not perturb the compiler's subsequent behavior. */
705 if (orig_dom_state == DOM_NONE)
706 free_dominance_info (CDI_DOMINATORS);
708 dom_computed[CDI_DOMINATORS] = orig_dom_state;
710 BITMAP_FREE (names_defined_in_bb);
711 timevar_pop (TV_TREE_SSA_VERIFY);
715 internal_error ("verify_ssa failed.");
719 /* Initialize global DFA and SSA structures. */
724 VARRAY_TREE_INIT (referenced_vars, 20, "referenced_vars");
725 call_clobbered_vars = BITMAP_ALLOC (NULL);
726 addressable_vars = BITMAP_ALLOC (NULL);
727 init_ssa_operands ();
730 global_var = NULL_TREE;
731 aliases_computed_p = false;
735 /* Deallocate memory associated with SSA data structures for FNDECL. */
738 delete_tree_ssa (void)
742 block_stmt_iterator bsi;
744 /* 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);
750 ggc_free (stmt->common.ann);
751 stmt->common.ann = NULL;
754 /* Remove annotations from every referenced variable. */
757 for (i = 0; i < num_referenced_vars; i++)
759 tree var = referenced_var (i);
760 ggc_free (var->common.ann);
761 var->common.ann = NULL;
763 referenced_vars = NULL;
768 fini_ssa_operands ();
770 global_var = NULL_TREE;
771 BITMAP_FREE (call_clobbered_vars);
772 call_clobbered_vars = NULL;
773 BITMAP_FREE (addressable_vars);
774 addressable_vars = NULL;
775 modified_noreturn_calls = NULL;
776 aliases_computed_p = false;
780 /* Return true if EXPR is a useless type conversion, otherwise return
784 tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
786 if (inner_type == outer_type)
789 /* Changes in machine mode are never useless conversions. */
790 if (TYPE_MODE (inner_type) != TYPE_MODE (outer_type))
793 /* If the inner and outer types are effectively the same, then
794 strip the type conversion and enter the equivalence into
796 if (lang_hooks.types_compatible_p (inner_type, outer_type))
799 /* If both types are pointers and the outer type is a (void *), then
800 the conversion is not necessary. The opposite is not true since
801 that conversion would result in a loss of information if the
802 equivalence was used. Consider an indirect function call where
803 we need to know the exact type of the function to correctly
804 implement the ABI. */
805 else if (POINTER_TYPE_P (inner_type)
806 && POINTER_TYPE_P (outer_type)
807 && TYPE_REF_CAN_ALIAS_ALL (inner_type)
808 == TYPE_REF_CAN_ALIAS_ALL (outer_type)
809 && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
812 /* Pointers and references are equivalent once we get to GENERIC,
813 so strip conversions that just switch between them. */
814 else if (POINTER_TYPE_P (inner_type)
815 && POINTER_TYPE_P (outer_type)
816 && TYPE_REF_CAN_ALIAS_ALL (inner_type)
817 == TYPE_REF_CAN_ALIAS_ALL (outer_type)
818 && lang_hooks.types_compatible_p (TREE_TYPE (inner_type),
819 TREE_TYPE (outer_type)))
822 /* If both the inner and outer types are integral types, then the
823 conversion is not necessary if they have the same mode and
824 signedness and precision, and both or neither are boolean. Some
825 code assumes an invariant that boolean types stay boolean and do
826 not become 1-bit bit-field types. Note that types with precision
827 not using all bits of the mode (such as bit-field types in C)
828 mean that testing of precision is necessary. */
829 else if (INTEGRAL_TYPE_P (inner_type)
830 && INTEGRAL_TYPE_P (outer_type)
831 && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
832 && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
834 bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE);
835 bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE);
836 if (first_boolean == second_boolean)
840 /* Recurse for complex types. */
841 else if (TREE_CODE (inner_type) == COMPLEX_TYPE
842 && TREE_CODE (outer_type) == COMPLEX_TYPE
843 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
844 TREE_TYPE (inner_type)))
850 /* Return true if EXPR is a useless type conversion, otherwise return
854 tree_ssa_useless_type_conversion (tree expr)
856 /* If we have an assignment that merely uses a NOP_EXPR to change
857 the top of the RHS to the type of the LHS and the type conversion
858 is "safe", then strip away the type conversion so that we can
859 enter LHS = RHS into the const_and_copies table. */
860 if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR
861 || TREE_CODE (expr) == VIEW_CONVERT_EXPR
862 || TREE_CODE (expr) == NON_LVALUE_EXPR)
863 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
864 TREE_TYPE (TREE_OPERAND (expr,
871 /* Returns true if statement STMT may read memory. */
874 stmt_references_memory_p (tree stmt)
878 get_stmt_operands (stmt);
879 ann = stmt_ann (stmt);
881 if (ann->has_volatile_ops)
884 return (NUM_VUSES (VUSE_OPS (ann)) > 0
885 || NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) > 0
886 || NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) > 0);
889 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
890 described in walk_use_def_chains.
892 VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
893 infinite loops. We used to have a bitmap for this to just mark
894 SSA versions we had visited. But non-sparse bitmaps are way too
895 expensive, while sparse bitmaps may cause quadratic behavior.
897 IS_DFS is true if the caller wants to perform a depth-first search
898 when visiting PHI nodes. A DFS will visit each PHI argument and
899 call FN after each one. Otherwise, all the arguments are
900 visited first and then FN is called with each of the visited
901 arguments in a separate pass. */
904 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
905 struct pointer_set_t *visited, bool is_dfs)
909 if (pointer_set_insert (visited, var))
912 def_stmt = SSA_NAME_DEF_STMT (var);
914 if (TREE_CODE (def_stmt) != PHI_NODE)
916 /* If we reached the end of the use-def chain, call FN. */
917 return fn (var, def_stmt, data);
923 /* When doing a breadth-first search, call FN before following the
924 use-def links for each argument. */
926 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
927 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
930 /* Follow use-def links out of each PHI argument. */
931 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
933 tree arg = PHI_ARG_DEF (def_stmt, i);
934 if (TREE_CODE (arg) == SSA_NAME
935 && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
939 /* When doing a depth-first search, call FN after following the
940 use-def links for each argument. */
942 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
943 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
952 /* Walk use-def chains starting at the SSA variable VAR. Call
953 function FN at each reaching definition found. FN takes three
954 arguments: VAR, its defining statement (DEF_STMT) and a generic
955 pointer to whatever state information that FN may want to maintain
956 (DATA). FN is able to stop the walk by returning true, otherwise
957 in order to continue the walk, FN should return false.
959 Note, that if DEF_STMT is a PHI node, the semantics are slightly
960 different. The first argument to FN is no longer the original
961 variable VAR, but the PHI argument currently being examined. If FN
962 wants to get at VAR, it should call PHI_RESULT (PHI).
964 If IS_DFS is true, this function will:
966 1- walk the use-def chains for all the PHI arguments, and,
967 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
969 If IS_DFS is false, the two steps above are done in reverse order
970 (i.e., a breadth-first search). */
974 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
979 gcc_assert (TREE_CODE (var) == SSA_NAME);
981 def_stmt = SSA_NAME_DEF_STMT (var);
983 /* We only need to recurse if the reaching definition comes from a PHI
985 if (TREE_CODE (def_stmt) != PHI_NODE)
986 (*fn) (var, def_stmt, data);
989 struct pointer_set_t *visited = pointer_set_create ();
990 walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
991 pointer_set_destroy (visited);
996 /* Replaces VAR with REPL in memory reference expression *X in
1000 propagate_into_addr (tree stmt, tree var, tree *x, tree repl)
1002 tree new_var, ass_stmt, addr_var;
1004 block_stmt_iterator bsi;
1006 /* There is nothing special to handle in the other cases. */
1007 if (TREE_CODE (repl) != ADDR_EXPR)
1009 addr_var = TREE_OPERAND (repl, 0);
1011 while (handled_component_p (*x)
1012 || TREE_CODE (*x) == REALPART_EXPR
1013 || TREE_CODE (*x) == IMAGPART_EXPR)
1014 x = &TREE_OPERAND (*x, 0);
1016 if (TREE_CODE (*x) != INDIRECT_REF
1017 || TREE_OPERAND (*x, 0) != var)
1020 if (TREE_TYPE (*x) == TREE_TYPE (addr_var))
1023 mark_new_vars_to_rename (stmt, vars_to_rename);
1028 /* Frontends sometimes produce expressions like *&a instead of a[0].
1029 Create a temporary variable to handle this case. */
1030 ass_stmt = build2 (MODIFY_EXPR, void_type_node, NULL_TREE, repl);
1031 new_var = duplicate_ssa_name (var, ass_stmt);
1032 TREE_OPERAND (*x, 0) = new_var;
1033 TREE_OPERAND (ass_stmt, 0) = new_var;
1035 bb = bb_for_stmt (stmt);
1036 tree_block_label (bb);
1037 bsi = bsi_after_labels (bb);
1038 bsi_insert_after (&bsi, ass_stmt, BSI_NEW_STMT);
1040 mark_new_vars_to_rename (stmt, vars_to_rename);
1043 /* Replaces immediate uses of VAR by REPL. */
1046 replace_immediate_uses (tree var, tree repl)
1053 use_operand_p use_p;
1055 df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
1056 n = num_immediate_uses (df);
1058 for (i = 0; i < n; i++)
1060 stmt = immediate_use (df, i);
1062 if (TREE_CODE (stmt) == PHI_NODE)
1064 for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
1065 if (PHI_ARG_DEF (stmt, j) == var)
1067 SET_PHI_ARG_DEF (stmt, j, repl);
1068 if (TREE_CODE (repl) == SSA_NAME
1069 && PHI_ARG_EDGE (stmt, j)->flags & EDGE_ABNORMAL)
1070 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl) = 1;
1076 get_stmt_operands (stmt);
1077 mark_new_vars = false;
1078 if (is_gimple_reg (SSA_NAME_VAR (var)))
1080 if (TREE_CODE (stmt) == MODIFY_EXPR)
1082 propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 0), repl);
1083 propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 1), repl);
1086 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1087 if (USE_FROM_PTR (use_p) == var)
1089 propagate_value (use_p, repl);
1090 mark_new_vars = POINTER_TYPE_P (TREE_TYPE (repl));
1095 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
1096 SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
1097 if (USE_FROM_PTR (use_p) == var)
1098 propagate_value (use_p, repl);
1101 /* FIXME. If REPL is a constant, we need to fold STMT.
1102 However, fold_stmt wants a pointer to the statement, because
1103 it may happen that it needs to replace the whole statement
1104 with a new expression. Since the current def-use machinery
1105 does not return pointers to statements, we call fold_stmt
1106 with the address of a local temporary, if that call changes
1107 the temporary then we fallback on looking for a proper
1108 pointer to STMT by scanning STMT's basic block.
1110 Note that all this will become unnecessary soon. This
1111 pass is being replaced with a proper copy propagation pass
1112 for 4.1 (dnovillo, 2004-09-17). */
1113 if (TREE_CODE (repl) != SSA_NAME)
1117 mark_new_vars = true;
1120 block_stmt_iterator si = bsi_for_stmt (stmt);
1121 mark_new_vars_to_rename (tmp, vars_to_rename);
1122 redirect_immediate_uses (stmt, tmp);
1123 bsi_replace (&si, tmp, true);
1124 stmt = bsi_stmt (si);
1128 /* If REPL is a pointer, it may have different memory tags associated
1129 with it. For instance, VAR may have had a name tag while REPL
1130 only had a type tag. In these cases, the virtual operands (if
1131 any) in the statement will refer to different symbols which need
1134 mark_new_vars_to_rename (stmt, vars_to_rename);
1140 /* Gets the value VAR is equivalent to according to EQ_TO. */
1143 get_eq_name (tree *eq_to, tree var)
1148 while (TREE_CODE (val) == SSA_NAME)
1150 ver = SSA_NAME_VERSION (val);
1157 while (TREE_CODE (var) == SSA_NAME)
1159 ver = SSA_NAME_VERSION (var);
1170 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1171 its result is redundant to to EQ_TO array. */
1174 check_phi_redundancy (tree phi, tree *eq_to)
1176 tree val = NULL_TREE, def, res = PHI_RESULT (phi), stmt;
1177 unsigned i, ver = SSA_NAME_VERSION (res), n;
1180 /* It is unlikely that such large phi node would be redundant. */
1181 if (PHI_NUM_ARGS (phi) > 16)
1184 for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
1186 def = PHI_ARG_DEF (phi, i);
1188 if (TREE_CODE (def) == SSA_NAME)
1190 def = get_eq_name (eq_to, def);
1196 && !operand_equal_for_phi_arg_p (val, def))
1202 /* At least one of the arguments should not be equal to the result, or
1203 something strange is happening. */
1206 if (get_eq_name (eq_to, res) == val)
1209 if (!may_propagate_copy (res, val))
1214 df = get_immediate_uses (SSA_NAME_DEF_STMT (res));
1215 n = num_immediate_uses (df);
1217 for (i = 0; i < n; i++)
1219 stmt = immediate_use (df, i);
1221 if (TREE_CODE (stmt) == PHI_NODE)
1222 check_phi_redundancy (stmt, eq_to);
1226 /* Removes redundant phi nodes.
1228 A redundant PHI node is a PHI node where all of its PHI arguments
1229 are the same value, excluding any PHI arguments which are the same
1232 A redundant PHI node is effectively a copy, so we forward copy propagate
1233 which removes all uses of the destination of the PHI node then
1234 finally we delete the redundant PHI node.
1236 Note that if we can not copy propagate the PHI node, then the PHI
1237 will not be removed. Thus we do not have to worry about dependencies
1238 between PHIs and the problems serializing PHIs into copies creates.
1240 The most important effect of this pass is to remove degenerate PHI
1241 nodes created by removing unreachable code. */
1244 kill_redundant_phi_nodes (void)
1247 unsigned i, old_num_ssa_names;
1249 tree phi, repl, stmt;
1251 /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1252 replaced. If EQ_TO[VER] is ssa name and it is decided to replace it by
1253 other value, it may be necessary to follow the chain till the final value.
1254 We perform path shortening (replacing the entries of the EQ_TO array with
1255 heads of these chains) whenever we access the field to prevent quadratic
1256 complexity (probably would not occur in practice anyway, but let us play
1258 eq_to = xcalloc (num_ssa_names, sizeof (tree));
1260 /* We have had cases where computing immediate uses takes a
1261 significant amount of compile time. If we run into such
1262 problems here, we may want to only compute immediate uses for
1263 a subset of all the SSA_NAMEs instead of computing it for
1264 all of the SSA_NAMEs. */
1265 compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
1266 old_num_ssa_names = num_ssa_names;
1270 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1271 check_phi_redundancy (phi, eq_to);
1274 /* Now propagate the values. */
1275 for (i = 0; i < old_num_ssa_names; i++)
1280 repl = get_eq_name (eq_to, ssa_name (i));
1281 if (repl != ssa_name (i))
1282 replace_immediate_uses (ssa_name (i), repl);
1285 /* And remove the dead phis. */
1286 for (i = 0; i < old_num_ssa_names; i++)
1291 repl = get_eq_name (eq_to, ssa_name (i));
1292 if (repl != ssa_name (i))
1294 stmt = SSA_NAME_DEF_STMT (ssa_name (i));
1295 remove_phi_node (stmt, NULL_TREE);
1303 struct tree_opt_pass pass_redundant_phi =
1305 "redphi", /* name */
1307 kill_redundant_phi_nodes, /* execute */
1310 0, /* static_pass_number */
1311 TV_TREE_REDPHI, /* tv_id */
1312 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1313 0, /* properties_provided */
1314 0, /* properties_destroyed */
1315 0, /* todo_flags_start */
1316 TODO_dump_func | TODO_rename_vars
1317 | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
1321 /* Emit warnings for uninitialized variables. This is done in two passes.
1323 The first pass notices real uses of SSA names with default definitions.
1324 Such uses are unconditionally uninitialized, and we can be certain that
1325 such a use is a mistake. This pass is run before most optimizations,
1326 so that we catch as many as we can.
1328 The second pass follows PHI nodes to find uses that are potentially
1329 uninitialized. In this case we can't necessarily prove that the use
1330 is really uninitialized. This pass is run after most optimizations,
1331 so that we thread as many jumps and possible, and delete as much dead
1332 code as possible, in order to reduce false positives. We also look
1333 again for plain uninitialized variables, since optimization may have
1334 changed conditionally uninitialized to unconditionally uninitialized. */
1336 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1337 warning text is in MSGID and LOCUS may contain a location or be null. */
1340 warn_uninit (tree t, const char *msgid, location_t *locus)
1342 tree var = SSA_NAME_VAR (t);
1343 tree def = SSA_NAME_DEF_STMT (t);
1345 /* Default uses (indicated by an empty definition statement),
1346 are uninitialized. */
1347 if (!IS_EMPTY_STMT (def))
1350 /* Except for PARMs of course, which are always initialized. */
1351 if (TREE_CODE (var) == PARM_DECL)
1354 /* Hard register variables get their initial value from the ether. */
1355 if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1358 /* TREE_NO_WARNING either means we already warned, or the front end
1359 wishes to suppress the warning. */
1360 if (TREE_NO_WARNING (var))
1364 locus = &DECL_SOURCE_LOCATION (var);
1365 warning (msgid, locus, var);
1366 TREE_NO_WARNING (var) = 1;
1369 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1370 and warn about them. */
1373 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
1375 location_t *locus = data;
1378 /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */
1379 if (TREE_CODE (t) == SSA_NAME)
1381 warn_uninit (t, "%H%qD is used uninitialized in this function", locus);
1384 else if (IS_TYPE_OR_DECL_P (t))
1390 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1391 and warn about them. */
1394 warn_uninitialized_phi (tree phi)
1396 int i, n = PHI_NUM_ARGS (phi);
1398 /* Don't look at memory tags. */
1399 if (!is_gimple_reg (PHI_RESULT (phi)))
1402 for (i = 0; i < n; ++i)
1404 tree op = PHI_ARG_DEF (phi, i);
1405 if (TREE_CODE (op) == SSA_NAME)
1406 warn_uninit (op, "%H%qD may be used uninitialized in this function",
1412 execute_early_warn_uninitialized (void)
1414 block_stmt_iterator bsi;
1418 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1419 walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1420 EXPR_LOCUS (bsi_stmt (bsi)), NULL);
1424 execute_late_warn_uninitialized (void)
1429 /* Re-do the plain uninitialized variable check, as optimization may have
1430 straightened control flow. Do this first so that we don't accidentally
1431 get a "may be" warning when we'd have seen an "is" warning later. */
1432 execute_early_warn_uninitialized ();
1435 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1436 warn_uninitialized_phi (phi);
1440 gate_warn_uninitialized (void)
1442 return warn_uninitialized != 0;
1445 struct tree_opt_pass pass_early_warn_uninitialized =
1448 gate_warn_uninitialized, /* gate */
1449 execute_early_warn_uninitialized, /* execute */
1452 0, /* static_pass_number */
1454 PROP_ssa, /* properties_required */
1455 0, /* properties_provided */
1456 0, /* properties_destroyed */
1457 0, /* todo_flags_start */
1458 0, /* todo_flags_finish */
1462 struct tree_opt_pass pass_late_warn_uninitialized =
1465 gate_warn_uninitialized, /* gate */
1466 execute_late_warn_uninitialized, /* execute */
1469 0, /* static_pass_number */
1471 PROP_ssa, /* properties_required */
1472 0, /* properties_provided */
1473 0, /* properties_destroyed */
1474 0, /* todo_flags_start */
1475 0, /* todo_flags_finish */