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 IDOM contains immediate dominator information for the flowgraph.
293 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
294 numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
295 block in that array slot contains the definition of SSA_NAME. */
298 verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)
302 int i, phi_num_args = PHI_NUM_ARGS (phi);
305 /* Mark all the incoming edges. */
306 FOR_EACH_EDGE (e, ei, bb->preds)
309 for (i = 0; i < phi_num_args; i++)
311 tree op = PHI_ARG_DEF (phi, i);
313 e = PHI_ARG_EDGE (phi, i);
315 if (TREE_CODE (op) == SSA_NAME)
316 err = verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op,
317 phi, e->flags & EDGE_ABNORMAL,
318 !is_gimple_reg (PHI_RESULT (phi)),
323 error ("Wrong edge %d->%d for PHI argument\n",
324 e->src->index, e->dest->index, bb->index);
328 if (e->aux == (void *) 0)
330 error ("PHI argument flowing through dead edge %d->%d\n",
331 e->src->index, e->dest->index);
335 if (e->aux == (void *) 2)
337 error ("PHI argument duplicated for edge %d->%d\n", e->src->index,
344 fprintf (stderr, "PHI argument\n");
345 print_generic_stmt (stderr, op, TDF_VOPS);
352 FOR_EACH_EDGE (e, ei, bb->preds)
354 if (e->aux != (void *) 2)
356 error ("No argument flowing through edge %d->%d\n", e->src->index,
367 fprintf (stderr, "for PHI node\n");
368 print_generic_stmt (stderr, phi, TDF_VOPS);
377 verify_flow_insensitive_alias_info (void)
381 bitmap visited = BITMAP_XMALLOC ();
383 for (i = 0; i < num_referenced_vars; i++)
387 varray_type may_aliases;
389 var = referenced_var (i);
391 may_aliases = ann->may_aliases;
393 for (j = 0; may_aliases && j < VARRAY_ACTIVE_SIZE (may_aliases); j++)
395 tree alias = VARRAY_TREE (may_aliases, j);
397 bitmap_set_bit (visited, var_ann (alias)->uid);
399 if (!may_be_aliased (alias))
401 error ("Non-addressable variable inside an alias set.");
402 debug_variable (alias);
408 for (i = 0; i < num_referenced_vars; i++)
412 var = referenced_var (i);
415 if (ann->mem_tag_kind == NOT_A_TAG
417 && !bitmap_bit_p (visited, ann->uid))
419 error ("Addressable variable that is an alias tag but is not in any alias set.");
424 BITMAP_XFREE (visited);
428 debug_variable (var);
429 internal_error ("verify_flow_insensitive_alias_info failed.");
434 verify_flow_sensitive_alias_info (void)
439 for (i = 1; i < num_ssa_names; i++)
442 struct ptr_info_def *pi;
447 ann = var_ann (SSA_NAME_VAR (ptr));
448 pi = SSA_NAME_PTR_INFO (ptr);
450 /* We only care for pointers that are actually referenced in the
452 if (!TREE_VISITED (ptr) || !POINTER_TYPE_P (TREE_TYPE (ptr)))
455 /* RESULT_DECL is special. If it's a GIMPLE register, then it
456 is only written-to only once in the return statement.
457 Otherwise, aggregate RESULT_DECLs may be written-to more than
458 once in virtual operands. */
459 if (TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL
460 && is_gimple_reg (ptr))
466 if (pi->is_dereferenced && !pi->name_mem_tag && !ann->type_mem_tag)
468 error ("Dereferenced pointers should have a name or a type tag");
474 && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars)))
476 error ("Pointers with a memory tag, should have points-to sets or point to malloc");
480 if (pi->value_escapes_p
482 && !is_call_clobbered (pi->name_mem_tag))
484 error ("Pointer escapes but its name tag is not call-clobbered.");
492 debug_variable (ptr);
493 internal_error ("verify_flow_sensitive_alias_info failed.");
496 DEF_VEC_MALLOC_P (bitmap);
498 /* Verify that all name tags have different points to sets.
499 This algorithm takes advantage of the fact that every variable with the
500 same name tag must have the same points-to set.
501 So we check a single variable for each name tag, and verify that its
502 points-to set is different from every other points-to set for other name
506 verify_name_tags (void)
510 bitmap first, second;
511 VEC (tree) *name_tag_reps = NULL;
512 VEC (bitmap) *pt_vars_for_reps = NULL;
514 /* First we compute the name tag representatives and their points-to sets. */
515 for (i = 0; i < num_ssa_names; i++)
519 tree ptr = ssa_name (i);
520 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
521 if (!TREE_VISITED (ptr)
522 || !POINTER_TYPE_P (TREE_TYPE (ptr))
525 || TREE_VISITED (pi->name_mem_tag))
527 TREE_VISITED (pi->name_mem_tag) = 1;
528 if (pi->pt_vars != NULL)
530 VEC_safe_push (tree, name_tag_reps, ptr);
531 VEC_safe_push (bitmap, pt_vars_for_reps, pi->pt_vars);
536 /* Now compare all the representative bitmaps with all other representative
537 bitmaps, to verify that they are all different. */
538 for (i = 0; VEC_iterate (bitmap, pt_vars_for_reps, i, first); i++)
540 for (j = i + 1; VEC_iterate (bitmap, pt_vars_for_reps, j, second); j++)
542 if (bitmap_equal_p (first, second))
544 error ("Two different pointers with identical points-to sets but different name tags");
545 debug_variable (VEC_index (tree, name_tag_reps, j));
551 /* Lastly, clear out the visited flags. */
552 for (i = 0; i < num_ssa_names; i++)
556 tree ptr = ssa_name (i);
557 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
558 if (!TREE_VISITED (ptr)
559 || !POINTER_TYPE_P (TREE_TYPE (ptr))
561 || !pi->name_mem_tag)
563 TREE_VISITED (pi->name_mem_tag) = 0;
566 VEC_free (bitmap, pt_vars_for_reps);
570 debug_variable (VEC_index (tree, name_tag_reps, i));
571 internal_error ("verify_name_tags failed");
573 /* Verify the consistency of aliasing information. */
576 verify_alias_info (void)
578 verify_flow_sensitive_alias_info ();
580 verify_flow_insensitive_alias_info ();
584 /* Verify common invariants in the SSA web.
585 TODO: verify the variable annotations. */
592 basic_block *definition_block = xcalloc (num_ssa_names, sizeof (basic_block));
595 enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS];
596 bitmap names_defined_in_bb = BITMAP_XMALLOC ();
598 timevar_push (TV_TREE_SSA_VERIFY);
600 /* Keep track of SSA names present in the IL. */
601 for (i = 1; i < num_ssa_names; i++)
603 TREE_VISITED (ssa_name (i)) = 0;
605 calculate_dominance_info (CDI_DOMINATORS);
607 /* Verify and register all the SSA_NAME definitions found in the
612 block_stmt_iterator bsi;
614 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
617 if (verify_def (bb, definition_block, PHI_RESULT (phi), phi,
618 !is_gimple_reg (PHI_RESULT (phi))))
620 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
622 tree def = PHI_ARG_DEF (phi, i);
623 if (TREE_CODE (def) != SSA_NAME && !is_gimple_min_invariant (def))
625 error ("PHI argument is not SSA_NAME, or invariant");
626 print_generic_stmt (stderr, phi, TDF_VOPS);
632 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
636 stmt = bsi_stmt (bsi);
637 get_stmt_operands (stmt);
639 if (stmt_ann (stmt)->makes_aliased_stores
640 && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) == 0)
642 error ("Statement makes aliased stores, but has no V_MAY_DEFS");
643 print_generic_stmt (stderr, stmt, TDF_VOPS);
647 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
649 if (verify_def (bb, definition_block, op, stmt, true))
653 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
655 if (verify_def (bb, definition_block, op, stmt, false))
662 /* Now verify all the uses and make sure they agree with the definitions
663 found in the previous pass. */
669 block_stmt_iterator bsi;
671 /* Make sure that all edges have a clear 'aux' field. */
672 FOR_EACH_EDGE (e, ei, bb->preds)
676 error ("AUX pointer initialized for edge %d->%d\n", e->src->index,
682 /* Verify the arguments for every PHI node in the block. */
683 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
685 if (verify_phi_args (phi, bb, definition_block))
687 bitmap_set_bit (names_defined_in_bb,
688 SSA_NAME_VERSION (PHI_RESULT (phi)));
691 /* Now verify all the uses and vuses in every statement of the block. */
692 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
694 tree stmt = bsi_stmt (bsi);
696 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
698 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
699 op, stmt, false, true,
700 names_defined_in_bb))
704 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
706 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
707 op, stmt, false, false,
708 names_defined_in_bb))
712 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
714 bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
718 /* Verify the uses in arguments of PHI nodes at the exits from the
720 FOR_EACH_EDGE (e, ei, bb->succs)
722 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
724 bool virtual = !is_gimple_reg (PHI_RESULT (phi));
725 op = PHI_ARG_DEF_FROM_EDGE (phi, e);
726 if (TREE_CODE (op) != SSA_NAME)
729 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
730 op, phi, false, virtual,
731 names_defined_in_bb))
736 bitmap_clear (names_defined_in_bb);
739 /* Finally, verify alias information. */
740 verify_alias_info ();
742 free (definition_block);
743 /* Restore the dominance information to its prior known state, so
744 that we do not perturb the compiler's subsequent behavior. */
745 if (orig_dom_state == DOM_NONE)
746 free_dominance_info (CDI_DOMINATORS);
748 dom_computed[CDI_DOMINATORS] = orig_dom_state;
750 BITMAP_XFREE (names_defined_in_bb);
751 timevar_pop (TV_TREE_SSA_VERIFY);
755 internal_error ("verify_ssa failed.");
759 /* Initialize global DFA and SSA structures. */
764 VARRAY_TREE_INIT (referenced_vars, 20, "referenced_vars");
765 call_clobbered_vars = BITMAP_XMALLOC ();
766 addressable_vars = BITMAP_XMALLOC ();
767 init_ssa_operands ();
770 global_var = NULL_TREE;
774 /* Deallocate memory associated with SSA data structures for FNDECL. */
777 delete_tree_ssa (void)
781 block_stmt_iterator bsi;
783 /* Remove annotations from every tree in the function. */
785 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
787 tree stmt = bsi_stmt (bsi);
789 ggc_free (stmt->common.ann);
790 stmt->common.ann = NULL;
793 /* Remove annotations from every referenced variable. */
796 for (i = 0; i < num_referenced_vars; i++)
798 tree var = referenced_var (i);
799 ggc_free (var->common.ann);
800 var->common.ann = NULL;
802 referenced_vars = NULL;
807 fini_ssa_operands ();
809 global_var = NULL_TREE;
810 BITMAP_XFREE (call_clobbered_vars);
811 call_clobbered_vars = NULL;
812 BITMAP_XFREE (addressable_vars);
813 addressable_vars = NULL;
817 /* Return true if EXPR is a useless type conversion, otherwise return
821 tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
823 /* If the inner and outer types are effectively the same, then
824 strip the type conversion and enter the equivalence into
826 if (inner_type == outer_type
827 || (lang_hooks.types_compatible_p (inner_type, outer_type)))
830 /* If both types are pointers and the outer type is a (void *), then
831 the conversion is not necessary. The opposite is not true since
832 that conversion would result in a loss of information if the
833 equivalence was used. Consider an indirect function call where
834 we need to know the exact type of the function to correctly
835 implement the ABI. */
836 else if (POINTER_TYPE_P (inner_type)
837 && POINTER_TYPE_P (outer_type)
838 && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
839 && TYPE_REF_CAN_ALIAS_ALL (inner_type)
840 == TYPE_REF_CAN_ALIAS_ALL (outer_type)
841 && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
844 /* Pointers and references are equivalent once we get to GENERIC,
845 so strip conversions that just switch between them. */
846 else if (POINTER_TYPE_P (inner_type)
847 && POINTER_TYPE_P (outer_type)
848 && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
849 && TYPE_REF_CAN_ALIAS_ALL (inner_type)
850 == TYPE_REF_CAN_ALIAS_ALL (outer_type)
851 && lang_hooks.types_compatible_p (TREE_TYPE (inner_type),
852 TREE_TYPE (outer_type)))
855 /* If both the inner and outer types are integral types, then the
856 conversion is not necessary if they have the same mode and
857 signedness and precision, and both or neither are boolean. Some
858 code assumes an invariant that boolean types stay boolean and do
859 not become 1-bit bit-field types. Note that types with precision
860 not using all bits of the mode (such as bit-field types in C)
861 mean that testing of precision is necessary. */
862 else if (INTEGRAL_TYPE_P (inner_type)
863 && INTEGRAL_TYPE_P (outer_type)
864 && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
865 && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
866 && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
868 bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE);
869 bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE);
870 if (first_boolean == second_boolean)
874 /* Recurse for complex types. */
875 else if (TREE_CODE (inner_type) == COMPLEX_TYPE
876 && TREE_CODE (outer_type) == COMPLEX_TYPE
877 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
878 TREE_TYPE (inner_type)))
884 /* Return true if EXPR is a useless type conversion, otherwise return
888 tree_ssa_useless_type_conversion (tree expr)
890 /* If we have an assignment that merely uses a NOP_EXPR to change
891 the top of the RHS to the type of the LHS and the type conversion
892 is "safe", then strip away the type conversion so that we can
893 enter LHS = RHS into the const_and_copies table. */
894 if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR
895 || TREE_CODE (expr) == VIEW_CONVERT_EXPR
896 || TREE_CODE (expr) == NON_LVALUE_EXPR)
897 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
898 TREE_TYPE (TREE_OPERAND (expr,
905 /* Returns true if statement STMT may read memory. */
908 stmt_references_memory_p (tree stmt)
912 get_stmt_operands (stmt);
913 ann = stmt_ann (stmt);
915 if (ann->has_volatile_ops)
918 return (NUM_VUSES (VUSE_OPS (ann)) > 0
919 || NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) > 0
920 || NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) > 0);
923 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
924 described in walk_use_def_chains.
926 VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
927 infinite loops. We used to have a bitmap for this to just mark
928 SSA versions we had visited. But non-sparse bitmaps are way too
929 expensive, while sparse bitmaps may cause quadratic behavior.
931 IS_DFS is true if the caller wants to perform a depth-first search
932 when visiting PHI nodes. A DFS will visit each PHI argument and
933 call FN after each one. Otherwise, all the arguments are
934 visited first and then FN is called with each of the visited
935 arguments in a separate pass. */
938 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
939 struct pointer_set_t *visited, bool is_dfs)
943 if (pointer_set_insert (visited, var))
946 def_stmt = SSA_NAME_DEF_STMT (var);
948 if (TREE_CODE (def_stmt) != PHI_NODE)
950 /* If we reached the end of the use-def chain, call FN. */
951 return fn (var, def_stmt, data);
957 /* When doing a breadth-first search, call FN before following the
958 use-def links for each argument. */
960 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
961 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
964 /* Follow use-def links out of each PHI argument. */
965 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
967 tree arg = PHI_ARG_DEF (def_stmt, i);
968 if (TREE_CODE (arg) == SSA_NAME
969 && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
973 /* When doing a depth-first search, call FN after following the
974 use-def links for each argument. */
976 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
977 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
986 /* Walk use-def chains starting at the SSA variable VAR. Call
987 function FN at each reaching definition found. FN takes three
988 arguments: VAR, its defining statement (DEF_STMT) and a generic
989 pointer to whatever state information that FN may want to maintain
990 (DATA). FN is able to stop the walk by returning true, otherwise
991 in order to continue the walk, FN should return false.
993 Note, that if DEF_STMT is a PHI node, the semantics are slightly
994 different. The first argument to FN is no longer the original
995 variable VAR, but the PHI argument currently being examined. If FN
996 wants to get at VAR, it should call PHI_RESULT (PHI).
998 If IS_DFS is true, this function will:
1000 1- walk the use-def chains for all the PHI arguments, and,
1001 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
1003 If IS_DFS is false, the two steps above are done in reverse order
1004 (i.e., a breadth-first search). */
1008 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
1013 gcc_assert (TREE_CODE (var) == SSA_NAME);
1015 def_stmt = SSA_NAME_DEF_STMT (var);
1017 /* We only need to recurse if the reaching definition comes from a PHI
1019 if (TREE_CODE (def_stmt) != PHI_NODE)
1020 (*fn) (var, def_stmt, data);
1023 struct pointer_set_t *visited = pointer_set_create ();
1024 walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
1025 pointer_set_destroy (visited);
1030 /* Replaces VAR with REPL in memory reference expression *X in
1034 propagate_into_addr (tree stmt, tree var, tree *x, tree repl)
1036 tree new_var, ass_stmt, addr_var;
1038 block_stmt_iterator bsi;
1040 /* There is nothing special to handle in the other cases. */
1041 if (TREE_CODE (repl) != ADDR_EXPR)
1043 addr_var = TREE_OPERAND (repl, 0);
1045 while (handled_component_p (*x)
1046 || TREE_CODE (*x) == REALPART_EXPR
1047 || TREE_CODE (*x) == IMAGPART_EXPR)
1048 x = &TREE_OPERAND (*x, 0);
1050 if (TREE_CODE (*x) != INDIRECT_REF
1051 || TREE_OPERAND (*x, 0) != var)
1054 if (TREE_TYPE (*x) == TREE_TYPE (addr_var))
1057 mark_new_vars_to_rename (stmt, vars_to_rename);
1062 /* Frontends sometimes produce expressions like *&a instead of a[0].
1063 Create a temporary variable to handle this case. */
1064 ass_stmt = build2 (MODIFY_EXPR, void_type_node, NULL_TREE, repl);
1065 new_var = duplicate_ssa_name (var, ass_stmt);
1066 TREE_OPERAND (*x, 0) = new_var;
1067 TREE_OPERAND (ass_stmt, 0) = new_var;
1069 bb = bb_for_stmt (stmt);
1070 tree_block_label (bb);
1071 bsi = bsi_after_labels (bb);
1072 bsi_insert_after (&bsi, ass_stmt, BSI_NEW_STMT);
1074 mark_new_vars_to_rename (stmt, vars_to_rename);
1077 /* Replaces immediate uses of VAR by REPL. */
1080 replace_immediate_uses (tree var, tree repl)
1087 use_operand_p use_p;
1089 df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
1090 n = num_immediate_uses (df);
1092 for (i = 0; i < n; i++)
1094 stmt = immediate_use (df, i);
1096 if (TREE_CODE (stmt) == PHI_NODE)
1098 for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
1099 if (PHI_ARG_DEF (stmt, j) == var)
1101 SET_PHI_ARG_DEF (stmt, j, repl);
1102 if (TREE_CODE (repl) == SSA_NAME
1103 && PHI_ARG_EDGE (stmt, j)->flags & EDGE_ABNORMAL)
1104 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl) = 1;
1110 get_stmt_operands (stmt);
1111 mark_new_vars = false;
1112 if (is_gimple_reg (SSA_NAME_VAR (var)))
1114 if (TREE_CODE (stmt) == MODIFY_EXPR)
1116 propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 0), repl);
1117 propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 1), repl);
1120 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1121 if (USE_FROM_PTR (use_p) == var)
1123 propagate_value (use_p, repl);
1124 mark_new_vars = POINTER_TYPE_P (TREE_TYPE (repl));
1129 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
1130 SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
1131 if (USE_FROM_PTR (use_p) == var)
1132 propagate_value (use_p, repl);
1135 /* FIXME. If REPL is a constant, we need to fold STMT.
1136 However, fold_stmt wants a pointer to the statement, because
1137 it may happen that it needs to replace the whole statement
1138 with a new expression. Since the current def-use machinery
1139 does not return pointers to statements, we call fold_stmt
1140 with the address of a local temporary, if that call changes
1141 the temporary then we fallback on looking for a proper
1142 pointer to STMT by scanning STMT's basic block.
1144 Note that all this will become unnecessary soon. This
1145 pass is being replaced with a proper copy propagation pass
1146 for 4.1 (dnovillo, 2004-09-17). */
1147 if (TREE_CODE (repl) != SSA_NAME)
1151 mark_new_vars = true;
1154 block_stmt_iterator si = bsi_for_stmt (stmt);
1155 bsi_replace (&si, tmp, true);
1156 stmt = bsi_stmt (si);
1160 /* If REPL is a pointer, it may have different memory tags associated
1161 with it. For instance, VAR may have had a name tag while REPL
1162 only had a type tag. In these cases, the virtual operands (if
1163 any) in the statement will refer to different symbols which need
1166 mark_new_vars_to_rename (stmt, vars_to_rename);
1172 /* Gets the value VAR is equivalent to according to EQ_TO. */
1175 get_eq_name (tree *eq_to, tree var)
1180 while (TREE_CODE (val) == SSA_NAME)
1182 ver = SSA_NAME_VERSION (val);
1189 while (TREE_CODE (var) == SSA_NAME)
1191 ver = SSA_NAME_VERSION (var);
1202 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1203 its result is redundant to to EQ_TO array. */
1206 check_phi_redundancy (tree phi, tree *eq_to)
1208 tree val = NULL_TREE, def, res = PHI_RESULT (phi), stmt;
1209 unsigned i, ver = SSA_NAME_VERSION (res), n;
1212 /* It is unlikely that such large phi node would be redundant. */
1213 if (PHI_NUM_ARGS (phi) > 16)
1216 for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
1218 def = PHI_ARG_DEF (phi, i);
1220 if (TREE_CODE (def) == SSA_NAME)
1222 def = get_eq_name (eq_to, def);
1228 && !operand_equal_p (val, def, 0))
1234 /* At least one of the arguments should not be equal to the result, or
1235 something strange is happening. */
1238 if (get_eq_name (eq_to, res) == val)
1241 if (!may_propagate_copy (res, val))
1246 df = get_immediate_uses (SSA_NAME_DEF_STMT (res));
1247 n = num_immediate_uses (df);
1249 for (i = 0; i < n; i++)
1251 stmt = immediate_use (df, i);
1253 if (TREE_CODE (stmt) == PHI_NODE)
1254 check_phi_redundancy (stmt, eq_to);
1258 /* Removes redundant phi nodes.
1260 A redundant PHI node is a PHI node where all of its PHI arguments
1261 are the same value, excluding any PHI arguments which are the same
1264 A redundant PHI node is effectively a copy, so we forward copy propagate
1265 which removes all uses of the destination of the PHI node then
1266 finally we delete the redundant PHI node.
1268 Note that if we can not copy propagate the PHI node, then the PHI
1269 will not be removed. Thus we do not have to worry about dependencies
1270 between PHIs and the problems serializing PHIs into copies creates.
1272 The most important effect of this pass is to remove degenerate PHI
1273 nodes created by removing unreachable code. */
1276 kill_redundant_phi_nodes (void)
1279 unsigned i, old_num_ssa_names;
1281 tree phi, var, repl, stmt;
1283 /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1284 replaced. If EQ_TO[VER] is ssa name and it is decided to replace it by
1285 other value, it may be necessary to follow the chain till the final value.
1286 We perform path shortening (replacing the entries of the EQ_TO array with
1287 heads of these chains) whenever we access the field to prevent quadratic
1288 complexity (probably would not occur in practice anyway, but let us play
1290 eq_to = xcalloc (num_ssa_names, sizeof (tree));
1292 /* We have had cases where computing immediate uses takes a
1293 significant amount of compile time. If we run into such
1294 problems here, we may want to only compute immediate uses for
1295 a subset of all the SSA_NAMEs instead of computing it for
1296 all of the SSA_NAMEs. */
1297 compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
1298 old_num_ssa_names = num_ssa_names;
1302 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1304 var = PHI_RESULT (phi);
1305 check_phi_redundancy (phi, eq_to);
1309 /* Now propagate the values. */
1310 for (i = 0; i < old_num_ssa_names; i++)
1315 repl = get_eq_name (eq_to, ssa_name (i));
1316 if (repl != ssa_name (i))
1317 replace_immediate_uses (ssa_name (i), repl);
1320 /* And remove the dead phis. */
1321 for (i = 0; i < old_num_ssa_names; i++)
1326 repl = get_eq_name (eq_to, ssa_name (i));
1327 if (repl != ssa_name (i))
1329 stmt = SSA_NAME_DEF_STMT (ssa_name (i));
1330 remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
1338 struct tree_opt_pass pass_redundant_phi =
1340 "redphi", /* name */
1342 kill_redundant_phi_nodes, /* execute */
1345 0, /* static_pass_number */
1347 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1348 0, /* properties_provided */
1349 0, /* properties_destroyed */
1350 0, /* todo_flags_start */
1351 TODO_dump_func | TODO_rename_vars
1352 | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
1356 /* Emit warnings for uninitialized variables. This is done in two passes.
1358 The first pass notices real uses of SSA names with default definitions.
1359 Such uses are unconditionally uninitialized, and we can be certain that
1360 such a use is a mistake. This pass is run before most optimizations,
1361 so that we catch as many as we can.
1363 The second pass follows PHI nodes to find uses that are potentially
1364 uninitialized. In this case we can't necessarily prove that the use
1365 is really uninitialized. This pass is run after most optimizations,
1366 so that we thread as many jumps and possible, and delete as much dead
1367 code as possible, in order to reduce false positives. We also look
1368 again for plain uninitialized variables, since optimization may have
1369 changed conditionally uninitialized to unconditionally uninitialized. */
1371 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1372 warning text is in MSGID and LOCUS may contain a location or be null. */
1375 warn_uninit (tree t, const char *msgid, location_t *locus)
1377 tree var = SSA_NAME_VAR (t);
1378 tree def = SSA_NAME_DEF_STMT (t);
1380 /* Default uses (indicated by an empty definition statement),
1381 are uninitialized. */
1382 if (!IS_EMPTY_STMT (def))
1385 /* Except for PARMs of course, which are always initialized. */
1386 if (TREE_CODE (var) == PARM_DECL)
1389 /* Hard register variables get their initial value from the ether. */
1390 if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1393 /* TREE_NO_WARNING either means we already warned, or the front end
1394 wishes to suppress the warning. */
1395 if (TREE_NO_WARNING (var))
1399 locus = &DECL_SOURCE_LOCATION (var);
1400 warning (msgid, locus, var);
1401 TREE_NO_WARNING (var) = 1;
1404 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1405 and warn about them. */
1408 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
1410 location_t *locus = data;
1413 /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */
1414 if (TREE_CODE (t) == SSA_NAME)
1416 warn_uninit (t, "%H%qD is used uninitialized in this function", locus);
1419 else if (IS_TYPE_OR_DECL_P (t))
1425 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1426 and warn about them. */
1429 warn_uninitialized_phi (tree phi)
1431 int i, n = PHI_NUM_ARGS (phi);
1433 /* Don't look at memory tags. */
1434 if (!is_gimple_reg (PHI_RESULT (phi)))
1437 for (i = 0; i < n; ++i)
1439 tree op = PHI_ARG_DEF (phi, i);
1440 if (TREE_CODE (op) == SSA_NAME)
1441 warn_uninit (op, "%H%qD may be used uninitialized in this function",
1447 execute_early_warn_uninitialized (void)
1449 block_stmt_iterator bsi;
1453 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1454 walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1455 EXPR_LOCUS (bsi_stmt (bsi)), NULL);
1459 execute_late_warn_uninitialized (void)
1464 /* Re-do the plain uninitialized variable check, as optimization may have
1465 straightened control flow. Do this first so that we don't accidentally
1466 get a "may be" warning when we'd have seen an "is" warning later. */
1467 execute_early_warn_uninitialized ();
1470 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1471 warn_uninitialized_phi (phi);
1475 gate_warn_uninitialized (void)
1477 return warn_uninitialized != 0;
1480 struct tree_opt_pass pass_early_warn_uninitialized =
1483 gate_warn_uninitialized, /* gate */
1484 execute_early_warn_uninitialized, /* execute */
1487 0, /* static_pass_number */
1489 PROP_ssa, /* properties_required */
1490 0, /* properties_provided */
1491 0, /* properties_destroyed */
1492 0, /* todo_flags_start */
1493 0, /* todo_flags_finish */
1497 struct tree_opt_pass pass_late_warn_uninitialized =
1500 gate_warn_uninitialized, /* gate */
1501 execute_late_warn_uninitialized, /* execute */
1504 0, /* static_pass_number */
1506 PROP_ssa, /* properties_required */
1507 0, /* properties_provided */
1508 0, /* properties_destroyed */
1509 0, /* todo_flags_start */
1510 0, /* todo_flags_finish */