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
= next
)
63 next
= PHI_CHAIN (phi
);
65 if (PHI_ARG_DEF (phi
, e
->dest_idx
) == NULL_TREE
)
68 src
= PHI_ARG_DEF (phi
, e
->dest_idx
);
69 dst
= PHI_RESULT (phi
);
70 node
= build_tree_list (dst
, src
);
72 last
= &TREE_CHAIN (node
);
75 e
= redirect_edge_succ_nodup (e
, dest
);
76 PENDING_STMT (e
) = list
;
81 /* Add PHI arguments queued in PENDINT_STMT list on edge E to edge
85 flush_pending_stmts (edge e
)
89 if (!PENDING_STMT (e
))
92 for (phi
= phi_nodes (e
->dest
), arg
= PENDING_STMT (e
);
94 phi
= PHI_CHAIN (phi
), arg
= TREE_CHAIN (arg
))
96 tree def
= TREE_VALUE (arg
);
97 add_phi_arg (phi
, def
, e
);
100 PENDING_STMT (e
) = NULL
;
103 /* Return true if SSA_NAME is malformed and mark it visited.
105 IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
109 verify_ssa_name (tree ssa_name
, bool is_virtual
)
111 if (TREE_CODE (ssa_name
) != SSA_NAME
)
113 error ("Expected an SSA_NAME object");
117 if (TREE_TYPE (ssa_name
) != TREE_TYPE (SSA_NAME_VAR (ssa_name
)))
119 error ("Type mismatch between an SSA_NAME and its symbol.");
123 if (SSA_NAME_IN_FREE_LIST (ssa_name
))
125 error ("Found an SSA_NAME that had been released into the free pool");
129 if (is_virtual
&& is_gimple_reg (ssa_name
))
131 error ("Found a virtual definition for a GIMPLE register");
135 if (!is_virtual
&& !is_gimple_reg (ssa_name
))
137 error ("Found a real definition for a non-register");
145 /* Return true if the definition of SSA_NAME at block BB is malformed.
147 STMT is the statement where SSA_NAME is created.
149 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
150 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
151 it means that the block in that array slot contains the
152 definition of SSA_NAME.
154 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
158 verify_def (basic_block bb
, basic_block
*definition_block
, tree ssa_name
,
159 tree stmt
, bool is_virtual
)
161 if (verify_ssa_name (ssa_name
, is_virtual
))
164 if (definition_block
[SSA_NAME_VERSION (ssa_name
)])
166 error ("SSA_NAME created in two different blocks %i and %i",
167 definition_block
[SSA_NAME_VERSION (ssa_name
)]->index
, bb
->index
);
171 definition_block
[SSA_NAME_VERSION (ssa_name
)] = bb
;
173 if (SSA_NAME_DEF_STMT (ssa_name
) != stmt
)
175 error ("SSA_NAME_DEF_STMT is wrong");
176 fprintf (stderr
, "Expected definition statement:\n");
177 print_generic_stmt (stderr
, SSA_NAME_DEF_STMT (ssa_name
), TDF_VOPS
);
178 fprintf (stderr
, "\nActual definition statement:\n");
179 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
186 fprintf (stderr
, "while verifying SSA_NAME ");
187 print_generic_expr (stderr
, ssa_name
, 0);
188 fprintf (stderr
, " in statement\n");
189 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
195 /* Return true if the use of SSA_NAME at statement STMT in block BB is
198 DEF_BB is the block where SSA_NAME was found to be created.
200 IDOM contains immediate dominator information for the flowgraph.
202 CHECK_ABNORMAL is true if the caller wants to check whether this use
203 is flowing through an abnormal edge (only used when checking PHI
206 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
209 If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
210 that are defined before STMT in basic block BB. */
213 verify_use (basic_block bb
, basic_block def_bb
, tree ssa_name
,
214 tree stmt
, bool check_abnormal
, bool is_virtual
,
215 bitmap names_defined_in_bb
)
219 err
= verify_ssa_name (ssa_name
, is_virtual
);
220 TREE_VISITED (ssa_name
) = 1;
222 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name
))
223 && var_ann (SSA_NAME_VAR (ssa_name
))->default_def
== ssa_name
)
224 ; /* Default definitions have empty statements. Nothing to do. */
227 error ("Missing definition");
230 else if (bb
!= def_bb
231 && !dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
233 error ("Definition in block %i does not dominate use in block %i",
234 def_bb
->index
, bb
->index
);
237 else if (bb
== def_bb
238 && names_defined_in_bb
!= NULL
239 && !bitmap_bit_p (names_defined_in_bb
, SSA_NAME_VERSION (ssa_name
)))
241 error ("Definition in block %i follows the use", def_bb
->index
);
246 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name
))
248 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
254 fprintf (stderr
, "for SSA_NAME: ");
255 print_generic_expr (stderr
, ssa_name
, TDF_VOPS
);
256 fprintf (stderr
, "in statement:\n");
257 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
264 /* Return true if any of the arguments for PHI node PHI at block BB is
267 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
268 numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
269 block in that array slot contains the definition of SSA_NAME. */
272 verify_phi_args (tree phi
, basic_block bb
, basic_block
*definition_block
)
276 unsigned i
, phi_num_args
= PHI_NUM_ARGS (phi
);
278 if (EDGE_COUNT (bb
->preds
) != phi_num_args
)
280 error ("Incoming edge count does not match number of PHI arguments\n");
285 for (i
= 0; i
< phi_num_args
; i
++)
287 tree op
= PHI_ARG_DEF (phi
, i
);
289 e
= EDGE_PRED (bb
, i
);
293 error ("PHI argument is missing for edge %d->%d\n",
300 if (TREE_CODE (op
) != SSA_NAME
&& !is_gimple_min_invariant (op
))
302 error ("PHI argument is not SSA_NAME, or invariant");
306 if (TREE_CODE (op
) == SSA_NAME
)
307 err
= verify_use (e
->src
, definition_block
[SSA_NAME_VERSION (op
)], op
,
308 phi
, e
->flags
& EDGE_ABNORMAL
,
309 !is_gimple_reg (PHI_RESULT (phi
)),
314 error ("Wrong edge %d->%d for PHI argument\n",
315 e
->src
->index
, e
->dest
->index
, bb
->index
);
321 fprintf (stderr
, "PHI argument\n");
322 print_generic_stmt (stderr
, op
, TDF_VOPS
);
330 fprintf (stderr
, "for PHI node\n");
331 print_generic_stmt (stderr
, phi
, TDF_VOPS
);
340 verify_flow_insensitive_alias_info (void)
344 bitmap visited
= BITMAP_ALLOC (NULL
);
346 for (i
= 0; i
< num_referenced_vars
; i
++)
350 varray_type may_aliases
;
352 var
= referenced_var (i
);
354 may_aliases
= ann
->may_aliases
;
356 for (j
= 0; may_aliases
&& j
< VARRAY_ACTIVE_SIZE (may_aliases
); j
++)
358 tree alias
= VARRAY_TREE (may_aliases
, j
);
360 bitmap_set_bit (visited
, var_ann (alias
)->uid
);
362 if (!may_be_aliased (alias
))
364 error ("Non-addressable variable inside an alias set.");
365 debug_variable (alias
);
371 for (i
= 0; i
< num_referenced_vars
; i
++)
375 var
= referenced_var (i
);
378 if (ann
->mem_tag_kind
== NOT_A_TAG
380 && !bitmap_bit_p (visited
, ann
->uid
))
382 error ("Addressable variable that is an alias tag but is not in any alias set.");
387 BITMAP_FREE (visited
);
391 debug_variable (var
);
392 internal_error ("verify_flow_insensitive_alias_info failed.");
397 verify_flow_sensitive_alias_info (void)
402 for (i
= 1; i
< num_ssa_names
; i
++)
406 struct ptr_info_def
*pi
;
413 /* We only care for pointers that are actually referenced in the
415 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)) || !TREE_VISITED (ptr
))
418 /* RESULT_DECL is special. If it's a GIMPLE register, then it
419 is only written-to only once in the return statement.
420 Otherwise, aggregate RESULT_DECLs may be written-to more than
421 once in virtual operands. */
422 var
= SSA_NAME_VAR (ptr
);
423 if (TREE_CODE (var
) == RESULT_DECL
424 && is_gimple_reg (ptr
))
427 pi
= SSA_NAME_PTR_INFO (ptr
);
432 if (pi
->is_dereferenced
&& !pi
->name_mem_tag
&& !ann
->type_mem_tag
)
434 error ("Dereferenced pointers should have a name or a type tag");
440 && (pi
->pt_vars
== NULL
|| bitmap_empty_p (pi
->pt_vars
)))
442 error ("Pointers with a memory tag, should have points-to sets or point to malloc");
446 if (pi
->value_escapes_p
448 && !is_call_clobbered (pi
->name_mem_tag
))
450 error ("Pointer escapes but its name tag is not call-clobbered.");
458 debug_variable (ptr
);
459 internal_error ("verify_flow_sensitive_alias_info failed.");
462 DEF_VEC_MALLOC_P (bitmap
);
464 /* Verify that all name tags have different points to sets.
465 This algorithm takes advantage of the fact that every variable with the
466 same name tag must have the same points-to set.
467 So we check a single variable for each name tag, and verify that its
468 points-to set is different from every other points-to set for other name
471 Additionally, given a pointer P_i with name tag NMT and type tag
472 TMT, this function verified the alias set of TMT is a superset of
473 the alias set of NMT. */
476 verify_name_tags (void)
480 bitmap first
, second
;
481 VEC (tree
) *name_tag_reps
= NULL
;
482 VEC (bitmap
) *pt_vars_for_reps
= NULL
;
483 bitmap type_aliases
= BITMAP_ALLOC (NULL
);
485 /* First we compute the name tag representatives and their points-to sets. */
486 for (i
= 0; i
< num_ssa_names
; i
++)
488 struct ptr_info_def
*pi
;
489 tree tmt
, ptr
= ssa_name (i
);
491 if (ptr
== NULL_TREE
)
494 pi
= SSA_NAME_PTR_INFO (ptr
);
496 if (!TREE_VISITED (ptr
)
497 || !POINTER_TYPE_P (TREE_TYPE (ptr
))
500 || TREE_VISITED (pi
->name_mem_tag
))
503 TREE_VISITED (pi
->name_mem_tag
) = 1;
505 if (pi
->pt_vars
== NULL
)
508 VEC_safe_push (tree
, name_tag_reps
, ptr
);
509 VEC_safe_push (bitmap
, pt_vars_for_reps
, pi
->pt_vars
);
511 /* Verify that alias set of PTR's type tag is a superset of the
512 alias set of PTR's name tag. */
513 tmt
= var_ann (SSA_NAME_VAR (ptr
))->type_mem_tag
;
517 varray_type aliases
= var_ann (tmt
)->may_aliases
;
518 bitmap_clear (type_aliases
);
519 for (i
= 0; aliases
&& i
< VARRAY_ACTIVE_SIZE (aliases
); i
++)
521 tree alias
= VARRAY_TREE (aliases
, i
);
522 bitmap_set_bit (type_aliases
, var_ann (alias
)->uid
);
525 /* When grouping, we may have added PTR's type tag into the
526 alias set of PTR's name tag. To prevent a false
527 positive, pretend that TMT is in its own alias set. */
528 bitmap_set_bit (type_aliases
, var_ann (tmt
)->uid
);
530 if (bitmap_equal_p (type_aliases
, pi
->pt_vars
))
533 if (!bitmap_intersect_compl_p (type_aliases
, pi
->pt_vars
))
535 error ("Alias set of a pointer's type tag should be a superset of the corresponding name tag");
536 debug_variable (tmt
);
537 debug_variable (pi
->name_mem_tag
);
543 /* Now compare all the representative bitmaps with all other representative
544 bitmaps, to verify that they are all different. */
545 for (i
= 0; VEC_iterate (bitmap
, pt_vars_for_reps
, i
, first
); i
++)
547 for (j
= i
+ 1; VEC_iterate (bitmap
, pt_vars_for_reps
, j
, second
); j
++)
549 if (bitmap_equal_p (first
, second
))
551 error ("Two different pointers with identical points-to sets but different name tags");
552 debug_variable (VEC_index (tree
, name_tag_reps
, j
));
558 /* Lastly, clear out the visited flags. */
559 for (i
= 0; i
< num_ssa_names
; i
++)
563 tree ptr
= ssa_name (i
);
564 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
565 if (!TREE_VISITED (ptr
)
566 || !POINTER_TYPE_P (TREE_TYPE (ptr
))
568 || !pi
->name_mem_tag
)
570 TREE_VISITED (pi
->name_mem_tag
) = 0;
574 VEC_free (bitmap
, pt_vars_for_reps
);
575 BITMAP_FREE (type_aliases
);
579 debug_variable (VEC_index (tree
, name_tag_reps
, i
));
580 internal_error ("verify_name_tags failed");
584 /* Verify the consistency of aliasing information. */
587 verify_alias_info (void)
589 verify_flow_sensitive_alias_info ();
591 verify_flow_insensitive_alias_info ();
595 /* Verify common invariants in the SSA web.
596 TODO: verify the variable annotations. */
603 basic_block
*definition_block
= xcalloc (num_ssa_names
, sizeof (basic_block
));
606 enum dom_state orig_dom_state
= dom_computed
[CDI_DOMINATORS
];
607 bitmap names_defined_in_bb
= BITMAP_ALLOC (NULL
);
609 timevar_push (TV_TREE_SSA_VERIFY
);
611 /* Keep track of SSA names present in the IL. */
612 for (i
= 1; i
< num_ssa_names
; i
++)
614 tree name
= ssa_name (i
);
618 TREE_VISITED (name
) = 0;
620 stmt
= SSA_NAME_DEF_STMT (name
);
621 if (!IS_EMPTY_STMT (stmt
))
623 basic_block bb
= bb_for_stmt (stmt
);
624 verify_def (bb
, definition_block
,
625 name
, stmt
, !is_gimple_reg (name
));
631 calculate_dominance_info (CDI_DOMINATORS
);
633 /* Now verify all the uses and make sure they agree with the definitions
634 found in the previous pass. */
640 block_stmt_iterator bsi
;
642 /* Make sure that all edges have a clear 'aux' field. */
643 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
647 error ("AUX pointer initialized for edge %d->%d\n", e
->src
->index
,
653 /* Verify the arguments for every PHI node in the block. */
654 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
656 if (verify_phi_args (phi
, bb
, definition_block
))
658 bitmap_set_bit (names_defined_in_bb
,
659 SSA_NAME_VERSION (PHI_RESULT (phi
)));
662 /* Now verify all the uses and vuses in every statement of the block. */
663 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
665 tree stmt
= bsi_stmt (bsi
);
667 get_stmt_operands (stmt
);
669 if (stmt_ann (stmt
)->makes_aliased_stores
670 && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt
)) == 0)
672 error ("Statement makes aliased stores, but has no V_MAY_DEFS");
673 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
677 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_ALL_USES
| SSA_OP_ALL_KILLS
)
679 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
680 op
, stmt
, false, !is_gimple_reg (op
),
681 names_defined_in_bb
))
685 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_ALL_DEFS
)
687 bitmap_set_bit (names_defined_in_bb
, SSA_NAME_VERSION (op
));
691 bitmap_clear (names_defined_in_bb
);
694 /* Finally, verify alias information. */
695 verify_alias_info ();
697 free (definition_block
);
698 /* Restore the dominance information to its prior known state, so
699 that we do not perturb the compiler's subsequent behavior. */
700 if (orig_dom_state
== DOM_NONE
)
701 free_dominance_info (CDI_DOMINATORS
);
703 dom_computed
[CDI_DOMINATORS
] = orig_dom_state
;
705 BITMAP_FREE (names_defined_in_bb
);
706 timevar_pop (TV_TREE_SSA_VERIFY
);
710 internal_error ("verify_ssa failed.");
714 /* Initialize global DFA and SSA structures. */
719 VARRAY_TREE_INIT (referenced_vars
, 20, "referenced_vars");
720 call_clobbered_vars
= BITMAP_ALLOC (NULL
);
721 addressable_vars
= BITMAP_ALLOC (NULL
);
722 init_ssa_operands ();
725 global_var
= NULL_TREE
;
726 aliases_computed_p
= false;
730 /* Deallocate memory associated with SSA data structures for FNDECL. */
733 delete_tree_ssa (void)
737 block_stmt_iterator bsi
;
739 /* Remove annotations from every tree in the function. */
741 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
743 tree stmt
= bsi_stmt (bsi
);
745 ggc_free (stmt
->common
.ann
);
746 stmt
->common
.ann
= NULL
;
749 /* Remove annotations from every referenced variable. */
752 for (i
= 0; i
< num_referenced_vars
; i
++)
754 tree var
= referenced_var (i
);
755 ggc_free (var
->common
.ann
);
756 var
->common
.ann
= NULL
;
758 referenced_vars
= NULL
;
763 fini_ssa_operands ();
765 global_var
= NULL_TREE
;
766 BITMAP_FREE (call_clobbered_vars
);
767 call_clobbered_vars
= NULL
;
768 BITMAP_FREE (addressable_vars
);
769 addressable_vars
= NULL
;
770 modified_noreturn_calls
= NULL
;
771 aliases_computed_p
= false;
775 /* Return true if EXPR is a useless type conversion, otherwise return
779 tree_ssa_useless_type_conversion_1 (tree outer_type
, tree inner_type
)
781 if (inner_type
== outer_type
)
784 /* Changes in machine mode are never useless conversions. */
785 if (TYPE_MODE (inner_type
) != TYPE_MODE (outer_type
))
788 /* If the inner and outer types are effectively the same, then
789 strip the type conversion and enter the equivalence into
791 if (lang_hooks
.types_compatible_p (inner_type
, outer_type
))
794 /* If both types are pointers and the outer type is a (void *), then
795 the conversion is not necessary. The opposite is not true since
796 that conversion would result in a loss of information if the
797 equivalence was used. Consider an indirect function call where
798 we need to know the exact type of the function to correctly
799 implement the ABI. */
800 else if (POINTER_TYPE_P (inner_type
)
801 && POINTER_TYPE_P (outer_type
)
802 && TYPE_REF_CAN_ALIAS_ALL (inner_type
)
803 == TYPE_REF_CAN_ALIAS_ALL (outer_type
)
804 && TREE_CODE (TREE_TYPE (outer_type
)) == VOID_TYPE
)
807 /* Don't lose casts between pointers to volatile and non-volatile
808 qualified types. Doing so would result in changing the semantics
809 of later accesses. */
810 else if (POINTER_TYPE_P (inner_type
)
811 && POINTER_TYPE_P (outer_type
)
812 && TYPE_VOLATILE (TREE_TYPE (outer_type
))
813 != TYPE_VOLATILE (TREE_TYPE (inner_type
)))
816 /* Pointers and references are equivalent once we get to GENERIC,
817 so strip conversions that just switch between them. */
818 else if (POINTER_TYPE_P (inner_type
)
819 && POINTER_TYPE_P (outer_type
)
820 && TYPE_REF_CAN_ALIAS_ALL (inner_type
)
821 == TYPE_REF_CAN_ALIAS_ALL (outer_type
)
822 && lang_hooks
.types_compatible_p (TREE_TYPE (inner_type
),
823 TREE_TYPE (outer_type
)))
826 /* If both the inner and outer types are integral types, then the
827 conversion is not necessary if they have the same mode and
828 signedness and precision, and both or neither are boolean. Some
829 code assumes an invariant that boolean types stay boolean and do
830 not become 1-bit bit-field types. Note that types with precision
831 not using all bits of the mode (such as bit-field types in C)
832 mean that testing of precision is necessary. */
833 else if (INTEGRAL_TYPE_P (inner_type
)
834 && INTEGRAL_TYPE_P (outer_type
)
835 && TYPE_UNSIGNED (inner_type
) == TYPE_UNSIGNED (outer_type
)
836 && TYPE_PRECISION (inner_type
) == TYPE_PRECISION (outer_type
))
838 bool first_boolean
= (TREE_CODE (inner_type
) == BOOLEAN_TYPE
);
839 bool second_boolean
= (TREE_CODE (outer_type
) == BOOLEAN_TYPE
);
840 if (first_boolean
== second_boolean
)
844 /* Recurse for complex types. */
845 else if (TREE_CODE (inner_type
) == COMPLEX_TYPE
846 && TREE_CODE (outer_type
) == COMPLEX_TYPE
847 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type
),
848 TREE_TYPE (inner_type
)))
854 /* Return true if EXPR is a useless type conversion, otherwise return
858 tree_ssa_useless_type_conversion (tree expr
)
860 /* If we have an assignment that merely uses a NOP_EXPR to change
861 the top of the RHS to the type of the LHS and the type conversion
862 is "safe", then strip away the type conversion so that we can
863 enter LHS = RHS into the const_and_copies table. */
864 if (TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
865 || TREE_CODE (expr
) == VIEW_CONVERT_EXPR
866 || TREE_CODE (expr
) == NON_LVALUE_EXPR
)
867 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr
),
868 TREE_TYPE (TREE_OPERAND (expr
,
875 /* Returns true if statement STMT may read memory. */
878 stmt_references_memory_p (tree stmt
)
882 get_stmt_operands (stmt
);
883 ann
= stmt_ann (stmt
);
885 if (ann
->has_volatile_ops
)
888 return (NUM_VUSES (VUSE_OPS (ann
)) > 0
889 || NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann
)) > 0
890 || NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann
)) > 0);
893 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
894 described in walk_use_def_chains.
896 VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
897 infinite loops. We used to have a bitmap for this to just mark
898 SSA versions we had visited. But non-sparse bitmaps are way too
899 expensive, while sparse bitmaps may cause quadratic behavior.
901 IS_DFS is true if the caller wants to perform a depth-first search
902 when visiting PHI nodes. A DFS will visit each PHI argument and
903 call FN after each one. Otherwise, all the arguments are
904 visited first and then FN is called with each of the visited
905 arguments in a separate pass. */
908 walk_use_def_chains_1 (tree var
, walk_use_def_chains_fn fn
, void *data
,
909 struct pointer_set_t
*visited
, bool is_dfs
)
913 if (pointer_set_insert (visited
, var
))
916 def_stmt
= SSA_NAME_DEF_STMT (var
);
918 if (TREE_CODE (def_stmt
) != PHI_NODE
)
920 /* If we reached the end of the use-def chain, call FN. */
921 return fn (var
, def_stmt
, data
);
927 /* When doing a breadth-first search, call FN before following the
928 use-def links for each argument. */
930 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
931 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
934 /* Follow use-def links out of each PHI argument. */
935 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
937 tree arg
= PHI_ARG_DEF (def_stmt
, i
);
938 if (TREE_CODE (arg
) == SSA_NAME
939 && walk_use_def_chains_1 (arg
, fn
, data
, visited
, is_dfs
))
943 /* When doing a depth-first search, call FN after following the
944 use-def links for each argument. */
946 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
947 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
956 /* Walk use-def chains starting at the SSA variable VAR. Call
957 function FN at each reaching definition found. FN takes three
958 arguments: VAR, its defining statement (DEF_STMT) and a generic
959 pointer to whatever state information that FN may want to maintain
960 (DATA). FN is able to stop the walk by returning true, otherwise
961 in order to continue the walk, FN should return false.
963 Note, that if DEF_STMT is a PHI node, the semantics are slightly
964 different. The first argument to FN is no longer the original
965 variable VAR, but the PHI argument currently being examined. If FN
966 wants to get at VAR, it should call PHI_RESULT (PHI).
968 If IS_DFS is true, this function will:
970 1- walk the use-def chains for all the PHI arguments, and,
971 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
973 If IS_DFS is false, the two steps above are done in reverse order
974 (i.e., a breadth-first search). */
978 walk_use_def_chains (tree var
, walk_use_def_chains_fn fn
, void *data
,
983 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
985 def_stmt
= SSA_NAME_DEF_STMT (var
);
987 /* We only need to recurse if the reaching definition comes from a PHI
989 if (TREE_CODE (def_stmt
) != PHI_NODE
)
990 (*fn
) (var
, def_stmt
, data
);
993 struct pointer_set_t
*visited
= pointer_set_create ();
994 walk_use_def_chains_1 (var
, fn
, data
, visited
, is_dfs
);
995 pointer_set_destroy (visited
);
1000 /* Replaces VAR with REPL in memory reference expression *X in
1004 propagate_into_addr (tree stmt
, tree var
, tree
*x
, tree repl
)
1006 tree new_var
, ass_stmt
, addr_var
;
1008 block_stmt_iterator bsi
;
1010 /* There is nothing special to handle in the other cases. */
1011 if (TREE_CODE (repl
) != ADDR_EXPR
)
1013 addr_var
= TREE_OPERAND (repl
, 0);
1015 while (handled_component_p (*x
)
1016 || TREE_CODE (*x
) == REALPART_EXPR
1017 || TREE_CODE (*x
) == IMAGPART_EXPR
)
1018 x
= &TREE_OPERAND (*x
, 0);
1020 if (TREE_CODE (*x
) != INDIRECT_REF
1021 || TREE_OPERAND (*x
, 0) != var
)
1024 if (TREE_TYPE (*x
) == TREE_TYPE (addr_var
))
1027 mark_new_vars_to_rename (stmt
, vars_to_rename
);
1032 /* Frontends sometimes produce expressions like *&a instead of a[0].
1033 Create a temporary variable to handle this case. */
1034 ass_stmt
= build2 (MODIFY_EXPR
, void_type_node
, NULL_TREE
, repl
);
1035 new_var
= duplicate_ssa_name (var
, ass_stmt
);
1036 TREE_OPERAND (*x
, 0) = new_var
;
1037 TREE_OPERAND (ass_stmt
, 0) = new_var
;
1039 bb
= bb_for_stmt (stmt
);
1040 tree_block_label (bb
);
1041 bsi
= bsi_after_labels (bb
);
1042 bsi_insert_after (&bsi
, ass_stmt
, BSI_NEW_STMT
);
1044 mark_new_vars_to_rename (stmt
, vars_to_rename
);
1047 /* Replaces immediate uses of VAR by REPL. */
1050 replace_immediate_uses (tree var
, tree repl
)
1057 use_operand_p use_p
;
1059 df
= get_immediate_uses (SSA_NAME_DEF_STMT (var
));
1060 n
= num_immediate_uses (df
);
1062 for (i
= 0; i
< n
; i
++)
1064 stmt
= immediate_use (df
, i
);
1066 if (TREE_CODE (stmt
) == PHI_NODE
)
1068 for (j
= 0; j
< PHI_NUM_ARGS (stmt
); j
++)
1069 if (PHI_ARG_DEF (stmt
, j
) == var
)
1071 SET_PHI_ARG_DEF (stmt
, j
, repl
);
1072 if (TREE_CODE (repl
) == SSA_NAME
1073 && PHI_ARG_EDGE (stmt
, j
)->flags
& EDGE_ABNORMAL
)
1074 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl
) = 1;
1080 get_stmt_operands (stmt
);
1081 mark_new_vars
= false;
1082 if (is_gimple_reg (SSA_NAME_VAR (var
)))
1084 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
1086 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 0), repl
);
1087 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 1), repl
);
1090 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
1091 if (USE_FROM_PTR (use_p
) == var
)
1093 propagate_value (use_p
, repl
);
1094 mark_new_vars
= POINTER_TYPE_P (TREE_TYPE (repl
));
1099 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
,
1100 SSA_OP_VIRTUAL_USES
| SSA_OP_VIRTUAL_KILLS
)
1101 if (USE_FROM_PTR (use_p
) == var
)
1102 propagate_value (use_p
, repl
);
1105 /* FIXME. If REPL is a constant, we need to fold STMT.
1106 However, fold_stmt wants a pointer to the statement, because
1107 it may happen that it needs to replace the whole statement
1108 with a new expression. Since the current def-use machinery
1109 does not return pointers to statements, we call fold_stmt
1110 with the address of a local temporary, if that call changes
1111 the temporary then we fallback on looking for a proper
1112 pointer to STMT by scanning STMT's basic block.
1114 Note that all this will become unnecessary soon. This
1115 pass is being replaced with a proper copy propagation pass
1116 for 4.1 (dnovillo, 2004-09-17). */
1117 if (TREE_CODE (repl
) != SSA_NAME
)
1121 mark_new_vars
= true;
1124 block_stmt_iterator si
= bsi_for_stmt (stmt
);
1125 mark_new_vars_to_rename (tmp
, vars_to_rename
);
1126 redirect_immediate_uses (stmt
, tmp
);
1127 bsi_replace (&si
, tmp
, true);
1128 stmt
= bsi_stmt (si
);
1132 /* If REPL is a pointer, it may have different memory tags associated
1133 with it. For instance, VAR may have had a name tag while REPL
1134 only had a type tag. In these cases, the virtual operands (if
1135 any) in the statement will refer to different symbols which need
1138 mark_new_vars_to_rename (stmt
, vars_to_rename
);
1144 /* Gets the value VAR is equivalent to according to EQ_TO. */
1147 get_eq_name (tree
*eq_to
, tree var
)
1152 while (TREE_CODE (val
) == SSA_NAME
)
1154 ver
= SSA_NAME_VERSION (val
);
1161 while (TREE_CODE (var
) == SSA_NAME
)
1163 ver
= SSA_NAME_VERSION (var
);
1174 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1175 its result is redundant to to EQ_TO array. */
1178 check_phi_redundancy (tree phi
, tree
*eq_to
)
1180 tree val
= NULL_TREE
, def
, res
= PHI_RESULT (phi
), stmt
;
1181 unsigned i
, ver
= SSA_NAME_VERSION (res
), n
;
1184 /* It is unlikely that such large phi node would be redundant. */
1185 if (PHI_NUM_ARGS (phi
) > 16)
1188 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (phi
); i
++)
1190 def
= PHI_ARG_DEF (phi
, i
);
1192 if (TREE_CODE (def
) == SSA_NAME
)
1194 def
= get_eq_name (eq_to
, def
);
1200 && !operand_equal_for_phi_arg_p (val
, def
))
1206 /* At least one of the arguments should not be equal to the result, or
1207 something strange is happening. */
1210 if (get_eq_name (eq_to
, res
) == val
)
1213 if (!may_propagate_copy (res
, val
))
1218 df
= get_immediate_uses (SSA_NAME_DEF_STMT (res
));
1219 n
= num_immediate_uses (df
);
1221 for (i
= 0; i
< n
; i
++)
1223 stmt
= immediate_use (df
, i
);
1225 if (TREE_CODE (stmt
) == PHI_NODE
)
1226 check_phi_redundancy (stmt
, eq_to
);
1230 /* Removes redundant phi nodes.
1232 A redundant PHI node is a PHI node where all of its PHI arguments
1233 are the same value, excluding any PHI arguments which are the same
1236 A redundant PHI node is effectively a copy, so we forward copy propagate
1237 which removes all uses of the destination of the PHI node then
1238 finally we delete the redundant PHI node.
1240 Note that if we can not copy propagate the PHI node, then the PHI
1241 will not be removed. Thus we do not have to worry about dependencies
1242 between PHIs and the problems serializing PHIs into copies creates.
1244 The most important effect of this pass is to remove degenerate PHI
1245 nodes created by removing unreachable code. */
1248 kill_redundant_phi_nodes (void)
1251 unsigned i
, old_num_ssa_names
;
1253 tree phi
, var
, repl
, stmt
;
1255 /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1256 replaced. If EQ_TO[VER] is ssa name and it is decided to replace it by
1257 other value, it may be necessary to follow the chain till the final value.
1258 We perform path shortening (replacing the entries of the EQ_TO array with
1259 heads of these chains) whenever we access the field to prevent quadratic
1260 complexity (probably would not occur in practice anyway, but let us play
1262 eq_to
= xcalloc (num_ssa_names
, sizeof (tree
));
1264 /* We have had cases where computing immediate uses takes a
1265 significant amount of compile time. If we run into such
1266 problems here, we may want to only compute immediate uses for
1267 a subset of all the SSA_NAMEs instead of computing it for
1268 all of the SSA_NAMEs. */
1269 compute_immediate_uses (TDFA_USE_OPS
| TDFA_USE_VOPS
, NULL
);
1270 old_num_ssa_names
= num_ssa_names
;
1274 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1276 var
= PHI_RESULT (phi
);
1277 check_phi_redundancy (phi
, eq_to
);
1281 /* Now propagate the values. */
1282 for (i
= 0; i
< old_num_ssa_names
; i
++)
1287 repl
= get_eq_name (eq_to
, ssa_name (i
));
1288 if (repl
!= ssa_name (i
))
1289 replace_immediate_uses (ssa_name (i
), repl
);
1292 /* And remove the dead phis. */
1293 for (i
= 0; i
< old_num_ssa_names
; i
++)
1298 repl
= get_eq_name (eq_to
, ssa_name (i
));
1299 if (repl
!= ssa_name (i
))
1301 stmt
= SSA_NAME_DEF_STMT (ssa_name (i
));
1302 remove_phi_node (stmt
, NULL_TREE
, bb_for_stmt (stmt
));
1310 struct tree_opt_pass pass_redundant_phi
=
1312 "redphi", /* name */
1314 kill_redundant_phi_nodes
, /* execute */
1317 0, /* static_pass_number */
1318 TV_TREE_REDPHI
, /* tv_id */
1319 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
1320 0, /* properties_provided */
1321 0, /* properties_destroyed */
1322 0, /* todo_flags_start */
1323 TODO_dump_func
| TODO_rename_vars
1324 | TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */
1328 /* Emit warnings for uninitialized variables. This is done in two passes.
1330 The first pass notices real uses of SSA names with default definitions.
1331 Such uses are unconditionally uninitialized, and we can be certain that
1332 such a use is a mistake. This pass is run before most optimizations,
1333 so that we catch as many as we can.
1335 The second pass follows PHI nodes to find uses that are potentially
1336 uninitialized. In this case we can't necessarily prove that the use
1337 is really uninitialized. This pass is run after most optimizations,
1338 so that we thread as many jumps and possible, and delete as much dead
1339 code as possible, in order to reduce false positives. We also look
1340 again for plain uninitialized variables, since optimization may have
1341 changed conditionally uninitialized to unconditionally uninitialized. */
1343 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1344 warning text is in MSGID and LOCUS may contain a location or be null. */
1347 warn_uninit (tree t
, const char *gmsgid
, location_t
*locus
)
1349 tree var
= SSA_NAME_VAR (t
);
1350 tree def
= SSA_NAME_DEF_STMT (t
);
1352 /* Default uses (indicated by an empty definition statement),
1353 are uninitialized. */
1354 if (!IS_EMPTY_STMT (def
))
1357 /* Except for PARMs of course, which are always initialized. */
1358 if (TREE_CODE (var
) == PARM_DECL
)
1361 /* Hard register variables get their initial value from the ether. */
1362 if (TREE_CODE (var
) == VAR_DECL
&& DECL_HARD_REGISTER (var
))
1365 /* TREE_NO_WARNING either means we already warned, or the front end
1366 wishes to suppress the warning. */
1367 if (TREE_NO_WARNING (var
))
1371 locus
= &DECL_SOURCE_LOCATION (var
);
1372 warning (gmsgid
, locus
, var
);
1373 TREE_NO_WARNING (var
) = 1;
1376 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1377 and warn about them. */
1380 warn_uninitialized_var (tree
*tp
, int *walk_subtrees
, void *data
)
1382 location_t
*locus
= data
;
1385 /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */
1386 if (TREE_CODE (t
) == SSA_NAME
)
1388 warn_uninit (t
, "%H%qD is used uninitialized in this function", locus
);
1391 else if (IS_TYPE_OR_DECL_P (t
))
1397 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1398 and warn about them. */
1401 warn_uninitialized_phi (tree phi
)
1403 int i
, n
= PHI_NUM_ARGS (phi
);
1405 /* Don't look at memory tags. */
1406 if (!is_gimple_reg (PHI_RESULT (phi
)))
1409 for (i
= 0; i
< n
; ++i
)
1411 tree op
= PHI_ARG_DEF (phi
, i
);
1412 if (TREE_CODE (op
) == SSA_NAME
)
1413 warn_uninit (op
, "%H%qD may be used uninitialized in this function",
1419 execute_early_warn_uninitialized (void)
1421 block_stmt_iterator bsi
;
1425 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1426 walk_tree (bsi_stmt_ptr (bsi
), warn_uninitialized_var
,
1427 EXPR_LOCUS (bsi_stmt (bsi
)), NULL
);
1431 execute_late_warn_uninitialized (void)
1436 /* Re-do the plain uninitialized variable check, as optimization may have
1437 straightened control flow. Do this first so that we don't accidentally
1438 get a "may be" warning when we'd have seen an "is" warning later. */
1439 execute_early_warn_uninitialized ();
1442 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1443 warn_uninitialized_phi (phi
);
1447 gate_warn_uninitialized (void)
1449 return warn_uninitialized
!= 0;
1452 struct tree_opt_pass pass_early_warn_uninitialized
=
1455 gate_warn_uninitialized
, /* gate */
1456 execute_early_warn_uninitialized
, /* execute */
1459 0, /* static_pass_number */
1461 PROP_ssa
, /* properties_required */
1462 0, /* properties_provided */
1463 0, /* properties_destroyed */
1464 0, /* todo_flags_start */
1465 0, /* todo_flags_finish */
1469 struct tree_opt_pass pass_late_warn_uninitialized
=
1472 gate_warn_uninitialized
, /* gate */
1473 execute_late_warn_uninitialized
, /* execute */
1476 0, /* static_pass_number */
1478 PROP_ssa
, /* properties_required */
1479 0, /* properties_provided */
1480 0, /* properties_destroyed */
1481 0, /* todo_flags_start */
1482 0, /* todo_flags_finish */