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 (TREE_TYPE (ssa_name
) != TREE_TYPE (SSA_NAME_VAR (ssa_name
)))
123 error ("Type mismatch between an SSA_NAME and its symbol.");
127 if (SSA_NAME_IN_FREE_LIST (ssa_name
))
129 error ("Found an SSA_NAME that had been released into the free pool");
133 if (is_virtual
&& is_gimple_reg (ssa_name
))
135 error ("Found a virtual definition for a GIMPLE register");
139 if (!is_virtual
&& !is_gimple_reg (ssa_name
))
141 error ("Found a real definition for a non-register");
149 /* Return true if the definition of SSA_NAME at block BB is malformed.
151 STMT is the statement where SSA_NAME is created.
153 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
154 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
155 it means that the block in that array slot contains the
156 definition of SSA_NAME.
158 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
162 verify_def (basic_block bb
, basic_block
*definition_block
, tree ssa_name
,
163 tree stmt
, bool is_virtual
)
165 if (verify_ssa_name (ssa_name
, is_virtual
))
168 if (definition_block
[SSA_NAME_VERSION (ssa_name
)])
170 error ("SSA_NAME created in two different blocks %i and %i",
171 definition_block
[SSA_NAME_VERSION (ssa_name
)]->index
, bb
->index
);
175 definition_block
[SSA_NAME_VERSION (ssa_name
)] = bb
;
177 if (SSA_NAME_DEF_STMT (ssa_name
) != stmt
)
179 error ("SSA_NAME_DEF_STMT is wrong");
180 fprintf (stderr
, "Expected definition statement:\n");
181 debug_generic_stmt (SSA_NAME_DEF_STMT (ssa_name
));
182 fprintf (stderr
, "\nActual definition statement:\n");
183 debug_generic_stmt (stmt
);
190 fprintf (stderr
, "while verifying SSA_NAME ");
191 print_generic_expr (stderr
, ssa_name
, 0);
192 fprintf (stderr
, " in statement\n");
193 debug_generic_stmt (stmt
);
199 /* Return true if the use of SSA_NAME at statement STMT in block BB is
202 DEF_BB is the block where SSA_NAME was found to be created.
204 IDOM contains immediate dominator information for the flowgraph.
206 CHECK_ABNORMAL is true if the caller wants to check whether this use
207 is flowing through an abnormal edge (only used when checking PHI
210 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
214 verify_use (basic_block bb
, basic_block def_bb
, tree ssa_name
,
215 tree stmt
, bool check_abnormal
, bool is_virtual
)
219 err
= verify_ssa_name (ssa_name
, is_virtual
);
221 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name
))
222 && var_ann (SSA_NAME_VAR (ssa_name
))->default_def
== ssa_name
)
223 ; /* Default definitions have empty statements. Nothing to do. */
226 error ("Missing definition");
229 else if (bb
!= def_bb
230 && !dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
232 error ("Definition in block %i does not dominate use in block %i",
233 def_bb
->index
, bb
->index
);
238 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name
))
240 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
246 fprintf (stderr
, "for SSA_NAME: ");
247 debug_generic_expr (ssa_name
);
248 fprintf (stderr
, "in statement:\n");
249 debug_generic_stmt (stmt
);
256 /* Return true if any of the arguments for PHI node PHI at block BB is
259 IDOM contains immediate dominator information for the flowgraph.
261 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
262 numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
263 block in that array slot contains the definition of SSA_NAME. */
266 verify_phi_args (tree phi
, basic_block bb
, basic_block
*definition_block
)
270 int i
, phi_num_args
= PHI_NUM_ARGS (phi
);
272 /* Mark all the incoming edges. */
273 FOR_EACH_EDGE (e
, bb
->preds
)
279 for (i
= 0; i
< phi_num_args
; i
++)
281 tree op
= PHI_ARG_DEF (phi
, i
);
283 e
= PHI_ARG_EDGE (phi
, i
);
285 if (TREE_CODE (op
) == SSA_NAME
)
286 err
= verify_use (e
->src
, definition_block
[SSA_NAME_VERSION (op
)], op
,
287 phi
, e
->flags
& EDGE_ABNORMAL
,
288 !is_gimple_reg (PHI_RESULT (phi
)));
292 error ("Wrong edge %d->%d for PHI argument\n",
293 e
->src
->index
, e
->dest
->index
, bb
->index
);
297 if (e
->aux
== (void *) 0)
299 error ("PHI argument flowing through dead edge %d->%d\n",
300 e
->src
->index
, e
->dest
->index
);
304 if (e
->aux
== (void *) 2)
306 error ("PHI argument duplicated for edge %d->%d\n", e
->src
->index
,
313 fprintf (stderr
, "PHI argument\n");
314 debug_generic_stmt (op
);
321 FOR_EACH_EDGE (e
, bb
->preds
)
323 if (e
->aux
!= (void *) 2)
325 error ("No argument flowing through edge %d->%d\n", e
->src
->index
,
337 fprintf (stderr
, "for PHI node\n");
338 debug_generic_stmt (phi
);
347 verify_flow_insensitive_alias_info (void)
351 bitmap visited
= BITMAP_XMALLOC ();
353 for (i
= 0; i
< num_referenced_vars
; i
++)
357 varray_type may_aliases
;
359 var
= referenced_var (i
);
361 may_aliases
= ann
->may_aliases
;
363 for (j
= 0; may_aliases
&& j
< VARRAY_ACTIVE_SIZE (may_aliases
); j
++)
365 tree alias
= VARRAY_TREE (may_aliases
, j
);
367 bitmap_set_bit (visited
, var_ann (alias
)->uid
);
369 if (!may_be_aliased (alias
))
371 error ("Non-addressable variable inside an alias set.");
372 debug_variable (alias
);
378 for (i
= 0; i
< num_referenced_vars
; i
++)
382 var
= referenced_var (i
);
385 if (ann
->mem_tag_kind
== NOT_A_TAG
387 && !bitmap_bit_p (visited
, ann
->uid
))
389 error ("Addressable variable that is an alias tag but is not in any alias set.");
394 BITMAP_XFREE (visited
);
398 debug_variable (var
);
399 internal_error ("verify_flow_insensitive_alias_info failed.");
404 verify_flow_sensitive_alias_info (void)
409 for (i
= 1; i
< num_ssa_names
; i
++)
412 struct ptr_info_def
*pi
;
415 ann
= var_ann (SSA_NAME_VAR (ptr
));
416 pi
= SSA_NAME_PTR_INFO (ptr
);
418 /* We only care for pointers that are actually referenced in the
420 if (!TREE_VISITED (ptr
) || !POINTER_TYPE_P (TREE_TYPE (ptr
)))
423 /* RESULT_DECL is special. If it's a GIMPLE register, then it
424 is only written-to only once in the return statement.
425 Otherwise, aggregate RESULT_DECLs may be written-to more than
426 once in virtual operands. */
427 if (TREE_CODE (SSA_NAME_VAR (ptr
)) == RESULT_DECL
428 && is_gimple_reg (ptr
))
434 if (pi
->is_dereferenced
&& !pi
->name_mem_tag
&& !ann
->type_mem_tag
)
436 error ("Dereferenced pointers should have a name or a type tag");
440 if (pi
->pt_anything
&& (pi
->pt_malloc
|| pi
->pt_vars
))
442 error ("Pointers that point to anything should not point to malloc or other vars");
446 if (pi
->pt_malloc
&& pi
->pt_vars
)
448 error ("Pointers pointing to malloc get a unique tag and cannot point to other vars");
454 && (pi
->pt_vars
== NULL
455 || bitmap_first_set_bit (pi
->pt_vars
) < 0))
457 error ("Pointers with a memory tag, should have points-to sets or point to malloc");
461 if (pi
->value_escapes_p
463 && !is_call_clobbered (pi
->name_mem_tag
))
465 error ("Pointer escapes but its name tag is not call-clobbered.");
469 if (pi
->name_mem_tag
&& pi
->pt_vars
)
473 for (j
= i
+ 1; j
< num_ssa_names
; j
++)
475 tree ptr2
= ssa_name (j
);
476 struct ptr_info_def
*pi2
= SSA_NAME_PTR_INFO (ptr2
);
478 if (!TREE_VISITED (ptr2
) || !POINTER_TYPE_P (TREE_TYPE (ptr2
)))
484 && bitmap_first_set_bit (pi2
->pt_vars
) >= 0
485 && pi
->name_mem_tag
!= pi2
->name_mem_tag
486 && bitmap_equal_p (pi
->pt_vars
, pi2
->pt_vars
))
488 error ("Two pointers with different name tags and identical points-to sets");
489 debug_variable (ptr2
);
499 debug_variable (ptr
);
500 internal_error ("verify_flow_sensitive_alias_info failed.");
504 /* Verify the consistency of aliasing information. */
507 verify_alias_info (void)
509 verify_flow_sensitive_alias_info ();
510 verify_flow_insensitive_alias_info ();
514 /* Verify common invariants in the SSA web.
515 TODO: verify the variable annotations. */
522 basic_block
*definition_block
= xcalloc (num_ssa_names
, sizeof (basic_block
));
524 timevar_push (TV_TREE_SSA_VERIFY
);
526 /* Keep track of SSA names present in the IL. */
527 for (i
= 1; i
< num_ssa_names
; i
++)
528 TREE_VISITED (ssa_name (i
)) = 0;
530 calculate_dominance_info (CDI_DOMINATORS
);
532 /* Verify and register all the SSA_NAME definitions found in the
537 block_stmt_iterator bsi
;
539 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
540 if (verify_def (bb
, definition_block
, PHI_RESULT (phi
), phi
,
541 !is_gimple_reg (PHI_RESULT (phi
))))
544 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
549 v_may_def_optype v_may_defs
;
550 v_must_def_optype v_must_defs
;
553 stmt
= bsi_stmt (bsi
);
554 ann
= stmt_ann (stmt
);
555 get_stmt_operands (stmt
);
557 v_may_defs
= V_MAY_DEF_OPS (ann
);
558 if (ann
->makes_aliased_stores
&& NUM_V_MAY_DEFS (v_may_defs
) == 0)
560 error ("Statement makes aliased stores, but has no V_MAY_DEFS");
561 debug_generic_stmt (stmt
);
565 for (j
= 0; j
< NUM_V_MAY_DEFS (v_may_defs
); j
++)
567 tree op
= V_MAY_DEF_RESULT (v_may_defs
, j
);
568 if (verify_def (bb
, definition_block
, op
, stmt
, true))
572 v_must_defs
= STMT_V_MUST_DEF_OPS (stmt
);
573 for (j
= 0; j
< NUM_V_MUST_DEFS (v_must_defs
); j
++)
575 tree op
= V_MUST_DEF_OP (v_must_defs
, j
);
576 if (verify_def (bb
, definition_block
, op
, stmt
, true))
580 defs
= DEF_OPS (ann
);
581 for (j
= 0; j
< NUM_DEFS (defs
); j
++)
583 tree op
= DEF_OP (defs
, j
);
584 if (verify_def (bb
, definition_block
, op
, stmt
, false))
591 /* Now verify all the uses and make sure they agree with the definitions
592 found in the previous pass. */
597 block_stmt_iterator bsi
;
599 /* Make sure that all edges have a clear 'aux' field. */
600 FOR_EACH_EDGE (e
, bb
->preds
)
604 error ("AUX pointer initialized for edge %d->%d\n", e
->src
->index
,
611 /* Verify the arguments for every PHI node in the block. */
612 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
613 if (verify_phi_args (phi
, bb
, definition_block
))
616 /* Now verify all the uses and vuses in every statement of the block. */
617 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
619 tree stmt
= bsi_stmt (bsi
);
620 stmt_ann_t ann
= stmt_ann (stmt
);
623 v_may_def_optype v_may_defs
;
626 vuses
= VUSE_OPS (ann
);
627 for (j
= 0; j
< NUM_VUSES (vuses
); j
++)
629 tree op
= VUSE_OP (vuses
, j
);
630 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
631 op
, stmt
, false, true))
635 v_may_defs
= V_MAY_DEF_OPS (ann
);
636 for (j
= 0; j
< NUM_V_MAY_DEFS (v_may_defs
); j
++)
638 tree op
= V_MAY_DEF_OP (v_may_defs
, j
);
639 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
640 op
, stmt
, false, true))
644 uses
= USE_OPS (ann
);
645 for (j
= 0; j
< NUM_USES (uses
); j
++)
647 tree op
= USE_OP (uses
, j
);
648 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
649 op
, stmt
, false, false))
655 /* Finally, verify alias information. */
656 verify_alias_info ();
658 free (definition_block
);
659 timevar_pop (TV_TREE_SSA_VERIFY
);
663 internal_error ("verify_ssa failed.");
667 /* Initialize global DFA and SSA structures. */
672 VARRAY_TREE_INIT (referenced_vars
, 20, "referenced_vars");
673 call_clobbered_vars
= BITMAP_XMALLOC ();
674 addressable_vars
= BITMAP_XMALLOC ();
675 init_ssa_operands ();
678 global_var
= NULL_TREE
;
682 /* Deallocate memory associated with SSA data structures for FNDECL. */
685 delete_tree_ssa (void)
689 block_stmt_iterator bsi
;
691 /* Remove annotations from every tree in the function. */
693 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
694 bsi_stmt (bsi
)->common
.ann
= NULL
;
696 /* Remove annotations from every referenced variable. */
699 for (i
= 0; i
< num_referenced_vars
; i
++)
700 referenced_var (i
)->common
.ann
= NULL
;
701 referenced_vars
= NULL
;
706 fini_ssa_operands ();
708 global_var
= NULL_TREE
;
709 BITMAP_XFREE (call_clobbered_vars
);
710 call_clobbered_vars
= NULL
;
711 BITMAP_XFREE (addressable_vars
);
712 addressable_vars
= NULL
;
716 /* Return true if EXPR is a useless type conversion, otherwise return
720 tree_ssa_useless_type_conversion_1 (tree outer_type
, tree inner_type
)
722 /* If the inner and outer types are effectively the same, then
723 strip the type conversion and enter the equivalence into
725 if (inner_type
== outer_type
726 || (lang_hooks
.types_compatible_p (inner_type
, outer_type
)))
729 /* If both types are pointers and the outer type is a (void *), then
730 the conversion is not necessary. The opposite is not true since
731 that conversion would result in a loss of information if the
732 equivalence was used. Consider an indirect function call where
733 we need to know the exact type of the function to correctly
734 implement the ABI. */
735 else if (POINTER_TYPE_P (inner_type
)
736 && POINTER_TYPE_P (outer_type
)
737 && TREE_CODE (TREE_TYPE (outer_type
)) == VOID_TYPE
)
740 /* Pointers and references are equivalent once we get to GENERIC,
741 so strip conversions that just switch between them. */
742 else if (POINTER_TYPE_P (inner_type
)
743 && POINTER_TYPE_P (outer_type
)
744 && lang_hooks
.types_compatible_p (TREE_TYPE (inner_type
),
745 TREE_TYPE (outer_type
)))
748 /* If both the inner and outer types are integral types, then the
749 conversion is not necessary if they have the same mode and
750 signedness and precision, and both or neither are boolean. Some
751 code assumes an invariant that boolean types stay boolean and do
752 not become 1-bit bit-field types. Note that types with precision
753 not using all bits of the mode (such as bit-field types in C)
754 mean that testing of precision is necessary. */
755 else if (INTEGRAL_TYPE_P (inner_type
)
756 && INTEGRAL_TYPE_P (outer_type
)
757 && TYPE_MODE (inner_type
) == TYPE_MODE (outer_type
)
758 && TYPE_UNSIGNED (inner_type
) == TYPE_UNSIGNED (outer_type
)
759 && TYPE_PRECISION (inner_type
) == TYPE_PRECISION (outer_type
))
761 bool first_boolean
= (TREE_CODE (inner_type
) == BOOLEAN_TYPE
);
762 bool second_boolean
= (TREE_CODE (outer_type
) == BOOLEAN_TYPE
);
763 if (first_boolean
== second_boolean
)
767 /* Recurse for complex types. */
768 else if (TREE_CODE (inner_type
) == COMPLEX_TYPE
769 && TREE_CODE (outer_type
) == COMPLEX_TYPE
770 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type
),
771 TREE_TYPE (inner_type
)))
777 /* Return true if EXPR is a useless type conversion, otherwise return
781 tree_ssa_useless_type_conversion (tree expr
)
783 /* If we have an assignment that merely uses a NOP_EXPR to change
784 the top of the RHS to the type of the LHS and the type conversion
785 is "safe", then strip away the type conversion so that we can
786 enter LHS = RHS into the const_and_copies table. */
787 if (TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
788 || TREE_CODE (expr
) == VIEW_CONVERT_EXPR
789 || TREE_CODE (expr
) == NON_LVALUE_EXPR
)
790 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr
),
791 TREE_TYPE (TREE_OPERAND (expr
,
799 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
800 described in walk_use_def_chains.
802 VISITED is a bitmap used to mark visited SSA_NAMEs to avoid
805 IS_DFS is true if the caller wants to perform a depth-first search
806 when visiting PHI nodes. A DFS will visit each PHI argument and
807 call FN after each one. Otherwise, all the arguments are
808 visited first and then FN is called with each of the visited
809 arguments in a separate pass. */
812 walk_use_def_chains_1 (tree var
, walk_use_def_chains_fn fn
, void *data
,
813 bitmap visited
, bool is_dfs
)
817 if (bitmap_bit_p (visited
, SSA_NAME_VERSION (var
)))
820 bitmap_set_bit (visited
, SSA_NAME_VERSION (var
));
822 def_stmt
= SSA_NAME_DEF_STMT (var
);
824 if (TREE_CODE (def_stmt
) != PHI_NODE
)
826 /* If we reached the end of the use-def chain, call FN. */
827 return fn (var
, def_stmt
, data
);
833 /* When doing a breadth-first search, call FN before following the
834 use-def links for each argument. */
836 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
837 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
840 /* Follow use-def links out of each PHI argument. */
841 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
843 tree arg
= PHI_ARG_DEF (def_stmt
, i
);
844 if (TREE_CODE (arg
) == SSA_NAME
845 && walk_use_def_chains_1 (arg
, fn
, data
, visited
, is_dfs
))
849 /* When doing a depth-first search, call FN after following the
850 use-def links for each argument. */
852 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
853 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
862 /* Walk use-def chains starting at the SSA variable VAR. Call
863 function FN at each reaching definition found. FN takes three
864 arguments: VAR, its defining statement (DEF_STMT) and a generic
865 pointer to whatever state information that FN may want to maintain
866 (DATA). FN is able to stop the walk by returning true, otherwise
867 in order to continue the walk, FN should return false.
869 Note, that if DEF_STMT is a PHI node, the semantics are slightly
870 different. The first argument to FN is no longer the original
871 variable VAR, but the PHI argument currently being examined. If FN
872 wants to get at VAR, it should call PHI_RESULT (PHI).
874 If IS_DFS is true, this function will:
876 1- walk the use-def chains for all the PHI arguments, and,
877 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
879 If IS_DFS is false, the two steps above are done in reverse order
880 (i.e., a breadth-first search). */
884 walk_use_def_chains (tree var
, walk_use_def_chains_fn fn
, void *data
,
889 #if defined ENABLE_CHECKING
890 if (TREE_CODE (var
) != SSA_NAME
)
894 def_stmt
= SSA_NAME_DEF_STMT (var
);
896 /* We only need to recurse if the reaching definition comes from a PHI
898 if (TREE_CODE (def_stmt
) != PHI_NODE
)
899 (*fn
) (var
, def_stmt
, data
);
902 bitmap visited
= BITMAP_XMALLOC ();
903 walk_use_def_chains_1 (var
, fn
, data
, visited
, is_dfs
);
904 BITMAP_XFREE (visited
);
909 /* Replaces VAR with REPL in memory reference expression *X in
913 propagate_into_addr (tree stmt
, tree var
, tree
*x
, tree repl
)
915 tree new_var
, ass_stmt
, addr_var
;
917 block_stmt_iterator bsi
;
919 /* There is nothing special to handle in the other cases. */
920 if (TREE_CODE (repl
) != ADDR_EXPR
)
922 addr_var
= TREE_OPERAND (repl
, 0);
924 while (TREE_CODE (*x
) == ARRAY_REF
925 || TREE_CODE (*x
) == COMPONENT_REF
926 || TREE_CODE (*x
) == BIT_FIELD_REF
)
927 x
= &TREE_OPERAND (*x
, 0);
929 if (TREE_CODE (*x
) != INDIRECT_REF
930 || TREE_OPERAND (*x
, 0) != var
)
934 if (TREE_TYPE (*x
) == TREE_TYPE (addr_var
))
937 mark_new_vars_to_rename (stmt
, vars_to_rename
);
941 /* Frontends sometimes produce expressions like *&a instead of a[0].
942 Create a temporary variable to handle this case. */
943 ass_stmt
= build2 (MODIFY_EXPR
, void_type_node
, NULL_TREE
, repl
);
944 new_var
= duplicate_ssa_name (var
, ass_stmt
);
945 TREE_OPERAND (*x
, 0) = new_var
;
946 TREE_OPERAND (ass_stmt
, 0) = new_var
;
948 bb
= bb_for_stmt (stmt
);
949 tree_block_label (bb
);
950 bsi
= bsi_after_labels (bb
);
951 bsi_insert_after (&bsi
, ass_stmt
, BSI_NEW_STMT
);
953 mark_new_vars_to_rename (stmt
, vars_to_rename
);
956 /* Replaces immediate uses of VAR by REPL. */
959 replace_immediate_uses (tree var
, tree repl
)
963 v_may_def_optype v_may_defs
;
970 df
= get_immediate_uses (SSA_NAME_DEF_STMT (var
));
971 n
= num_immediate_uses (df
);
973 for (i
= 0; i
< n
; i
++)
975 stmt
= immediate_use (df
, i
);
976 ann
= stmt_ann (stmt
);
978 if (TREE_CODE (stmt
) == PHI_NODE
)
980 for (j
= 0; j
< PHI_NUM_ARGS (stmt
); j
++)
981 if (PHI_ARG_DEF (stmt
, j
) == var
)
983 SET_PHI_ARG_DEF (stmt
, j
, repl
);
984 if (TREE_CODE (repl
) == SSA_NAME
985 && PHI_ARG_EDGE (stmt
, j
)->flags
& EDGE_ABNORMAL
)
986 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl
) = 1;
992 get_stmt_operands (stmt
);
993 mark_new_vars
= false;
994 if (is_gimple_reg (SSA_NAME_VAR (var
)))
996 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
998 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 0), repl
);
999 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 1), repl
);
1002 uses
= USE_OPS (ann
);
1003 for (j
= 0; j
< (int) NUM_USES (uses
); j
++)
1004 if (USE_OP (uses
, j
) == var
)
1006 propagate_value (USE_OP_PTR (uses
, j
), repl
);
1007 mark_new_vars
= POINTER_TYPE_P (TREE_TYPE (repl
));
1012 vuses
= VUSE_OPS (ann
);
1013 for (j
= 0; j
< (int) NUM_VUSES (vuses
); j
++)
1014 if (VUSE_OP (vuses
, j
) == var
)
1015 propagate_value (VUSE_OP_PTR (vuses
, j
), repl
);
1017 v_may_defs
= V_MAY_DEF_OPS (ann
);
1018 for (j
= 0; j
< (int) NUM_V_MAY_DEFS (v_may_defs
); j
++)
1019 if (V_MAY_DEF_OP (v_may_defs
, j
) == var
)
1020 propagate_value (V_MAY_DEF_OP_PTR (v_may_defs
, j
), repl
);
1023 /* If REPL is a pointer, it may have different memory tags associated
1024 with it. For instance, VAR may have had a name tag while REPL
1025 only had a type tag. In these cases, the virtual operands (if
1026 any) in the statement will refer to different symbols which need
1029 mark_new_vars_to_rename (stmt
, vars_to_rename
);
1035 /* Gets the value VAR is equivalent to according to EQ_TO. */
1038 get_eq_name (tree
*eq_to
, tree var
)
1043 while (TREE_CODE (val
) == SSA_NAME
)
1045 ver
= SSA_NAME_VERSION (val
);
1052 while (TREE_CODE (var
) == SSA_NAME
)
1054 ver
= SSA_NAME_VERSION (var
);
1065 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1066 its result is redundant to to EQ_TO array. */
1069 check_phi_redundancy (tree phi
, tree
*eq_to
)
1071 tree val
= NULL_TREE
, def
, res
= PHI_RESULT (phi
), stmt
;
1072 unsigned i
, ver
= SSA_NAME_VERSION (res
), n
;
1075 /* It is unlikely that such large phi node would be redundant. */
1076 if (PHI_NUM_ARGS (phi
) > 16)
1079 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (phi
); i
++)
1081 def
= PHI_ARG_DEF (phi
, i
);
1083 if (TREE_CODE (def
) == SSA_NAME
)
1085 def
= get_eq_name (eq_to
, def
);
1091 && !operand_equal_p (val
, def
, 0))
1097 /* At least one of the arguments should not be equal to the result, or
1098 something strange is happening. */
1102 if (get_eq_name (eq_to
, res
) == val
)
1105 if (!may_propagate_copy (res
, val
))
1110 df
= get_immediate_uses (SSA_NAME_DEF_STMT (res
));
1111 n
= num_immediate_uses (df
);
1113 for (i
= 0; i
< n
; i
++)
1115 stmt
= immediate_use (df
, i
);
1117 if (TREE_CODE (stmt
) == PHI_NODE
)
1118 check_phi_redundancy (stmt
, eq_to
);
1122 /* Removes redundant phi nodes.
1124 A redundant PHI node is a PHI node where all of its PHI arguments
1125 are the same value, excluding any PHI arguments which are the same
1128 A redundant PHI node is effectively a copy, so we forward copy propagate
1129 which removes all uses of the destination of the PHI node then
1130 finally we delete the redundant PHI node.
1132 Note that if we can not copy propagate the PHI node, then the PHI
1133 will not be removed. Thus we do not have to worry about dependencies
1134 between PHIs and the problems serializing PHIs into copies creates.
1136 The most important effect of this pass is to remove degenerate PHI
1137 nodes created by removing unreachable code. */
1140 kill_redundant_phi_nodes (void)
1143 unsigned i
, old_num_ssa_names
;
1145 tree phi
, var
, repl
, stmt
;
1147 /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1148 replaced. If EQ_TO[VER] is ssa name and it is decided to replace it by
1149 other value, it may be necessary to follow the chain till the final value.
1150 We perform path shortening (replacing the entries of the EQ_TO array with
1151 heads of these chains) whenever we access the field to prevent quadratic
1152 complexity (probably would not occur in practice anyway, but let us play
1154 eq_to
= xcalloc (num_ssa_names
, sizeof (tree
));
1156 /* We have had cases where computing immediate uses takes a
1157 significant amount of compile time. If we run into such
1158 problems here, we may want to only compute immediate uses for
1159 a subset of all the SSA_NAMEs instead of computing it for
1160 all of the SSA_NAMEs. */
1161 compute_immediate_uses (TDFA_USE_OPS
| TDFA_USE_VOPS
, NULL
);
1162 old_num_ssa_names
= num_ssa_names
;
1166 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
1168 var
= PHI_RESULT (phi
);
1169 check_phi_redundancy (phi
, eq_to
);
1173 /* Now propagate the values. */
1174 for (i
= 0; i
< old_num_ssa_names
; i
++)
1179 repl
= get_eq_name (eq_to
, ssa_name (i
));
1180 if (repl
!= ssa_name (i
))
1181 replace_immediate_uses (ssa_name (i
), repl
);
1184 /* And remove the dead phis. */
1185 for (i
= 0; i
< old_num_ssa_names
; i
++)
1190 repl
= get_eq_name (eq_to
, ssa_name (i
));
1191 if (repl
!= ssa_name (i
))
1193 stmt
= SSA_NAME_DEF_STMT (ssa_name (i
));
1194 remove_phi_node (stmt
, NULL_TREE
, bb_for_stmt (stmt
));
1202 struct tree_opt_pass pass_redundant_phi
=
1204 "redphi", /* name */
1206 kill_redundant_phi_nodes
, /* execute */
1209 0, /* static_pass_number */
1211 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
1212 0, /* properties_provided */
1213 0, /* properties_destroyed */
1214 0, /* todo_flags_start */
1215 TODO_dump_func
| TODO_rename_vars
1216 | TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */
1219 /* Emit warnings for uninitialized variables. This is done in two passes.
1221 The first pass notices real uses of SSA names with default definitions.
1222 Such uses are unconditionally uninitialized, and we can be certain that
1223 such a use is a mistake. This pass is run before most optimizations,
1224 so that we catch as many as we can.
1226 The second pass follows PHI nodes to find uses that are potentially
1227 uninitialized. In this case we can't necessarily prove that the use
1228 is really uninitialized. This pass is run after most optimizations,
1229 so that we thread as many jumps and possible, and delete as much dead
1230 code as possible, in order to reduce false positives. We also look
1231 again for plain uninitialized variables, since optimization may have
1232 changed conditionally uninitialized to unconditionally uninitialized. */
1234 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1235 warning text is in MSGID and LOCUS may contain a location or be null. */
1238 warn_uninit (tree t
, const char *msgid
, location_t
*locus
)
1240 tree var
= SSA_NAME_VAR (t
);
1241 tree def
= SSA_NAME_DEF_STMT (t
);
1243 /* Default uses (indicated by an empty definition statement),
1244 are uninitialized. */
1245 if (!IS_EMPTY_STMT (def
))
1248 /* Except for PARMs of course, which are always initialized. */
1249 if (TREE_CODE (var
) == PARM_DECL
)
1252 /* Hard register variables get their initial value from the ether. */
1253 if (DECL_HARD_REGISTER (var
))
1256 /* TREE_NO_WARNING either means we already warned, or the front end
1257 wishes to suppress the warning. */
1258 if (TREE_NO_WARNING (var
))
1262 locus
= &DECL_SOURCE_LOCATION (var
);
1263 warning (msgid
, locus
, var
);
1264 TREE_NO_WARNING (var
) = 1;
1267 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1268 and warn about them. */
1271 warn_uninitialized_var (tree
*tp
, int *walk_subtrees
, void *data
)
1273 location_t
*locus
= data
;
1276 /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */
1277 if (TREE_CODE (t
) == SSA_NAME
)
1279 warn_uninit (t
, "%H'%D' is used uninitialized in this function", locus
);
1282 else if (DECL_P (t
) || TYPE_P (t
))
1288 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1289 and warn about them. */
1292 warn_uninitialized_phi (tree phi
)
1294 int i
, n
= PHI_NUM_ARGS (phi
);
1296 /* Don't look at memory tags. */
1297 if (!is_gimple_reg (PHI_RESULT (phi
)))
1300 for (i
= 0; i
< n
; ++i
)
1302 tree op
= PHI_ARG_DEF (phi
, i
);
1303 if (TREE_CODE (op
) == SSA_NAME
)
1304 warn_uninit (op
, "%H'%D' may be used uninitialized in this function",
1310 execute_early_warn_uninitialized (void)
1312 block_stmt_iterator bsi
;
1316 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1317 walk_tree (bsi_stmt_ptr (bsi
), warn_uninitialized_var
,
1318 EXPR_LOCUS (bsi_stmt (bsi
)), NULL
);
1322 execute_late_warn_uninitialized (void)
1327 /* Re-do the plain uninitialized variable check, as optimization may have
1328 straightened control flow. Do this first so that we don't accidentally
1329 get a "may be" warning when we'd have seen an "is" warning later. */
1330 execute_early_warn_uninitialized ();
1333 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1334 warn_uninitialized_phi (phi
);
1338 gate_warn_uninitialized (void)
1340 return warn_uninitialized
!= 0;
1343 struct tree_opt_pass pass_early_warn_uninitialized
=
1346 gate_warn_uninitialized
, /* gate */
1347 execute_early_warn_uninitialized
, /* execute */
1350 0, /* static_pass_number */
1352 PROP_ssa
, /* properties_required */
1353 0, /* properties_provided */
1354 0, /* properties_destroyed */
1355 0, /* todo_flags_start */
1356 0 /* todo_flags_finish */
1359 struct tree_opt_pass pass_late_warn_uninitialized
=
1362 gate_warn_uninitialized
, /* gate */
1363 execute_late_warn_uninitialized
, /* execute */
1366 0, /* static_pass_number */
1368 PROP_ssa
, /* properties_required */
1369 0, /* properties_provided */
1370 0, /* properties_destroyed */
1371 0, /* todo_flags_start */
1372 0 /* todo_flags_finish */