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");
139 if (is_virtual
&& var_ann (SSA_NAME_VAR (ssa_name
))
140 && get_subvars_for_var (SSA_NAME_VAR (ssa_name
)) != NULL
)
142 error ("Found real variable when subvariables should have appeared");
150 /* Return true if the definition of SSA_NAME at block BB is malformed.
152 STMT is the statement where SSA_NAME is created.
154 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
155 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
156 it means that the block in that array slot contains the
157 definition of SSA_NAME.
159 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
163 verify_def (basic_block bb
, basic_block
*definition_block
, tree ssa_name
,
164 tree stmt
, bool is_virtual
)
166 if (verify_ssa_name (ssa_name
, is_virtual
))
169 if (definition_block
[SSA_NAME_VERSION (ssa_name
)])
171 error ("SSA_NAME created in two different blocks %i and %i",
172 definition_block
[SSA_NAME_VERSION (ssa_name
)]->index
, bb
->index
);
176 definition_block
[SSA_NAME_VERSION (ssa_name
)] = bb
;
178 if (SSA_NAME_DEF_STMT (ssa_name
) != stmt
)
180 error ("SSA_NAME_DEF_STMT is wrong");
181 fprintf (stderr
, "Expected definition statement:\n");
182 print_generic_stmt (stderr
, SSA_NAME_DEF_STMT (ssa_name
), TDF_VOPS
);
183 fprintf (stderr
, "\nActual definition statement:\n");
184 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
191 fprintf (stderr
, "while verifying SSA_NAME ");
192 print_generic_expr (stderr
, ssa_name
, 0);
193 fprintf (stderr
, " in statement\n");
194 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
200 /* Return true if the use of SSA_NAME at statement STMT in block BB is
203 DEF_BB is the block where SSA_NAME was found to be created.
205 IDOM contains immediate dominator information for the flowgraph.
207 CHECK_ABNORMAL is true if the caller wants to check whether this use
208 is flowing through an abnormal edge (only used when checking PHI
211 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
214 If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
215 that are defined before STMT in basic block BB. */
218 verify_use (basic_block bb
, basic_block def_bb
, use_operand_p use_p
,
219 tree stmt
, bool check_abnormal
, bool is_virtual
,
220 bitmap names_defined_in_bb
)
223 tree ssa_name
= USE_FROM_PTR (use_p
);
225 err
= verify_ssa_name (ssa_name
, is_virtual
);
227 if (!TREE_VISITED (ssa_name
))
228 if (verify_imm_links (stderr
, ssa_name
))
231 TREE_VISITED (ssa_name
) = 1;
233 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name
))
234 && var_ann (SSA_NAME_VAR (ssa_name
))->default_def
== ssa_name
)
235 ; /* Default definitions have empty statements. Nothing to do. */
238 error ("Missing definition");
241 else if (bb
!= def_bb
242 && !dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
244 error ("Definition in block %i does not dominate use in block %i",
245 def_bb
->index
, bb
->index
);
248 else if (bb
== def_bb
249 && names_defined_in_bb
!= NULL
250 && !bitmap_bit_p (names_defined_in_bb
, SSA_NAME_VERSION (ssa_name
)))
252 error ("Definition in block %i follows the use", def_bb
->index
);
257 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name
))
259 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
263 /* Make sure the use is in an appropriate list by checking the previous
264 element to make sure its the same. */
265 if (use_p
->prev
== NULL
)
267 error ("No immediate_use list");
273 if (use_p
->prev
->use
== NULL
)
274 listvar
= use_p
->prev
->stmt
;
276 listvar
= USE_FROM_PTR (use_p
->prev
);
277 if (listvar
!= ssa_name
)
279 error ("Wrong immediate use list");
286 fprintf (stderr
, "for SSA_NAME: ");
287 print_generic_expr (stderr
, ssa_name
, TDF_VOPS
);
288 fprintf (stderr
, "in statement:\n");
289 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
296 /* Return true if any of the arguments for PHI node PHI at block BB is
299 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
300 numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
301 block in that array slot contains the definition of SSA_NAME. */
304 verify_phi_args (tree phi
, basic_block bb
, basic_block
*definition_block
)
308 unsigned i
, phi_num_args
= PHI_NUM_ARGS (phi
);
310 if (EDGE_COUNT (bb
->preds
) != phi_num_args
)
312 error ("Incoming edge count does not match number of PHI arguments\n");
317 for (i
= 0; i
< phi_num_args
; i
++)
319 use_operand_p op_p
= PHI_ARG_DEF_PTR (phi
, i
);
320 tree op
= USE_FROM_PTR (op_p
);
323 e
= EDGE_PRED (bb
, i
);
327 error ("PHI argument is missing for edge %d->%d\n",
334 if (TREE_CODE (op
) != SSA_NAME
&& !is_gimple_min_invariant (op
))
336 error ("PHI argument is not SSA_NAME, or invariant");
340 if (TREE_CODE (op
) == SSA_NAME
)
341 err
= verify_use (e
->src
, definition_block
[SSA_NAME_VERSION (op
)], op_p
,
342 phi
, e
->flags
& EDGE_ABNORMAL
,
343 !is_gimple_reg (PHI_RESULT (phi
)),
348 error ("Wrong edge %d->%d for PHI argument\n",
349 e
->src
->index
, e
->dest
->index
, bb
->index
);
355 fprintf (stderr
, "PHI argument\n");
356 print_generic_stmt (stderr
, op
, TDF_VOPS
);
364 fprintf (stderr
, "for PHI node\n");
365 print_generic_stmt (stderr
, phi
, TDF_VOPS
);
374 verify_flow_insensitive_alias_info (void)
378 bitmap visited
= BITMAP_ALLOC (NULL
);
380 for (i
= 0; i
< num_referenced_vars
; i
++)
384 varray_type may_aliases
;
386 var
= referenced_var (i
);
388 may_aliases
= ann
->may_aliases
;
390 for (j
= 0; may_aliases
&& j
< VARRAY_ACTIVE_SIZE (may_aliases
); j
++)
392 tree alias
= VARRAY_TREE (may_aliases
, j
);
394 bitmap_set_bit (visited
, var_ann (alias
)->uid
);
396 if (!may_be_aliased (alias
))
398 error ("Non-addressable variable inside an alias set.");
399 debug_variable (alias
);
405 for (i
= 0; i
< num_referenced_vars
; i
++)
409 var
= referenced_var (i
);
412 if (ann
->mem_tag_kind
== NOT_A_TAG
414 && !bitmap_bit_p (visited
, ann
->uid
))
416 error ("Addressable variable that is an alias tag but is not in any alias set.");
421 BITMAP_FREE (visited
);
425 debug_variable (var
);
426 internal_error ("verify_flow_insensitive_alias_info failed.");
431 verify_flow_sensitive_alias_info (void)
436 for (i
= 1; i
< num_ssa_names
; i
++)
440 struct ptr_info_def
*pi
;
447 /* We only care for pointers that are actually referenced in the
449 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)) || !TREE_VISITED (ptr
))
452 /* RESULT_DECL is special. If it's a GIMPLE register, then it
453 is only written-to only once in the return statement.
454 Otherwise, aggregate RESULT_DECLs may be written-to more than
455 once in virtual operands. */
456 var
= SSA_NAME_VAR (ptr
);
457 if (TREE_CODE (var
) == RESULT_DECL
458 && is_gimple_reg (ptr
))
461 pi
= SSA_NAME_PTR_INFO (ptr
);
466 if (pi
->is_dereferenced
&& !pi
->name_mem_tag
&& !ann
->type_mem_tag
)
468 error ("Dereferenced pointers should have a name or a type tag");
474 && (pi
->pt_vars
== NULL
|| bitmap_empty_p (pi
->pt_vars
)))
476 error ("Pointers with a memory tag, should have points-to sets or point to malloc");
480 if (pi
->value_escapes_p
482 && !is_call_clobbered (pi
->name_mem_tag
))
484 error ("Pointer escapes but its name tag is not call-clobbered.");
492 debug_variable (ptr
);
493 internal_error ("verify_flow_sensitive_alias_info failed.");
496 DEF_VEC_MALLOC_P (bitmap
);
498 /* Verify that all name tags have different points to sets.
499 This algorithm takes advantage of the fact that every variable with the
500 same name tag must have the same points-to set.
501 So we check a single variable for each name tag, and verify that its
502 points-to set is different from every other points-to set for other name
505 Additionally, given a pointer P_i with name tag NMT and type tag
506 TMT, this function verified the alias set of TMT is a superset of
507 the alias set of NMT. */
510 verify_name_tags (void)
514 bitmap first
, second
;
515 VEC (tree
) *name_tag_reps
= NULL
;
516 VEC (bitmap
) *pt_vars_for_reps
= NULL
;
517 bitmap type_aliases
= BITMAP_ALLOC (NULL
);
519 /* First we compute the name tag representatives and their points-to sets. */
520 for (i
= 0; i
< num_ssa_names
; i
++)
522 struct ptr_info_def
*pi
;
523 tree tmt
, ptr
= ssa_name (i
);
525 if (ptr
== NULL_TREE
)
528 pi
= SSA_NAME_PTR_INFO (ptr
);
530 if (!TREE_VISITED (ptr
)
531 || !POINTER_TYPE_P (TREE_TYPE (ptr
))
534 || TREE_VISITED (pi
->name_mem_tag
))
537 TREE_VISITED (pi
->name_mem_tag
) = 1;
539 if (pi
->pt_vars
== NULL
)
542 VEC_safe_push (tree
, name_tag_reps
, ptr
);
543 VEC_safe_push (bitmap
, pt_vars_for_reps
, pi
->pt_vars
);
545 /* Verify that alias set of PTR's type tag is a superset of the
546 alias set of PTR's name tag. */
547 tmt
= var_ann (SSA_NAME_VAR (ptr
))->type_mem_tag
;
551 varray_type aliases
= var_ann (tmt
)->may_aliases
;
552 bitmap_clear (type_aliases
);
553 for (i
= 0; aliases
&& i
< VARRAY_ACTIVE_SIZE (aliases
); i
++)
555 tree alias
= VARRAY_TREE (aliases
, i
);
556 bitmap_set_bit (type_aliases
, var_ann (alias
)->uid
);
559 /* When grouping, we may have added PTR's type tag into the
560 alias set of PTR's name tag. To prevent a false
561 positive, pretend that TMT is in its own alias set. */
562 bitmap_set_bit (type_aliases
, var_ann (tmt
)->uid
);
564 if (bitmap_equal_p (type_aliases
, pi
->pt_vars
))
567 if (!bitmap_intersect_compl_p (type_aliases
, pi
->pt_vars
))
569 error ("Alias set of a pointer's type tag should be a superset of the corresponding name tag");
570 debug_variable (tmt
);
571 debug_variable (pi
->name_mem_tag
);
577 /* Now compare all the representative bitmaps with all other representative
578 bitmaps, to verify that they are all different. */
579 for (i
= 0; VEC_iterate (bitmap
, pt_vars_for_reps
, i
, first
); i
++)
581 for (j
= i
+ 1; VEC_iterate (bitmap
, pt_vars_for_reps
, j
, second
); j
++)
583 if (bitmap_equal_p (first
, second
))
585 error ("Two different pointers with identical points-to sets but different name tags");
586 debug_variable (VEC_index (tree
, name_tag_reps
, j
));
592 /* Lastly, clear out the visited flags. */
593 for (i
= 0; i
< num_ssa_names
; i
++)
597 tree ptr
= ssa_name (i
);
598 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
599 if (!TREE_VISITED (ptr
)
600 || !POINTER_TYPE_P (TREE_TYPE (ptr
))
602 || !pi
->name_mem_tag
)
604 TREE_VISITED (pi
->name_mem_tag
) = 0;
608 VEC_free (bitmap
, pt_vars_for_reps
);
609 BITMAP_FREE (type_aliases
);
613 debug_variable (VEC_index (tree
, name_tag_reps
, i
));
614 internal_error ("verify_name_tags failed");
618 /* Verify the consistency of aliasing information. */
621 verify_alias_info (void)
623 verify_flow_sensitive_alias_info ();
625 verify_flow_insensitive_alias_info ();
629 /* Verify common invariants in the SSA web.
630 TODO: verify the variable annotations. */
633 verify_ssa (bool check_modified_stmt
)
637 basic_block
*definition_block
= xcalloc (num_ssa_names
, sizeof (basic_block
));
640 enum dom_state orig_dom_state
= dom_computed
[CDI_DOMINATORS
];
641 bitmap names_defined_in_bb
= BITMAP_ALLOC (NULL
);
643 timevar_push (TV_TREE_SSA_VERIFY
);
645 /* Keep track of SSA names present in the IL. */
646 for (i
= 1; i
< num_ssa_names
; i
++)
648 tree name
= ssa_name (i
);
652 TREE_VISITED (name
) = 0;
654 stmt
= SSA_NAME_DEF_STMT (name
);
655 if (!IS_EMPTY_STMT (stmt
))
657 basic_block bb
= bb_for_stmt (stmt
);
658 verify_def (bb
, definition_block
,
659 name
, stmt
, !is_gimple_reg (name
));
665 calculate_dominance_info (CDI_DOMINATORS
);
667 /* Now verify all the uses and make sure they agree with the definitions
668 found in the previous pass. */
674 block_stmt_iterator bsi
;
676 /* Make sure that all edges have a clear 'aux' field. */
677 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
681 error ("AUX pointer initialized for edge %d->%d\n", e
->src
->index
,
687 /* Verify the arguments for every PHI node in the block. */
688 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
690 if (verify_phi_args (phi
, bb
, definition_block
))
692 bitmap_set_bit (names_defined_in_bb
,
693 SSA_NAME_VERSION (PHI_RESULT (phi
)));
696 /* Now verify all the uses and vuses in every statement of the block. */
697 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
699 tree stmt
= bsi_stmt (bsi
);
702 if (check_modified_stmt
&& stmt_modified_p (stmt
))
704 error ("Stmt (0x%x) marked modified after optimization pass : ",
705 (unsigned long)stmt
);
706 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
711 if (stmt_ann (stmt
)->makes_aliased_stores
712 && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt
)) == 0)
714 error ("Statement makes aliased stores, but has no V_MAY_DEFS");
715 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
719 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
| SSA_OP_ALL_KILLS
)
721 op
= USE_FROM_PTR (use_p
);
722 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
723 use_p
, stmt
, false, !is_gimple_reg (op
),
724 names_defined_in_bb
))
728 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_ALL_DEFS
)
730 bitmap_set_bit (names_defined_in_bb
, SSA_NAME_VERSION (op
));
734 bitmap_clear (names_defined_in_bb
);
737 /* Finally, verify alias information. */
738 verify_alias_info ();
740 free (definition_block
);
741 /* Restore the dominance information to its prior known state, so
742 that we do not perturb the compiler's subsequent behavior. */
743 if (orig_dom_state
== DOM_NONE
)
744 free_dominance_info (CDI_DOMINATORS
);
746 dom_computed
[CDI_DOMINATORS
] = orig_dom_state
;
748 BITMAP_FREE (names_defined_in_bb
);
749 timevar_pop (TV_TREE_SSA_VERIFY
);
753 internal_error ("verify_ssa failed.");
757 /* Initialize global DFA and SSA structures. */
762 VARRAY_TREE_INIT (referenced_vars
, 20, "referenced_vars");
763 call_clobbered_vars
= BITMAP_ALLOC (NULL
);
764 addressable_vars
= BITMAP_ALLOC (NULL
);
767 global_var
= NULL_TREE
;
768 aliases_computed_p
= false;
772 /* Deallocate memory associated with SSA data structures for FNDECL. */
775 delete_tree_ssa (void)
779 block_stmt_iterator bsi
;
781 /* Remove annotations from every tree in the function. */
783 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
785 tree stmt
= bsi_stmt (bsi
);
787 ggc_free (stmt
->common
.ann
);
788 stmt
->common
.ann
= NULL
;
791 /* Remove annotations from every referenced variable. */
794 for (i
= 0; i
< num_referenced_vars
; i
++)
796 tree var
= referenced_var (i
);
797 ggc_free (var
->common
.ann
);
798 var
->common
.ann
= NULL
;
800 referenced_vars
= NULL
;
806 global_var
= NULL_TREE
;
807 BITMAP_FREE (call_clobbered_vars
);
808 call_clobbered_vars
= NULL
;
809 BITMAP_FREE (addressable_vars
);
810 addressable_vars
= NULL
;
811 modified_noreturn_calls
= NULL
;
812 aliases_computed_p
= false;
816 /* Return true if EXPR is a useless type conversion, otherwise return
820 tree_ssa_useless_type_conversion_1 (tree outer_type
, tree inner_type
)
822 if (inner_type
== outer_type
)
825 /* Changes in machine mode are never useless conversions. */
826 if (TYPE_MODE (inner_type
) != TYPE_MODE (outer_type
))
829 /* If the inner and outer types are effectively the same, then
830 strip the type conversion and enter the equivalence into
832 if (lang_hooks
.types_compatible_p (inner_type
, outer_type
))
835 /* If both types are pointers and the outer type is a (void *), then
836 the conversion is not necessary. The opposite is not true since
837 that conversion would result in a loss of information if the
838 equivalence was used. Consider an indirect function call where
839 we need to know the exact type of the function to correctly
840 implement the ABI. */
841 else if (POINTER_TYPE_P (inner_type
)
842 && POINTER_TYPE_P (outer_type
)
843 && TYPE_REF_CAN_ALIAS_ALL (inner_type
)
844 == TYPE_REF_CAN_ALIAS_ALL (outer_type
)
845 && TREE_CODE (TREE_TYPE (outer_type
)) == VOID_TYPE
)
848 /* Pointers and references are equivalent once we get to GENERIC,
849 so strip conversions that just switch between them. */
850 else if (POINTER_TYPE_P (inner_type
)
851 && POINTER_TYPE_P (outer_type
)
852 && TYPE_REF_CAN_ALIAS_ALL (inner_type
)
853 == TYPE_REF_CAN_ALIAS_ALL (outer_type
)
854 && lang_hooks
.types_compatible_p (TREE_TYPE (inner_type
),
855 TREE_TYPE (outer_type
)))
858 /* If both the inner and outer types are integral types, then the
859 conversion is not necessary if they have the same mode and
860 signedness and precision, and both or neither are boolean. Some
861 code assumes an invariant that boolean types stay boolean and do
862 not become 1-bit bit-field types. Note that types with precision
863 not using all bits of the mode (such as bit-field types in C)
864 mean that testing of precision is necessary. */
865 else if (INTEGRAL_TYPE_P (inner_type
)
866 && INTEGRAL_TYPE_P (outer_type
)
867 && TYPE_UNSIGNED (inner_type
) == TYPE_UNSIGNED (outer_type
)
868 && TYPE_PRECISION (inner_type
) == TYPE_PRECISION (outer_type
))
870 bool first_boolean
= (TREE_CODE (inner_type
) == BOOLEAN_TYPE
);
871 bool second_boolean
= (TREE_CODE (outer_type
) == BOOLEAN_TYPE
);
872 if (first_boolean
== second_boolean
)
876 /* Recurse for complex types. */
877 else if (TREE_CODE (inner_type
) == COMPLEX_TYPE
878 && TREE_CODE (outer_type
) == COMPLEX_TYPE
879 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type
),
880 TREE_TYPE (inner_type
)))
886 /* Return true if EXPR is a useless type conversion, otherwise return
890 tree_ssa_useless_type_conversion (tree expr
)
892 /* If we have an assignment that merely uses a NOP_EXPR to change
893 the top of the RHS to the type of the LHS and the type conversion
894 is "safe", then strip away the type conversion so that we can
895 enter LHS = RHS into the const_and_copies table. */
896 if (TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
897 || TREE_CODE (expr
) == VIEW_CONVERT_EXPR
898 || TREE_CODE (expr
) == NON_LVALUE_EXPR
)
899 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr
),
900 TREE_TYPE (TREE_OPERAND (expr
,
907 /* Returns true if statement STMT may read memory. */
910 stmt_references_memory_p (tree stmt
)
914 get_stmt_operands (stmt
);
915 ann
= stmt_ann (stmt
);
917 if (ann
->has_volatile_ops
)
920 return (NUM_VUSES (VUSE_OPS (ann
)) > 0
921 || NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann
)) > 0
922 || NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann
)) > 0);
925 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
926 described in walk_use_def_chains.
928 VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
929 infinite loops. We used to have a bitmap for this to just mark
930 SSA versions we had visited. But non-sparse bitmaps are way too
931 expensive, while sparse bitmaps may cause quadratic behavior.
933 IS_DFS is true if the caller wants to perform a depth-first search
934 when visiting PHI nodes. A DFS will visit each PHI argument and
935 call FN after each one. Otherwise, all the arguments are
936 visited first and then FN is called with each of the visited
937 arguments in a separate pass. */
940 walk_use_def_chains_1 (tree var
, walk_use_def_chains_fn fn
, void *data
,
941 struct pointer_set_t
*visited
, bool is_dfs
)
945 if (pointer_set_insert (visited
, var
))
948 def_stmt
= SSA_NAME_DEF_STMT (var
);
950 if (TREE_CODE (def_stmt
) != PHI_NODE
)
952 /* If we reached the end of the use-def chain, call FN. */
953 return fn (var
, def_stmt
, data
);
959 /* When doing a breadth-first search, call FN before following the
960 use-def links for each argument. */
962 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
963 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
966 /* Follow use-def links out of each PHI argument. */
967 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
969 tree arg
= PHI_ARG_DEF (def_stmt
, i
);
970 if (TREE_CODE (arg
) == SSA_NAME
971 && walk_use_def_chains_1 (arg
, fn
, data
, visited
, is_dfs
))
975 /* When doing a depth-first search, call FN after following the
976 use-def links for each argument. */
978 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
979 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
988 /* Walk use-def chains starting at the SSA variable VAR. Call
989 function FN at each reaching definition found. FN takes three
990 arguments: VAR, its defining statement (DEF_STMT) and a generic
991 pointer to whatever state information that FN may want to maintain
992 (DATA). FN is able to stop the walk by returning true, otherwise
993 in order to continue the walk, FN should return false.
995 Note, that if DEF_STMT is a PHI node, the semantics are slightly
996 different. The first argument to FN is no longer the original
997 variable VAR, but the PHI argument currently being examined. If FN
998 wants to get at VAR, it should call PHI_RESULT (PHI).
1000 If IS_DFS is true, this function will:
1002 1- walk the use-def chains for all the PHI arguments, and,
1003 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
1005 If IS_DFS is false, the two steps above are done in reverse order
1006 (i.e., a breadth-first search). */
1010 walk_use_def_chains (tree var
, walk_use_def_chains_fn fn
, void *data
,
1015 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
1017 def_stmt
= SSA_NAME_DEF_STMT (var
);
1019 /* We only need to recurse if the reaching definition comes from a PHI
1021 if (TREE_CODE (def_stmt
) != PHI_NODE
)
1022 (*fn
) (var
, def_stmt
, data
);
1025 struct pointer_set_t
*visited
= pointer_set_create ();
1026 walk_use_def_chains_1 (var
, fn
, data
, visited
, is_dfs
);
1027 pointer_set_destroy (visited
);
1032 /* Replaces VAR with REPL in memory reference expression *X in
1033 statement STMT at use location USE_P. Return TRUE if Anything was done. */
1036 propagate_into_addr (tree stmt
, use_operand_p use_p
, tree
*x
, tree repl
)
1038 tree new_var
, ass_stmt
, addr_var
;
1040 block_stmt_iterator bsi
;
1042 /* There is nothing special to handle in the other cases. */
1043 if (TREE_CODE (repl
) != ADDR_EXPR
)
1045 addr_var
= TREE_OPERAND (repl
, 0);
1047 while (handled_component_p (*x
)
1048 || TREE_CODE (*x
) == REALPART_EXPR
1049 || TREE_CODE (*x
) == IMAGPART_EXPR
)
1050 x
= &TREE_OPERAND (*x
, 0);
1052 /* Heres a hack but since KRPhinodes is going away soon, Im not going to
1054 if (TREE_CODE (*x
) != INDIRECT_REF
1055 || &(TREE_OPERAND (*x
, 0)) != use_p
->use
) /* HACK ALERT. */
1058 if (TREE_TYPE (*x
) == TREE_TYPE (addr_var
))
1061 mark_new_vars_to_rename (stmt
, vars_to_rename
);
1066 /* Frontends sometimes produce expressions like *&a instead of a[0].
1067 Create a temporary variable to handle this case. */
1068 ass_stmt
= build2 (MODIFY_EXPR
, void_type_node
, NULL_TREE
, repl
);
1069 new_var
= duplicate_ssa_name (USE_FROM_PTR (use_p
), ass_stmt
);
1070 TREE_OPERAND (*x
, 0) = new_var
;
1071 TREE_OPERAND (ass_stmt
, 0) = new_var
;
1073 bb
= bb_for_stmt (stmt
);
1074 tree_block_label (bb
);
1075 bsi
= bsi_after_labels (bb
);
1076 bsi_insert_after (&bsi
, ass_stmt
, BSI_NEW_STMT
);
1078 mark_new_vars_to_rename (stmt
, vars_to_rename
);
1082 /* Replaces immediate uses of VAR by REPL. */
1085 replace_immediate_uses (tree var
, tree repl
)
1089 use_operand_p imm_use
;
1090 imm_use_iterator imm_iter
;
1092 FOR_EACH_IMM_USE_SAFE (imm_use
, imm_iter
, var
)
1094 stmt
= USE_STMT (imm_use
);
1096 if (TREE_CODE (stmt
) == PHI_NODE
)
1098 int index
= PHI_ARG_INDEX_FROM_USE (imm_use
);
1099 #ifdef ENABLE_CHECKING
1100 gcc_assert (&(PHI_ARG_IMM_USE_NODE (stmt
, index
)) == imm_use
);
1102 SET_USE (imm_use
, repl
);
1103 if (TREE_CODE (repl
) == SSA_NAME
1104 && PHI_ARG_EDGE (stmt
, index
)->flags
& EDGE_ABNORMAL
)
1105 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl
) = 1;
1109 gcc_assert (!stmt_modified_p (stmt
));
1111 mark_new_vars
= false;
1112 if (is_gimple_reg (SSA_NAME_VAR (var
)))
1114 bool propagated
= false;
1115 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
1117 if (TREE_CODE (repl
) == ADDR_EXPR
)
1120 propagate_into_addr (stmt
, imm_use
, &TREE_OPERAND (stmt
, 0),
1124 propagate_into_addr (stmt
, imm_use
,
1125 &TREE_OPERAND (stmt
, 1), repl
);
1129 propagate_value (imm_use
, repl
);
1130 mark_new_vars
= POINTER_TYPE_P (TREE_TYPE (repl
));
1133 propagate_value (imm_use
, repl
);
1135 /* FIXME. If REPL is a constant, we need to fold STMT.
1136 However, fold_stmt wants a pointer to the statement, because
1137 it may happen that it needs to replace the whole statement
1138 with a new expression. Since the current def-use machinery
1139 does not return pointers to statements, we call fold_stmt
1140 with the address of a local temporary, if that call changes
1141 the temporary then we fallback on looking for a proper
1142 pointer to STMT by scanning STMT's basic block.
1144 Note that all this will become unnecessary soon. This
1145 pass is being replaced with a proper copy propagation pass
1146 for 4.1 (dnovillo, 2004-09-17). */
1147 if (TREE_CODE (repl
) != SSA_NAME
)
1151 mark_new_vars
= true;
1154 block_stmt_iterator si
= bsi_for_stmt (stmt
);
1155 mark_new_vars_to_rename (tmp
, vars_to_rename
);
1156 bsi_replace (&si
, tmp
, true);
1157 stmt
= bsi_stmt (si
);
1161 /* If REPL is a pointer, it may have different memory tags associated
1162 with it. For instance, VAR may have had a name tag while REPL
1163 only had a type tag. In these cases, the virtual operands (if
1164 any) in the statement will refer to different symbols which need
1167 mark_new_vars_to_rename (stmt
, vars_to_rename
);
1174 /* Gets the value VAR is equivalent to according to EQ_TO. */
1177 get_eq_name (tree
*eq_to
, tree var
)
1182 while (TREE_CODE (val
) == SSA_NAME
)
1184 ver
= SSA_NAME_VERSION (val
);
1191 while (TREE_CODE (var
) == SSA_NAME
)
1193 ver
= SSA_NAME_VERSION (var
);
1204 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1205 its result is redundant to to EQ_TO array. */
1208 check_phi_redundancy (tree phi
, tree
*eq_to
)
1210 tree val
= NULL_TREE
, def
, res
= PHI_RESULT (phi
), stmt
;
1211 unsigned i
, ver
= SSA_NAME_VERSION (res
);
1212 imm_use_iterator imm_iter
;
1213 use_operand_p use_p
;
1215 /* It is unlikely that such large phi node would be redundant. */
1216 if (PHI_NUM_ARGS (phi
) > 16)
1219 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (phi
); i
++)
1221 def
= PHI_ARG_DEF (phi
, i
);
1223 if (TREE_CODE (def
) == SSA_NAME
)
1225 def
= get_eq_name (eq_to
, def
);
1231 && !operand_equal_for_phi_arg_p (val
, def
))
1237 /* At least one of the arguments should not be equal to the result, or
1238 something strange is happening. */
1241 if (get_eq_name (eq_to
, res
) == val
)
1244 if (!may_propagate_copy (res
, val
))
1249 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, res
)
1251 stmt
= USE_STMT (use_p
);
1252 if (TREE_CODE (stmt
) == PHI_NODE
)
1253 check_phi_redundancy (stmt
, eq_to
);
1257 /* Removes redundant phi nodes.
1259 A redundant PHI node is a PHI node where all of its PHI arguments
1260 are the same value, excluding any PHI arguments which are the same
1263 A redundant PHI node is effectively a copy, so we forward copy propagate
1264 which removes all uses of the destination of the PHI node then
1265 finally we delete the redundant PHI node.
1267 Note that if we can not copy propagate the PHI node, then the PHI
1268 will not be removed. Thus we do not have to worry about dependencies
1269 between PHIs and the problems serializing PHIs into copies creates.
1271 The most important effect of this pass is to remove degenerate PHI
1272 nodes created by removing unreachable code. */
1275 kill_redundant_phi_nodes (void)
1278 unsigned i
, old_num_ssa_names
;
1280 tree phi
, repl
, stmt
;
1282 /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1283 replaced. If EQ_TO[VER] is ssa name and it is decided to replace it by
1284 other value, it may be necessary to follow the chain till the final value.
1285 We perform path shortening (replacing the entries of the EQ_TO array with
1286 heads of these chains) whenever we access the field to prevent quadratic
1287 complexity (probably would not occur in practice anyway, but let us play
1289 eq_to
= xcalloc (num_ssa_names
, sizeof (tree
));
1291 old_num_ssa_names
= num_ssa_names
;
1295 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1296 check_phi_redundancy (phi
, eq_to
);
1299 /* Now propagate the values. */
1300 for (i
= 0; i
< old_num_ssa_names
; i
++)
1305 repl
= get_eq_name (eq_to
, ssa_name (i
));
1306 if (repl
!= ssa_name (i
))
1307 replace_immediate_uses (ssa_name (i
), repl
);
1310 /* And remove the dead phis. */
1311 for (i
= 0; i
< old_num_ssa_names
; i
++)
1316 repl
= get_eq_name (eq_to
, ssa_name (i
));
1317 if (repl
!= ssa_name (i
))
1319 stmt
= SSA_NAME_DEF_STMT (ssa_name (i
));
1320 remove_phi_node (stmt
, NULL_TREE
);
1327 struct tree_opt_pass pass_redundant_phi
=
1329 "redphi", /* name */
1331 kill_redundant_phi_nodes
, /* execute */
1334 0, /* static_pass_number */
1335 TV_TREE_REDPHI
, /* tv_id */
1336 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
1337 0, /* properties_provided */
1338 0, /* properties_destroyed */
1339 0, /* todo_flags_start */
1340 TODO_dump_func
| TODO_rename_vars
1341 | TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */
1345 /* Emit warnings for uninitialized variables. This is done in two passes.
1347 The first pass notices real uses of SSA names with default definitions.
1348 Such uses are unconditionally uninitialized, and we can be certain that
1349 such a use is a mistake. This pass is run before most optimizations,
1350 so that we catch as many as we can.
1352 The second pass follows PHI nodes to find uses that are potentially
1353 uninitialized. In this case we can't necessarily prove that the use
1354 is really uninitialized. This pass is run after most optimizations,
1355 so that we thread as many jumps and possible, and delete as much dead
1356 code as possible, in order to reduce false positives. We also look
1357 again for plain uninitialized variables, since optimization may have
1358 changed conditionally uninitialized to unconditionally uninitialized. */
1360 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1361 warning text is in MSGID and LOCUS may contain a location or be null. */
1364 warn_uninit (tree t
, const char *msgid
, void *data
)
1366 tree var
= SSA_NAME_VAR (t
);
1367 tree def
= SSA_NAME_DEF_STMT (t
);
1368 tree context
= (tree
) data
;
1371 /* Default uses (indicated by an empty definition statement),
1372 are uninitialized. */
1373 if (!IS_EMPTY_STMT (def
))
1376 /* Except for PARMs of course, which are always initialized. */
1377 if (TREE_CODE (var
) == PARM_DECL
)
1380 /* Hard register variables get their initial value from the ether. */
1381 if (TREE_CODE (var
) == VAR_DECL
&& DECL_HARD_REGISTER (var
))
1384 /* TREE_NO_WARNING either means we already warned, or the front end
1385 wishes to suppress the warning. */
1386 if (TREE_NO_WARNING (var
))
1389 locus
= (context
!= NULL
&& EXPR_HAS_LOCATION (context
)
1390 ? EXPR_LOCUS (context
)
1391 : &DECL_SOURCE_LOCATION (var
));
1392 warning (msgid
, locus
, var
);
1393 TREE_NO_WARNING (var
) = 1;
1396 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1397 and warn about them. */
1400 warn_uninitialized_var (tree
*tp
, int *walk_subtrees
, void *data
)
1404 /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */
1405 if (TREE_CODE (t
) == SSA_NAME
)
1407 warn_uninit (t
, "%H%qD is used uninitialized in this function", data
);
1410 else if (IS_TYPE_OR_DECL_P (t
))
1416 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1417 and warn about them. */
1420 warn_uninitialized_phi (tree phi
)
1422 int i
, n
= PHI_NUM_ARGS (phi
);
1424 /* Don't look at memory tags. */
1425 if (!is_gimple_reg (PHI_RESULT (phi
)))
1428 for (i
= 0; i
< n
; ++i
)
1430 tree op
= PHI_ARG_DEF (phi
, i
);
1431 if (TREE_CODE (op
) == SSA_NAME
)
1432 warn_uninit (op
, "%H%qD may be used uninitialized in this function",
1438 execute_early_warn_uninitialized (void)
1440 block_stmt_iterator bsi
;
1444 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1446 tree context
= bsi_stmt (bsi
);
1447 walk_tree (bsi_stmt_ptr (bsi
), warn_uninitialized_var
,
1453 execute_late_warn_uninitialized (void)
1458 /* Re-do the plain uninitialized variable check, as optimization may have
1459 straightened control flow. Do this first so that we don't accidentally
1460 get a "may be" warning when we'd have seen an "is" warning later. */
1461 execute_early_warn_uninitialized ();
1464 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1465 warn_uninitialized_phi (phi
);
1469 gate_warn_uninitialized (void)
1471 return warn_uninitialized
!= 0;
1474 struct tree_opt_pass pass_early_warn_uninitialized
=
1477 gate_warn_uninitialized
, /* gate */
1478 execute_early_warn_uninitialized
, /* execute */
1481 0, /* static_pass_number */
1483 PROP_ssa
, /* properties_required */
1484 0, /* properties_provided */
1485 0, /* properties_destroyed */
1486 0, /* todo_flags_start */
1487 0, /* todo_flags_finish */
1491 struct tree_opt_pass pass_late_warn_uninitialized
=
1494 gate_warn_uninitialized
, /* gate */
1495 execute_late_warn_uninitialized
, /* execute */
1498 0, /* static_pass_number */
1500 PROP_ssa
, /* properties_required */
1501 0, /* properties_provided */
1502 0, /* properties_destroyed */
1503 0, /* todo_flags_start */
1504 0, /* todo_flags_finish */