1 /* Miscellaneous SSA utility functions.
2 Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
23 #include "coretypes.h"
30 #include "langhooks.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
37 #include "diagnostic.h"
39 #include "tree-flow.h"
40 #include "tree-gimple.h"
41 #include "tree-inline.h"
45 #include "tree-dump.h"
46 #include "tree-pass.h"
49 /* Remove edge E and remove the corresponding arguments from the PHI nodes
50 in E's destination block. */
53 ssa_remove_edge (edge e)
57 /* Remove the appropriate PHI arguments in E's destination block. */
58 for (phi = phi_nodes (e->dest); phi; phi = next)
60 next = PHI_CHAIN (phi);
61 remove_phi_arg (phi, e->src);
67 /* Remove the corresponding arguments from the PHI nodes in E's
68 destination block and redirect it to DEST. Return redirected edge.
69 The list of removed arguments is stored in PENDING_STMT (e). */
72 ssa_redirect_edge (edge e, basic_block dest)
75 tree list = NULL, *last = &list;
79 /* Remove the appropriate PHI arguments in E's destination block. */
80 for (phi = phi_nodes (e->dest); phi; phi = next)
82 next = PHI_CHAIN (phi);
84 i = phi_arg_from_edge (phi, e);
88 src = PHI_ARG_DEF (phi, i);
89 dst = PHI_RESULT (phi);
90 node = build_tree_list (dst, src);
92 last = &TREE_CHAIN (node);
94 remove_phi_arg_num (phi, i);
97 e = redirect_edge_succ_nodup (e, dest);
98 PENDING_STMT (e) = list;
104 /* Return true if SSA_NAME is malformed and mark it visited.
106 IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
110 verify_ssa_name (tree ssa_name, bool is_virtual)
112 TREE_VISITED (ssa_name) = 1;
114 if (TREE_CODE (ssa_name) != SSA_NAME)
116 error ("Expected an SSA_NAME object");
120 if (TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name)))
122 error ("Type mismatch between an SSA_NAME and its symbol.");
126 if (SSA_NAME_IN_FREE_LIST (ssa_name))
128 error ("Found an SSA_NAME that had been released into the free pool");
132 if (is_virtual && is_gimple_reg (ssa_name))
134 error ("Found a virtual definition for a GIMPLE register");
138 if (!is_virtual && !is_gimple_reg (ssa_name))
140 error ("Found a real definition for a non-register");
148 /* Return true if the definition of SSA_NAME at block BB is malformed.
150 STMT is the statement where SSA_NAME is created.
152 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
153 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
154 it means that the block in that array slot contains the
155 definition of SSA_NAME.
157 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
161 verify_def (basic_block bb, basic_block *definition_block, tree ssa_name,
162 tree stmt, bool is_virtual)
164 if (verify_ssa_name (ssa_name, is_virtual))
167 if (definition_block[SSA_NAME_VERSION (ssa_name)])
169 error ("SSA_NAME created in two different blocks %i and %i",
170 definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index);
174 definition_block[SSA_NAME_VERSION (ssa_name)] = bb;
176 if (SSA_NAME_DEF_STMT (ssa_name) != stmt)
178 error ("SSA_NAME_DEF_STMT is wrong");
179 fprintf (stderr, "Expected definition statement:\n");
180 debug_generic_stmt (SSA_NAME_DEF_STMT (ssa_name));
181 fprintf (stderr, "\nActual definition statement:\n");
182 debug_generic_stmt (stmt);
189 fprintf (stderr, "while verifying SSA_NAME ");
190 print_generic_expr (stderr, ssa_name, 0);
191 fprintf (stderr, " in statement\n");
192 debug_generic_stmt (stmt);
198 /* Return true if the use of SSA_NAME at statement STMT in block BB is
201 DEF_BB is the block where SSA_NAME was found to be created.
203 IDOM contains immediate dominator information for the flowgraph.
205 CHECK_ABNORMAL is true if the caller wants to check whether this use
206 is flowing through an abnormal edge (only used when checking PHI
209 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
212 If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
213 that are defined before STMT in basic block BB. */
216 verify_use (basic_block bb, basic_block def_bb, tree ssa_name,
217 tree stmt, bool check_abnormal, bool is_virtual,
218 bitmap names_defined_in_bb)
222 err = verify_ssa_name (ssa_name, is_virtual);
224 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name))
225 && var_ann (SSA_NAME_VAR (ssa_name))->default_def == ssa_name)
226 ; /* Default definitions have empty statements. Nothing to do. */
229 error ("Missing definition");
232 else if (bb != def_bb
233 && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
235 error ("Definition in block %i does not dominate use in block %i",
236 def_bb->index, bb->index);
239 else if (bb == def_bb
240 && names_defined_in_bb != NULL
241 && !bitmap_bit_p (names_defined_in_bb, SSA_NAME_VERSION (ssa_name)))
243 error ("Definition in block %i follows the use", def_bb->index);
248 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
250 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
256 fprintf (stderr, "for SSA_NAME: ");
257 debug_generic_expr (ssa_name);
258 fprintf (stderr, "in statement:\n");
259 debug_generic_stmt (stmt);
266 /* Return true if any of the arguments for PHI node PHI at block BB is
269 IDOM contains immediate dominator information for the flowgraph.
271 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
272 numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
273 block in that array slot contains the definition of SSA_NAME. */
276 verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)
280 int i, phi_num_args = PHI_NUM_ARGS (phi);
282 /* Mark all the incoming edges. */
283 for (e = bb->pred; e; e = e->pred_next)
286 for (i = 0; i < phi_num_args; i++)
288 tree op = PHI_ARG_DEF (phi, i);
290 e = PHI_ARG_EDGE (phi, i);
292 if (TREE_CODE (op) == SSA_NAME)
293 err = verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op,
294 phi, e->flags & EDGE_ABNORMAL,
295 !is_gimple_reg (PHI_RESULT (phi)),
300 error ("Wrong edge %d->%d for PHI argument\n",
301 e->src->index, e->dest->index, bb->index);
305 if (e->aux == (void *) 0)
307 error ("PHI argument flowing through dead edge %d->%d\n",
308 e->src->index, e->dest->index);
312 if (e->aux == (void *) 2)
314 error ("PHI argument duplicated for edge %d->%d\n", e->src->index,
321 fprintf (stderr, "PHI argument\n");
322 debug_generic_stmt (op);
329 for (e = bb->pred; e; e = e->pred_next)
331 if (e->aux != (void *) 2)
333 error ("No argument flowing through edge %d->%d\n", e->src->index,
344 fprintf (stderr, "for PHI node\n");
345 debug_generic_stmt (phi);
354 verify_flow_insensitive_alias_info (void)
358 bitmap visited = BITMAP_XMALLOC ();
360 for (i = 0; i < num_referenced_vars; i++)
364 varray_type may_aliases;
366 var = referenced_var (i);
368 may_aliases = ann->may_aliases;
370 for (j = 0; may_aliases && j < VARRAY_ACTIVE_SIZE (may_aliases); j++)
372 tree alias = VARRAY_TREE (may_aliases, j);
374 bitmap_set_bit (visited, var_ann (alias)->uid);
376 if (!may_be_aliased (alias))
378 error ("Non-addressable variable inside an alias set.");
379 debug_variable (alias);
385 for (i = 0; i < num_referenced_vars; i++)
389 var = referenced_var (i);
392 if (ann->mem_tag_kind == NOT_A_TAG
394 && !bitmap_bit_p (visited, ann->uid))
396 error ("Addressable variable that is an alias tag but is not in any alias set.");
401 BITMAP_XFREE (visited);
405 debug_variable (var);
406 internal_error ("verify_flow_insensitive_alias_info failed.");
411 verify_flow_sensitive_alias_info (void)
416 for (i = 1; i < num_ssa_names; i++)
419 struct ptr_info_def *pi;
422 ann = var_ann (SSA_NAME_VAR (ptr));
423 pi = SSA_NAME_PTR_INFO (ptr);
425 /* We only care for pointers that are actually referenced in the
427 if (!TREE_VISITED (ptr) || !POINTER_TYPE_P (TREE_TYPE (ptr)))
430 /* RESULT_DECL is special. If it's a GIMPLE register, then it
431 is only written-to only once in the return statement.
432 Otherwise, aggregate RESULT_DECLs may be written-to more than
433 once in virtual operands. */
434 if (TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL
435 && is_gimple_reg (ptr))
441 if (pi->is_dereferenced && !pi->name_mem_tag && !ann->type_mem_tag)
443 error ("Dereferenced pointers should have a name or a type tag");
449 && (pi->pt_vars == NULL
450 || bitmap_first_set_bit (pi->pt_vars) < 0))
452 error ("Pointers with a memory tag, should have points-to sets or point to malloc");
456 if (pi->value_escapes_p
458 && !is_call_clobbered (pi->name_mem_tag))
460 error ("Pointer escapes but its name tag is not call-clobbered.");
464 if (pi->name_mem_tag && pi->pt_vars)
468 for (j = i + 1; j < num_ssa_names; j++)
470 tree ptr2 = ssa_name (j);
471 struct ptr_info_def *pi2 = SSA_NAME_PTR_INFO (ptr2);
473 if (!TREE_VISITED (ptr2) || !POINTER_TYPE_P (TREE_TYPE (ptr2)))
479 && bitmap_first_set_bit (pi2->pt_vars) >= 0
480 && pi->name_mem_tag != pi2->name_mem_tag
481 && bitmap_equal_p (pi->pt_vars, pi2->pt_vars))
483 error ("Two pointers with different name tags and identical points-to sets");
484 debug_variable (ptr2);
494 debug_variable (ptr);
495 internal_error ("verify_flow_sensitive_alias_info failed.");
499 /* Verify the consistency of aliasing information. */
502 verify_alias_info (void)
504 verify_flow_sensitive_alias_info ();
505 verify_flow_insensitive_alias_info ();
509 /* Verify common invariants in the SSA web.
510 TODO: verify the variable annotations. */
517 basic_block *definition_block = xcalloc (num_ssa_names, sizeof (basic_block));
520 enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS];
521 bitmap names_defined_in_bb = BITMAP_XMALLOC ();
523 timevar_push (TV_TREE_SSA_VERIFY);
525 /* Keep track of SSA names present in the IL. */
526 for (i = 1; i < num_ssa_names; i++)
527 TREE_VISITED (ssa_name (i)) = 0;
529 calculate_dominance_info (CDI_DOMINATORS);
531 /* Verify and register all the SSA_NAME definitions found in the
536 block_stmt_iterator bsi;
538 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
539 if (verify_def (bb, definition_block, PHI_RESULT (phi), phi,
540 !is_gimple_reg (PHI_RESULT (phi))))
543 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
547 stmt = bsi_stmt (bsi);
548 get_stmt_operands (stmt);
550 if (stmt_ann (stmt)->makes_aliased_stores
551 && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) == 0)
553 error ("Statement makes aliased stores, but has no V_MAY_DEFS");
554 debug_generic_stmt (stmt);
558 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
560 if (verify_def (bb, definition_block, op, stmt, true))
564 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
566 if (verify_def (bb, definition_block, op, stmt, false))
573 /* Now verify all the uses and make sure they agree with the definitions
574 found in the previous pass. */
579 block_stmt_iterator bsi;
581 /* Make sure that all edges have a clear 'aux' field. */
582 for (e = bb->pred; e; e = e->pred_next)
586 error ("AUX pointer initialized for edge %d->%d\n", e->src->index,
592 /* Verify the arguments for every PHI node in the block. */
593 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
595 if (verify_phi_args (phi, bb, definition_block))
597 bitmap_set_bit (names_defined_in_bb,
598 SSA_NAME_VERSION (PHI_RESULT (phi)));
601 /* Now verify all the uses and vuses in every statement of the block. */
602 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
604 tree stmt = bsi_stmt (bsi);
606 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_USES)
608 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
609 op, stmt, false, true,
610 names_defined_in_bb))
614 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
616 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
617 op, stmt, false, false,
618 names_defined_in_bb))
622 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
624 bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
628 /* Verify the uses in arguments of PHI nodes at the exits from the
630 for (e = bb->succ; e; e = e->succ_next)
632 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
634 bool virtual = !is_gimple_reg (PHI_RESULT (phi));
635 op = PHI_ARG_DEF_FROM_EDGE (phi, e);
636 if (TREE_CODE (op) != SSA_NAME)
639 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
640 op, phi, false, virtual,
641 names_defined_in_bb))
646 bitmap_clear (names_defined_in_bb);
649 /* Finally, verify alias information. */
650 verify_alias_info ();
652 free (definition_block);
653 /* Restore the dominance infomation to its prior known state, so
654 that we do not perturb the compiler's subsequent behaviour. */
655 if (orig_dom_state == DOM_NONE)
656 free_dominance_info (CDI_DOMINATORS);
658 dom_computed[CDI_DOMINATORS] = orig_dom_state;
660 BITMAP_XFREE (names_defined_in_bb);
661 timevar_pop (TV_TREE_SSA_VERIFY);
665 internal_error ("verify_ssa failed.");
669 /* Initialize global DFA and SSA structures. */
674 VARRAY_TREE_INIT (referenced_vars, 20, "referenced_vars");
675 call_clobbered_vars = BITMAP_XMALLOC ();
676 addressable_vars = BITMAP_XMALLOC ();
677 init_ssa_operands ();
680 global_var = NULL_TREE;
684 /* Deallocate memory associated with SSA data structures for FNDECL. */
687 delete_tree_ssa (void)
691 block_stmt_iterator bsi;
693 /* Remove annotations from every tree in the function. */
695 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
697 tree stmt = bsi_stmt (bsi);
699 ggc_free (stmt->common.ann);
700 stmt->common.ann = NULL;
703 /* Remove annotations from every referenced variable. */
706 for (i = 0; i < num_referenced_vars; i++)
708 tree var = referenced_var (i);
709 ggc_free (var->common.ann);
710 var->common.ann = NULL;
712 referenced_vars = NULL;
717 fini_ssa_operands ();
719 global_var = NULL_TREE;
720 BITMAP_XFREE (call_clobbered_vars);
721 call_clobbered_vars = NULL;
722 BITMAP_XFREE (addressable_vars);
723 addressable_vars = NULL;
727 /* Return true if EXPR is a useless type conversion, otherwise return
731 tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
733 /* If the inner and outer types are effectively the same, then
734 strip the type conversion and enter the equivalence into
736 if (inner_type == outer_type
737 || (lang_hooks.types_compatible_p (inner_type, outer_type)))
740 /* If both types are pointers and the outer type is a (void *), then
741 the conversion is not necessary. The opposite is not true since
742 that conversion would result in a loss of information if the
743 equivalence was used. Consider an indirect function call where
744 we need to know the exact type of the function to correctly
745 implement the ABI. */
746 else if (POINTER_TYPE_P (inner_type)
747 && POINTER_TYPE_P (outer_type)
748 && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
751 /* Pointers and references are equivalent once we get to GENERIC,
752 so strip conversions that just switch between them. */
753 else if (POINTER_TYPE_P (inner_type)
754 && POINTER_TYPE_P (outer_type)
755 && lang_hooks.types_compatible_p (TREE_TYPE (inner_type),
756 TREE_TYPE (outer_type)))
759 /* If both the inner and outer types are integral types, then the
760 conversion is not necessary if they have the same mode and
761 signedness and precision, and both or neither are boolean. Some
762 code assumes an invariant that boolean types stay boolean and do
763 not become 1-bit bit-field types. Note that types with precision
764 not using all bits of the mode (such as bit-field types in C)
765 mean that testing of precision is necessary. */
766 else if (INTEGRAL_TYPE_P (inner_type)
767 && INTEGRAL_TYPE_P (outer_type)
768 && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
769 && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
770 && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
772 bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE);
773 bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE);
774 if (first_boolean == second_boolean)
778 /* Recurse for complex types. */
779 else if (TREE_CODE (inner_type) == COMPLEX_TYPE
780 && TREE_CODE (outer_type) == COMPLEX_TYPE
781 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
782 TREE_TYPE (inner_type)))
788 /* Return true if EXPR is a useless type conversion, otherwise return
792 tree_ssa_useless_type_conversion (tree expr)
794 /* If we have an assignment that merely uses a NOP_EXPR to change
795 the top of the RHS to the type of the LHS and the type conversion
796 is "safe", then strip away the type conversion so that we can
797 enter LHS = RHS into the const_and_copies table. */
798 if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR
799 || TREE_CODE (expr) == VIEW_CONVERT_EXPR
800 || TREE_CODE (expr) == NON_LVALUE_EXPR)
801 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
802 TREE_TYPE (TREE_OPERAND (expr,
810 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
811 described in walk_use_def_chains.
813 VISITED is a bitmap used to mark visited SSA_NAMEs to avoid
816 IS_DFS is true if the caller wants to perform a depth-first search
817 when visiting PHI nodes. A DFS will visit each PHI argument and
818 call FN after each one. Otherwise, all the arguments are
819 visited first and then FN is called with each of the visited
820 arguments in a separate pass. */
823 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
824 bitmap visited, bool is_dfs)
828 if (bitmap_bit_p (visited, SSA_NAME_VERSION (var)))
831 bitmap_set_bit (visited, SSA_NAME_VERSION (var));
833 def_stmt = SSA_NAME_DEF_STMT (var);
835 if (TREE_CODE (def_stmt) != PHI_NODE)
837 /* If we reached the end of the use-def chain, call FN. */
838 return fn (var, def_stmt, data);
844 /* When doing a breadth-first search, call FN before following the
845 use-def links for each argument. */
847 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
848 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
851 /* Follow use-def links out of each PHI argument. */
852 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
854 tree arg = PHI_ARG_DEF (def_stmt, i);
855 if (TREE_CODE (arg) == SSA_NAME
856 && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
860 /* When doing a depth-first search, call FN after following the
861 use-def links for each argument. */
863 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
864 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
873 /* Walk use-def chains starting at the SSA variable VAR. Call
874 function FN at each reaching definition found. FN takes three
875 arguments: VAR, its defining statement (DEF_STMT) and a generic
876 pointer to whatever state information that FN may want to maintain
877 (DATA). FN is able to stop the walk by returning true, otherwise
878 in order to continue the walk, FN should return false.
880 Note, that if DEF_STMT is a PHI node, the semantics are slightly
881 different. The first argument to FN is no longer the original
882 variable VAR, but the PHI argument currently being examined. If FN
883 wants to get at VAR, it should call PHI_RESULT (PHI).
885 If IS_DFS is true, this function will:
887 1- walk the use-def chains for all the PHI arguments, and,
888 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
890 If IS_DFS is false, the two steps above are done in reverse order
891 (i.e., a breadth-first search). */
895 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
900 gcc_assert (TREE_CODE (var) == SSA_NAME);
902 def_stmt = SSA_NAME_DEF_STMT (var);
904 /* We only need to recurse if the reaching definition comes from a PHI
906 if (TREE_CODE (def_stmt) != PHI_NODE)
907 (*fn) (var, def_stmt, data);
910 bitmap visited = BITMAP_XMALLOC ();
911 walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
912 BITMAP_XFREE (visited);
917 /* Replaces VAR with REPL in memory reference expression *X in
921 propagate_into_addr (tree stmt, tree var, tree *x, tree repl)
923 tree new_var, ass_stmt, addr_var;
925 block_stmt_iterator bsi;
927 /* There is nothing special to handle in the other cases. */
928 if (TREE_CODE (repl) != ADDR_EXPR)
930 addr_var = TREE_OPERAND (repl, 0);
932 while (handled_component_p (*x)
933 || TREE_CODE (*x) == REALPART_EXPR
934 || TREE_CODE (*x) == IMAGPART_EXPR)
935 x = &TREE_OPERAND (*x, 0);
937 if (TREE_CODE (*x) != INDIRECT_REF
938 || TREE_OPERAND (*x, 0) != var)
941 if (TREE_TYPE (*x) == TREE_TYPE (addr_var))
944 mark_new_vars_to_rename (stmt, vars_to_rename);
949 /* Frontends sometimes produce expressions like *&a instead of a[0].
950 Create a temporary variable to handle this case. */
951 ass_stmt = build2 (MODIFY_EXPR, void_type_node, NULL_TREE, repl);
952 new_var = duplicate_ssa_name (var, ass_stmt);
953 TREE_OPERAND (*x, 0) = new_var;
954 TREE_OPERAND (ass_stmt, 0) = new_var;
956 bb = bb_for_stmt (stmt);
957 tree_block_label (bb);
958 bsi = bsi_after_labels (bb);
959 bsi_insert_after (&bsi, ass_stmt, BSI_NEW_STMT);
961 mark_new_vars_to_rename (stmt, vars_to_rename);
964 /* Replaces immediate uses of VAR by REPL. */
967 replace_immediate_uses (tree var, tree repl)
976 df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
977 n = num_immediate_uses (df);
979 for (i = 0; i < n; i++)
981 stmt = immediate_use (df, i);
983 if (TREE_CODE (stmt) == PHI_NODE)
985 for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
986 if (PHI_ARG_DEF (stmt, j) == var)
988 SET_PHI_ARG_DEF (stmt, j, repl);
989 if (TREE_CODE (repl) == SSA_NAME
990 && PHI_ARG_EDGE (stmt, j)->flags & EDGE_ABNORMAL)
991 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl) = 1;
997 get_stmt_operands (stmt);
998 mark_new_vars = false;
999 if (is_gimple_reg (SSA_NAME_VAR (var)))
1001 if (TREE_CODE (stmt) == MODIFY_EXPR)
1003 propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 0), repl);
1004 propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 1), repl);
1007 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1008 if (USE_FROM_PTR (use_p) == var)
1010 propagate_value (use_p, repl);
1011 mark_new_vars = POINTER_TYPE_P (TREE_TYPE (repl));
1016 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_VIRTUAL_USES)
1017 if (USE_FROM_PTR (use_p) == var)
1018 propagate_value (use_p, repl);
1021 /* If REPL is a pointer, it may have different memory tags associated
1022 with it. For instance, VAR may have had a name tag while REPL
1023 only had a type tag. In these cases, the virtual operands (if
1024 any) in the statement will refer to different symbols which need
1027 mark_new_vars_to_rename (stmt, vars_to_rename);
1033 /* Gets the value VAR is equivalent to according to EQ_TO. */
1036 get_eq_name (tree *eq_to, tree var)
1041 while (TREE_CODE (val) == SSA_NAME)
1043 ver = SSA_NAME_VERSION (val);
1050 while (TREE_CODE (var) == SSA_NAME)
1052 ver = SSA_NAME_VERSION (var);
1063 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1064 its result is redundant to to EQ_TO array. */
1067 check_phi_redundancy (tree phi, tree *eq_to)
1069 tree val = NULL_TREE, def, res = PHI_RESULT (phi), stmt;
1070 unsigned i, ver = SSA_NAME_VERSION (res), n;
1073 /* It is unlikely that such large phi node would be redundant. */
1074 if (PHI_NUM_ARGS (phi) > 16)
1077 for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
1079 def = PHI_ARG_DEF (phi, i);
1081 if (TREE_CODE (def) == SSA_NAME)
1083 def = get_eq_name (eq_to, def);
1089 && !operand_equal_p (val, def, 0))
1095 /* At least one of the arguments should not be equal to the result, or
1096 something strange is happening. */
1099 if (get_eq_name (eq_to, res) == val)
1102 if (!may_propagate_copy (res, val))
1107 df = get_immediate_uses (SSA_NAME_DEF_STMT (res));
1108 n = num_immediate_uses (df);
1110 for (i = 0; i < n; i++)
1112 stmt = immediate_use (df, i);
1114 if (TREE_CODE (stmt) == PHI_NODE)
1115 check_phi_redundancy (stmt, eq_to);
1119 /* Removes redundant phi nodes.
1121 A redundant PHI node is a PHI node where all of its PHI arguments
1122 are the same value, excluding any PHI arguments which are the same
1125 A redundant PHI node is effectively a copy, so we forward copy propagate
1126 which removes all uses of the destination of the PHI node then
1127 finally we delete the redundant PHI node.
1129 Note that if we can not copy propagate the PHI node, then the PHI
1130 will not be removed. Thus we do not have to worry about dependencies
1131 between PHIs and the problems serializing PHIs into copies creates.
1133 The most important effect of this pass is to remove degenerate PHI
1134 nodes created by removing unreachable code. */
1137 kill_redundant_phi_nodes (void)
1140 unsigned i, old_num_ssa_names;
1142 tree phi, var, repl, stmt;
1144 /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1145 replaced. If EQ_TO[VER] is ssa name and it is decided to replace it by
1146 other value, it may be necessary to follow the chain till the final value.
1147 We perform path shortening (replacing the entries of the EQ_TO array with
1148 heads of these chains) whenever we access the field to prevent quadratic
1149 complexity (probably would not occur in practice anyway, but let us play
1151 eq_to = xcalloc (num_ssa_names, sizeof (tree));
1153 /* We have had cases where computing immediate uses takes a
1154 significant amount of compile time. If we run into such
1155 problems here, we may want to only compute immediate uses for
1156 a subset of all the SSA_NAMEs instead of computing it for
1157 all of the SSA_NAMEs. */
1158 compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
1159 old_num_ssa_names = num_ssa_names;
1163 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1165 var = PHI_RESULT (phi);
1166 check_phi_redundancy (phi, eq_to);
1170 /* Now propagate the values. */
1171 for (i = 0; i < old_num_ssa_names; i++)
1176 repl = get_eq_name (eq_to, ssa_name (i));
1177 if (repl != ssa_name (i))
1178 replace_immediate_uses (ssa_name (i), repl);
1181 /* And remove the dead phis. */
1182 for (i = 0; i < old_num_ssa_names; i++)
1187 repl = get_eq_name (eq_to, ssa_name (i));
1188 if (repl != ssa_name (i))
1190 stmt = SSA_NAME_DEF_STMT (ssa_name (i));
1191 remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
1199 struct tree_opt_pass pass_redundant_phi =
1201 "redphi", /* name */
1203 kill_redundant_phi_nodes, /* execute */
1206 0, /* static_pass_number */
1208 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1209 0, /* properties_provided */
1210 0, /* properties_destroyed */
1211 0, /* todo_flags_start */
1212 TODO_dump_func | TODO_rename_vars
1213 | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
1217 /* Emit warnings for uninitialized variables. This is done in two passes.
1219 The first pass notices real uses of SSA names with default definitions.
1220 Such uses are unconditionally uninitialized, and we can be certain that
1221 such a use is a mistake. This pass is run before most optimizations,
1222 so that we catch as many as we can.
1224 The second pass follows PHI nodes to find uses that are potentially
1225 uninitialized. In this case we can't necessarily prove that the use
1226 is really uninitialized. This pass is run after most optimizations,
1227 so that we thread as many jumps and possible, and delete as much dead
1228 code as possible, in order to reduce false positives. We also look
1229 again for plain uninitialized variables, since optimization may have
1230 changed conditionally uninitialized to unconditionally uninitialized. */
1232 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1233 warning text is in MSGID and LOCUS may contain a location or be null. */
1236 warn_uninit (tree t, const char *msgid, location_t *locus)
1238 tree var = SSA_NAME_VAR (t);
1239 tree def = SSA_NAME_DEF_STMT (t);
1241 /* Default uses (indicated by an empty definition statement),
1242 are uninitialized. */
1243 if (!IS_EMPTY_STMT (def))
1246 /* Except for PARMs of course, which are always initialized. */
1247 if (TREE_CODE (var) == PARM_DECL)
1250 /* Hard register variables get their initial value from the ether. */
1251 if (DECL_HARD_REGISTER (var))
1254 /* TREE_NO_WARNING either means we already warned, or the front end
1255 wishes to suppress the warning. */
1256 if (TREE_NO_WARNING (var))
1260 locus = &DECL_SOURCE_LOCATION (var);
1261 warning (msgid, locus, var);
1262 TREE_NO_WARNING (var) = 1;
1265 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1266 and warn about them. */
1269 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
1271 location_t *locus = data;
1274 /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */
1275 if (TREE_CODE (t) == SSA_NAME)
1277 warn_uninit (t, "%H'%D' is used uninitialized in this function", locus);
1280 else if (DECL_P (t) || TYPE_P (t))
1286 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1287 and warn about them. */
1290 warn_uninitialized_phi (tree phi)
1292 int i, n = PHI_NUM_ARGS (phi);
1294 /* Don't look at memory tags. */
1295 if (!is_gimple_reg (PHI_RESULT (phi)))
1298 for (i = 0; i < n; ++i)
1300 tree op = PHI_ARG_DEF (phi, i);
1301 if (TREE_CODE (op) == SSA_NAME)
1302 warn_uninit (op, "%H'%D' may be used uninitialized in this function",
1308 execute_early_warn_uninitialized (void)
1310 block_stmt_iterator bsi;
1314 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1315 walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1316 EXPR_LOCUS (bsi_stmt (bsi)), NULL);
1320 execute_late_warn_uninitialized (void)
1325 /* Re-do the plain uninitialized variable check, as optimization may have
1326 straightened control flow. Do this first so that we don't accidentally
1327 get a "may be" warning when we'd have seen an "is" warning later. */
1328 execute_early_warn_uninitialized ();
1331 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1332 warn_uninitialized_phi (phi);
1336 gate_warn_uninitialized (void)
1338 return warn_uninitialized != 0;
1341 struct tree_opt_pass pass_early_warn_uninitialized =
1344 gate_warn_uninitialized, /* gate */
1345 execute_early_warn_uninitialized, /* execute */
1348 0, /* static_pass_number */
1350 PROP_ssa, /* properties_required */
1351 0, /* properties_provided */
1352 0, /* properties_destroyed */
1353 0, /* todo_flags_start */
1354 0, /* todo_flags_finish */
1358 struct tree_opt_pass pass_late_warn_uninitialized =
1361 gate_warn_uninitialized, /* gate */
1362 execute_late_warn_uninitialized, /* execute */
1365 0, /* static_pass_number */
1367 PROP_ssa, /* properties_required */
1368 0, /* properties_provided */
1369 0, /* properties_destroyed */
1370 0, /* todo_flags_start */
1371 0, /* todo_flags_finish */