1 /* Miscellaneous SSA utility functions.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007 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 3, 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 COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
29 #include "langhooks.h"
30 #include "hard-reg-set.h"
31 #include "basic-block.h"
35 #include "diagnostic.h"
37 #include "pointer-set.h"
38 #include "tree-flow.h"
39 #include "tree-gimple.h"
40 #include "tree-inline.h"
44 #include "tree-dump.h"
45 #include "tree-pass.h"
48 /* Remove the corresponding arguments from the PHI nodes in E's
49 destination block and redirect it to DEST. Return redirected edge.
50 The list of removed arguments is stored in PENDING_STMT (e). */
53 ssa_redirect_edge (edge e
, basic_block dest
)
56 tree list
= NULL
, *last
= &list
;
59 /* Remove the appropriate PHI arguments in E's destination block. */
60 for (phi
= phi_nodes (e
->dest
); phi
; phi
= PHI_CHAIN (phi
))
62 if (PHI_ARG_DEF (phi
, e
->dest_idx
) == NULL_TREE
)
65 src
= PHI_ARG_DEF (phi
, e
->dest_idx
);
66 dst
= PHI_RESULT (phi
);
67 node
= build_tree_list (dst
, src
);
69 last
= &TREE_CHAIN (node
);
72 e
= redirect_edge_succ_nodup (e
, dest
);
73 PENDING_STMT (e
) = list
;
78 /* Add PHI arguments queued in PENDINT_STMT list on edge E to edge
82 flush_pending_stmts (edge e
)
86 if (!PENDING_STMT (e
))
89 for (phi
= phi_nodes (e
->dest
), arg
= PENDING_STMT (e
);
91 phi
= PHI_CHAIN (phi
), arg
= TREE_CHAIN (arg
))
93 tree def
= TREE_VALUE (arg
);
94 add_phi_arg (phi
, def
, e
);
97 PENDING_STMT (e
) = NULL
;
100 /* Return true if SSA_NAME is malformed and mark it visited.
102 IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
106 verify_ssa_name (tree ssa_name
, bool is_virtual
)
108 if (TREE_CODE (ssa_name
) != SSA_NAME
)
110 error ("expected an SSA_NAME object");
114 if (TREE_TYPE (ssa_name
) != TREE_TYPE (SSA_NAME_VAR (ssa_name
)))
116 error ("type mismatch between an SSA_NAME and its symbol");
120 if (SSA_NAME_IN_FREE_LIST (ssa_name
))
122 error ("found an SSA_NAME that had been released into the free pool");
126 if (is_virtual
&& is_gimple_reg (ssa_name
))
128 error ("found a virtual definition for a GIMPLE register");
132 if (!is_virtual
&& !is_gimple_reg (ssa_name
))
134 error ("found a real definition for a non-register");
138 if (is_virtual
&& var_ann (SSA_NAME_VAR (ssa_name
))
139 && get_subvars_for_var (SSA_NAME_VAR (ssa_name
)) != NULL
)
141 error ("found real variable when subvariables should have appeared");
149 /* Return true if the definition of SSA_NAME at block BB is malformed.
151 STMT is the statement where SSA_NAME is created.
153 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
154 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
155 it means that the block in that array slot contains the
156 definition of SSA_NAME.
158 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
162 verify_def (basic_block bb
, basic_block
*definition_block
, tree ssa_name
,
163 tree stmt
, bool is_virtual
)
165 if (verify_ssa_name (ssa_name
, is_virtual
))
168 if (definition_block
[SSA_NAME_VERSION (ssa_name
)])
170 error ("SSA_NAME created in two different blocks %i and %i",
171 definition_block
[SSA_NAME_VERSION (ssa_name
)]->index
, bb
->index
);
175 definition_block
[SSA_NAME_VERSION (ssa_name
)] = bb
;
177 if (SSA_NAME_DEF_STMT (ssa_name
) != stmt
)
179 error ("SSA_NAME_DEF_STMT is wrong");
180 fprintf (stderr
, "Expected definition statement:\n");
181 print_generic_stmt (stderr
, SSA_NAME_DEF_STMT (ssa_name
), TDF_VOPS
);
182 fprintf (stderr
, "\nActual definition statement:\n");
183 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
190 fprintf (stderr
, "while verifying SSA_NAME ");
191 print_generic_expr (stderr
, ssa_name
, 0);
192 fprintf (stderr
, " in statement\n");
193 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
199 /* Return true if the use of SSA_NAME at statement STMT in block BB is
202 DEF_BB is the block where SSA_NAME was found to be created.
204 IDOM contains immediate dominator information for the flowgraph.
206 CHECK_ABNORMAL is true if the caller wants to check whether this use
207 is flowing through an abnormal edge (only used when checking PHI
210 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
213 If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
214 that are defined before STMT in basic block BB. */
217 verify_use (basic_block bb
, basic_block def_bb
, use_operand_p use_p
,
218 tree stmt
, bool check_abnormal
, bool is_virtual
,
219 bitmap names_defined_in_bb
)
222 tree ssa_name
= USE_FROM_PTR (use_p
);
224 err
= verify_ssa_name (ssa_name
, is_virtual
);
226 if (!TREE_VISITED (ssa_name
))
227 if (verify_imm_links (stderr
, ssa_name
))
230 TREE_VISITED (ssa_name
) = 1;
232 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name
))
233 && default_def (SSA_NAME_VAR (ssa_name
)) == ssa_name
)
234 ; /* Default definitions have empty statements. Nothing to do. */
237 error ("missing definition");
240 else if (bb
!= def_bb
241 && !dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
243 error ("definition in block %i does not dominate use in block %i",
244 def_bb
->index
, bb
->index
);
247 else if (bb
== def_bb
248 && names_defined_in_bb
!= NULL
249 && !bitmap_bit_p (names_defined_in_bb
, SSA_NAME_VERSION (ssa_name
)))
251 error ("definition in block %i follows the use", def_bb
->index
);
256 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name
))
258 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
262 /* Make sure the use is in an appropriate list by checking the previous
263 element to make sure it's the same. */
264 if (use_p
->prev
== NULL
)
266 error ("no immediate_use list");
272 if (use_p
->prev
->use
== NULL
)
273 listvar
= use_p
->prev
->stmt
;
275 listvar
= USE_FROM_PTR (use_p
->prev
);
276 if (listvar
!= ssa_name
)
278 error ("wrong immediate use list");
285 fprintf (stderr
, "for SSA_NAME: ");
286 print_generic_expr (stderr
, ssa_name
, TDF_VOPS
);
287 fprintf (stderr
, " in statement:\n");
288 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
295 /* Return true if any of the arguments for PHI node PHI at block BB is
298 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
299 numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
300 block in that array slot contains the definition of SSA_NAME. */
303 verify_phi_args (tree phi
, basic_block bb
, basic_block
*definition_block
)
307 unsigned i
, phi_num_args
= PHI_NUM_ARGS (phi
);
309 if (EDGE_COUNT (bb
->preds
) != phi_num_args
)
311 error ("incoming edge count does not match number of PHI arguments");
316 for (i
= 0; i
< phi_num_args
; i
++)
318 use_operand_p op_p
= PHI_ARG_DEF_PTR (phi
, i
);
319 tree op
= USE_FROM_PTR (op_p
);
322 e
= EDGE_PRED (bb
, i
);
326 error ("PHI argument is missing for edge %d->%d",
333 if (TREE_CODE (op
) != SSA_NAME
&& !is_gimple_min_invariant (op
))
335 error ("PHI argument is not SSA_NAME, or invariant");
339 if (TREE_CODE (op
) == SSA_NAME
)
340 err
= verify_use (e
->src
, definition_block
[SSA_NAME_VERSION (op
)], op_p
,
341 phi
, e
->flags
& EDGE_ABNORMAL
,
342 !is_gimple_reg (PHI_RESULT (phi
)),
347 error ("wrong edge %d->%d for PHI argument",
348 e
->src
->index
, e
->dest
->index
);
354 fprintf (stderr
, "PHI argument\n");
355 print_generic_stmt (stderr
, op
, TDF_VOPS
);
363 fprintf (stderr
, "for PHI node\n");
364 print_generic_stmt (stderr
, phi
, TDF_VOPS
);
373 verify_flow_insensitive_alias_info (void)
376 bitmap visited
= BITMAP_ALLOC (NULL
);
377 referenced_var_iterator rvi
;
379 FOR_EACH_REFERENCED_VAR (var
, rvi
)
383 VEC(tree
,gc
) *may_aliases
;
387 may_aliases
= ann
->may_aliases
;
389 for (j
= 0; VEC_iterate (tree
, may_aliases
, j
, alias
); j
++)
391 bitmap_set_bit (visited
, DECL_UID (alias
));
393 if (!may_be_aliased (alias
))
395 error ("non-addressable variable inside an alias set");
396 debug_variable (alias
);
402 FOR_EACH_REFERENCED_VAR (var
, rvi
)
409 && !bitmap_bit_p (visited
, DECL_UID (var
)))
411 error ("addressable variable that is aliased but is not in any alias set");
416 BITMAP_FREE (visited
);
420 debug_variable (var
);
421 internal_error ("verify_flow_insensitive_alias_info failed");
426 verify_flow_sensitive_alias_info (void)
431 for (i
= 1; i
< num_ssa_names
; i
++)
435 struct ptr_info_def
*pi
;
442 /* We only care for pointers that are actually referenced in the
444 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)) || !TREE_VISITED (ptr
))
447 /* RESULT_DECL is special. If it's a GIMPLE register, then it
448 is only written-to only once in the return statement.
449 Otherwise, aggregate RESULT_DECLs may be written-to more than
450 once in virtual operands. */
451 var
= SSA_NAME_VAR (ptr
);
452 if (TREE_CODE (var
) == RESULT_DECL
453 && is_gimple_reg (ptr
))
456 pi
= SSA_NAME_PTR_INFO (ptr
);
461 if (pi
->is_dereferenced
&& !pi
->name_mem_tag
&& !ann
->symbol_mem_tag
)
463 error ("dereferenced pointers should have a name or a symbol tag");
468 && (pi
->pt_vars
== NULL
|| bitmap_empty_p (pi
->pt_vars
)))
470 error ("pointers with a memory tag, should have points-to sets");
474 if (pi
->value_escapes_p
476 && !is_call_clobbered (pi
->name_mem_tag
))
478 error ("pointer escapes but its name tag is not call-clobbered");
486 debug_variable (ptr
);
487 internal_error ("verify_flow_sensitive_alias_info failed");
491 DEF_VEC_ALLOC_P (bitmap
,heap
);
493 /* Verify that all name tags have different points to sets.
494 This algorithm takes advantage of the fact that every variable with the
495 same name tag must have the same points-to set.
496 So we check a single variable for each name tag, and verify that its
497 points-to set is different from every other points-to set for other name
500 Additionally, given a pointer P_i with name tag NMT and symbol tag
501 SMT, this function verified the alias set of SMT is a superset of
502 the alias set of NMT. */
505 verify_name_tags (void)
509 bitmap first
, second
;
510 VEC(tree
,heap
) *name_tag_reps
= NULL
;
511 VEC(bitmap
,heap
) *pt_vars_for_reps
= NULL
;
512 bitmap type_aliases
= BITMAP_ALLOC (NULL
);
514 /* First we compute the name tag representatives and their points-to sets. */
515 for (i
= 0; i
< num_ssa_names
; i
++)
517 struct ptr_info_def
*pi
;
518 tree smt
, ptr
= ssa_name (i
);
520 if (ptr
== NULL_TREE
)
523 pi
= SSA_NAME_PTR_INFO (ptr
);
525 if (!TREE_VISITED (ptr
)
526 || !POINTER_TYPE_P (TREE_TYPE (ptr
))
529 || TREE_VISITED (pi
->name_mem_tag
))
532 TREE_VISITED (pi
->name_mem_tag
) = 1;
534 if (pi
->pt_vars
== NULL
)
537 VEC_safe_push (tree
, heap
, name_tag_reps
, ptr
);
538 VEC_safe_push (bitmap
, heap
, pt_vars_for_reps
, pi
->pt_vars
);
540 /* Verify that alias set of PTR's symbol tag is a superset of the
541 alias set of PTR's name tag. */
542 smt
= var_ann (SSA_NAME_VAR (ptr
))->symbol_mem_tag
;
546 VEC(tree
,gc
) *aliases
= var_ann (smt
)->may_aliases
;
549 bitmap_clear (type_aliases
);
550 for (i
= 0; VEC_iterate (tree
, aliases
, i
, alias
); i
++)
551 bitmap_set_bit (type_aliases
, DECL_UID (alias
));
553 /* When grouping, we may have added PTR's symbol tag into the
554 alias set of PTR's name tag. To prevent a false
555 positive, pretend that SMT is in its own alias set. */
556 bitmap_set_bit (type_aliases
, DECL_UID (smt
));
558 if (bitmap_equal_p (type_aliases
, pi
->pt_vars
))
561 if (!bitmap_intersect_compl_p (type_aliases
, pi
->pt_vars
))
563 error ("alias set of a pointer's symbol tag should be a superset of the corresponding name tag");
564 debug_variable (smt
);
565 debug_variable (pi
->name_mem_tag
);
571 /* Now compare all the representative bitmaps with all other representative
572 bitmaps, to verify that they are all different. */
573 for (i
= 0; VEC_iterate (bitmap
, pt_vars_for_reps
, i
, first
); i
++)
575 for (j
= i
+ 1; VEC_iterate (bitmap
, pt_vars_for_reps
, j
, second
); j
++)
577 if (bitmap_equal_p (first
, second
))
579 error ("two different pointers with identical points-to sets but different name tags");
580 debug_variable (VEC_index (tree
, name_tag_reps
, j
));
586 /* Lastly, clear out the visited flags. */
587 for (i
= 0; i
< num_ssa_names
; i
++)
591 tree ptr
= ssa_name (i
);
592 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
593 if (!TREE_VISITED (ptr
)
594 || !POINTER_TYPE_P (TREE_TYPE (ptr
))
596 || !pi
->name_mem_tag
)
598 TREE_VISITED (pi
->name_mem_tag
) = 0;
602 /* We do not have to free the bitmaps or trees in the vectors, as
603 they are not owned by us. */
604 VEC_free (bitmap
, heap
, pt_vars_for_reps
);
605 VEC_free (tree
, heap
, name_tag_reps
);
606 BITMAP_FREE (type_aliases
);
610 debug_variable (VEC_index (tree
, name_tag_reps
, i
));
611 internal_error ("verify_name_tags failed");
615 /* Verify the consistency of call clobbering information. */
617 verify_call_clobbering (void)
622 referenced_var_iterator rvi
;
624 /* At all times, the result of the DECL_CALL_CLOBBERED flag should
625 match the result of the call_clobbered_vars bitmap. Verify both
626 that everything in call_clobbered_vars is marked
627 DECL_CALL_CLOBBERED, and that everything marked
628 DECL_CALL_CLOBBERED is in call_clobbered_vars. */
629 EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars
, 0, i
, bi
)
631 var
= referenced_var (i
);
632 if (!MTAG_P (var
) && !DECL_CALL_CLOBBERED (var
))
634 error ("variable in call_clobbered_vars but not marked DECL_CALL_CLOBBERED");
635 debug_variable (var
);
639 FOR_EACH_REFERENCED_VAR (var
, rvi
)
641 if (!MTAG_P (var
) && DECL_CALL_CLOBBERED (var
)
642 && !bitmap_bit_p (call_clobbered_vars
, DECL_UID (var
)))
644 error ("variable marked DECL_CALL_CLOBBERED but not in call_clobbered_vars bitmap.");
645 debug_variable (var
);
652 internal_error ("verify_call_clobbering failed");
655 /* Verify the consistency of aliasing information. */
658 verify_alias_info (void)
660 verify_flow_sensitive_alias_info ();
662 verify_call_clobbering ();
663 verify_flow_insensitive_alias_info ();
667 /* Verify common invariants in the SSA web.
668 TODO: verify the variable annotations. */
671 verify_ssa (bool check_modified_stmt
)
675 basic_block
*definition_block
= XCNEWVEC (basic_block
, num_ssa_names
);
678 enum dom_state orig_dom_state
= dom_computed
[CDI_DOMINATORS
];
679 bitmap names_defined_in_bb
= BITMAP_ALLOC (NULL
);
681 gcc_assert (!need_ssa_update_p ());
685 timevar_push (TV_TREE_SSA_VERIFY
);
687 /* Keep track of SSA names present in the IL. */
688 for (i
= 1; i
< num_ssa_names
; i
++)
690 tree name
= ssa_name (i
);
694 TREE_VISITED (name
) = 0;
696 stmt
= SSA_NAME_DEF_STMT (name
);
697 if (!IS_EMPTY_STMT (stmt
))
699 basic_block bb
= bb_for_stmt (stmt
);
700 verify_def (bb
, definition_block
,
701 name
, stmt
, !is_gimple_reg (name
));
707 calculate_dominance_info (CDI_DOMINATORS
);
709 /* Now verify all the uses and make sure they agree with the definitions
710 found in the previous pass. */
716 block_stmt_iterator bsi
;
718 /* Make sure that all edges have a clear 'aux' field. */
719 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
723 error ("AUX pointer initialized for edge %d->%d", e
->src
->index
,
729 /* Verify the arguments for every PHI node in the block. */
730 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
732 if (verify_phi_args (phi
, bb
, definition_block
))
734 bitmap_set_bit (names_defined_in_bb
,
735 SSA_NAME_VERSION (PHI_RESULT (phi
)));
738 /* Now verify all the uses and vuses in every statement of the block. */
739 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
741 tree stmt
= bsi_stmt (bsi
);
744 if (check_modified_stmt
&& stmt_modified_p (stmt
))
746 error ("stmt (%p) marked modified after optimization pass : ",
748 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
752 if (TREE_CODE (stmt
) == MODIFY_EXPR
753 && TREE_CODE (TREE_OPERAND (stmt
, 0)) != SSA_NAME
)
755 tree lhs
, base_address
;
757 lhs
= TREE_OPERAND (stmt
, 0);
758 base_address
= get_base_address (lhs
);
761 && SSA_VAR_P (base_address
)
762 && ZERO_SSA_OPERANDS (stmt
, SSA_OP_VMAYDEF
|SSA_OP_VMUSTDEF
))
764 error ("statement makes a memory store, but has no "
765 "V_MAY_DEFS nor V_MUST_DEFS");
766 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
771 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
,
772 SSA_OP_ALL_USES
| SSA_OP_ALL_KILLS
)
774 op
= USE_FROM_PTR (use_p
);
775 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
776 use_p
, stmt
, false, !is_gimple_reg (op
),
777 names_defined_in_bb
))
781 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_ALL_DEFS
)
782 bitmap_set_bit (names_defined_in_bb
, SSA_NAME_VERSION (op
));
785 bitmap_clear (names_defined_in_bb
);
788 /* Finally, verify alias information. */
789 verify_alias_info ();
791 free (definition_block
);
793 /* Restore the dominance information to its prior known state, so
794 that we do not perturb the compiler's subsequent behavior. */
795 if (orig_dom_state
== DOM_NONE
)
796 free_dominance_info (CDI_DOMINATORS
);
798 dom_computed
[CDI_DOMINATORS
] = orig_dom_state
;
800 BITMAP_FREE (names_defined_in_bb
);
801 timevar_pop (TV_TREE_SSA_VERIFY
);
805 internal_error ("verify_ssa failed");
808 /* Return true if the uid in both int tree maps are equal. */
811 int_tree_map_eq (const void *va
, const void *vb
)
813 const struct int_tree_map
*a
= (const struct int_tree_map
*) va
;
814 const struct int_tree_map
*b
= (const struct int_tree_map
*) vb
;
815 return (a
->uid
== b
->uid
);
818 /* Hash a UID in a int_tree_map. */
821 int_tree_map_hash (const void *item
)
823 return ((const struct int_tree_map
*)item
)->uid
;
827 /* Initialize global DFA and SSA structures. */
832 referenced_vars
= htab_create_ggc (20, int_tree_map_hash
,
833 int_tree_map_eq
, NULL
);
834 default_defs
= htab_create_ggc (20, int_tree_map_hash
, int_tree_map_eq
, NULL
);
835 call_clobbered_vars
= BITMAP_ALLOC (NULL
);
836 addressable_vars
= BITMAP_ALLOC (NULL
);
837 init_alias_heapvars ();
840 global_var
= NULL_TREE
;
841 aliases_computed_p
= false;
845 /* Deallocate memory associated with SSA data structures for FNDECL. */
848 delete_tree_ssa (void)
852 block_stmt_iterator bsi
;
853 referenced_var_iterator rvi
;
856 /* Release any ssa_names still in use. */
857 for (i
= 0; i
< num_ssa_names
; i
++)
859 tree var
= ssa_name (i
);
860 if (var
&& TREE_CODE (var
) == SSA_NAME
)
862 SSA_NAME_IMM_USE_NODE (var
).prev
= &(SSA_NAME_IMM_USE_NODE (var
));
863 SSA_NAME_IMM_USE_NODE (var
).next
= &(SSA_NAME_IMM_USE_NODE (var
));
865 release_ssa_name (var
);
868 /* Remove annotations from every tree in the function. */
871 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
873 tree stmt
= bsi_stmt (bsi
);
874 stmt_ann_t ann
= get_stmt_ann (stmt
);
876 free_ssa_operands (&ann
->operands
);
877 ann
->addresses_taken
= 0;
878 mark_stmt_modified (stmt
);
880 set_phi_nodes (bb
, NULL
);
883 /* Remove annotations from every referenced variable. */
884 FOR_EACH_REFERENCED_VAR (var
, rvi
)
886 ggc_free (var
->common
.ann
);
887 var
->common
.ann
= NULL
;
889 htab_delete (referenced_vars
);
890 referenced_vars
= NULL
;
895 global_var
= NULL_TREE
;
897 htab_delete (default_defs
);
898 BITMAP_FREE (call_clobbered_vars
);
899 call_clobbered_vars
= NULL
;
900 BITMAP_FREE (addressable_vars
);
901 addressable_vars
= NULL
;
902 modified_noreturn_calls
= NULL
;
903 aliases_computed_p
= false;
904 delete_alias_heapvars ();
905 gcc_assert (!need_ssa_update_p ());
909 /* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a
910 useless type conversion, otherwise return false. */
913 tree_ssa_useless_type_conversion_1 (tree outer_type
, tree inner_type
)
915 if (inner_type
== outer_type
)
918 /* Changes in machine mode are never useless conversions. */
919 if (TYPE_MODE (inner_type
) != TYPE_MODE (outer_type
))
922 /* If the inner and outer types are effectively the same, then
923 strip the type conversion and enter the equivalence into
925 if (lang_hooks
.types_compatible_p (inner_type
, outer_type
))
928 /* If both types are pointers and the outer type is a (void *), then
929 the conversion is not necessary. The opposite is not true since
930 that conversion would result in a loss of information if the
931 equivalence was used. Consider an indirect function call where
932 we need to know the exact type of the function to correctly
933 implement the ABI. */
934 else if (POINTER_TYPE_P (inner_type
)
935 && POINTER_TYPE_P (outer_type
)
936 && TYPE_REF_CAN_ALIAS_ALL (inner_type
)
937 == TYPE_REF_CAN_ALIAS_ALL (outer_type
)
938 && TREE_CODE (TREE_TYPE (outer_type
)) == VOID_TYPE
)
941 /* Don't lose casts between pointers to volatile and non-volatile
942 qualified types. Doing so would result in changing the semantics
943 of later accesses. */
944 else if (POINTER_TYPE_P (inner_type
)
945 && POINTER_TYPE_P (outer_type
)
946 && TYPE_VOLATILE (TREE_TYPE (outer_type
))
947 != TYPE_VOLATILE (TREE_TYPE (inner_type
)))
950 /* Pointers/references are equivalent if their pointed to types
951 are effectively the same. This allows to strip conversions between
952 pointer types with different type qualifiers. */
953 else if (POINTER_TYPE_P (inner_type
)
954 && POINTER_TYPE_P (outer_type
)
955 && TYPE_REF_CAN_ALIAS_ALL (inner_type
)
956 == TYPE_REF_CAN_ALIAS_ALL (outer_type
)
957 && lang_hooks
.types_compatible_p (TREE_TYPE (inner_type
),
958 TREE_TYPE (outer_type
)))
961 /* If both the inner and outer types are integral types, then the
962 conversion is not necessary if they have the same mode and
963 signedness and precision, and both or neither are boolean. Some
964 code assumes an invariant that boolean types stay boolean and do
965 not become 1-bit bit-field types. Note that types with precision
966 not using all bits of the mode (such as bit-field types in C)
967 mean that testing of precision is necessary. */
968 else if (INTEGRAL_TYPE_P (inner_type
)
969 && INTEGRAL_TYPE_P (outer_type
)
970 && TYPE_UNSIGNED (inner_type
) == TYPE_UNSIGNED (outer_type
)
971 && TYPE_PRECISION (inner_type
) == TYPE_PRECISION (outer_type
)
972 && simple_cst_equal (TYPE_MAX_VALUE (inner_type
), TYPE_MAX_VALUE (outer_type
))
973 && simple_cst_equal (TYPE_MIN_VALUE (inner_type
), TYPE_MIN_VALUE (outer_type
)))
975 bool first_boolean
= (TREE_CODE (inner_type
) == BOOLEAN_TYPE
);
976 bool second_boolean
= (TREE_CODE (outer_type
) == BOOLEAN_TYPE
);
977 if (first_boolean
== second_boolean
)
981 /* Recurse for complex types. */
982 else if (TREE_CODE (inner_type
) == COMPLEX_TYPE
983 && TREE_CODE (outer_type
) == COMPLEX_TYPE
984 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type
),
985 TREE_TYPE (inner_type
)))
991 /* Return true if EXPR is a useless type conversion, otherwise return
995 tree_ssa_useless_type_conversion (tree expr
)
997 /* If we have an assignment that merely uses a NOP_EXPR to change
998 the top of the RHS to the type of the LHS and the type conversion
999 is "safe", then strip away the type conversion so that we can
1000 enter LHS = RHS into the const_and_copies table. */
1001 if (TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
1002 || TREE_CODE (expr
) == VIEW_CONVERT_EXPR
1003 || TREE_CODE (expr
) == NON_LVALUE_EXPR
)
1004 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr
),
1005 TREE_TYPE (TREE_OPERAND (expr
,
1012 /* Returns true if statement STMT may read memory. */
1015 stmt_references_memory_p (tree stmt
)
1017 stmt_ann_t ann
= stmt_ann (stmt
);
1019 if (ann
->has_volatile_ops
)
1022 return (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
));
1025 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
1026 described in walk_use_def_chains.
1028 VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
1029 infinite loops. We used to have a bitmap for this to just mark
1030 SSA versions we had visited. But non-sparse bitmaps are way too
1031 expensive, while sparse bitmaps may cause quadratic behavior.
1033 IS_DFS is true if the caller wants to perform a depth-first search
1034 when visiting PHI nodes. A DFS will visit each PHI argument and
1035 call FN after each one. Otherwise, all the arguments are
1036 visited first and then FN is called with each of the visited
1037 arguments in a separate pass. */
1040 walk_use_def_chains_1 (tree var
, walk_use_def_chains_fn fn
, void *data
,
1041 struct pointer_set_t
*visited
, bool is_dfs
)
1045 if (pointer_set_insert (visited
, var
))
1048 def_stmt
= SSA_NAME_DEF_STMT (var
);
1050 if (TREE_CODE (def_stmt
) != PHI_NODE
)
1052 /* If we reached the end of the use-def chain, call FN. */
1053 return fn (var
, def_stmt
, data
);
1059 /* When doing a breadth-first search, call FN before following the
1060 use-def links for each argument. */
1062 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
1063 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
1066 /* Follow use-def links out of each PHI argument. */
1067 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
1069 tree arg
= PHI_ARG_DEF (def_stmt
, i
);
1070 if (TREE_CODE (arg
) == SSA_NAME
1071 && walk_use_def_chains_1 (arg
, fn
, data
, visited
, is_dfs
))
1075 /* When doing a depth-first search, call FN after following the
1076 use-def links for each argument. */
1078 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
1079 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
1088 /* Walk use-def chains starting at the SSA variable VAR. Call
1089 function FN at each reaching definition found. FN takes three
1090 arguments: VAR, its defining statement (DEF_STMT) and a generic
1091 pointer to whatever state information that FN may want to maintain
1092 (DATA). FN is able to stop the walk by returning true, otherwise
1093 in order to continue the walk, FN should return false.
1095 Note, that if DEF_STMT is a PHI node, the semantics are slightly
1096 different. The first argument to FN is no longer the original
1097 variable VAR, but the PHI argument currently being examined. If FN
1098 wants to get at VAR, it should call PHI_RESULT (PHI).
1100 If IS_DFS is true, this function will:
1102 1- walk the use-def chains for all the PHI arguments, and,
1103 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
1105 If IS_DFS is false, the two steps above are done in reverse order
1106 (i.e., a breadth-first search). */
1110 walk_use_def_chains (tree var
, walk_use_def_chains_fn fn
, void *data
,
1115 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
1117 def_stmt
= SSA_NAME_DEF_STMT (var
);
1119 /* We only need to recurse if the reaching definition comes from a PHI
1121 if (TREE_CODE (def_stmt
) != PHI_NODE
)
1122 (*fn
) (var
, def_stmt
, data
);
1125 struct pointer_set_t
*visited
= pointer_set_create ();
1126 walk_use_def_chains_1 (var
, fn
, data
, visited
, is_dfs
);
1127 pointer_set_destroy (visited
);
1132 /* Emit warnings for uninitialized variables. This is done in two passes.
1134 The first pass notices real uses of SSA names with default definitions.
1135 Such uses are unconditionally uninitialized, and we can be certain that
1136 such a use is a mistake. This pass is run before most optimizations,
1137 so that we catch as many as we can.
1139 The second pass follows PHI nodes to find uses that are potentially
1140 uninitialized. In this case we can't necessarily prove that the use
1141 is really uninitialized. This pass is run after most optimizations,
1142 so that we thread as many jumps and possible, and delete as much dead
1143 code as possible, in order to reduce false positives. We also look
1144 again for plain uninitialized variables, since optimization may have
1145 changed conditionally uninitialized to unconditionally uninitialized. */
1147 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1148 warning text is in MSGID and LOCUS may contain a location or be null. */
1151 warn_uninit (tree t
, const char *gmsgid
, void *data
)
1153 tree var
= SSA_NAME_VAR (t
);
1154 tree def
= SSA_NAME_DEF_STMT (t
);
1155 tree context
= (tree
) data
;
1156 location_t
*locus
, *fun_locus
;
1158 /* Default uses (indicated by an empty definition statement),
1159 are uninitialized. */
1160 if (!IS_EMPTY_STMT (def
))
1163 /* Except for PARMs of course, which are always initialized. */
1164 if (TREE_CODE (var
) == PARM_DECL
)
1167 /* Hard register variables get their initial value from the ether. */
1168 if (TREE_CODE (var
) == VAR_DECL
&& DECL_HARD_REGISTER (var
))
1171 /* TREE_NO_WARNING either means we already warned, or the front end
1172 wishes to suppress the warning. */
1173 if (TREE_NO_WARNING (var
))
1176 locus
= (context
!= NULL
&& EXPR_HAS_LOCATION (context
)
1177 ? EXPR_LOCUS (context
)
1178 : &DECL_SOURCE_LOCATION (var
));
1179 warning (0, gmsgid
, locus
, var
);
1180 fun_locus
= &DECL_SOURCE_LOCATION (cfun
->decl
);
1181 if (locus
->file
!= fun_locus
->file
1182 || locus
->line
< fun_locus
->line
1183 || locus
->line
> cfun
->function_end_locus
.line
)
1184 inform ("%J%qD was declared here", var
, var
);
1186 TREE_NO_WARNING (var
) = 1;
1189 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1190 and warn about them. */
1193 warn_uninitialized_var (tree
*tp
, int *walk_subtrees
, void *data
)
1197 switch (TREE_CODE (t
))
1200 /* We only do data flow with SSA_NAMEs, so that's all we
1202 warn_uninit (t
, "%H%qD is used uninitialized in this function", data
);
1208 /* The total store transformation performed during gimplification
1209 creates uninitialized variable uses. If all is well, these will
1210 be optimized away, so don't warn now. */
1211 if (TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
)
1216 if (IS_TYPE_OR_DECL_P (t
))
1224 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1225 and warn about them. */
1228 warn_uninitialized_phi (tree phi
)
1230 int i
, n
= PHI_NUM_ARGS (phi
);
1232 /* Don't look at memory tags. */
1233 if (!is_gimple_reg (PHI_RESULT (phi
)))
1236 for (i
= 0; i
< n
; ++i
)
1238 tree op
= PHI_ARG_DEF (phi
, i
);
1239 if (TREE_CODE (op
) == SSA_NAME
)
1240 warn_uninit (op
, "%H%qD may be used uninitialized in this function",
1246 execute_early_warn_uninitialized (void)
1248 block_stmt_iterator bsi
;
1252 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1254 tree context
= bsi_stmt (bsi
);
1255 walk_tree (bsi_stmt_ptr (bsi
), warn_uninitialized_var
,
1262 execute_late_warn_uninitialized (void)
1267 /* Re-do the plain uninitialized variable check, as optimization may have
1268 straightened control flow. Do this first so that we don't accidentally
1269 get a "may be" warning when we'd have seen an "is" warning later. */
1270 execute_early_warn_uninitialized ();
1273 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1274 warn_uninitialized_phi (phi
);
1279 gate_warn_uninitialized (void)
1281 return warn_uninitialized
!= 0;
1284 struct tree_opt_pass pass_early_warn_uninitialized
=
1287 gate_warn_uninitialized
, /* gate */
1288 execute_early_warn_uninitialized
, /* execute */
1291 0, /* static_pass_number */
1293 PROP_ssa
, /* properties_required */
1294 0, /* properties_provided */
1295 0, /* properties_destroyed */
1296 0, /* todo_flags_start */
1297 0, /* todo_flags_finish */
1301 struct tree_opt_pass pass_late_warn_uninitialized
=
1304 gate_warn_uninitialized
, /* gate */
1305 execute_late_warn_uninitialized
, /* execute */
1308 0, /* static_pass_number */
1310 PROP_ssa
, /* properties_required */
1311 0, /* properties_provided */
1312 0, /* properties_destroyed */
1313 0, /* todo_flags_start */
1314 0, /* todo_flags_finish */