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 print_generic_stmt (stderr
, SSA_NAME_DEF_STMT (ssa_name
), TDF_VOPS
);
181 fprintf (stderr
, "\nActual definition statement:\n");
182 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
189 fprintf (stderr
, "while verifying SSA_NAME ");
190 print_generic_expr (stderr
, ssa_name
, 0);
191 fprintf (stderr
, " in statement\n");
192 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
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 print_generic_expr (stderr
, ssa_name
, TDF_VOPS
);
258 fprintf (stderr
, "in statement:\n");
259 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
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 print_generic_stmt (stderr
, op
, TDF_VOPS
);
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 print_generic_stmt (stderr
, phi
, TDF_VOPS
);
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
;
424 ann
= var_ann (SSA_NAME_VAR (ptr
));
425 pi
= SSA_NAME_PTR_INFO (ptr
);
427 /* We only care for pointers that are actually referenced in the
429 if (!TREE_VISITED (ptr
) || !POINTER_TYPE_P (TREE_TYPE (ptr
)))
432 /* RESULT_DECL is special. If it's a GIMPLE register, then it
433 is only written-to only once in the return statement.
434 Otherwise, aggregate RESULT_DECLs may be written-to more than
435 once in virtual operands. */
436 if (TREE_CODE (SSA_NAME_VAR (ptr
)) == RESULT_DECL
437 && is_gimple_reg (ptr
))
443 if (pi
->is_dereferenced
&& !pi
->name_mem_tag
&& !ann
->type_mem_tag
)
445 error ("Dereferenced pointers should have a name or a type tag");
451 && (pi
->pt_vars
== NULL
452 || bitmap_first_set_bit (pi
->pt_vars
) < 0))
454 error ("Pointers with a memory tag, should have points-to sets or point to malloc");
458 if (pi
->value_escapes_p
460 && !is_call_clobbered (pi
->name_mem_tag
))
462 error ("Pointer escapes but its name tag is not call-clobbered.");
466 if (pi
->name_mem_tag
&& pi
->pt_vars
)
470 for (j
= i
+ 1; j
< num_ssa_names
; j
++)
473 tree ptr2
= ssa_name (j
);
474 struct ptr_info_def
*pi2
= SSA_NAME_PTR_INFO (ptr2
);
476 if (!TREE_VISITED (ptr2
) || !POINTER_TYPE_P (TREE_TYPE (ptr2
)))
482 && bitmap_first_set_bit (pi2
->pt_vars
) >= 0
483 && pi
->name_mem_tag
!= pi2
->name_mem_tag
484 && bitmap_equal_p (pi
->pt_vars
, pi2
->pt_vars
))
486 error ("Two pointers with different name tags and identical points-to sets");
487 debug_variable (ptr2
);
497 debug_variable (ptr
);
498 internal_error ("verify_flow_sensitive_alias_info failed.");
502 /* Verify the consistency of aliasing information. */
505 verify_alias_info (void)
507 verify_flow_sensitive_alias_info ();
508 verify_flow_insensitive_alias_info ();
512 /* Verify common invariants in the SSA web.
513 TODO: verify the variable annotations. */
520 basic_block
*definition_block
= xcalloc (num_ssa_names
, sizeof (basic_block
));
523 enum dom_state orig_dom_state
= dom_computed
[CDI_DOMINATORS
];
524 bitmap names_defined_in_bb
= BITMAP_XMALLOC ();
526 timevar_push (TV_TREE_SSA_VERIFY
);
528 /* Keep track of SSA names present in the IL. */
529 for (i
= 1; i
< num_ssa_names
; i
++)
531 TREE_VISITED (ssa_name (i
)) = 0;
533 calculate_dominance_info (CDI_DOMINATORS
);
535 /* Verify and register all the SSA_NAME definitions found in the
540 block_stmt_iterator bsi
;
542 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
543 if (verify_def (bb
, definition_block
, PHI_RESULT (phi
), phi
,
544 !is_gimple_reg (PHI_RESULT (phi
))))
547 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
551 stmt
= bsi_stmt (bsi
);
552 get_stmt_operands (stmt
);
554 if (stmt_ann (stmt
)->makes_aliased_stores
555 && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt
)) == 0)
557 error ("Statement makes aliased stores, but has no V_MAY_DEFS");
558 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
562 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
564 if (verify_def (bb
, definition_block
, op
, stmt
, true))
568 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
570 if (verify_def (bb
, definition_block
, op
, stmt
, false))
577 /* Now verify all the uses and make sure they agree with the definitions
578 found in the previous pass. */
583 block_stmt_iterator bsi
;
585 /* Make sure that all edges have a clear 'aux' field. */
586 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
590 error ("AUX pointer initialized for edge %d->%d\n", e
->src
->index
,
596 /* Verify the arguments for every PHI node in the block. */
597 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
599 if (verify_phi_args (phi
, bb
, definition_block
))
601 bitmap_set_bit (names_defined_in_bb
,
602 SSA_NAME_VERSION (PHI_RESULT (phi
)));
605 /* Now verify all the uses and vuses in every statement of the block. */
606 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
608 tree stmt
= bsi_stmt (bsi
);
610 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
612 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
613 op
, stmt
, false, true,
614 names_defined_in_bb
))
618 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
620 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
621 op
, stmt
, false, false,
622 names_defined_in_bb
))
626 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_ALL_DEFS
)
628 bitmap_set_bit (names_defined_in_bb
, SSA_NAME_VERSION (op
));
632 /* Verify the uses in arguments of PHI nodes at the exits from the
634 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
636 for (phi
= phi_nodes (e
->dest
); phi
; phi
= PHI_CHAIN (phi
))
638 bool virtual = !is_gimple_reg (PHI_RESULT (phi
));
639 op
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
640 if (TREE_CODE (op
) != SSA_NAME
)
643 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
644 op
, phi
, false, virtual,
645 names_defined_in_bb
))
650 bitmap_clear (names_defined_in_bb
);
653 /* Finally, verify alias information. */
654 verify_alias_info ();
656 free (definition_block
);
657 /* Restore the dominance information to its prior known state, so
658 that we do not perturb the compiler's subsequent behavior. */
659 if (orig_dom_state
== DOM_NONE
)
660 free_dominance_info (CDI_DOMINATORS
);
662 dom_computed
[CDI_DOMINATORS
] = orig_dom_state
;
664 BITMAP_XFREE (names_defined_in_bb
);
665 timevar_pop (TV_TREE_SSA_VERIFY
);
669 internal_error ("verify_ssa failed.");
673 /* Initialize global DFA and SSA structures. */
678 VARRAY_TREE_INIT (referenced_vars
, 20, "referenced_vars");
679 call_clobbered_vars
= BITMAP_XMALLOC ();
680 addressable_vars
= BITMAP_XMALLOC ();
681 init_ssa_operands ();
684 global_var
= NULL_TREE
;
688 /* Deallocate memory associated with SSA data structures for FNDECL. */
691 delete_tree_ssa (void)
695 block_stmt_iterator bsi
;
697 /* Remove annotations from every tree in the function. */
699 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
701 tree stmt
= bsi_stmt (bsi
);
703 ggc_free (stmt
->common
.ann
);
704 stmt
->common
.ann
= NULL
;
707 /* Remove annotations from every referenced variable. */
710 for (i
= 0; i
< num_referenced_vars
; i
++)
712 tree var
= referenced_var (i
);
713 ggc_free (var
->common
.ann
);
714 var
->common
.ann
= NULL
;
716 referenced_vars
= NULL
;
721 fini_ssa_operands ();
723 global_var
= NULL_TREE
;
724 BITMAP_XFREE (call_clobbered_vars
);
725 call_clobbered_vars
= NULL
;
726 BITMAP_XFREE (addressable_vars
);
727 addressable_vars
= NULL
;
731 /* Return true if EXPR is a useless type conversion, otherwise return
735 tree_ssa_useless_type_conversion_1 (tree outer_type
, tree inner_type
)
737 /* If the inner and outer types are effectively the same, then
738 strip the type conversion and enter the equivalence into
740 if (inner_type
== outer_type
741 || (lang_hooks
.types_compatible_p (inner_type
, outer_type
)))
744 /* If both types are pointers and the outer type is a (void *), then
745 the conversion is not necessary. The opposite is not true since
746 that conversion would result in a loss of information if the
747 equivalence was used. Consider an indirect function call where
748 we need to know the exact type of the function to correctly
749 implement the ABI. */
750 else if (POINTER_TYPE_P (inner_type
)
751 && POINTER_TYPE_P (outer_type
)
752 && TREE_CODE (TREE_TYPE (outer_type
)) == VOID_TYPE
)
755 /* Pointers and references are equivalent once we get to GENERIC,
756 so strip conversions that just switch between them. */
757 else if (POINTER_TYPE_P (inner_type
)
758 && POINTER_TYPE_P (outer_type
)
759 && lang_hooks
.types_compatible_p (TREE_TYPE (inner_type
),
760 TREE_TYPE (outer_type
)))
763 /* If both the inner and outer types are integral types, then the
764 conversion is not necessary if they have the same mode and
765 signedness and precision, and both or neither are boolean. Some
766 code assumes an invariant that boolean types stay boolean and do
767 not become 1-bit bit-field types. Note that types with precision
768 not using all bits of the mode (such as bit-field types in C)
769 mean that testing of precision is necessary. */
770 else if (INTEGRAL_TYPE_P (inner_type
)
771 && INTEGRAL_TYPE_P (outer_type
)
772 && TYPE_MODE (inner_type
) == TYPE_MODE (outer_type
)
773 && TYPE_UNSIGNED (inner_type
) == TYPE_UNSIGNED (outer_type
)
774 && TYPE_PRECISION (inner_type
) == TYPE_PRECISION (outer_type
))
776 bool first_boolean
= (TREE_CODE (inner_type
) == BOOLEAN_TYPE
);
777 bool second_boolean
= (TREE_CODE (outer_type
) == BOOLEAN_TYPE
);
778 if (first_boolean
== second_boolean
)
782 /* Recurse for complex types. */
783 else if (TREE_CODE (inner_type
) == COMPLEX_TYPE
784 && TREE_CODE (outer_type
) == COMPLEX_TYPE
785 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type
),
786 TREE_TYPE (inner_type
)))
792 /* Return true if EXPR is a useless type conversion, otherwise return
796 tree_ssa_useless_type_conversion (tree expr
)
798 /* If we have an assignment that merely uses a NOP_EXPR to change
799 the top of the RHS to the type of the LHS and the type conversion
800 is "safe", then strip away the type conversion so that we can
801 enter LHS = RHS into the const_and_copies table. */
802 if (TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
803 || TREE_CODE (expr
) == VIEW_CONVERT_EXPR
804 || TREE_CODE (expr
) == NON_LVALUE_EXPR
)
805 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr
),
806 TREE_TYPE (TREE_OPERAND (expr
,
814 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
815 described in walk_use_def_chains.
817 VISITED is a bitmap used to mark visited SSA_NAMEs to avoid
820 IS_DFS is true if the caller wants to perform a depth-first search
821 when visiting PHI nodes. A DFS will visit each PHI argument and
822 call FN after each one. Otherwise, all the arguments are
823 visited first and then FN is called with each of the visited
824 arguments in a separate pass. */
827 walk_use_def_chains_1 (tree var
, walk_use_def_chains_fn fn
, void *data
,
828 bitmap visited
, bool is_dfs
)
832 if (bitmap_bit_p (visited
, SSA_NAME_VERSION (var
)))
835 bitmap_set_bit (visited
, SSA_NAME_VERSION (var
));
837 def_stmt
= SSA_NAME_DEF_STMT (var
);
839 if (TREE_CODE (def_stmt
) != PHI_NODE
)
841 /* If we reached the end of the use-def chain, call FN. */
842 return fn (var
, def_stmt
, data
);
848 /* When doing a breadth-first search, call FN before following the
849 use-def links for each argument. */
851 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
852 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
855 /* Follow use-def links out of each PHI argument. */
856 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
858 tree arg
= PHI_ARG_DEF (def_stmt
, i
);
859 if (TREE_CODE (arg
) == SSA_NAME
860 && walk_use_def_chains_1 (arg
, fn
, data
, visited
, is_dfs
))
864 /* When doing a depth-first search, call FN after following the
865 use-def links for each argument. */
867 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
868 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
877 /* Walk use-def chains starting at the SSA variable VAR. Call
878 function FN at each reaching definition found. FN takes three
879 arguments: VAR, its defining statement (DEF_STMT) and a generic
880 pointer to whatever state information that FN may want to maintain
881 (DATA). FN is able to stop the walk by returning true, otherwise
882 in order to continue the walk, FN should return false.
884 Note, that if DEF_STMT is a PHI node, the semantics are slightly
885 different. The first argument to FN is no longer the original
886 variable VAR, but the PHI argument currently being examined. If FN
887 wants to get at VAR, it should call PHI_RESULT (PHI).
889 If IS_DFS is true, this function will:
891 1- walk the use-def chains for all the PHI arguments, and,
892 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
894 If IS_DFS is false, the two steps above are done in reverse order
895 (i.e., a breadth-first search). */
899 walk_use_def_chains (tree var
, walk_use_def_chains_fn fn
, void *data
,
904 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
906 def_stmt
= SSA_NAME_DEF_STMT (var
);
908 /* We only need to recurse if the reaching definition comes from a PHI
910 if (TREE_CODE (def_stmt
) != PHI_NODE
)
911 (*fn
) (var
, def_stmt
, data
);
914 bitmap visited
= BITMAP_XMALLOC ();
915 walk_use_def_chains_1 (var
, fn
, data
, visited
, is_dfs
);
916 BITMAP_XFREE (visited
);
921 /* Replaces VAR with REPL in memory reference expression *X in
925 propagate_into_addr (tree stmt
, tree var
, tree
*x
, tree repl
)
927 tree new_var
, ass_stmt
, addr_var
;
929 block_stmt_iterator bsi
;
931 /* There is nothing special to handle in the other cases. */
932 if (TREE_CODE (repl
) != ADDR_EXPR
)
934 addr_var
= TREE_OPERAND (repl
, 0);
936 while (handled_component_p (*x
)
937 || TREE_CODE (*x
) == REALPART_EXPR
938 || TREE_CODE (*x
) == IMAGPART_EXPR
)
939 x
= &TREE_OPERAND (*x
, 0);
941 if (TREE_CODE (*x
) != INDIRECT_REF
942 || TREE_OPERAND (*x
, 0) != var
)
945 if (TREE_TYPE (*x
) == TREE_TYPE (addr_var
))
948 mark_new_vars_to_rename (stmt
, vars_to_rename
);
953 /* Frontends sometimes produce expressions like *&a instead of a[0].
954 Create a temporary variable to handle this case. */
955 ass_stmt
= build2 (MODIFY_EXPR
, void_type_node
, NULL_TREE
, repl
);
956 new_var
= duplicate_ssa_name (var
, ass_stmt
);
957 TREE_OPERAND (*x
, 0) = new_var
;
958 TREE_OPERAND (ass_stmt
, 0) = new_var
;
960 bb
= bb_for_stmt (stmt
);
961 tree_block_label (bb
);
962 bsi
= bsi_after_labels (bb
);
963 bsi_insert_after (&bsi
, ass_stmt
, BSI_NEW_STMT
);
965 mark_new_vars_to_rename (stmt
, vars_to_rename
);
968 /* Replaces immediate uses of VAR by REPL. */
971 replace_immediate_uses (tree var
, tree repl
)
980 df
= get_immediate_uses (SSA_NAME_DEF_STMT (var
));
981 n
= num_immediate_uses (df
);
983 for (i
= 0; i
< n
; i
++)
985 stmt
= immediate_use (df
, i
);
987 if (TREE_CODE (stmt
) == PHI_NODE
)
989 for (j
= 0; j
< PHI_NUM_ARGS (stmt
); j
++)
990 if (PHI_ARG_DEF (stmt
, j
) == var
)
992 SET_PHI_ARG_DEF (stmt
, j
, repl
);
993 if (TREE_CODE (repl
) == SSA_NAME
994 && PHI_ARG_EDGE (stmt
, j
)->flags
& EDGE_ABNORMAL
)
995 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl
) = 1;
1001 get_stmt_operands (stmt
);
1002 mark_new_vars
= false;
1003 if (is_gimple_reg (SSA_NAME_VAR (var
)))
1005 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
1007 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 0), repl
);
1008 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 1), repl
);
1011 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
1012 if (USE_FROM_PTR (use_p
) == var
)
1014 propagate_value (use_p
, repl
);
1015 mark_new_vars
= POINTER_TYPE_P (TREE_TYPE (repl
));
1020 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
1021 if (USE_FROM_PTR (use_p
) == var
)
1022 propagate_value (use_p
, repl
);
1025 /* FIXME. If REPL is a constant, we need to fold STMT.
1026 However, fold_stmt wants a pointer to the statement, because
1027 it may happen that it needs to replace the whole statement
1028 with a new expression. Since the current def-use machinery
1029 does not return pointers to statements, we call fold_stmt
1030 with the address of a local temporary, if that call changes
1031 the temporary then we fall on our swords.
1033 Note that all this will become unnecessary soon. This
1034 pass is being replaced with a proper copy propagation pass
1035 for 4.1 (dnovillo, 2004-09-17). */
1036 if (TREE_CODE (repl
) != SSA_NAME
)
1044 /* If REPL is a pointer, it may have different memory tags associated
1045 with it. For instance, VAR may have had a name tag while REPL
1046 only had a type tag. In these cases, the virtual operands (if
1047 any) in the statement will refer to different symbols which need
1050 mark_new_vars_to_rename (stmt
, vars_to_rename
);
1056 /* Gets the value VAR is equivalent to according to EQ_TO. */
1059 get_eq_name (tree
*eq_to
, tree var
)
1064 while (TREE_CODE (val
) == SSA_NAME
)
1066 ver
= SSA_NAME_VERSION (val
);
1073 while (TREE_CODE (var
) == SSA_NAME
)
1075 ver
= SSA_NAME_VERSION (var
);
1086 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1087 its result is redundant to to EQ_TO array. */
1090 check_phi_redundancy (tree phi
, tree
*eq_to
)
1092 tree val
= NULL_TREE
, def
, res
= PHI_RESULT (phi
), stmt
;
1093 unsigned i
, ver
= SSA_NAME_VERSION (res
), n
;
1096 /* It is unlikely that such large phi node would be redundant. */
1097 if (PHI_NUM_ARGS (phi
) > 16)
1100 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (phi
); i
++)
1102 def
= PHI_ARG_DEF (phi
, i
);
1104 if (TREE_CODE (def
) == SSA_NAME
)
1106 def
= get_eq_name (eq_to
, def
);
1112 && !operand_equal_p (val
, def
, 0))
1118 /* At least one of the arguments should not be equal to the result, or
1119 something strange is happening. */
1122 if (get_eq_name (eq_to
, res
) == val
)
1125 if (!may_propagate_copy (res
, val
))
1130 df
= get_immediate_uses (SSA_NAME_DEF_STMT (res
));
1131 n
= num_immediate_uses (df
);
1133 for (i
= 0; i
< n
; i
++)
1135 stmt
= immediate_use (df
, i
);
1137 if (TREE_CODE (stmt
) == PHI_NODE
)
1138 check_phi_redundancy (stmt
, eq_to
);
1142 /* Removes redundant phi nodes.
1144 A redundant PHI node is a PHI node where all of its PHI arguments
1145 are the same value, excluding any PHI arguments which are the same
1148 A redundant PHI node is effectively a copy, so we forward copy propagate
1149 which removes all uses of the destination of the PHI node then
1150 finally we delete the redundant PHI node.
1152 Note that if we can not copy propagate the PHI node, then the PHI
1153 will not be removed. Thus we do not have to worry about dependencies
1154 between PHIs and the problems serializing PHIs into copies creates.
1156 The most important effect of this pass is to remove degenerate PHI
1157 nodes created by removing unreachable code. */
1160 kill_redundant_phi_nodes (void)
1163 unsigned i
, old_num_ssa_names
;
1165 tree phi
, var
, repl
, stmt
;
1167 /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1168 replaced. If EQ_TO[VER] is ssa name and it is decided to replace it by
1169 other value, it may be necessary to follow the chain till the final value.
1170 We perform path shortening (replacing the entries of the EQ_TO array with
1171 heads of these chains) whenever we access the field to prevent quadratic
1172 complexity (probably would not occur in practice anyway, but let us play
1174 eq_to
= xcalloc (num_ssa_names
, sizeof (tree
));
1176 /* We have had cases where computing immediate uses takes a
1177 significant amount of compile time. If we run into such
1178 problems here, we may want to only compute immediate uses for
1179 a subset of all the SSA_NAMEs instead of computing it for
1180 all of the SSA_NAMEs. */
1181 compute_immediate_uses (TDFA_USE_OPS
| TDFA_USE_VOPS
, NULL
);
1182 old_num_ssa_names
= num_ssa_names
;
1186 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
1188 var
= PHI_RESULT (phi
);
1189 check_phi_redundancy (phi
, eq_to
);
1193 /* Now propagate the values. */
1194 for (i
= 0; i
< old_num_ssa_names
; i
++)
1199 repl
= get_eq_name (eq_to
, ssa_name (i
));
1200 if (repl
!= ssa_name (i
))
1201 replace_immediate_uses (ssa_name (i
), repl
);
1204 /* And remove the dead phis. */
1205 for (i
= 0; i
< old_num_ssa_names
; i
++)
1210 repl
= get_eq_name (eq_to
, ssa_name (i
));
1211 if (repl
!= ssa_name (i
))
1213 stmt
= SSA_NAME_DEF_STMT (ssa_name (i
));
1214 remove_phi_node (stmt
, NULL_TREE
, bb_for_stmt (stmt
));
1222 struct tree_opt_pass pass_redundant_phi
=
1224 "redphi", /* name */
1226 kill_redundant_phi_nodes
, /* execute */
1229 0, /* static_pass_number */
1231 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
1232 0, /* properties_provided */
1233 0, /* properties_destroyed */
1234 0, /* todo_flags_start */
1235 TODO_dump_func
| TODO_rename_vars
1236 | TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */
1240 /* Emit warnings for uninitialized variables. This is done in two passes.
1242 The first pass notices real uses of SSA names with default definitions.
1243 Such uses are unconditionally uninitialized, and we can be certain that
1244 such a use is a mistake. This pass is run before most optimizations,
1245 so that we catch as many as we can.
1247 The second pass follows PHI nodes to find uses that are potentially
1248 uninitialized. In this case we can't necessarily prove that the use
1249 is really uninitialized. This pass is run after most optimizations,
1250 so that we thread as many jumps and possible, and delete as much dead
1251 code as possible, in order to reduce false positives. We also look
1252 again for plain uninitialized variables, since optimization may have
1253 changed conditionally uninitialized to unconditionally uninitialized. */
1255 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1256 warning text is in MSGID and LOCUS may contain a location or be null. */
1259 warn_uninit (tree t
, const char *msgid
, location_t
*locus
)
1261 tree var
= SSA_NAME_VAR (t
);
1262 tree def
= SSA_NAME_DEF_STMT (t
);
1264 /* Default uses (indicated by an empty definition statement),
1265 are uninitialized. */
1266 if (!IS_EMPTY_STMT (def
))
1269 /* Except for PARMs of course, which are always initialized. */
1270 if (TREE_CODE (var
) == PARM_DECL
)
1273 /* Hard register variables get their initial value from the ether. */
1274 if (DECL_HARD_REGISTER (var
))
1277 /* TREE_NO_WARNING either means we already warned, or the front end
1278 wishes to suppress the warning. */
1279 if (TREE_NO_WARNING (var
))
1283 locus
= &DECL_SOURCE_LOCATION (var
);
1284 warning (msgid
, locus
, var
);
1285 TREE_NO_WARNING (var
) = 1;
1288 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1289 and warn about them. */
1292 warn_uninitialized_var (tree
*tp
, int *walk_subtrees
, void *data
)
1294 location_t
*locus
= data
;
1297 /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */
1298 if (TREE_CODE (t
) == SSA_NAME
)
1300 warn_uninit (t
, "%H'%D' is used uninitialized in this function", locus
);
1303 else if (IS_TYPE_OR_DECL_P (t
))
1309 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1310 and warn about them. */
1313 warn_uninitialized_phi (tree phi
)
1315 int i
, n
= PHI_NUM_ARGS (phi
);
1317 /* Don't look at memory tags. */
1318 if (!is_gimple_reg (PHI_RESULT (phi
)))
1321 for (i
= 0; i
< n
; ++i
)
1323 tree op
= PHI_ARG_DEF (phi
, i
);
1324 if (TREE_CODE (op
) == SSA_NAME
)
1325 warn_uninit (op
, "%H'%D' may be used uninitialized in this function",
1331 execute_early_warn_uninitialized (void)
1333 block_stmt_iterator bsi
;
1337 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1338 walk_tree (bsi_stmt_ptr (bsi
), warn_uninitialized_var
,
1339 EXPR_LOCUS (bsi_stmt (bsi
)), NULL
);
1343 execute_late_warn_uninitialized (void)
1348 /* Re-do the plain uninitialized variable check, as optimization may have
1349 straightened control flow. Do this first so that we don't accidentally
1350 get a "may be" warning when we'd have seen an "is" warning later. */
1351 execute_early_warn_uninitialized ();
1354 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1355 warn_uninitialized_phi (phi
);
1359 gate_warn_uninitialized (void)
1361 return warn_uninitialized
!= 0;
1364 struct tree_opt_pass pass_early_warn_uninitialized
=
1367 gate_warn_uninitialized
, /* gate */
1368 execute_early_warn_uninitialized
, /* execute */
1371 0, /* static_pass_number */
1373 PROP_ssa
, /* properties_required */
1374 0, /* properties_provided */
1375 0, /* properties_destroyed */
1376 0, /* todo_flags_start */
1377 0, /* todo_flags_finish */
1381 struct tree_opt_pass pass_late_warn_uninitialized
=
1384 gate_warn_uninitialized
, /* gate */
1385 execute_late_warn_uninitialized
, /* execute */
1388 0, /* static_pass_number */
1390 PROP_ssa
, /* properties_required */
1391 0, /* properties_provided */
1392 0, /* properties_destroyed */
1393 0, /* todo_flags_start */
1394 0, /* todo_flags_finish */