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"
44 #include "tree-alias-common.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
;
105 /* Return true if SSA_NAME is malformed and mark it visited.
107 IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
111 verify_ssa_name (tree ssa_name
, bool is_virtual
)
113 TREE_VISITED (ssa_name
) = 1;
115 if (TREE_CODE (ssa_name
) != SSA_NAME
)
117 error ("Expected an SSA_NAME object");
121 if (SSA_NAME_IN_FREE_LIST (ssa_name
))
123 error ("Found an SSA_NAME that had been released into the free pool");
127 if (is_virtual
&& is_gimple_reg (ssa_name
))
129 error ("Found a virtual definition for a GIMPLE register");
133 if (!is_virtual
&& !is_gimple_reg (ssa_name
))
135 error ("Found a real definition for a non-register");
143 /* Return true if the definition of SSA_NAME at block BB is malformed.
145 STMT is the statement where SSA_NAME is created.
147 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
148 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
149 it means that the block in that array slot contains the
150 definition of SSA_NAME.
152 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
156 verify_def (basic_block bb
, basic_block
*definition_block
, tree ssa_name
,
157 tree stmt
, bool is_virtual
)
159 if (verify_ssa_name (ssa_name
, is_virtual
))
162 if (definition_block
[SSA_NAME_VERSION (ssa_name
)])
164 error ("SSA_NAME created in two different blocks %i and %i",
165 definition_block
[SSA_NAME_VERSION (ssa_name
)]->index
, bb
->index
);
169 definition_block
[SSA_NAME_VERSION (ssa_name
)] = bb
;
171 if (SSA_NAME_DEF_STMT (ssa_name
) != stmt
)
173 error ("SSA_NAME_DEF_STMT is wrong");
174 fprintf (stderr
, "Expected definition statement:\n");
175 debug_generic_stmt (SSA_NAME_DEF_STMT (ssa_name
));
176 fprintf (stderr
, "\nActual definition statement:\n");
177 debug_generic_stmt (stmt
);
184 fprintf (stderr
, "while verifying SSA_NAME ");
185 print_generic_expr (stderr
, ssa_name
, 0);
186 fprintf (stderr
, " in statement\n");
187 debug_generic_stmt (stmt
);
193 /* Return true if the use of SSA_NAME at statement STMT in block BB is
196 DEF_BB is the block where SSA_NAME was found to be created.
198 IDOM contains immediate dominator information for the flowgraph.
200 CHECK_ABNORMAL is true if the caller wants to check whether this use
201 is flowing through an abnormal edge (only used when checking PHI
204 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
208 verify_use (basic_block bb
, basic_block def_bb
, tree ssa_name
,
209 tree stmt
, bool check_abnormal
, bool is_virtual
)
213 err
= verify_ssa_name (ssa_name
, is_virtual
);
215 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name
))
216 && var_ann (SSA_NAME_VAR (ssa_name
))->default_def
== ssa_name
)
217 ; /* Default definitions have empty statements. Nothing to do. */
220 error ("Missing definition");
223 else if (bb
!= def_bb
224 && !dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
226 error ("Definition in block %i does not dominate use in block %i",
227 def_bb
->index
, bb
->index
);
232 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name
))
234 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
240 fprintf (stderr
, "for SSA_NAME: ");
241 debug_generic_expr (ssa_name
);
242 fprintf (stderr
, "in statement:\n");
243 debug_generic_stmt (stmt
);
250 /* Return true if any of the arguments for PHI node PHI at block BB is
253 IDOM contains immediate dominator information for the flowgraph.
255 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
256 numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
257 block in that array slot contains the definition of SSA_NAME. */
260 verify_phi_args (tree phi
, basic_block bb
, basic_block
*definition_block
)
264 int i
, phi_num_args
= PHI_NUM_ARGS (phi
);
266 /* Mark all the incoming edges. */
267 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
270 for (i
= 0; i
< phi_num_args
; i
++)
272 tree op
= PHI_ARG_DEF (phi
, i
);
274 e
= PHI_ARG_EDGE (phi
, i
);
276 if (TREE_CODE (op
) == SSA_NAME
)
277 err
= verify_use (e
->src
, definition_block
[SSA_NAME_VERSION (op
)], op
,
278 phi
, e
->flags
& EDGE_ABNORMAL
,
279 !is_gimple_reg (PHI_RESULT (phi
)));
283 error ("Wrong edge %d->%d for PHI argument\n",
284 e
->src
->index
, e
->dest
->index
, bb
->index
);
288 if (e
->aux
== (void *) 0)
290 error ("PHI argument flowing through dead edge %d->%d\n",
291 e
->src
->index
, e
->dest
->index
);
295 if (e
->aux
== (void *) 2)
297 error ("PHI argument duplicated for edge %d->%d\n", e
->src
->index
,
304 fprintf (stderr
, "PHI argument\n");
305 debug_generic_stmt (op
);
312 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
314 if (e
->aux
!= (void *) 2)
316 error ("No argument flowing through edge %d->%d\n", e
->src
->index
,
327 fprintf (stderr
, "for PHI node\n");
328 debug_generic_stmt (phi
);
337 verify_flow_insensitive_alias_info (void)
341 bitmap visited
= BITMAP_XMALLOC ();
343 for (i
= 0; i
< num_referenced_vars
; i
++)
347 var
= referenced_var (i
);
350 if (ann
->mem_tag_kind
== TYPE_TAG
|| ann
->mem_tag_kind
== NAME_TAG
)
353 varray_type may_aliases
= ann
->may_aliases
;
355 for (j
= 0; may_aliases
&& j
< VARRAY_ACTIVE_SIZE (may_aliases
); j
++)
357 tree alias
= VARRAY_TREE (may_aliases
, j
);
359 bitmap_set_bit (visited
, var_ann (alias
)->uid
);
361 if (!may_be_aliased (alias
))
363 error ("Non-addressable variable inside an alias set.");
364 debug_variable (alias
);
371 for (i
= 0; i
< num_referenced_vars
; i
++)
375 var
= referenced_var (i
);
378 if (ann
->mem_tag_kind
== NOT_A_TAG
380 && !bitmap_bit_p (visited
, ann
->uid
))
382 error ("Addressable variable that is an alias tag but is not in any alias set.");
387 BITMAP_XFREE (visited
);
391 debug_variable (var
);
392 internal_error ("verify_flow_insensitive_alias_info failed.");
397 verify_flow_sensitive_alias_info (void)
402 for (i
= 1; i
< num_ssa_names
; i
++)
405 struct ptr_info_def
*pi
;
408 ann
= var_ann (SSA_NAME_VAR (ptr
));
409 pi
= SSA_NAME_PTR_INFO (ptr
);
411 /* We only care for pointers that are actually referenced in the
413 if (!TREE_VISITED (ptr
) || !POINTER_TYPE_P (TREE_TYPE (ptr
)))
416 /* RESULT_DECL is special. If it's a GIMPLE register, then it
417 is only written-to only once in the return statement.
418 Otherwise, aggregate RESULT_DECLs may be written-to more than
419 once in virtual operands. */
420 if (TREE_CODE (SSA_NAME_VAR (ptr
)) == RESULT_DECL
421 && is_gimple_reg (ptr
))
427 if (pi
->is_dereferenced
&& !pi
->name_mem_tag
&& !ann
->type_mem_tag
)
429 error ("Dereferenced pointers should have a name or a type tag");
433 if (pi
->pt_anything
&& (pi
->pt_malloc
|| pi
->pt_vars
))
435 error ("Pointers that point to anything should not point to malloc or other vars");
439 if (pi
->pt_malloc
&& pi
->pt_vars
)
441 error ("Pointers pointing to malloc get a unique tag and cannot point to other vars");
447 && (pi
->pt_vars
== NULL
448 || bitmap_first_set_bit (pi
->pt_vars
) < 0))
450 error ("Pointers with a memory tag, should have points-to sets or point to malloc");
454 if (pi
->value_escapes_p
456 && !is_call_clobbered (pi
->name_mem_tag
))
458 error ("Pointer escapes but its name tag is not call-clobbered.");
462 if (pi
->name_mem_tag
&& pi
->pt_vars
)
466 for (j
= i
+ 1; j
< num_ssa_names
; j
++)
468 tree ptr2
= ssa_name (j
);
469 struct ptr_info_def
*pi2
= SSA_NAME_PTR_INFO (ptr2
);
471 if (!POINTER_TYPE_P (TREE_TYPE (ptr2
)))
477 && bitmap_first_set_bit (pi2
->pt_vars
) >= 0
478 && pi
->name_mem_tag
!= pi2
->name_mem_tag
479 && bitmap_equal_p (pi
->pt_vars
, pi2
->pt_vars
))
481 error ("Two pointers with different name tags and identical points-to sets");
482 debug_variable (ptr2
);
492 debug_variable (ptr
);
493 internal_error ("verify_flow_sensitive_alias_info failed.");
497 /* Verify the consistency of aliasing information. */
500 verify_alias_info (void)
502 if (aliases_computed_p
)
504 verify_flow_sensitive_alias_info ();
505 verify_flow_insensitive_alias_info ();
510 /* Verify common invariants in the SSA web.
511 TODO: verify the variable annotations. */
518 basic_block
*definition_block
= xcalloc (num_ssa_names
, sizeof (basic_block
));
520 timevar_push (TV_TREE_SSA_VERIFY
);
522 /* Keep track of SSA names present in the IL. */
523 for (i
= 1; i
< num_ssa_names
; i
++)
524 TREE_VISITED (ssa_name (i
)) = 0;
526 calculate_dominance_info (CDI_DOMINATORS
);
528 /* Verify and register all the SSA_NAME definitions found in the
533 block_stmt_iterator bsi
;
535 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
536 if (verify_def (bb
, definition_block
, PHI_RESULT (phi
), phi
,
537 !is_gimple_reg (PHI_RESULT (phi
))))
540 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
545 v_may_def_optype v_may_defs
;
546 v_must_def_optype v_must_defs
;
549 stmt
= bsi_stmt (bsi
);
550 ann
= stmt_ann (stmt
);
551 get_stmt_operands (stmt
);
553 v_may_defs
= V_MAY_DEF_OPS (ann
);
554 if (ann
->makes_aliased_stores
&& NUM_V_MAY_DEFS (v_may_defs
) == 0)
556 error ("Statement makes aliased stores, but has no V_MAY_DEFS");
557 debug_generic_stmt (stmt
);
561 for (j
= 0; j
< NUM_V_MAY_DEFS (v_may_defs
); j
++)
563 tree op
= V_MAY_DEF_RESULT (v_may_defs
, j
);
564 if (verify_def (bb
, definition_block
, op
, stmt
, true))
568 v_must_defs
= STMT_V_MUST_DEF_OPS (stmt
);
569 for (j
= 0; j
< NUM_V_MUST_DEFS (v_must_defs
); j
++)
571 tree op
= V_MUST_DEF_OP (v_must_defs
, j
);
572 if (verify_def (bb
, definition_block
, op
, stmt
, true))
576 defs
= DEF_OPS (ann
);
577 for (j
= 0; j
< NUM_DEFS (defs
); j
++)
579 tree op
= DEF_OP (defs
, j
);
580 if (verify_def (bb
, definition_block
, op
, stmt
, false))
587 /* Now verify all the uses and make sure they agree with the definitions
588 found in the previous pass. */
593 block_stmt_iterator bsi
;
595 /* Make sure that all edges have a clear 'aux' field. */
596 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
600 error ("AUX pointer initialized for edge %d->%d\n", e
->src
->index
,
606 /* Verify the arguments for every PHI node in the block. */
607 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
608 if (verify_phi_args (phi
, bb
, definition_block
))
611 /* Now verify all the uses and vuses in every statement of the block. */
612 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
614 tree stmt
= bsi_stmt (bsi
);
615 stmt_ann_t ann
= stmt_ann (stmt
);
618 v_may_def_optype v_may_defs
;
621 vuses
= VUSE_OPS (ann
);
622 for (j
= 0; j
< NUM_VUSES (vuses
); j
++)
624 tree op
= VUSE_OP (vuses
, j
);
625 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
626 op
, stmt
, false, true))
630 v_may_defs
= V_MAY_DEF_OPS (ann
);
631 for (j
= 0; j
< NUM_V_MAY_DEFS (v_may_defs
); j
++)
633 tree op
= V_MAY_DEF_OP (v_may_defs
, j
);
634 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
635 op
, stmt
, false, true))
639 uses
= USE_OPS (ann
);
640 for (j
= 0; j
< NUM_USES (uses
); j
++)
642 tree op
= USE_OP (uses
, j
);
643 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
644 op
, stmt
, false, false))
650 /* Finally, verify alias information. */
651 verify_alias_info ();
653 free (definition_block
);
654 timevar_pop (TV_TREE_SSA_VERIFY
);
658 internal_error ("verify_ssa failed.");
662 /* Initialize global DFA and SSA structures. */
667 VARRAY_TREE_INIT (referenced_vars
, 20, "referenced_vars");
668 call_clobbered_vars
= BITMAP_XMALLOC ();
669 addressable_vars
= BITMAP_XMALLOC ();
670 init_ssa_operands ();
673 global_var
= NULL_TREE
;
674 aliases_computed_p
= false;
678 /* Deallocate memory associated with SSA data structures for FNDECL. */
681 delete_tree_ssa (void)
685 block_stmt_iterator bsi
;
687 /* Remove annotations from every tree in the function. */
689 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
690 bsi_stmt (bsi
)->common
.ann
= NULL
;
692 /* Remove annotations from every referenced variable. */
695 for (i
= 0; i
< num_referenced_vars
; i
++)
696 referenced_var (i
)->common
.ann
= NULL
;
697 referenced_vars
= NULL
;
702 fini_ssa_operands ();
704 global_var
= NULL_TREE
;
705 BITMAP_XFREE (call_clobbered_vars
);
706 call_clobbered_vars
= NULL
;
707 aliases_computed_p
= false;
708 BITMAP_XFREE (addressable_vars
);
709 addressable_vars
= NULL
;
713 /* Return true if EXPR is a useless type conversion, otherwise return
717 tree_ssa_useless_type_conversion_1 (tree outer_type
, tree inner_type
)
719 /* If the inner and outer types are effectively the same, then
720 strip the type conversion and enter the equivalence into
722 if (inner_type
== outer_type
723 || (lang_hooks
.types_compatible_p (inner_type
, outer_type
)))
726 /* If both types are pointers and the outer type is a (void *), then
727 the conversion is not necessary. The opposite is not true since
728 that conversion would result in a loss of information if the
729 equivalence was used. Consider an indirect function call where
730 we need to know the exact type of the function to correctly
731 implement the ABI. */
732 else if (POINTER_TYPE_P (inner_type
)
733 && POINTER_TYPE_P (outer_type
)
734 && TREE_CODE (TREE_TYPE (outer_type
)) == VOID_TYPE
)
737 /* Pointers and references are equivalent once we get to GENERIC,
738 so strip conversions that just switch between them. */
739 else if (POINTER_TYPE_P (inner_type
)
740 && POINTER_TYPE_P (outer_type
)
741 && lang_hooks
.types_compatible_p (TREE_TYPE (inner_type
),
742 TREE_TYPE (outer_type
)))
745 /* If both the inner and outer types are integral types, then the
746 conversion is not necessary if they have the same mode and
747 signedness and precision, and both or neither are boolean. Some
748 code assumes an invariant that boolean types stay boolean and do
749 not become 1-bit bit-field types. Note that types with precision
750 not using all bits of the mode (such as bit-field types in C)
751 mean that testing of precision is necessary. */
752 else if (INTEGRAL_TYPE_P (inner_type
)
753 && INTEGRAL_TYPE_P (outer_type
)
754 && TYPE_MODE (inner_type
) == TYPE_MODE (outer_type
)
755 && TYPE_UNSIGNED (inner_type
) == TYPE_UNSIGNED (outer_type
)
756 && TYPE_PRECISION (inner_type
) == TYPE_PRECISION (outer_type
))
758 bool first_boolean
= (TREE_CODE (inner_type
) == BOOLEAN_TYPE
);
759 bool second_boolean
= (TREE_CODE (outer_type
) == BOOLEAN_TYPE
);
760 if (first_boolean
== second_boolean
)
764 /* Recurse for complex types. */
765 else if (TREE_CODE (inner_type
) == COMPLEX_TYPE
766 && TREE_CODE (outer_type
) == COMPLEX_TYPE
767 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type
),
768 TREE_TYPE (inner_type
)))
774 /* Return true if EXPR is a useless type conversion, otherwise return
778 tree_ssa_useless_type_conversion (tree expr
)
780 /* If we have an assignment that merely uses a NOP_EXPR to change
781 the top of the RHS to the type of the LHS and the type conversion
782 is "safe", then strip away the type conversion so that we can
783 enter LHS = RHS into the const_and_copies table. */
784 if (TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
785 || TREE_CODE (expr
) == VIEW_CONVERT_EXPR
786 || TREE_CODE (expr
) == NON_LVALUE_EXPR
)
787 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr
),
788 TREE_TYPE (TREE_OPERAND (expr
,
796 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
797 described in walk_use_def_chains.
799 VISITED is a bitmap used to mark visited SSA_NAMEs to avoid
802 IS_DFS is true if the caller wants to perform a depth-first search
803 when visiting PHI nodes. A DFS will visit each PHI argument and
804 call FN after each one. Otherwise, all the arguments are
805 visited first and then FN is called with each of the visited
806 arguments in a separate pass. */
809 walk_use_def_chains_1 (tree var
, walk_use_def_chains_fn fn
, void *data
,
810 bitmap visited
, bool is_dfs
)
814 if (bitmap_bit_p (visited
, SSA_NAME_VERSION (var
)))
817 bitmap_set_bit (visited
, SSA_NAME_VERSION (var
));
819 def_stmt
= SSA_NAME_DEF_STMT (var
);
821 if (TREE_CODE (def_stmt
) != PHI_NODE
)
823 /* If we reached the end of the use-def chain, call FN. */
824 return fn (var
, def_stmt
, data
);
830 /* When doing a breadth-first search, call FN before following the
831 use-def links for each argument. */
833 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
834 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
837 /* Follow use-def links out of each PHI argument. */
838 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
840 tree arg
= PHI_ARG_DEF (def_stmt
, i
);
841 if (TREE_CODE (arg
) == SSA_NAME
842 && walk_use_def_chains_1 (arg
, fn
, data
, visited
, is_dfs
))
846 /* When doing a depth-first search, call FN after following the
847 use-def links for each argument. */
849 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
850 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
859 /* Walk use-def chains starting at the SSA variable VAR. Call
860 function FN at each reaching definition found. FN takes three
861 arguments: VAR, its defining statement (DEF_STMT) and a generic
862 pointer to whatever state information that FN may want to maintain
863 (DATA). FN is able to stop the walk by returning true, otherwise
864 in order to continue the walk, FN should return false.
866 Note, that if DEF_STMT is a PHI node, the semantics are slightly
867 different. The first argument to FN is no longer the original
868 variable VAR, but the PHI argument currently being examined. If FN
869 wants to get at VAR, it should call PHI_RESULT (PHI).
871 If IS_DFS is true, this function will:
873 1- walk the use-def chains for all the PHI arguments, and,
874 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
876 If IS_DFS is false, the two steps above are done in reverse order
877 (i.e., a breadth-first search). */
881 walk_use_def_chains (tree var
, walk_use_def_chains_fn fn
, void *data
,
886 #if defined ENABLE_CHECKING
887 if (TREE_CODE (var
) != SSA_NAME
)
891 def_stmt
= SSA_NAME_DEF_STMT (var
);
893 /* We only need to recurse if the reaching definition comes from a PHI
895 if (TREE_CODE (def_stmt
) != PHI_NODE
)
896 (*fn
) (var
, def_stmt
, data
);
899 bitmap visited
= BITMAP_XMALLOC ();
900 walk_use_def_chains_1 (var
, fn
, data
, visited
, is_dfs
);
901 BITMAP_XFREE (visited
);
906 /* Replaces VAR with REPL in memory reference expression *X in
910 propagate_into_addr (tree stmt
, tree var
, tree
*x
, tree repl
)
912 tree new_var
, ass_stmt
, addr_var
;
914 block_stmt_iterator bsi
;
916 /* There is nothing special to handle in the other cases. */
917 if (TREE_CODE (repl
) != ADDR_EXPR
)
919 addr_var
= TREE_OPERAND (repl
, 0);
921 while (TREE_CODE (*x
) == ARRAY_REF
922 || TREE_CODE (*x
) == COMPONENT_REF
923 || TREE_CODE (*x
) == BIT_FIELD_REF
)
924 x
= &TREE_OPERAND (*x
, 0);
926 if (TREE_CODE (*x
) != INDIRECT_REF
927 || TREE_OPERAND (*x
, 0) != var
)
931 if (TREE_TYPE (*x
) == TREE_TYPE (addr_var
))
934 mark_new_vars_to_rename (stmt
, vars_to_rename
);
938 /* Frontends sometimes produce expressions like *&a instead of a[0].
939 Create a temporary variable to handle this case. */
940 ass_stmt
= build2 (MODIFY_EXPR
, void_type_node
, NULL_TREE
, repl
);
941 new_var
= duplicate_ssa_name (var
, ass_stmt
);
942 TREE_OPERAND (*x
, 0) = new_var
;
943 TREE_OPERAND (ass_stmt
, 0) = new_var
;
945 bb
= bb_for_stmt (stmt
);
946 tree_block_label (bb
);
947 bsi
= bsi_after_labels (bb
);
948 bsi_insert_after (&bsi
, ass_stmt
, BSI_NEW_STMT
);
950 mark_new_vars_to_rename (stmt
, vars_to_rename
);
953 /* Replaces immediate uses of VAR by REPL. */
956 replace_immediate_uses (tree var
, tree repl
)
960 v_may_def_optype v_may_defs
;
967 df
= get_immediate_uses (SSA_NAME_DEF_STMT (var
));
968 n
= num_immediate_uses (df
);
970 for (i
= 0; i
< n
; i
++)
972 stmt
= immediate_use (df
, i
);
973 ann
= stmt_ann (stmt
);
975 if (TREE_CODE (stmt
) == PHI_NODE
)
977 for (j
= 0; j
< PHI_NUM_ARGS (stmt
); j
++)
978 if (PHI_ARG_DEF (stmt
, j
) == var
)
980 SET_PHI_ARG_DEF (stmt
, j
, repl
);
981 if (TREE_CODE (repl
) == SSA_NAME
982 && PHI_ARG_EDGE (stmt
, j
)->flags
& EDGE_ABNORMAL
)
983 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl
) = 1;
989 get_stmt_operands (stmt
);
990 mark_new_vars
= false;
991 if (is_gimple_reg (SSA_NAME_VAR (var
)))
993 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
995 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 0), repl
);
996 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 1), repl
);
999 uses
= USE_OPS (ann
);
1000 for (j
= 0; j
< (int) NUM_USES (uses
); j
++)
1001 if (USE_OP (uses
, j
) == var
)
1003 propagate_value (USE_OP_PTR (uses
, j
), repl
);
1004 mark_new_vars
= POINTER_TYPE_P (TREE_TYPE (repl
));
1009 vuses
= VUSE_OPS (ann
);
1010 for (j
= 0; j
< (int) NUM_VUSES (vuses
); j
++)
1011 if (VUSE_OP (vuses
, j
) == var
)
1012 propagate_value (VUSE_OP_PTR (vuses
, j
), repl
);
1014 v_may_defs
= V_MAY_DEF_OPS (ann
);
1015 for (j
= 0; j
< (int) NUM_V_MAY_DEFS (v_may_defs
); j
++)
1016 if (V_MAY_DEF_OP (v_may_defs
, j
) == var
)
1017 propagate_value (V_MAY_DEF_OP_PTR (v_may_defs
, j
), repl
);
1020 /* If REPL is a pointer, it may have different memory tags associated
1021 with it. For instance, VAR may have had a name tag while REPL
1022 only had a type tag. In these cases, the virtual operands (if
1023 any) in the statement will refer to different symbols which need
1026 mark_new_vars_to_rename (stmt
, vars_to_rename
);
1032 /* Gets the value VAR is equivalent to according to EQ_TO. */
1035 get_eq_name (tree
*eq_to
, tree var
)
1040 while (TREE_CODE (val
) == SSA_NAME
)
1042 ver
= SSA_NAME_VERSION (val
);
1049 while (TREE_CODE (var
) == SSA_NAME
)
1051 ver
= SSA_NAME_VERSION (var
);
1062 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1063 its result is redundant to to EQ_TO array. */
1066 check_phi_redundancy (tree phi
, tree
*eq_to
)
1068 tree val
= NULL_TREE
, def
, res
= PHI_RESULT (phi
), stmt
;
1069 unsigned i
, ver
= SSA_NAME_VERSION (res
), n
;
1072 /* It is unlikely that such large phi node would be redundant. */
1073 if (PHI_NUM_ARGS (phi
) > 16)
1076 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (phi
); i
++)
1078 def
= PHI_ARG_DEF (phi
, i
);
1080 if (TREE_CODE (def
) == SSA_NAME
)
1082 def
= get_eq_name (eq_to
, def
);
1088 && !operand_equal_p (val
, def
, 0))
1094 /* At least one of the arguments should not be equal to the result, or
1095 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
, /* 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 */
1216 /* Emit warnings for uninitialized variables. This is done in two passes.
1218 The first pass notices real uses of SSA names with default definitions.
1219 Such uses are unconditionally uninitialized, and we can be certain that
1220 such a use is a mistake. This pass is run before most optimizations,
1221 so that we catch as many as we can.
1223 The second pass follows PHI nodes to find uses that are potentially
1224 uninitialized. In this case we can't necessarily prove that the use
1225 is really uninitialized. This pass is run after most optimizations,
1226 so that we thread as many jumps and possible, and delete as much dead
1227 code as possible, in order to reduce false positives. We also look
1228 again for plain uninitialized variables, since optimization may have
1229 changed conditionally uninitialized to unconditionally uninitialized. */
1231 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1232 warning text is in MSGID and LOCUS may contain a location or be null. */
1235 warn_uninit (tree t
, const char *msgid
, location_t
*locus
)
1237 tree var
= SSA_NAME_VAR (t
);
1238 tree def
= SSA_NAME_DEF_STMT (t
);
1240 /* Default uses (indicated by an empty definition statement),
1241 are uninitialized. */
1242 if (!IS_EMPTY_STMT (def
))
1245 /* Except for PARMs of course, which are always initialized. */
1246 if (TREE_CODE (var
) == PARM_DECL
)
1249 /* Hard register variables get their initial value from the ether. */
1250 if (DECL_HARD_REGISTER (var
))
1253 /* TREE_NO_WARNING either means we already warned, or the front end
1254 wishes to suppress the warning. */
1255 if (TREE_NO_WARNING (var
))
1259 locus
= &DECL_SOURCE_LOCATION (var
);
1260 warning (msgid
, locus
, var
);
1261 TREE_NO_WARNING (var
) = 1;
1264 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1265 and warn about them. */
1268 warn_uninitialized_var (tree
*tp
, int *walk_subtrees
, void *data
)
1270 location_t
*locus
= data
;
1273 /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */
1274 if (TREE_CODE (t
) == SSA_NAME
)
1276 warn_uninit (t
, "%H'%D' is used uninitialized in this function", locus
);
1279 else if (DECL_P (t
) || TYPE_P (t
))
1285 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1286 and warn about them. */
1289 warn_uninitialized_phi (tree phi
)
1291 int i
, n
= PHI_NUM_ARGS (phi
);
1293 /* Don't look at memory tags. */
1294 if (!is_gimple_reg (PHI_RESULT (phi
)))
1297 for (i
= 0; i
< n
; ++i
)
1299 tree op
= PHI_ARG_DEF (phi
, i
);
1300 if (TREE_CODE (op
) == SSA_NAME
)
1301 warn_uninit (op
, "%H'%D' may be used uninitialized in this function",
1307 execute_early_warn_uninitialized (void)
1309 block_stmt_iterator bsi
;
1313 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1314 walk_tree (bsi_stmt_ptr (bsi
), warn_uninitialized_var
,
1315 EXPR_LOCUS (bsi_stmt (bsi
)), NULL
);
1319 execute_late_warn_uninitialized (void)
1324 /* Re-do the plain uninitialized variable check, as optimization may have
1325 straightened control flow. Do this first so that we don't accidentally
1326 get a "may be" warning when we'd have seen an "is" warning later. */
1327 execute_early_warn_uninitialized ();
1330 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1331 warn_uninitialized_phi (phi
);
1335 gate_warn_uninitialized (void)
1337 return warn_uninitialized
!= 0;
1340 struct tree_opt_pass pass_early_warn_uninitialized
=
1343 gate_warn_uninitialized
, /* gate */
1344 execute_early_warn_uninitialized
, /* execute */
1347 0, /* static_pass_number */
1349 PROP_ssa
, /* properties_required */
1350 0, /* properties_provided */
1351 0, /* properties_destroyed */
1352 0, /* todo_flags_start */
1353 0 /* todo_flags_finish */
1356 struct tree_opt_pass pass_late_warn_uninitialized
=
1359 gate_warn_uninitialized
, /* gate */
1360 execute_late_warn_uninitialized
, /* execute */
1363 0, /* static_pass_number */
1365 PROP_ssa
, /* properties_required */
1366 0, /* properties_provided */
1367 0, /* properties_destroyed */
1368 0, /* todo_flags_start */
1369 0 /* todo_flags_finish */