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 "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"
50 /* Remove edge E and remove the corresponding arguments from the PHI nodes
51 in E's destination block. */
54 ssa_remove_edge (edge e)
58 /* Remove the appropriate PHI arguments in E's destination block. */
59 for (phi = phi_nodes (e->dest); phi; phi = next)
61 next = PHI_CHAIN (phi);
62 remove_phi_arg (phi, e->src);
68 /* Remove the corresponding arguments from the PHI nodes in E's
69 destination block and redirect it to DEST. Return redirected edge.
70 The list of removed arguments is stored in PENDING_STMT (e). */
73 ssa_redirect_edge (edge e, basic_block dest)
76 tree list = NULL, *last = &list;
80 /* Remove the appropriate PHI arguments in E's destination block. */
81 for (phi = phi_nodes (e->dest); phi; phi = next)
83 next = PHI_CHAIN (phi);
85 i = phi_arg_from_edge (phi, e);
89 src = PHI_ARG_DEF (phi, i);
90 dst = PHI_RESULT (phi);
91 node = build_tree_list (dst, src);
93 last = &TREE_CHAIN (node);
95 remove_phi_arg_num (phi, i);
98 e = redirect_edge_succ_nodup (e, dest);
99 PENDING_STMT (e) = list;
104 /* Add PHI arguments queued in PENDINT_STMT list on edge E to edge
108 flush_pending_stmts (edge e)
112 if (!PENDING_STMT (e))
115 for (phi = phi_nodes (e->dest), arg = PENDING_STMT (e);
117 phi = PHI_CHAIN (phi), arg = TREE_CHAIN (arg))
119 tree def = TREE_VALUE (arg);
120 add_phi_arg (&phi, def, e);
123 PENDING_STMT (e) = NULL;
126 /* Return true if SSA_NAME is malformed and mark it visited.
128 IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
132 verify_ssa_name (tree ssa_name, bool is_virtual)
134 TREE_VISITED (ssa_name) = 1;
136 if (TREE_CODE (ssa_name) != SSA_NAME)
138 error ("Expected an SSA_NAME object");
142 if (TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name)))
144 error ("Type mismatch between an SSA_NAME and its symbol.");
148 if (SSA_NAME_IN_FREE_LIST (ssa_name))
150 error ("Found an SSA_NAME that had been released into the free pool");
154 if (is_virtual && is_gimple_reg (ssa_name))
156 error ("Found a virtual definition for a GIMPLE register");
160 if (!is_virtual && !is_gimple_reg (ssa_name))
162 error ("Found a real definition for a non-register");
170 /* Return true if the definition of SSA_NAME at block BB is malformed.
172 STMT is the statement where SSA_NAME is created.
174 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
175 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
176 it means that the block in that array slot contains the
177 definition of SSA_NAME.
179 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
183 verify_def (basic_block bb, basic_block *definition_block, tree ssa_name,
184 tree stmt, bool is_virtual)
186 if (verify_ssa_name (ssa_name, is_virtual))
189 if (definition_block[SSA_NAME_VERSION (ssa_name)])
191 error ("SSA_NAME created in two different blocks %i and %i",
192 definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index);
196 definition_block[SSA_NAME_VERSION (ssa_name)] = bb;
198 if (SSA_NAME_DEF_STMT (ssa_name) != stmt)
200 error ("SSA_NAME_DEF_STMT is wrong");
201 fprintf (stderr, "Expected definition statement:\n");
202 print_generic_stmt (stderr, SSA_NAME_DEF_STMT (ssa_name), TDF_VOPS);
203 fprintf (stderr, "\nActual definition statement:\n");
204 print_generic_stmt (stderr, stmt, TDF_VOPS);
211 fprintf (stderr, "while verifying SSA_NAME ");
212 print_generic_expr (stderr, ssa_name, 0);
213 fprintf (stderr, " in statement\n");
214 print_generic_stmt (stderr, stmt, TDF_VOPS);
220 /* Return true if the use of SSA_NAME at statement STMT in block BB is
223 DEF_BB is the block where SSA_NAME was found to be created.
225 IDOM contains immediate dominator information for the flowgraph.
227 CHECK_ABNORMAL is true if the caller wants to check whether this use
228 is flowing through an abnormal edge (only used when checking PHI
231 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
234 If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
235 that are defined before STMT in basic block BB. */
238 verify_use (basic_block bb, basic_block def_bb, tree ssa_name,
239 tree stmt, bool check_abnormal, bool is_virtual,
240 bitmap names_defined_in_bb)
244 err = verify_ssa_name (ssa_name, is_virtual);
246 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name))
247 && var_ann (SSA_NAME_VAR (ssa_name))->default_def == ssa_name)
248 ; /* Default definitions have empty statements. Nothing to do. */
251 error ("Missing definition");
254 else if (bb != def_bb
255 && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
257 error ("Definition in block %i does not dominate use in block %i",
258 def_bb->index, bb->index);
261 else if (bb == def_bb
262 && names_defined_in_bb != NULL
263 && !bitmap_bit_p (names_defined_in_bb, SSA_NAME_VERSION (ssa_name)))
265 error ("Definition in block %i follows the use", def_bb->index);
270 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
272 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
278 fprintf (stderr, "for SSA_NAME: ");
279 print_generic_expr (stderr, ssa_name, TDF_VOPS);
280 fprintf (stderr, "in statement:\n");
281 print_generic_stmt (stderr, stmt, TDF_VOPS);
288 /* Return true if any of the arguments for PHI node PHI at block BB is
291 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
292 numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
293 block in that array slot contains the definition of SSA_NAME. */
296 verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)
300 unsigned i, phi_num_args = PHI_NUM_ARGS (phi);
303 if (EDGE_COUNT (bb->preds) != phi_num_args)
305 error ("Incoming edge count does not match number of PHI arguments\n");
310 /* Mark all the incoming edges. */
311 FOR_EACH_EDGE (e, ei, bb->preds)
314 for (i = 0; i < phi_num_args; i++)
316 tree op = PHI_ARG_DEF (phi, i);
318 if (TREE_CODE (op) != SSA_NAME && !is_gimple_min_invariant (op))
320 error ("PHI argument is not SSA_NAME, or invariant");
324 e = PHI_ARG_EDGE (phi, i);
326 if (TREE_CODE (op) == SSA_NAME)
327 err = verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op,
328 phi, e->flags & EDGE_ABNORMAL,
329 !is_gimple_reg (PHI_RESULT (phi)),
334 error ("Wrong edge %d->%d for PHI argument\n",
335 e->src->index, e->dest->index, bb->index);
339 if (e->aux == (void *) 0)
341 error ("PHI argument flowing through dead or duplicated edge %d->%d\n",
342 e->src->index, e->dest->index);
348 fprintf (stderr, "PHI argument\n");
349 print_generic_stmt (stderr, op, TDF_VOPS);
359 fprintf (stderr, "for PHI node\n");
360 print_generic_stmt (stderr, phi, TDF_VOPS);
369 verify_flow_insensitive_alias_info (void)
373 bitmap visited = BITMAP_XMALLOC ();
375 for (i = 0; i < num_referenced_vars; i++)
379 varray_type may_aliases;
381 var = referenced_var (i);
383 may_aliases = ann->may_aliases;
385 for (j = 0; may_aliases && j < VARRAY_ACTIVE_SIZE (may_aliases); j++)
387 tree alias = VARRAY_TREE (may_aliases, j);
389 bitmap_set_bit (visited, var_ann (alias)->uid);
391 if (!may_be_aliased (alias))
393 error ("Non-addressable variable inside an alias set.");
394 debug_variable (alias);
400 for (i = 0; i < num_referenced_vars; i++)
404 var = referenced_var (i);
407 if (ann->mem_tag_kind == NOT_A_TAG
409 && !bitmap_bit_p (visited, ann->uid))
411 error ("Addressable variable that is an alias tag but is not in any alias set.");
416 BITMAP_XFREE (visited);
420 debug_variable (var);
421 internal_error ("verify_flow_insensitive_alias_info failed.");
426 verify_flow_sensitive_alias_info (void)
431 for (i = 1; i < num_ssa_names; i++)
434 struct ptr_info_def *pi;
439 ann = var_ann (SSA_NAME_VAR (ptr));
440 pi = SSA_NAME_PTR_INFO (ptr);
442 /* We only care for pointers that are actually referenced in the
444 if (!TREE_VISITED (ptr) || !POINTER_TYPE_P (TREE_TYPE (ptr)))
447 /* RESULT_DECL is special. If it's a GIMPLE register, then it
448 is only written-to only once in the return statement.
449 Otherwise, aggregate RESULT_DECLs may be written-to more than
450 once in virtual operands. */
451 if (TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL
452 && is_gimple_reg (ptr))
458 if (pi->is_dereferenced && !pi->name_mem_tag && !ann->type_mem_tag)
460 error ("Dereferenced pointers should have a name or a type tag");
466 && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars)))
468 error ("Pointers with a memory tag, should have points-to sets or point to malloc");
472 if (pi->value_escapes_p
474 && !is_call_clobbered (pi->name_mem_tag))
476 error ("Pointer escapes but its name tag is not call-clobbered.");
484 debug_variable (ptr);
485 internal_error ("verify_flow_sensitive_alias_info failed.");
488 DEF_VEC_MALLOC_P (bitmap);
490 /* Verify that all name tags have different points to sets.
491 This algorithm takes advantage of the fact that every variable with the
492 same name tag must have the same points-to set.
493 So we check a single variable for each name tag, and verify that its
494 points-to set is different from every other points-to set for other name
498 verify_name_tags (void)
502 bitmap first, second;
503 VEC (tree) *name_tag_reps = NULL;
504 VEC (bitmap) *pt_vars_for_reps = NULL;
506 /* First we compute the name tag representatives and their points-to sets. */
507 for (i = 0; i < num_ssa_names; i++)
511 tree ptr = ssa_name (i);
512 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
513 if (!TREE_VISITED (ptr)
514 || !POINTER_TYPE_P (TREE_TYPE (ptr))
517 || TREE_VISITED (pi->name_mem_tag))
519 TREE_VISITED (pi->name_mem_tag) = 1;
520 if (pi->pt_vars != NULL)
522 VEC_safe_push (tree, name_tag_reps, ptr);
523 VEC_safe_push (bitmap, pt_vars_for_reps, pi->pt_vars);
528 /* Now compare all the representative bitmaps with all other representative
529 bitmaps, to verify that they are all different. */
530 for (i = 0; VEC_iterate (bitmap, pt_vars_for_reps, i, first); i++)
532 for (j = i + 1; VEC_iterate (bitmap, pt_vars_for_reps, j, second); j++)
534 if (bitmap_equal_p (first, second))
536 error ("Two different pointers with identical points-to sets but different name tags");
537 debug_variable (VEC_index (tree, name_tag_reps, j));
543 /* Lastly, clear out the visited flags. */
544 for (i = 0; i < num_ssa_names; i++)
548 tree ptr = ssa_name (i);
549 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
550 if (!TREE_VISITED (ptr)
551 || !POINTER_TYPE_P (TREE_TYPE (ptr))
553 || !pi->name_mem_tag)
555 TREE_VISITED (pi->name_mem_tag) = 0;
558 VEC_free (bitmap, pt_vars_for_reps);
562 debug_variable (VEC_index (tree, name_tag_reps, i));
563 internal_error ("verify_name_tags failed");
565 /* Verify the consistency of aliasing information. */
568 verify_alias_info (void)
570 verify_flow_sensitive_alias_info ();
572 verify_flow_insensitive_alias_info ();
576 /* Verify common invariants in the SSA web.
577 TODO: verify the variable annotations. */
584 basic_block *definition_block = xcalloc (num_ssa_names, sizeof (basic_block));
587 enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS];
588 bitmap names_defined_in_bb = BITMAP_XMALLOC ();
590 timevar_push (TV_TREE_SSA_VERIFY);
592 /* Keep track of SSA names present in the IL. */
593 for (i = 1; i < num_ssa_names; i++)
595 tree name = ssa_name (i);
599 TREE_VISITED (name) = 0;
601 stmt = SSA_NAME_DEF_STMT (name);
602 if (!IS_EMPTY_STMT (stmt))
604 basic_block bb = bb_for_stmt (stmt);
605 verify_def (bb, definition_block,
606 name, stmt, !is_gimple_reg (name));
612 calculate_dominance_info (CDI_DOMINATORS);
614 /* Now verify all the uses and make sure they agree with the definitions
615 found in the previous pass. */
621 block_stmt_iterator bsi;
623 /* Make sure that all edges have a clear 'aux' field. */
624 FOR_EACH_EDGE (e, ei, bb->preds)
628 error ("AUX pointer initialized for edge %d->%d\n", e->src->index,
634 /* Verify the arguments for every PHI node in the block. */
635 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
637 if (verify_phi_args (phi, bb, definition_block))
639 bitmap_set_bit (names_defined_in_bb,
640 SSA_NAME_VERSION (PHI_RESULT (phi)));
643 /* Now verify all the uses and vuses in every statement of the block. */
644 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
646 tree stmt = bsi_stmt (bsi);
648 get_stmt_operands (stmt);
650 if (stmt_ann (stmt)->makes_aliased_stores
651 && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) == 0)
653 error ("Statement makes aliased stores, but has no V_MAY_DEFS");
654 print_generic_stmt (stderr, stmt, TDF_VOPS);
658 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
660 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
661 op, stmt, false, !is_gimple_reg (op),
662 names_defined_in_bb))
666 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
668 bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
672 bitmap_clear (names_defined_in_bb);
675 /* Finally, verify alias information. */
676 verify_alias_info ();
678 free (definition_block);
679 /* Restore the dominance information to its prior known state, so
680 that we do not perturb the compiler's subsequent behavior. */
681 if (orig_dom_state == DOM_NONE)
682 free_dominance_info (CDI_DOMINATORS);
684 dom_computed[CDI_DOMINATORS] = orig_dom_state;
686 BITMAP_XFREE (names_defined_in_bb);
687 timevar_pop (TV_TREE_SSA_VERIFY);
691 internal_error ("verify_ssa failed.");
695 /* Initialize global DFA and SSA structures. */
700 VARRAY_TREE_INIT (referenced_vars, 20, "referenced_vars");
701 call_clobbered_vars = BITMAP_XMALLOC ();
702 addressable_vars = BITMAP_XMALLOC ();
703 init_ssa_operands ();
706 global_var = NULL_TREE;
710 /* Deallocate memory associated with SSA data structures for FNDECL. */
713 delete_tree_ssa (void)
717 block_stmt_iterator bsi;
719 /* Remove annotations from every tree in the function. */
721 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
723 tree stmt = bsi_stmt (bsi);
725 ggc_free (stmt->common.ann);
726 stmt->common.ann = NULL;
729 /* Remove annotations from every referenced variable. */
732 for (i = 0; i < num_referenced_vars; i++)
734 tree var = referenced_var (i);
735 ggc_free (var->common.ann);
736 var->common.ann = NULL;
738 referenced_vars = NULL;
743 fini_ssa_operands ();
745 global_var = NULL_TREE;
746 BITMAP_XFREE (call_clobbered_vars);
747 call_clobbered_vars = NULL;
748 BITMAP_XFREE (addressable_vars);
749 addressable_vars = NULL;
753 /* Return true if EXPR is a useless type conversion, otherwise return
757 tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
759 /* If the inner and outer types are effectively the same, then
760 strip the type conversion and enter the equivalence into
762 if (inner_type == outer_type
763 || (lang_hooks.types_compatible_p (inner_type, outer_type)))
766 /* If both types are pointers and the outer type is a (void *), then
767 the conversion is not necessary. The opposite is not true since
768 that conversion would result in a loss of information if the
769 equivalence was used. Consider an indirect function call where
770 we need to know the exact type of the function to correctly
771 implement the ABI. */
772 else if (POINTER_TYPE_P (inner_type)
773 && POINTER_TYPE_P (outer_type)
774 && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
775 && TYPE_REF_CAN_ALIAS_ALL (inner_type)
776 == TYPE_REF_CAN_ALIAS_ALL (outer_type)
777 && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
780 /* Pointers and references are equivalent once we get to GENERIC,
781 so strip conversions that just switch between them. */
782 else if (POINTER_TYPE_P (inner_type)
783 && POINTER_TYPE_P (outer_type)
784 && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
785 && TYPE_REF_CAN_ALIAS_ALL (inner_type)
786 == TYPE_REF_CAN_ALIAS_ALL (outer_type)
787 && lang_hooks.types_compatible_p (TREE_TYPE (inner_type),
788 TREE_TYPE (outer_type)))
791 /* If both the inner and outer types are integral types, then the
792 conversion is not necessary if they have the same mode and
793 signedness and precision, and both or neither are boolean. Some
794 code assumes an invariant that boolean types stay boolean and do
795 not become 1-bit bit-field types. Note that types with precision
796 not using all bits of the mode (such as bit-field types in C)
797 mean that testing of precision is necessary. */
798 else if (INTEGRAL_TYPE_P (inner_type)
799 && INTEGRAL_TYPE_P (outer_type)
800 && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
801 && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
802 && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
804 bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE);
805 bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE);
806 if (first_boolean == second_boolean)
810 /* Recurse for complex types. */
811 else if (TREE_CODE (inner_type) == COMPLEX_TYPE
812 && TREE_CODE (outer_type) == COMPLEX_TYPE
813 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
814 TREE_TYPE (inner_type)))
820 /* Return true if EXPR is a useless type conversion, otherwise return
824 tree_ssa_useless_type_conversion (tree expr)
826 /* If we have an assignment that merely uses a NOP_EXPR to change
827 the top of the RHS to the type of the LHS and the type conversion
828 is "safe", then strip away the type conversion so that we can
829 enter LHS = RHS into the const_and_copies table. */
830 if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR
831 || TREE_CODE (expr) == VIEW_CONVERT_EXPR
832 || TREE_CODE (expr) == NON_LVALUE_EXPR)
833 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
834 TREE_TYPE (TREE_OPERAND (expr,
841 /* Returns true if statement STMT may read memory. */
844 stmt_references_memory_p (tree stmt)
848 get_stmt_operands (stmt);
849 ann = stmt_ann (stmt);
851 if (ann->has_volatile_ops)
854 return (NUM_VUSES (VUSE_OPS (ann)) > 0
855 || NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) > 0
856 || NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) > 0);
859 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
860 described in walk_use_def_chains.
862 VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
863 infinite loops. We used to have a bitmap for this to just mark
864 SSA versions we had visited. But non-sparse bitmaps are way too
865 expensive, while sparse bitmaps may cause quadratic behavior.
867 IS_DFS is true if the caller wants to perform a depth-first search
868 when visiting PHI nodes. A DFS will visit each PHI argument and
869 call FN after each one. Otherwise, all the arguments are
870 visited first and then FN is called with each of the visited
871 arguments in a separate pass. */
874 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
875 struct pointer_set_t *visited, bool is_dfs)
879 if (pointer_set_insert (visited, var))
882 def_stmt = SSA_NAME_DEF_STMT (var);
884 if (TREE_CODE (def_stmt) != PHI_NODE)
886 /* If we reached the end of the use-def chain, call FN. */
887 return fn (var, def_stmt, data);
893 /* When doing a breadth-first search, call FN before following the
894 use-def links for each argument. */
896 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
897 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
900 /* Follow use-def links out of each PHI argument. */
901 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
903 tree arg = PHI_ARG_DEF (def_stmt, i);
904 if (TREE_CODE (arg) == SSA_NAME
905 && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
909 /* When doing a depth-first search, call FN after following the
910 use-def links for each argument. */
912 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
913 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
922 /* Walk use-def chains starting at the SSA variable VAR. Call
923 function FN at each reaching definition found. FN takes three
924 arguments: VAR, its defining statement (DEF_STMT) and a generic
925 pointer to whatever state information that FN may want to maintain
926 (DATA). FN is able to stop the walk by returning true, otherwise
927 in order to continue the walk, FN should return false.
929 Note, that if DEF_STMT is a PHI node, the semantics are slightly
930 different. The first argument to FN is no longer the original
931 variable VAR, but the PHI argument currently being examined. If FN
932 wants to get at VAR, it should call PHI_RESULT (PHI).
934 If IS_DFS is true, this function will:
936 1- walk the use-def chains for all the PHI arguments, and,
937 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
939 If IS_DFS is false, the two steps above are done in reverse order
940 (i.e., a breadth-first search). */
944 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
949 gcc_assert (TREE_CODE (var) == SSA_NAME);
951 def_stmt = SSA_NAME_DEF_STMT (var);
953 /* We only need to recurse if the reaching definition comes from a PHI
955 if (TREE_CODE (def_stmt) != PHI_NODE)
956 (*fn) (var, def_stmt, data);
959 struct pointer_set_t *visited = pointer_set_create ();
960 walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
961 pointer_set_destroy (visited);
966 /* Replaces VAR with REPL in memory reference expression *X in
970 propagate_into_addr (tree stmt, tree var, tree *x, tree repl)
972 tree new_var, ass_stmt, addr_var;
974 block_stmt_iterator bsi;
976 /* There is nothing special to handle in the other cases. */
977 if (TREE_CODE (repl) != ADDR_EXPR)
979 addr_var = TREE_OPERAND (repl, 0);
981 while (handled_component_p (*x)
982 || TREE_CODE (*x) == REALPART_EXPR
983 || TREE_CODE (*x) == IMAGPART_EXPR)
984 x = &TREE_OPERAND (*x, 0);
986 if (TREE_CODE (*x) != INDIRECT_REF
987 || TREE_OPERAND (*x, 0) != var)
990 if (TREE_TYPE (*x) == TREE_TYPE (addr_var))
993 mark_new_vars_to_rename (stmt, vars_to_rename);
998 /* Frontends sometimes produce expressions like *&a instead of a[0].
999 Create a temporary variable to handle this case. */
1000 ass_stmt = build2 (MODIFY_EXPR, void_type_node, NULL_TREE, repl);
1001 new_var = duplicate_ssa_name (var, ass_stmt);
1002 TREE_OPERAND (*x, 0) = new_var;
1003 TREE_OPERAND (ass_stmt, 0) = new_var;
1005 bb = bb_for_stmt (stmt);
1006 tree_block_label (bb);
1007 bsi = bsi_after_labels (bb);
1008 bsi_insert_after (&bsi, ass_stmt, BSI_NEW_STMT);
1010 mark_new_vars_to_rename (stmt, vars_to_rename);
1013 /* Replaces immediate uses of VAR by REPL. */
1016 replace_immediate_uses (tree var, tree repl)
1023 use_operand_p use_p;
1025 df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
1026 n = num_immediate_uses (df);
1028 for (i = 0; i < n; i++)
1030 stmt = immediate_use (df, i);
1032 if (TREE_CODE (stmt) == PHI_NODE)
1034 for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
1035 if (PHI_ARG_DEF (stmt, j) == var)
1037 SET_PHI_ARG_DEF (stmt, j, repl);
1038 if (TREE_CODE (repl) == SSA_NAME
1039 && PHI_ARG_EDGE (stmt, j)->flags & EDGE_ABNORMAL)
1040 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl) = 1;
1046 get_stmt_operands (stmt);
1047 mark_new_vars = false;
1048 if (is_gimple_reg (SSA_NAME_VAR (var)))
1050 if (TREE_CODE (stmt) == MODIFY_EXPR)
1052 propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 0), repl);
1053 propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 1), repl);
1056 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1057 if (USE_FROM_PTR (use_p) == var)
1059 propagate_value (use_p, repl);
1060 mark_new_vars = POINTER_TYPE_P (TREE_TYPE (repl));
1065 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
1066 SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
1067 if (USE_FROM_PTR (use_p) == var)
1068 propagate_value (use_p, repl);
1071 /* FIXME. If REPL is a constant, we need to fold STMT.
1072 However, fold_stmt wants a pointer to the statement, because
1073 it may happen that it needs to replace the whole statement
1074 with a new expression. Since the current def-use machinery
1075 does not return pointers to statements, we call fold_stmt
1076 with the address of a local temporary, if that call changes
1077 the temporary then we fallback on looking for a proper
1078 pointer to STMT by scanning STMT's basic block.
1080 Note that all this will become unnecessary soon. This
1081 pass is being replaced with a proper copy propagation pass
1082 for 4.1 (dnovillo, 2004-09-17). */
1083 if (TREE_CODE (repl) != SSA_NAME)
1087 mark_new_vars = true;
1090 block_stmt_iterator si = bsi_for_stmt (stmt);
1091 bsi_replace (&si, tmp, true);
1092 stmt = bsi_stmt (si);
1096 /* If REPL is a pointer, it may have different memory tags associated
1097 with it. For instance, VAR may have had a name tag while REPL
1098 only had a type tag. In these cases, the virtual operands (if
1099 any) in the statement will refer to different symbols which need
1102 mark_new_vars_to_rename (stmt, vars_to_rename);
1108 /* Gets the value VAR is equivalent to according to EQ_TO. */
1111 get_eq_name (tree *eq_to, tree var)
1116 while (TREE_CODE (val) == SSA_NAME)
1118 ver = SSA_NAME_VERSION (val);
1125 while (TREE_CODE (var) == SSA_NAME)
1127 ver = SSA_NAME_VERSION (var);
1138 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1139 its result is redundant to to EQ_TO array. */
1142 check_phi_redundancy (tree phi, tree *eq_to)
1144 tree val = NULL_TREE, def, res = PHI_RESULT (phi), stmt;
1145 unsigned i, ver = SSA_NAME_VERSION (res), n;
1148 /* It is unlikely that such large phi node would be redundant. */
1149 if (PHI_NUM_ARGS (phi) > 16)
1152 for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
1154 def = PHI_ARG_DEF (phi, i);
1156 if (TREE_CODE (def) == SSA_NAME)
1158 def = get_eq_name (eq_to, def);
1164 && !operand_equal_p (val, def, 0))
1170 /* At least one of the arguments should not be equal to the result, or
1171 something strange is happening. */
1174 if (get_eq_name (eq_to, res) == val)
1177 if (!may_propagate_copy (res, val))
1182 df = get_immediate_uses (SSA_NAME_DEF_STMT (res));
1183 n = num_immediate_uses (df);
1185 for (i = 0; i < n; i++)
1187 stmt = immediate_use (df, i);
1189 if (TREE_CODE (stmt) == PHI_NODE)
1190 check_phi_redundancy (stmt, eq_to);
1194 /* Removes redundant phi nodes.
1196 A redundant PHI node is a PHI node where all of its PHI arguments
1197 are the same value, excluding any PHI arguments which are the same
1200 A redundant PHI node is effectively a copy, so we forward copy propagate
1201 which removes all uses of the destination of the PHI node then
1202 finally we delete the redundant PHI node.
1204 Note that if we can not copy propagate the PHI node, then the PHI
1205 will not be removed. Thus we do not have to worry about dependencies
1206 between PHIs and the problems serializing PHIs into copies creates.
1208 The most important effect of this pass is to remove degenerate PHI
1209 nodes created by removing unreachable code. */
1212 kill_redundant_phi_nodes (void)
1215 unsigned i, old_num_ssa_names;
1217 tree phi, var, repl, stmt;
1219 /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1220 replaced. If EQ_TO[VER] is ssa name and it is decided to replace it by
1221 other value, it may be necessary to follow the chain till the final value.
1222 We perform path shortening (replacing the entries of the EQ_TO array with
1223 heads of these chains) whenever we access the field to prevent quadratic
1224 complexity (probably would not occur in practice anyway, but let us play
1226 eq_to = xcalloc (num_ssa_names, sizeof (tree));
1228 /* We have had cases where computing immediate uses takes a
1229 significant amount of compile time. If we run into such
1230 problems here, we may want to only compute immediate uses for
1231 a subset of all the SSA_NAMEs instead of computing it for
1232 all of the SSA_NAMEs. */
1233 compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
1234 old_num_ssa_names = num_ssa_names;
1238 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1240 var = PHI_RESULT (phi);
1241 check_phi_redundancy (phi, eq_to);
1245 /* Now propagate the values. */
1246 for (i = 0; i < old_num_ssa_names; i++)
1251 repl = get_eq_name (eq_to, ssa_name (i));
1252 if (repl != ssa_name (i))
1253 replace_immediate_uses (ssa_name (i), repl);
1256 /* And remove the dead phis. */
1257 for (i = 0; i < old_num_ssa_names; i++)
1262 repl = get_eq_name (eq_to, ssa_name (i));
1263 if (repl != ssa_name (i))
1265 stmt = SSA_NAME_DEF_STMT (ssa_name (i));
1266 remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
1274 struct tree_opt_pass pass_redundant_phi =
1276 "redphi", /* name */
1278 kill_redundant_phi_nodes, /* execute */
1281 0, /* static_pass_number */
1283 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1284 0, /* properties_provided */
1285 0, /* properties_destroyed */
1286 0, /* todo_flags_start */
1287 TODO_dump_func | TODO_rename_vars
1288 | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
1292 /* Emit warnings for uninitialized variables. This is done in two passes.
1294 The first pass notices real uses of SSA names with default definitions.
1295 Such uses are unconditionally uninitialized, and we can be certain that
1296 such a use is a mistake. This pass is run before most optimizations,
1297 so that we catch as many as we can.
1299 The second pass follows PHI nodes to find uses that are potentially
1300 uninitialized. In this case we can't necessarily prove that the use
1301 is really uninitialized. This pass is run after most optimizations,
1302 so that we thread as many jumps and possible, and delete as much dead
1303 code as possible, in order to reduce false positives. We also look
1304 again for plain uninitialized variables, since optimization may have
1305 changed conditionally uninitialized to unconditionally uninitialized. */
1307 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1308 warning text is in MSGID and LOCUS may contain a location or be null. */
1311 warn_uninit (tree t, const char *msgid, location_t *locus)
1313 tree var = SSA_NAME_VAR (t);
1314 tree def = SSA_NAME_DEF_STMT (t);
1316 /* Default uses (indicated by an empty definition statement),
1317 are uninitialized. */
1318 if (!IS_EMPTY_STMT (def))
1321 /* Except for PARMs of course, which are always initialized. */
1322 if (TREE_CODE (var) == PARM_DECL)
1325 /* Hard register variables get their initial value from the ether. */
1326 if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1329 /* TREE_NO_WARNING either means we already warned, or the front end
1330 wishes to suppress the warning. */
1331 if (TREE_NO_WARNING (var))
1335 locus = &DECL_SOURCE_LOCATION (var);
1336 warning (msgid, locus, var);
1337 TREE_NO_WARNING (var) = 1;
1340 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1341 and warn about them. */
1344 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
1346 location_t *locus = data;
1349 /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */
1350 if (TREE_CODE (t) == SSA_NAME)
1352 warn_uninit (t, "%H%qD is used uninitialized in this function", locus);
1355 else if (IS_TYPE_OR_DECL_P (t))
1361 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1362 and warn about them. */
1365 warn_uninitialized_phi (tree phi)
1367 int i, n = PHI_NUM_ARGS (phi);
1369 /* Don't look at memory tags. */
1370 if (!is_gimple_reg (PHI_RESULT (phi)))
1373 for (i = 0; i < n; ++i)
1375 tree op = PHI_ARG_DEF (phi, i);
1376 if (TREE_CODE (op) == SSA_NAME)
1377 warn_uninit (op, "%H%qD may be used uninitialized in this function",
1383 execute_early_warn_uninitialized (void)
1385 block_stmt_iterator bsi;
1389 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1390 walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1391 EXPR_LOCUS (bsi_stmt (bsi)), NULL);
1395 execute_late_warn_uninitialized (void)
1400 /* Re-do the plain uninitialized variable check, as optimization may have
1401 straightened control flow. Do this first so that we don't accidentally
1402 get a "may be" warning when we'd have seen an "is" warning later. */
1403 execute_early_warn_uninitialized ();
1406 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1407 warn_uninitialized_phi (phi);
1411 gate_warn_uninitialized (void)
1413 return warn_uninitialized != 0;
1416 struct tree_opt_pass pass_early_warn_uninitialized =
1419 gate_warn_uninitialized, /* gate */
1420 execute_early_warn_uninitialized, /* execute */
1423 0, /* static_pass_number */
1425 PROP_ssa, /* properties_required */
1426 0, /* properties_provided */
1427 0, /* properties_destroyed */
1428 0, /* todo_flags_start */
1429 0, /* todo_flags_finish */
1433 struct tree_opt_pass pass_late_warn_uninitialized =
1436 gate_warn_uninitialized, /* gate */
1437 execute_late_warn_uninitialized, /* execute */
1440 0, /* static_pass_number */
1442 PROP_ssa, /* properties_required */
1443 0, /* properties_provided */
1444 0, /* properties_destroyed */
1445 0, /* todo_flags_start */
1446 0, /* todo_flags_finish */