1 /* Miscellaneous SSA utility functions.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
23 #include "coretypes.h"
30 #include "langhooks.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
37 #include "diagnostic.h"
39 #include "pointer-set.h"
40 #include "tree-flow.h"
41 #include "tree-gimple.h"
42 #include "tree-inline.h"
46 #include "tree-dump.h"
47 #include "tree-pass.h"
49 /* Remove the corresponding arguments from the PHI nodes in E's
50 destination block and redirect it to DEST. Return redirected edge.
51 The list of removed arguments is stored in PENDING_STMT (e). */
54 ssa_redirect_edge (edge e
, basic_block dest
)
57 tree list
= NULL
, *last
= &list
;
60 /* Remove the appropriate PHI arguments in E's destination block. */
61 for (phi
= phi_nodes (e
->dest
); phi
; phi
= PHI_CHAIN (phi
))
63 if (PHI_ARG_DEF (phi
, e
->dest_idx
) == NULL_TREE
)
66 src
= PHI_ARG_DEF (phi
, e
->dest_idx
);
67 dst
= PHI_RESULT (phi
);
68 node
= build_tree_list (dst
, src
);
70 last
= &TREE_CHAIN (node
);
73 e
= redirect_edge_succ_nodup (e
, dest
);
74 PENDING_STMT (e
) = list
;
79 /* Add PHI arguments queued in PENDINT_STMT list on edge E to edge
83 flush_pending_stmts (edge e
)
87 if (!PENDING_STMT (e
))
90 for (phi
= phi_nodes (e
->dest
), arg
= PENDING_STMT (e
);
92 phi
= PHI_CHAIN (phi
), arg
= TREE_CHAIN (arg
))
94 tree def
= TREE_VALUE (arg
);
95 add_phi_arg (phi
, def
, e
);
98 PENDING_STMT (e
) = NULL
;
101 /* Return true if SSA_NAME is malformed and mark it visited.
103 IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
107 verify_ssa_name (tree ssa_name
, bool is_virtual
)
109 if (TREE_CODE (ssa_name
) != SSA_NAME
)
111 error ("Expected an SSA_NAME object");
115 if (TREE_TYPE (ssa_name
) != TREE_TYPE (SSA_NAME_VAR (ssa_name
)))
117 error ("Type mismatch between an SSA_NAME and its symbol.");
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 print_generic_stmt (stderr
, SSA_NAME_DEF_STMT (ssa_name
), TDF_VOPS
);
176 fprintf (stderr
, "\nActual definition statement:\n");
177 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
184 fprintf (stderr
, "while verifying SSA_NAME ");
185 print_generic_expr (stderr
, ssa_name
, 0);
186 fprintf (stderr
, " in statement\n");
187 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
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
207 If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
208 that are defined before STMT in basic block BB. */
211 verify_use (basic_block bb
, basic_block def_bb
, tree ssa_name
,
212 tree stmt
, bool check_abnormal
, bool is_virtual
,
213 bitmap names_defined_in_bb
)
217 err
= verify_ssa_name (ssa_name
, is_virtual
);
218 TREE_VISITED (ssa_name
) = 1;
220 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name
))
221 && var_ann (SSA_NAME_VAR (ssa_name
))->default_def
== ssa_name
)
222 ; /* Default definitions have empty statements. Nothing to do. */
225 error ("Missing definition");
228 else if (bb
!= def_bb
229 && !dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
231 error ("Definition in block %i does not dominate use in block %i",
232 def_bb
->index
, bb
->index
);
235 else if (bb
== def_bb
236 && names_defined_in_bb
!= NULL
237 && !bitmap_bit_p (names_defined_in_bb
, SSA_NAME_VERSION (ssa_name
)))
239 error ("Definition in block %i follows the use", def_bb
->index
);
244 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name
))
246 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
252 fprintf (stderr
, "for SSA_NAME: ");
253 print_generic_expr (stderr
, ssa_name
, TDF_VOPS
);
254 fprintf (stderr
, "in statement:\n");
255 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
262 /* Return true if any of the arguments for PHI node PHI at block BB is
265 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
266 numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
267 block in that array slot contains the definition of SSA_NAME. */
270 verify_phi_args (tree phi
, basic_block bb
, basic_block
*definition_block
)
274 unsigned i
, phi_num_args
= PHI_NUM_ARGS (phi
);
276 if (EDGE_COUNT (bb
->preds
) != phi_num_args
)
278 error ("Incoming edge count does not match number of PHI arguments\n");
283 for (i
= 0; i
< phi_num_args
; i
++)
285 tree op
= PHI_ARG_DEF (phi
, i
);
287 e
= EDGE_PRED (bb
, i
);
291 error ("PHI argument is missing for edge %d->%d\n",
298 if (TREE_CODE (op
) != SSA_NAME
&& !is_gimple_min_invariant (op
))
300 error ("PHI argument is not SSA_NAME, or invariant");
304 if (TREE_CODE (op
) == SSA_NAME
)
305 err
= verify_use (e
->src
, definition_block
[SSA_NAME_VERSION (op
)], op
,
306 phi
, e
->flags
& EDGE_ABNORMAL
,
307 !is_gimple_reg (PHI_RESULT (phi
)),
312 error ("Wrong edge %d->%d for PHI argument\n",
313 e
->src
->index
, e
->dest
->index
, bb
->index
);
319 fprintf (stderr
, "PHI argument\n");
320 print_generic_stmt (stderr
, op
, TDF_VOPS
);
328 fprintf (stderr
, "for PHI node\n");
329 print_generic_stmt (stderr
, phi
, TDF_VOPS
);
338 verify_flow_insensitive_alias_info (void)
342 bitmap visited
= BITMAP_ALLOC (NULL
);
344 for (i
= 0; i
< num_referenced_vars
; i
++)
348 varray_type may_aliases
;
350 var
= referenced_var (i
);
352 may_aliases
= ann
->may_aliases
;
354 for (j
= 0; may_aliases
&& j
< VARRAY_ACTIVE_SIZE (may_aliases
); j
++)
356 tree alias
= VARRAY_TREE (may_aliases
, j
);
358 bitmap_set_bit (visited
, var_ann (alias
)->uid
);
360 if (!may_be_aliased (alias
))
362 error ("Non-addressable variable inside an alias set.");
363 debug_variable (alias
);
369 for (i
= 0; i
< num_referenced_vars
; i
++)
373 var
= referenced_var (i
);
376 if (ann
->mem_tag_kind
== NOT_A_TAG
378 && !bitmap_bit_p (visited
, ann
->uid
))
380 error ("Addressable variable that is an alias tag but is not in any alias set.");
385 BITMAP_FREE (visited
);
389 debug_variable (var
);
390 internal_error ("verify_flow_insensitive_alias_info failed.");
395 verify_flow_sensitive_alias_info (void)
400 for (i
= 1; i
< num_ssa_names
; i
++)
404 struct ptr_info_def
*pi
;
411 /* We only care for pointers that are actually referenced in the
413 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)) || !TREE_VISITED (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 var
= SSA_NAME_VAR (ptr
);
421 if (TREE_CODE (var
) == RESULT_DECL
422 && is_gimple_reg (ptr
))
425 pi
= SSA_NAME_PTR_INFO (ptr
);
430 if (pi
->is_dereferenced
&& !pi
->name_mem_tag
&& !ann
->type_mem_tag
)
432 error ("Dereferenced pointers should have a name or a type tag");
438 && (pi
->pt_vars
== NULL
|| bitmap_empty_p (pi
->pt_vars
)))
440 error ("Pointers with a memory tag, should have points-to sets or point to malloc");
444 if (pi
->value_escapes_p
446 && !is_call_clobbered (pi
->name_mem_tag
))
448 error ("Pointer escapes but its name tag is not call-clobbered.");
456 debug_variable (ptr
);
457 internal_error ("verify_flow_sensitive_alias_info failed.");
460 DEF_VEC_MALLOC_P (bitmap
);
462 /* Verify that all name tags have different points to sets.
463 This algorithm takes advantage of the fact that every variable with the
464 same name tag must have the same points-to set.
465 So we check a single variable for each name tag, and verify that its
466 points-to set is different from every other points-to set for other name
469 Additionally, given a pointer P_i with name tag NMT and type tag
470 TMT, this function verified the alias set of TMT is a superset of
471 the alias set of NMT. */
474 verify_name_tags (void)
478 bitmap first
, second
;
479 VEC (tree
) *name_tag_reps
= NULL
;
480 VEC (bitmap
) *pt_vars_for_reps
= NULL
;
481 bitmap type_aliases
= BITMAP_ALLOC (NULL
);
483 /* First we compute the name tag representatives and their points-to sets. */
484 for (i
= 0; i
< num_ssa_names
; i
++)
486 struct ptr_info_def
*pi
;
487 tree tmt
, ptr
= ssa_name (i
);
489 if (ptr
== NULL_TREE
)
492 pi
= SSA_NAME_PTR_INFO (ptr
);
494 if (!TREE_VISITED (ptr
)
495 || !POINTER_TYPE_P (TREE_TYPE (ptr
))
498 || TREE_VISITED (pi
->name_mem_tag
))
501 TREE_VISITED (pi
->name_mem_tag
) = 1;
503 if (pi
->pt_vars
== NULL
)
506 VEC_safe_push (tree
, name_tag_reps
, ptr
);
507 VEC_safe_push (bitmap
, pt_vars_for_reps
, pi
->pt_vars
);
509 /* Verify that alias set of PTR's type tag is a superset of the
510 alias set of PTR's name tag. */
511 tmt
= var_ann (SSA_NAME_VAR (ptr
))->type_mem_tag
;
515 varray_type aliases
= var_ann (tmt
)->may_aliases
;
516 bitmap_clear (type_aliases
);
517 for (i
= 0; aliases
&& i
< VARRAY_ACTIVE_SIZE (aliases
); i
++)
519 tree alias
= VARRAY_TREE (aliases
, i
);
520 bitmap_set_bit (type_aliases
, var_ann (alias
)->uid
);
523 /* When grouping, we may have added PTR's type tag into the
524 alias set of PTR's name tag. To prevent a false
525 positive, pretend that TMT is in its own alias set. */
526 bitmap_set_bit (type_aliases
, var_ann (tmt
)->uid
);
528 if (bitmap_equal_p (type_aliases
, pi
->pt_vars
))
531 if (!bitmap_intersect_compl_p (type_aliases
, pi
->pt_vars
))
533 error ("Alias set of a pointer's type tag should be a superset of the corresponding name tag");
534 debug_variable (tmt
);
535 debug_variable (pi
->name_mem_tag
);
541 /* Now compare all the representative bitmaps with all other representative
542 bitmaps, to verify that they are all different. */
543 for (i
= 0; VEC_iterate (bitmap
, pt_vars_for_reps
, i
, first
); i
++)
545 for (j
= i
+ 1; VEC_iterate (bitmap
, pt_vars_for_reps
, j
, second
); j
++)
547 if (bitmap_equal_p (first
, second
))
549 error ("Two different pointers with identical points-to sets but different name tags");
550 debug_variable (VEC_index (tree
, name_tag_reps
, j
));
556 /* Lastly, clear out the visited flags. */
557 for (i
= 0; i
< num_ssa_names
; i
++)
561 tree ptr
= ssa_name (i
);
562 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
563 if (!TREE_VISITED (ptr
)
564 || !POINTER_TYPE_P (TREE_TYPE (ptr
))
566 || !pi
->name_mem_tag
)
568 TREE_VISITED (pi
->name_mem_tag
) = 0;
572 VEC_free (bitmap
, pt_vars_for_reps
);
573 BITMAP_FREE (type_aliases
);
577 debug_variable (VEC_index (tree
, name_tag_reps
, i
));
578 internal_error ("verify_name_tags failed");
582 /* Verify the consistency of aliasing information. */
585 verify_alias_info (void)
587 verify_flow_sensitive_alias_info ();
589 verify_flow_insensitive_alias_info ();
593 /* Verify common invariants in the SSA web.
594 TODO: verify the variable annotations. */
601 basic_block
*definition_block
= xcalloc (num_ssa_names
, sizeof (basic_block
));
604 enum dom_state orig_dom_state
= dom_computed
[CDI_DOMINATORS
];
605 bitmap names_defined_in_bb
= BITMAP_ALLOC (NULL
);
607 timevar_push (TV_TREE_SSA_VERIFY
);
609 /* Keep track of SSA names present in the IL. */
610 for (i
= 1; i
< num_ssa_names
; i
++)
612 tree name
= ssa_name (i
);
616 TREE_VISITED (name
) = 0;
618 stmt
= SSA_NAME_DEF_STMT (name
);
619 if (!IS_EMPTY_STMT (stmt
))
621 basic_block bb
= bb_for_stmt (stmt
);
622 verify_def (bb
, definition_block
,
623 name
, stmt
, !is_gimple_reg (name
));
629 calculate_dominance_info (CDI_DOMINATORS
);
631 /* Now verify all the uses and make sure they agree with the definitions
632 found in the previous pass. */
638 block_stmt_iterator bsi
;
640 /* Make sure that all edges have a clear 'aux' field. */
641 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
645 error ("AUX pointer initialized for edge %d->%d\n", e
->src
->index
,
651 /* Verify the arguments for every PHI node in the block. */
652 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
654 if (verify_phi_args (phi
, bb
, definition_block
))
656 bitmap_set_bit (names_defined_in_bb
,
657 SSA_NAME_VERSION (PHI_RESULT (phi
)));
660 /* Now verify all the uses and vuses in every statement of the block. */
661 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
663 tree stmt
= bsi_stmt (bsi
);
665 get_stmt_operands (stmt
);
667 if (stmt_ann (stmt
)->makes_aliased_stores
668 && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt
)) == 0)
670 error ("Statement makes aliased stores, but has no V_MAY_DEFS");
671 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
675 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_ALL_USES
| SSA_OP_ALL_KILLS
)
677 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
678 op
, stmt
, false, !is_gimple_reg (op
),
679 names_defined_in_bb
))
683 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_ALL_DEFS
)
685 bitmap_set_bit (names_defined_in_bb
, SSA_NAME_VERSION (op
));
689 bitmap_clear (names_defined_in_bb
);
692 /* Finally, verify alias information. */
693 verify_alias_info ();
695 free (definition_block
);
696 /* Restore the dominance information to its prior known state, so
697 that we do not perturb the compiler's subsequent behavior. */
698 if (orig_dom_state
== DOM_NONE
)
699 free_dominance_info (CDI_DOMINATORS
);
701 dom_computed
[CDI_DOMINATORS
] = orig_dom_state
;
703 BITMAP_FREE (names_defined_in_bb
);
704 timevar_pop (TV_TREE_SSA_VERIFY
);
708 internal_error ("verify_ssa failed.");
712 /* Initialize global DFA and SSA structures. */
717 VARRAY_TREE_INIT (referenced_vars
, 20, "referenced_vars");
718 call_clobbered_vars
= BITMAP_ALLOC (NULL
);
719 addressable_vars
= BITMAP_ALLOC (NULL
);
720 init_ssa_operands ();
723 global_var
= NULL_TREE
;
724 aliases_computed_p
= false;
728 /* Deallocate memory associated with SSA data structures for FNDECL. */
731 delete_tree_ssa (void)
735 block_stmt_iterator bsi
;
737 /* Remove annotations from every tree in the function. */
739 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
741 tree stmt
= bsi_stmt (bsi
);
743 ggc_free (stmt
->common
.ann
);
744 stmt
->common
.ann
= NULL
;
747 /* Remove annotations from every referenced variable. */
750 for (i
= 0; i
< num_referenced_vars
; i
++)
752 tree var
= referenced_var (i
);
753 ggc_free (var
->common
.ann
);
754 var
->common
.ann
= NULL
;
756 referenced_vars
= NULL
;
761 fini_ssa_operands ();
763 global_var
= NULL_TREE
;
764 BITMAP_FREE (call_clobbered_vars
);
765 call_clobbered_vars
= NULL
;
766 BITMAP_FREE (addressable_vars
);
767 addressable_vars
= NULL
;
768 modified_noreturn_calls
= NULL
;
769 aliases_computed_p
= false;
773 /* Return true if EXPR is a useless type conversion, otherwise return
777 tree_ssa_useless_type_conversion_1 (tree outer_type
, tree inner_type
)
779 if (inner_type
== outer_type
)
782 /* Changes in machine mode are never useless conversions. */
783 if (TYPE_MODE (inner_type
) != TYPE_MODE (outer_type
))
786 /* If the inner and outer types are effectively the same, then
787 strip the type conversion and enter the equivalence into
789 if (lang_hooks
.types_compatible_p (inner_type
, outer_type
))
792 /* If both types are pointers and the outer type is a (void *), then
793 the conversion is not necessary. The opposite is not true since
794 that conversion would result in a loss of information if the
795 equivalence was used. Consider an indirect function call where
796 we need to know the exact type of the function to correctly
797 implement the ABI. */
798 else if (POINTER_TYPE_P (inner_type
)
799 && POINTER_TYPE_P (outer_type
)
800 && TYPE_REF_CAN_ALIAS_ALL (inner_type
)
801 == TYPE_REF_CAN_ALIAS_ALL (outer_type
)
802 && TREE_CODE (TREE_TYPE (outer_type
)) == VOID_TYPE
)
805 /* Pointers and references are equivalent once we get to GENERIC,
806 so strip conversions that just switch between them. */
807 else if (POINTER_TYPE_P (inner_type
)
808 && POINTER_TYPE_P (outer_type
)
809 && TYPE_REF_CAN_ALIAS_ALL (inner_type
)
810 == TYPE_REF_CAN_ALIAS_ALL (outer_type
)
811 && lang_hooks
.types_compatible_p (TREE_TYPE (inner_type
),
812 TREE_TYPE (outer_type
)))
815 /* If both the inner and outer types are integral types, then the
816 conversion is not necessary if they have the same mode and
817 signedness and precision, and both or neither are boolean. Some
818 code assumes an invariant that boolean types stay boolean and do
819 not become 1-bit bit-field types. Note that types with precision
820 not using all bits of the mode (such as bit-field types in C)
821 mean that testing of precision is necessary. */
822 else if (INTEGRAL_TYPE_P (inner_type
)
823 && INTEGRAL_TYPE_P (outer_type
)
824 && TYPE_UNSIGNED (inner_type
) == TYPE_UNSIGNED (outer_type
)
825 && TYPE_PRECISION (inner_type
) == TYPE_PRECISION (outer_type
))
827 bool first_boolean
= (TREE_CODE (inner_type
) == BOOLEAN_TYPE
);
828 bool second_boolean
= (TREE_CODE (outer_type
) == BOOLEAN_TYPE
);
829 if (first_boolean
== second_boolean
)
833 /* Recurse for complex types. */
834 else if (TREE_CODE (inner_type
) == COMPLEX_TYPE
835 && TREE_CODE (outer_type
) == COMPLEX_TYPE
836 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type
),
837 TREE_TYPE (inner_type
)))
843 /* Return true if EXPR is a useless type conversion, otherwise return
847 tree_ssa_useless_type_conversion (tree expr
)
849 /* If we have an assignment that merely uses a NOP_EXPR to change
850 the top of the RHS to the type of the LHS and the type conversion
851 is "safe", then strip away the type conversion so that we can
852 enter LHS = RHS into the const_and_copies table. */
853 if (TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
854 || TREE_CODE (expr
) == VIEW_CONVERT_EXPR
855 || TREE_CODE (expr
) == NON_LVALUE_EXPR
)
856 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr
),
857 TREE_TYPE (TREE_OPERAND (expr
,
864 /* Returns true if statement STMT may read memory. */
867 stmt_references_memory_p (tree stmt
)
871 get_stmt_operands (stmt
);
872 ann
= stmt_ann (stmt
);
874 if (ann
->has_volatile_ops
)
877 return (NUM_VUSES (VUSE_OPS (ann
)) > 0
878 || NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann
)) > 0
879 || NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann
)) > 0);
882 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
883 described in walk_use_def_chains.
885 VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
886 infinite loops. We used to have a bitmap for this to just mark
887 SSA versions we had visited. But non-sparse bitmaps are way too
888 expensive, while sparse bitmaps may cause quadratic behavior.
890 IS_DFS is true if the caller wants to perform a depth-first search
891 when visiting PHI nodes. A DFS will visit each PHI argument and
892 call FN after each one. Otherwise, all the arguments are
893 visited first and then FN is called with each of the visited
894 arguments in a separate pass. */
897 walk_use_def_chains_1 (tree var
, walk_use_def_chains_fn fn
, void *data
,
898 struct pointer_set_t
*visited
, bool is_dfs
)
902 if (pointer_set_insert (visited
, var
))
905 def_stmt
= SSA_NAME_DEF_STMT (var
);
907 if (TREE_CODE (def_stmt
) != PHI_NODE
)
909 /* If we reached the end of the use-def chain, call FN. */
910 return fn (var
, def_stmt
, data
);
916 /* When doing a breadth-first search, call FN before following the
917 use-def links for each argument. */
919 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
920 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
923 /* Follow use-def links out of each PHI argument. */
924 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
926 tree arg
= PHI_ARG_DEF (def_stmt
, i
);
927 if (TREE_CODE (arg
) == SSA_NAME
928 && walk_use_def_chains_1 (arg
, fn
, data
, visited
, is_dfs
))
932 /* When doing a depth-first search, call FN after following the
933 use-def links for each argument. */
935 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
936 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
945 /* Walk use-def chains starting at the SSA variable VAR. Call
946 function FN at each reaching definition found. FN takes three
947 arguments: VAR, its defining statement (DEF_STMT) and a generic
948 pointer to whatever state information that FN may want to maintain
949 (DATA). FN is able to stop the walk by returning true, otherwise
950 in order to continue the walk, FN should return false.
952 Note, that if DEF_STMT is a PHI node, the semantics are slightly
953 different. The first argument to FN is no longer the original
954 variable VAR, but the PHI argument currently being examined. If FN
955 wants to get at VAR, it should call PHI_RESULT (PHI).
957 If IS_DFS is true, this function will:
959 1- walk the use-def chains for all the PHI arguments, and,
960 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
962 If IS_DFS is false, the two steps above are done in reverse order
963 (i.e., a breadth-first search). */
967 walk_use_def_chains (tree var
, walk_use_def_chains_fn fn
, void *data
,
972 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
974 def_stmt
= SSA_NAME_DEF_STMT (var
);
976 /* We only need to recurse if the reaching definition comes from a PHI
978 if (TREE_CODE (def_stmt
) != PHI_NODE
)
979 (*fn
) (var
, def_stmt
, data
);
982 struct pointer_set_t
*visited
= pointer_set_create ();
983 walk_use_def_chains_1 (var
, fn
, data
, visited
, is_dfs
);
984 pointer_set_destroy (visited
);
989 /* Replaces VAR with REPL in memory reference expression *X in
993 propagate_into_addr (tree stmt
, tree var
, tree
*x
, tree repl
)
995 tree new_var
, ass_stmt
, addr_var
;
997 block_stmt_iterator bsi
;
999 /* There is nothing special to handle in the other cases. */
1000 if (TREE_CODE (repl
) != ADDR_EXPR
)
1002 addr_var
= TREE_OPERAND (repl
, 0);
1004 while (handled_component_p (*x
)
1005 || TREE_CODE (*x
) == REALPART_EXPR
1006 || TREE_CODE (*x
) == IMAGPART_EXPR
)
1007 x
= &TREE_OPERAND (*x
, 0);
1009 if (TREE_CODE (*x
) != INDIRECT_REF
1010 || TREE_OPERAND (*x
, 0) != var
)
1013 if (TREE_TYPE (*x
) == TREE_TYPE (addr_var
))
1016 mark_new_vars_to_rename (stmt
, vars_to_rename
);
1021 /* Frontends sometimes produce expressions like *&a instead of a[0].
1022 Create a temporary variable to handle this case. */
1023 ass_stmt
= build2 (MODIFY_EXPR
, void_type_node
, NULL_TREE
, repl
);
1024 new_var
= duplicate_ssa_name (var
, ass_stmt
);
1025 TREE_OPERAND (*x
, 0) = new_var
;
1026 TREE_OPERAND (ass_stmt
, 0) = new_var
;
1028 bb
= bb_for_stmt (stmt
);
1029 tree_block_label (bb
);
1030 bsi
= bsi_after_labels (bb
);
1031 bsi_insert_after (&bsi
, ass_stmt
, BSI_NEW_STMT
);
1033 mark_new_vars_to_rename (stmt
, vars_to_rename
);
1036 /* Replaces immediate uses of VAR by REPL. */
1039 replace_immediate_uses (tree var
, tree repl
)
1046 use_operand_p use_p
;
1048 df
= get_immediate_uses (SSA_NAME_DEF_STMT (var
));
1049 n
= num_immediate_uses (df
);
1051 for (i
= 0; i
< n
; i
++)
1053 stmt
= immediate_use (df
, i
);
1055 if (TREE_CODE (stmt
) == PHI_NODE
)
1057 for (j
= 0; j
< PHI_NUM_ARGS (stmt
); j
++)
1058 if (PHI_ARG_DEF (stmt
, j
) == var
)
1060 SET_PHI_ARG_DEF (stmt
, j
, repl
);
1061 if (TREE_CODE (repl
) == SSA_NAME
1062 && PHI_ARG_EDGE (stmt
, j
)->flags
& EDGE_ABNORMAL
)
1063 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl
) = 1;
1069 get_stmt_operands (stmt
);
1070 mark_new_vars
= false;
1071 if (is_gimple_reg (SSA_NAME_VAR (var
)))
1073 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
1075 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 0), repl
);
1076 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 1), repl
);
1079 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
1080 if (USE_FROM_PTR (use_p
) == var
)
1082 propagate_value (use_p
, repl
);
1083 mark_new_vars
= POINTER_TYPE_P (TREE_TYPE (repl
));
1088 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
,
1089 SSA_OP_VIRTUAL_USES
| SSA_OP_VIRTUAL_KILLS
)
1090 if (USE_FROM_PTR (use_p
) == var
)
1091 propagate_value (use_p
, repl
);
1094 /* FIXME. If REPL is a constant, we need to fold STMT.
1095 However, fold_stmt wants a pointer to the statement, because
1096 it may happen that it needs to replace the whole statement
1097 with a new expression. Since the current def-use machinery
1098 does not return pointers to statements, we call fold_stmt
1099 with the address of a local temporary, if that call changes
1100 the temporary then we fallback on looking for a proper
1101 pointer to STMT by scanning STMT's basic block.
1103 Note that all this will become unnecessary soon. This
1104 pass is being replaced with a proper copy propagation pass
1105 for 4.1 (dnovillo, 2004-09-17). */
1106 if (TREE_CODE (repl
) != SSA_NAME
)
1110 mark_new_vars
= true;
1113 block_stmt_iterator si
= bsi_for_stmt (stmt
);
1114 mark_new_vars_to_rename (tmp
, vars_to_rename
);
1115 redirect_immediate_uses (stmt
, tmp
);
1116 bsi_replace (&si
, tmp
, true);
1117 stmt
= bsi_stmt (si
);
1121 /* If REPL is a pointer, it may have different memory tags associated
1122 with it. For instance, VAR may have had a name tag while REPL
1123 only had a type tag. In these cases, the virtual operands (if
1124 any) in the statement will refer to different symbols which need
1127 mark_new_vars_to_rename (stmt
, vars_to_rename
);
1133 /* Gets the value VAR is equivalent to according to EQ_TO. */
1136 get_eq_name (tree
*eq_to
, tree var
)
1141 while (TREE_CODE (val
) == SSA_NAME
)
1143 ver
= SSA_NAME_VERSION (val
);
1150 while (TREE_CODE (var
) == SSA_NAME
)
1152 ver
= SSA_NAME_VERSION (var
);
1163 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1164 its result is redundant to to EQ_TO array. */
1167 check_phi_redundancy (tree phi
, tree
*eq_to
)
1169 tree val
= NULL_TREE
, def
, res
= PHI_RESULT (phi
), stmt
;
1170 unsigned i
, ver
= SSA_NAME_VERSION (res
), n
;
1173 /* It is unlikely that such large phi node would be redundant. */
1174 if (PHI_NUM_ARGS (phi
) > 16)
1177 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (phi
); i
++)
1179 def
= PHI_ARG_DEF (phi
, i
);
1181 if (TREE_CODE (def
) == SSA_NAME
)
1183 def
= get_eq_name (eq_to
, def
);
1189 && !operand_equal_for_phi_arg_p (val
, def
))
1195 /* At least one of the arguments should not be equal to the result, or
1196 something strange is happening. */
1199 if (get_eq_name (eq_to
, res
) == val
)
1202 if (!may_propagate_copy (res
, val
))
1207 df
= get_immediate_uses (SSA_NAME_DEF_STMT (res
));
1208 n
= num_immediate_uses (df
);
1210 for (i
= 0; i
< n
; i
++)
1212 stmt
= immediate_use (df
, i
);
1214 if (TREE_CODE (stmt
) == PHI_NODE
)
1215 check_phi_redundancy (stmt
, eq_to
);
1219 /* Removes redundant phi nodes.
1221 A redundant PHI node is a PHI node where all of its PHI arguments
1222 are the same value, excluding any PHI arguments which are the same
1225 A redundant PHI node is effectively a copy, so we forward copy propagate
1226 which removes all uses of the destination of the PHI node then
1227 finally we delete the redundant PHI node.
1229 Note that if we can not copy propagate the PHI node, then the PHI
1230 will not be removed. Thus we do not have to worry about dependencies
1231 between PHIs and the problems serializing PHIs into copies creates.
1233 The most important effect of this pass is to remove degenerate PHI
1234 nodes created by removing unreachable code. */
1237 kill_redundant_phi_nodes (void)
1240 unsigned i
, old_num_ssa_names
;
1242 tree phi
, repl
, stmt
;
1244 /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1245 replaced. If EQ_TO[VER] is ssa name and it is decided to replace it by
1246 other value, it may be necessary to follow the chain till the final value.
1247 We perform path shortening (replacing the entries of the EQ_TO array with
1248 heads of these chains) whenever we access the field to prevent quadratic
1249 complexity (probably would not occur in practice anyway, but let us play
1251 eq_to
= xcalloc (num_ssa_names
, sizeof (tree
));
1253 /* We have had cases where computing immediate uses takes a
1254 significant amount of compile time. If we run into such
1255 problems here, we may want to only compute immediate uses for
1256 a subset of all the SSA_NAMEs instead of computing it for
1257 all of the SSA_NAMEs. */
1258 compute_immediate_uses (TDFA_USE_OPS
| TDFA_USE_VOPS
, NULL
);
1259 old_num_ssa_names
= num_ssa_names
;
1263 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1264 check_phi_redundancy (phi
, eq_to
);
1267 /* Now propagate the values. */
1268 for (i
= 0; i
< old_num_ssa_names
; i
++)
1273 repl
= get_eq_name (eq_to
, ssa_name (i
));
1274 if (repl
!= ssa_name (i
))
1275 replace_immediate_uses (ssa_name (i
), repl
);
1278 /* And remove the dead phis. */
1279 for (i
= 0; i
< old_num_ssa_names
; i
++)
1284 repl
= get_eq_name (eq_to
, ssa_name (i
));
1285 if (repl
!= ssa_name (i
))
1287 stmt
= SSA_NAME_DEF_STMT (ssa_name (i
));
1288 remove_phi_node (stmt
, NULL_TREE
);
1296 struct tree_opt_pass pass_redundant_phi
=
1298 "redphi", /* name */
1300 kill_redundant_phi_nodes
, /* execute */
1303 0, /* static_pass_number */
1304 TV_TREE_REDPHI
, /* tv_id */
1305 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
1306 0, /* properties_provided */
1307 0, /* properties_destroyed */
1308 0, /* todo_flags_start */
1309 TODO_dump_func
| TODO_rename_vars
1310 | TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */
1314 /* Emit warnings for uninitialized variables. This is done in two passes.
1316 The first pass notices real uses of SSA names with default definitions.
1317 Such uses are unconditionally uninitialized, and we can be certain that
1318 such a use is a mistake. This pass is run before most optimizations,
1319 so that we catch as many as we can.
1321 The second pass follows PHI nodes to find uses that are potentially
1322 uninitialized. In this case we can't necessarily prove that the use
1323 is really uninitialized. This pass is run after most optimizations,
1324 so that we thread as many jumps and possible, and delete as much dead
1325 code as possible, in order to reduce false positives. We also look
1326 again for plain uninitialized variables, since optimization may have
1327 changed conditionally uninitialized to unconditionally uninitialized. */
1329 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1330 warning text is in MSGID and LOCUS may contain a location or be null. */
1333 warn_uninit (tree t
, const char *msgid
, location_t
*locus
)
1335 tree var
= SSA_NAME_VAR (t
);
1336 tree def
= SSA_NAME_DEF_STMT (t
);
1338 /* Default uses (indicated by an empty definition statement),
1339 are uninitialized. */
1340 if (!IS_EMPTY_STMT (def
))
1343 /* Except for PARMs of course, which are always initialized. */
1344 if (TREE_CODE (var
) == PARM_DECL
)
1347 /* Hard register variables get their initial value from the ether. */
1348 if (TREE_CODE (var
) == VAR_DECL
&& DECL_HARD_REGISTER (var
))
1351 /* TREE_NO_WARNING either means we already warned, or the front end
1352 wishes to suppress the warning. */
1353 if (TREE_NO_WARNING (var
))
1357 locus
= &DECL_SOURCE_LOCATION (var
);
1358 warning (msgid
, locus
, var
);
1359 TREE_NO_WARNING (var
) = 1;
1362 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1363 and warn about them. */
1366 warn_uninitialized_var (tree
*tp
, int *walk_subtrees
, void *data
)
1368 location_t
*locus
= data
;
1371 /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */
1372 if (TREE_CODE (t
) == SSA_NAME
)
1374 warn_uninit (t
, "%H%qD is used uninitialized in this function", locus
);
1377 else if (IS_TYPE_OR_DECL_P (t
))
1383 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1384 and warn about them. */
1387 warn_uninitialized_phi (tree phi
)
1389 int i
, n
= PHI_NUM_ARGS (phi
);
1391 /* Don't look at memory tags. */
1392 if (!is_gimple_reg (PHI_RESULT (phi
)))
1395 for (i
= 0; i
< n
; ++i
)
1397 tree op
= PHI_ARG_DEF (phi
, i
);
1398 if (TREE_CODE (op
) == SSA_NAME
)
1399 warn_uninit (op
, "%H%qD may be used uninitialized in this function",
1405 execute_early_warn_uninitialized (void)
1407 block_stmt_iterator bsi
;
1411 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1412 walk_tree (bsi_stmt_ptr (bsi
), warn_uninitialized_var
,
1413 EXPR_LOCUS (bsi_stmt (bsi
)), NULL
);
1417 execute_late_warn_uninitialized (void)
1422 /* Re-do the plain uninitialized variable check, as optimization may have
1423 straightened control flow. Do this first so that we don't accidentally
1424 get a "may be" warning when we'd have seen an "is" warning later. */
1425 execute_early_warn_uninitialized ();
1428 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1429 warn_uninitialized_phi (phi
);
1433 gate_warn_uninitialized (void)
1435 return warn_uninitialized
!= 0;
1438 struct tree_opt_pass pass_early_warn_uninitialized
=
1441 gate_warn_uninitialized
, /* gate */
1442 execute_early_warn_uninitialized
, /* execute */
1445 0, /* static_pass_number */
1447 PROP_ssa
, /* properties_required */
1448 0, /* properties_provided */
1449 0, /* properties_destroyed */
1450 0, /* todo_flags_start */
1451 0, /* todo_flags_finish */
1455 struct tree_opt_pass pass_late_warn_uninitialized
=
1458 gate_warn_uninitialized
, /* gate */
1459 execute_late_warn_uninitialized
, /* execute */
1462 0, /* static_pass_number */
1464 PROP_ssa
, /* properties_required */
1465 0, /* properties_provided */
1466 0, /* properties_destroyed */
1467 0, /* todo_flags_start */
1468 0, /* todo_flags_finish */