1 /* Miscellaneous SSA utility functions.
2 Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
23 #include "coretypes.h"
30 #include "langhooks.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
37 #include "diagnostic.h"
39 #include "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
;
61 /* Remove the appropriate PHI arguments in E's destination block. */
62 for (phi
= phi_nodes (e
->dest
); phi
; phi
= next
)
64 next
= PHI_CHAIN (phi
);
66 i
= phi_arg_from_edge (phi
, e
);
67 if (PHI_ARG_DEF (phi
, i
) == NULL_TREE
)
70 src
= PHI_ARG_DEF (phi
, i
);
71 dst
= PHI_RESULT (phi
);
72 node
= build_tree_list (dst
, src
);
74 last
= &TREE_CHAIN (node
);
77 e
= redirect_edge_succ_nodup (e
, dest
);
78 PENDING_STMT (e
) = list
;
83 /* Add PHI arguments queued in PENDINT_STMT list on edge E to edge
87 flush_pending_stmts (edge e
)
91 if (!PENDING_STMT (e
))
94 for (phi
= phi_nodes (e
->dest
), arg
= PENDING_STMT (e
);
96 phi
= PHI_CHAIN (phi
), arg
= TREE_CHAIN (arg
))
98 tree def
= TREE_VALUE (arg
);
99 add_phi_arg (phi
, def
, e
);
102 PENDING_STMT (e
) = NULL
;
105 /* Return true if SSA_NAME is malformed and mark it visited.
107 IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
111 verify_ssa_name (tree ssa_name
, bool is_virtual
)
113 TREE_VISITED (ssa_name
) = 1;
115 if (TREE_CODE (ssa_name
) != SSA_NAME
)
117 error ("Expected an SSA_NAME object");
121 if (TREE_TYPE (ssa_name
) != TREE_TYPE (SSA_NAME_VAR (ssa_name
)))
123 error ("Type mismatch between an SSA_NAME and its symbol.");
127 if (SSA_NAME_IN_FREE_LIST (ssa_name
))
129 error ("Found an SSA_NAME that had been released into the free pool");
133 if (is_virtual
&& is_gimple_reg (ssa_name
))
135 error ("Found a virtual definition for a GIMPLE register");
139 if (!is_virtual
&& !is_gimple_reg (ssa_name
))
141 error ("Found a real definition for a non-register");
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
, tree ssa_name
,
218 tree stmt
, bool check_abnormal
, bool is_virtual
,
219 bitmap names_defined_in_bb
)
223 err
= verify_ssa_name (ssa_name
, is_virtual
);
225 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name
))
226 && var_ann (SSA_NAME_VAR (ssa_name
))->default_def
== ssa_name
)
227 ; /* Default definitions have empty statements. Nothing to do. */
230 error ("Missing definition");
233 else if (bb
!= def_bb
234 && !dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
236 error ("Definition in block %i does not dominate use in block %i",
237 def_bb
->index
, bb
->index
);
240 else if (bb
== def_bb
241 && names_defined_in_bb
!= NULL
242 && !bitmap_bit_p (names_defined_in_bb
, SSA_NAME_VERSION (ssa_name
)))
244 error ("Definition in block %i follows the use", def_bb
->index
);
249 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name
))
251 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
257 fprintf (stderr
, "for SSA_NAME: ");
258 print_generic_expr (stderr
, ssa_name
, TDF_VOPS
);
259 fprintf (stderr
, "in statement:\n");
260 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
267 /* Return true if any of the arguments for PHI node PHI at block BB is
270 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
271 numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
272 block in that array slot contains the definition of SSA_NAME. */
275 verify_phi_args (tree phi
, basic_block bb
, basic_block
*definition_block
)
279 unsigned i
, phi_num_args
= PHI_NUM_ARGS (phi
);
281 if (EDGE_COUNT (bb
->preds
) != phi_num_args
)
283 error ("Incoming edge count does not match number of PHI arguments\n");
288 for (i
= 0; i
< phi_num_args
; i
++)
290 tree op
= PHI_ARG_DEF (phi
, i
);
292 e
= PHI_ARG_EDGE (phi
, i
);
296 error ("PHI argument is missing for edge %d->%d\n",
303 if (TREE_CODE (op
) != SSA_NAME
&& !is_gimple_min_invariant (op
))
305 error ("PHI argument is not SSA_NAME, or invariant");
309 if (TREE_CODE (op
) == SSA_NAME
)
310 err
= verify_use (e
->src
, definition_block
[SSA_NAME_VERSION (op
)], op
,
311 phi
, e
->flags
& EDGE_ABNORMAL
,
312 !is_gimple_reg (PHI_RESULT (phi
)),
317 error ("Wrong edge %d->%d for PHI argument\n",
318 e
->src
->index
, e
->dest
->index
, bb
->index
);
324 fprintf (stderr
, "PHI argument\n");
325 print_generic_stmt (stderr
, op
, TDF_VOPS
);
333 fprintf (stderr
, "for PHI node\n");
334 print_generic_stmt (stderr
, phi
, TDF_VOPS
);
343 verify_flow_insensitive_alias_info (void)
347 bitmap visited
= BITMAP_XMALLOC ();
349 for (i
= 0; i
< num_referenced_vars
; i
++)
353 varray_type may_aliases
;
355 var
= referenced_var (i
);
357 may_aliases
= ann
->may_aliases
;
359 for (j
= 0; may_aliases
&& j
< VARRAY_ACTIVE_SIZE (may_aliases
); j
++)
361 tree alias
= VARRAY_TREE (may_aliases
, j
);
363 bitmap_set_bit (visited
, var_ann (alias
)->uid
);
365 if (!may_be_aliased (alias
))
367 error ("Non-addressable variable inside an alias set.");
368 debug_variable (alias
);
374 for (i
= 0; i
< num_referenced_vars
; i
++)
378 var
= referenced_var (i
);
381 if (ann
->mem_tag_kind
== NOT_A_TAG
383 && !bitmap_bit_p (visited
, ann
->uid
))
385 error ("Addressable variable that is an alias tag but is not in any alias set.");
390 BITMAP_XFREE (visited
);
394 debug_variable (var
);
395 internal_error ("verify_flow_insensitive_alias_info failed.");
400 verify_flow_sensitive_alias_info (void)
405 for (i
= 1; i
< num_ssa_names
; i
++)
408 struct ptr_info_def
*pi
;
413 ann
= var_ann (SSA_NAME_VAR (ptr
));
414 pi
= SSA_NAME_PTR_INFO (ptr
);
416 /* We only care for pointers that are actually referenced in the
418 if (!TREE_VISITED (ptr
) || !POINTER_TYPE_P (TREE_TYPE (ptr
)))
421 /* RESULT_DECL is special. If it's a GIMPLE register, then it
422 is only written-to only once in the return statement.
423 Otherwise, aggregate RESULT_DECLs may be written-to more than
424 once in virtual operands. */
425 if (TREE_CODE (SSA_NAME_VAR (ptr
)) == RESULT_DECL
426 && is_gimple_reg (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
472 verify_name_tags (void)
476 bitmap first
, second
;
477 VEC (tree
) *name_tag_reps
= NULL
;
478 VEC (bitmap
) *pt_vars_for_reps
= NULL
;
480 /* First we compute the name tag representatives and their points-to sets. */
481 for (i
= 0; i
< num_ssa_names
; i
++)
485 tree ptr
= ssa_name (i
);
486 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
487 if (!TREE_VISITED (ptr
)
488 || !POINTER_TYPE_P (TREE_TYPE (ptr
))
491 || TREE_VISITED (pi
->name_mem_tag
))
493 TREE_VISITED (pi
->name_mem_tag
) = 1;
494 if (pi
->pt_vars
!= NULL
)
496 VEC_safe_push (tree
, name_tag_reps
, ptr
);
497 VEC_safe_push (bitmap
, pt_vars_for_reps
, pi
->pt_vars
);
502 /* Now compare all the representative bitmaps with all other representative
503 bitmaps, to verify that they are all different. */
504 for (i
= 0; VEC_iterate (bitmap
, pt_vars_for_reps
, i
, first
); i
++)
506 for (j
= i
+ 1; VEC_iterate (bitmap
, pt_vars_for_reps
, j
, second
); j
++)
508 if (bitmap_equal_p (first
, second
))
510 error ("Two different pointers with identical points-to sets but different name tags");
511 debug_variable (VEC_index (tree
, name_tag_reps
, j
));
517 /* Lastly, clear out the visited flags. */
518 for (i
= 0; i
< num_ssa_names
; i
++)
522 tree ptr
= ssa_name (i
);
523 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
524 if (!TREE_VISITED (ptr
)
525 || !POINTER_TYPE_P (TREE_TYPE (ptr
))
527 || !pi
->name_mem_tag
)
529 TREE_VISITED (pi
->name_mem_tag
) = 0;
532 VEC_free (bitmap
, pt_vars_for_reps
);
536 debug_variable (VEC_index (tree
, name_tag_reps
, i
));
537 internal_error ("verify_name_tags failed");
539 /* Verify the consistency of aliasing information. */
542 verify_alias_info (void)
544 verify_flow_sensitive_alias_info ();
546 verify_flow_insensitive_alias_info ();
550 /* Verify common invariants in the SSA web.
551 TODO: verify the variable annotations. */
558 basic_block
*definition_block
= xcalloc (num_ssa_names
, sizeof (basic_block
));
561 enum dom_state orig_dom_state
= dom_computed
[CDI_DOMINATORS
];
562 bitmap names_defined_in_bb
= BITMAP_XMALLOC ();
564 timevar_push (TV_TREE_SSA_VERIFY
);
566 /* Keep track of SSA names present in the IL. */
567 for (i
= 1; i
< num_ssa_names
; i
++)
569 tree name
= ssa_name (i
);
573 TREE_VISITED (name
) = 0;
575 stmt
= SSA_NAME_DEF_STMT (name
);
576 if (!IS_EMPTY_STMT (stmt
))
578 basic_block bb
= bb_for_stmt (stmt
);
579 verify_def (bb
, definition_block
,
580 name
, stmt
, !is_gimple_reg (name
));
586 calculate_dominance_info (CDI_DOMINATORS
);
588 /* Now verify all the uses and make sure they agree with the definitions
589 found in the previous pass. */
595 block_stmt_iterator bsi
;
597 /* Make sure that all edges have a clear 'aux' field. */
598 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
602 error ("AUX pointer initialized for edge %d->%d\n", e
->src
->index
,
608 /* Verify the arguments for every PHI node in the block. */
609 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
611 if (verify_phi_args (phi
, bb
, definition_block
))
613 bitmap_set_bit (names_defined_in_bb
,
614 SSA_NAME_VERSION (PHI_RESULT (phi
)));
617 /* Now verify all the uses and vuses in every statement of the block. */
618 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
620 tree stmt
= bsi_stmt (bsi
);
622 get_stmt_operands (stmt
);
624 if (stmt_ann (stmt
)->makes_aliased_stores
625 && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt
)) == 0)
627 error ("Statement makes aliased stores, but has no V_MAY_DEFS");
628 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
632 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_ALL_USES
| SSA_OP_ALL_KILLS
)
634 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
635 op
, stmt
, false, !is_gimple_reg (op
),
636 names_defined_in_bb
))
640 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_ALL_DEFS
)
642 bitmap_set_bit (names_defined_in_bb
, SSA_NAME_VERSION (op
));
646 bitmap_clear (names_defined_in_bb
);
649 /* Finally, verify alias information. */
650 verify_alias_info ();
652 free (definition_block
);
653 /* Restore the dominance information to its prior known state, so
654 that we do not perturb the compiler's subsequent behavior. */
655 if (orig_dom_state
== DOM_NONE
)
656 free_dominance_info (CDI_DOMINATORS
);
658 dom_computed
[CDI_DOMINATORS
] = orig_dom_state
;
660 BITMAP_XFREE (names_defined_in_bb
);
661 timevar_pop (TV_TREE_SSA_VERIFY
);
665 internal_error ("verify_ssa failed.");
669 /* Initialize global DFA and SSA structures. */
674 VARRAY_TREE_INIT (referenced_vars
, 20, "referenced_vars");
675 call_clobbered_vars
= BITMAP_XMALLOC ();
676 addressable_vars
= BITMAP_XMALLOC ();
677 init_ssa_operands ();
680 global_var
= NULL_TREE
;
684 /* Deallocate memory associated with SSA data structures for FNDECL. */
687 delete_tree_ssa (void)
691 block_stmt_iterator bsi
;
693 /* Remove annotations from every tree in the function. */
695 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
697 tree stmt
= bsi_stmt (bsi
);
699 ggc_free (stmt
->common
.ann
);
700 stmt
->common
.ann
= NULL
;
703 /* Remove annotations from every referenced variable. */
706 for (i
= 0; i
< num_referenced_vars
; i
++)
708 tree var
= referenced_var (i
);
709 ggc_free (var
->common
.ann
);
710 var
->common
.ann
= NULL
;
712 referenced_vars
= NULL
;
717 fini_ssa_operands ();
719 global_var
= NULL_TREE
;
720 BITMAP_XFREE (call_clobbered_vars
);
721 call_clobbered_vars
= NULL
;
722 BITMAP_XFREE (addressable_vars
);
723 addressable_vars
= NULL
;
727 /* Return true if EXPR is a useless type conversion, otherwise return
731 tree_ssa_useless_type_conversion_1 (tree outer_type
, tree inner_type
)
733 /* If the inner and outer types are effectively the same, then
734 strip the type conversion and enter the equivalence into
736 if (inner_type
== outer_type
737 || (lang_hooks
.types_compatible_p (inner_type
, outer_type
)))
740 /* If both types are pointers and the outer type is a (void *), then
741 the conversion is not necessary. The opposite is not true since
742 that conversion would result in a loss of information if the
743 equivalence was used. Consider an indirect function call where
744 we need to know the exact type of the function to correctly
745 implement the ABI. */
746 else if (POINTER_TYPE_P (inner_type
)
747 && POINTER_TYPE_P (outer_type
)
748 && TYPE_MODE (inner_type
) == TYPE_MODE (outer_type
)
749 && TYPE_REF_CAN_ALIAS_ALL (inner_type
)
750 == TYPE_REF_CAN_ALIAS_ALL (outer_type
)
751 && TREE_CODE (TREE_TYPE (outer_type
)) == VOID_TYPE
)
754 /* Pointers and references are equivalent once we get to GENERIC,
755 so strip conversions that just switch between them. */
756 else if (POINTER_TYPE_P (inner_type
)
757 && POINTER_TYPE_P (outer_type
)
758 && TYPE_MODE (inner_type
) == TYPE_MODE (outer_type
)
759 && TYPE_REF_CAN_ALIAS_ALL (inner_type
)
760 == TYPE_REF_CAN_ALIAS_ALL (outer_type
)
761 && lang_hooks
.types_compatible_p (TREE_TYPE (inner_type
),
762 TREE_TYPE (outer_type
)))
765 /* If both the inner and outer types are integral types, then the
766 conversion is not necessary if they have the same mode and
767 signedness and precision, and both or neither are boolean. Some
768 code assumes an invariant that boolean types stay boolean and do
769 not become 1-bit bit-field types. Note that types with precision
770 not using all bits of the mode (such as bit-field types in C)
771 mean that testing of precision is necessary. */
772 else if (INTEGRAL_TYPE_P (inner_type
)
773 && INTEGRAL_TYPE_P (outer_type
)
774 && TYPE_MODE (inner_type
) == TYPE_MODE (outer_type
)
775 && TYPE_UNSIGNED (inner_type
) == TYPE_UNSIGNED (outer_type
)
776 && TYPE_PRECISION (inner_type
) == TYPE_PRECISION (outer_type
))
778 bool first_boolean
= (TREE_CODE (inner_type
) == BOOLEAN_TYPE
);
779 bool second_boolean
= (TREE_CODE (outer_type
) == BOOLEAN_TYPE
);
780 if (first_boolean
== second_boolean
)
784 /* Recurse for complex types. */
785 else if (TREE_CODE (inner_type
) == COMPLEX_TYPE
786 && TREE_CODE (outer_type
) == COMPLEX_TYPE
787 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type
),
788 TREE_TYPE (inner_type
)))
794 /* Return true if EXPR is a useless type conversion, otherwise return
798 tree_ssa_useless_type_conversion (tree expr
)
800 /* If we have an assignment that merely uses a NOP_EXPR to change
801 the top of the RHS to the type of the LHS and the type conversion
802 is "safe", then strip away the type conversion so that we can
803 enter LHS = RHS into the const_and_copies table. */
804 if (TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
805 || TREE_CODE (expr
) == VIEW_CONVERT_EXPR
806 || TREE_CODE (expr
) == NON_LVALUE_EXPR
)
807 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr
),
808 TREE_TYPE (TREE_OPERAND (expr
,
815 /* Returns true if statement STMT may read memory. */
818 stmt_references_memory_p (tree stmt
)
822 get_stmt_operands (stmt
);
823 ann
= stmt_ann (stmt
);
825 if (ann
->has_volatile_ops
)
828 return (NUM_VUSES (VUSE_OPS (ann
)) > 0
829 || NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann
)) > 0
830 || NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann
)) > 0);
833 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
834 described in walk_use_def_chains.
836 VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
837 infinite loops. We used to have a bitmap for this to just mark
838 SSA versions we had visited. But non-sparse bitmaps are way too
839 expensive, while sparse bitmaps may cause quadratic behavior.
841 IS_DFS is true if the caller wants to perform a depth-first search
842 when visiting PHI nodes. A DFS will visit each PHI argument and
843 call FN after each one. Otherwise, all the arguments are
844 visited first and then FN is called with each of the visited
845 arguments in a separate pass. */
848 walk_use_def_chains_1 (tree var
, walk_use_def_chains_fn fn
, void *data
,
849 struct pointer_set_t
*visited
, bool is_dfs
)
853 if (pointer_set_insert (visited
, var
))
856 def_stmt
= SSA_NAME_DEF_STMT (var
);
858 if (TREE_CODE (def_stmt
) != PHI_NODE
)
860 /* If we reached the end of the use-def chain, call FN. */
861 return fn (var
, def_stmt
, data
);
867 /* When doing a breadth-first search, call FN before following the
868 use-def links for each argument. */
870 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
871 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
874 /* Follow use-def links out of each PHI argument. */
875 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
877 tree arg
= PHI_ARG_DEF (def_stmt
, i
);
878 if (TREE_CODE (arg
) == SSA_NAME
879 && walk_use_def_chains_1 (arg
, fn
, data
, visited
, is_dfs
))
883 /* When doing a depth-first search, call FN after following the
884 use-def links for each argument. */
886 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
887 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
896 /* Walk use-def chains starting at the SSA variable VAR. Call
897 function FN at each reaching definition found. FN takes three
898 arguments: VAR, its defining statement (DEF_STMT) and a generic
899 pointer to whatever state information that FN may want to maintain
900 (DATA). FN is able to stop the walk by returning true, otherwise
901 in order to continue the walk, FN should return false.
903 Note, that if DEF_STMT is a PHI node, the semantics are slightly
904 different. The first argument to FN is no longer the original
905 variable VAR, but the PHI argument currently being examined. If FN
906 wants to get at VAR, it should call PHI_RESULT (PHI).
908 If IS_DFS is true, this function will:
910 1- walk the use-def chains for all the PHI arguments, and,
911 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
913 If IS_DFS is false, the two steps above are done in reverse order
914 (i.e., a breadth-first search). */
918 walk_use_def_chains (tree var
, walk_use_def_chains_fn fn
, void *data
,
923 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
925 def_stmt
= SSA_NAME_DEF_STMT (var
);
927 /* We only need to recurse if the reaching definition comes from a PHI
929 if (TREE_CODE (def_stmt
) != PHI_NODE
)
930 (*fn
) (var
, def_stmt
, data
);
933 struct pointer_set_t
*visited
= pointer_set_create ();
934 walk_use_def_chains_1 (var
, fn
, data
, visited
, is_dfs
);
935 pointer_set_destroy (visited
);
940 /* Replaces VAR with REPL in memory reference expression *X in
944 propagate_into_addr (tree stmt
, tree var
, tree
*x
, tree repl
)
946 tree new_var
, ass_stmt
, addr_var
;
948 block_stmt_iterator bsi
;
950 /* There is nothing special to handle in the other cases. */
951 if (TREE_CODE (repl
) != ADDR_EXPR
)
953 addr_var
= TREE_OPERAND (repl
, 0);
955 while (handled_component_p (*x
)
956 || TREE_CODE (*x
) == REALPART_EXPR
957 || TREE_CODE (*x
) == IMAGPART_EXPR
)
958 x
= &TREE_OPERAND (*x
, 0);
960 if (TREE_CODE (*x
) != INDIRECT_REF
961 || TREE_OPERAND (*x
, 0) != var
)
964 if (TREE_TYPE (*x
) == TREE_TYPE (addr_var
))
967 mark_new_vars_to_rename (stmt
, vars_to_rename
);
972 /* Frontends sometimes produce expressions like *&a instead of a[0].
973 Create a temporary variable to handle this case. */
974 ass_stmt
= build2 (MODIFY_EXPR
, void_type_node
, NULL_TREE
, repl
);
975 new_var
= duplicate_ssa_name (var
, ass_stmt
);
976 TREE_OPERAND (*x
, 0) = new_var
;
977 TREE_OPERAND (ass_stmt
, 0) = new_var
;
979 bb
= bb_for_stmt (stmt
);
980 tree_block_label (bb
);
981 bsi
= bsi_after_labels (bb
);
982 bsi_insert_after (&bsi
, ass_stmt
, BSI_NEW_STMT
);
984 mark_new_vars_to_rename (stmt
, vars_to_rename
);
987 /* Replaces immediate uses of VAR by REPL. */
990 replace_immediate_uses (tree var
, tree repl
)
999 df
= get_immediate_uses (SSA_NAME_DEF_STMT (var
));
1000 n
= num_immediate_uses (df
);
1002 for (i
= 0; i
< n
; i
++)
1004 stmt
= immediate_use (df
, i
);
1006 if (TREE_CODE (stmt
) == PHI_NODE
)
1008 for (j
= 0; j
< PHI_NUM_ARGS (stmt
); j
++)
1009 if (PHI_ARG_DEF (stmt
, j
) == var
)
1011 SET_PHI_ARG_DEF (stmt
, j
, repl
);
1012 if (TREE_CODE (repl
) == SSA_NAME
1013 && PHI_ARG_EDGE (stmt
, j
)->flags
& EDGE_ABNORMAL
)
1014 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl
) = 1;
1020 get_stmt_operands (stmt
);
1021 mark_new_vars
= false;
1022 if (is_gimple_reg (SSA_NAME_VAR (var
)))
1024 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
1026 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 0), repl
);
1027 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 1), repl
);
1030 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
1031 if (USE_FROM_PTR (use_p
) == var
)
1033 propagate_value (use_p
, repl
);
1034 mark_new_vars
= POINTER_TYPE_P (TREE_TYPE (repl
));
1039 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
,
1040 SSA_OP_VIRTUAL_USES
| SSA_OP_VIRTUAL_KILLS
)
1041 if (USE_FROM_PTR (use_p
) == var
)
1042 propagate_value (use_p
, repl
);
1045 /* FIXME. If REPL is a constant, we need to fold STMT.
1046 However, fold_stmt wants a pointer to the statement, because
1047 it may happen that it needs to replace the whole statement
1048 with a new expression. Since the current def-use machinery
1049 does not return pointers to statements, we call fold_stmt
1050 with the address of a local temporary, if that call changes
1051 the temporary then we fallback on looking for a proper
1052 pointer to STMT by scanning STMT's basic block.
1054 Note that all this will become unnecessary soon. This
1055 pass is being replaced with a proper copy propagation pass
1056 for 4.1 (dnovillo, 2004-09-17). */
1057 if (TREE_CODE (repl
) != SSA_NAME
)
1061 mark_new_vars
= true;
1064 block_stmt_iterator si
= bsi_for_stmt (stmt
);
1065 bsi_replace (&si
, tmp
, true);
1066 stmt
= bsi_stmt (si
);
1070 /* If REPL is a pointer, it may have different memory tags associated
1071 with it. For instance, VAR may have had a name tag while REPL
1072 only had a type tag. In these cases, the virtual operands (if
1073 any) in the statement will refer to different symbols which need
1076 mark_new_vars_to_rename (stmt
, vars_to_rename
);
1082 /* Gets the value VAR is equivalent to according to EQ_TO. */
1085 get_eq_name (tree
*eq_to
, tree var
)
1090 while (TREE_CODE (val
) == SSA_NAME
)
1092 ver
= SSA_NAME_VERSION (val
);
1099 while (TREE_CODE (var
) == SSA_NAME
)
1101 ver
= SSA_NAME_VERSION (var
);
1112 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1113 its result is redundant to to EQ_TO array. */
1116 check_phi_redundancy (tree phi
, tree
*eq_to
)
1118 tree val
= NULL_TREE
, def
, res
= PHI_RESULT (phi
), stmt
;
1119 unsigned i
, ver
= SSA_NAME_VERSION (res
), n
;
1122 /* It is unlikely that such large phi node would be redundant. */
1123 if (PHI_NUM_ARGS (phi
) > 16)
1126 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (phi
); i
++)
1128 def
= PHI_ARG_DEF (phi
, i
);
1130 if (TREE_CODE (def
) == SSA_NAME
)
1132 def
= get_eq_name (eq_to
, def
);
1138 && !operand_equal_p (val
, def
, 0))
1144 /* At least one of the arguments should not be equal to the result, or
1145 something strange is happening. */
1148 if (get_eq_name (eq_to
, res
) == val
)
1151 if (!may_propagate_copy (res
, val
))
1156 df
= get_immediate_uses (SSA_NAME_DEF_STMT (res
));
1157 n
= num_immediate_uses (df
);
1159 for (i
= 0; i
< n
; i
++)
1161 stmt
= immediate_use (df
, i
);
1163 if (TREE_CODE (stmt
) == PHI_NODE
)
1164 check_phi_redundancy (stmt
, eq_to
);
1168 /* Removes redundant phi nodes.
1170 A redundant PHI node is a PHI node where all of its PHI arguments
1171 are the same value, excluding any PHI arguments which are the same
1174 A redundant PHI node is effectively a copy, so we forward copy propagate
1175 which removes all uses of the destination of the PHI node then
1176 finally we delete the redundant PHI node.
1178 Note that if we can not copy propagate the PHI node, then the PHI
1179 will not be removed. Thus we do not have to worry about dependencies
1180 between PHIs and the problems serializing PHIs into copies creates.
1182 The most important effect of this pass is to remove degenerate PHI
1183 nodes created by removing unreachable code. */
1186 kill_redundant_phi_nodes (void)
1189 unsigned i
, old_num_ssa_names
;
1191 tree phi
, var
, repl
, stmt
;
1193 /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1194 replaced. If EQ_TO[VER] is ssa name and it is decided to replace it by
1195 other value, it may be necessary to follow the chain till the final value.
1196 We perform path shortening (replacing the entries of the EQ_TO array with
1197 heads of these chains) whenever we access the field to prevent quadratic
1198 complexity (probably would not occur in practice anyway, but let us play
1200 eq_to
= xcalloc (num_ssa_names
, sizeof (tree
));
1202 /* We have had cases where computing immediate uses takes a
1203 significant amount of compile time. If we run into such
1204 problems here, we may want to only compute immediate uses for
1205 a subset of all the SSA_NAMEs instead of computing it for
1206 all of the SSA_NAMEs. */
1207 compute_immediate_uses (TDFA_USE_OPS
| TDFA_USE_VOPS
, NULL
);
1208 old_num_ssa_names
= num_ssa_names
;
1212 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1214 var
= PHI_RESULT (phi
);
1215 check_phi_redundancy (phi
, eq_to
);
1219 /* Now propagate the values. */
1220 for (i
= 0; i
< old_num_ssa_names
; i
++)
1225 repl
= get_eq_name (eq_to
, ssa_name (i
));
1226 if (repl
!= ssa_name (i
))
1227 replace_immediate_uses (ssa_name (i
), repl
);
1230 /* And remove the dead phis. */
1231 for (i
= 0; i
< old_num_ssa_names
; i
++)
1236 repl
= get_eq_name (eq_to
, ssa_name (i
));
1237 if (repl
!= ssa_name (i
))
1239 stmt
= SSA_NAME_DEF_STMT (ssa_name (i
));
1240 remove_phi_node (stmt
, NULL_TREE
, bb_for_stmt (stmt
));
1248 struct tree_opt_pass pass_redundant_phi
=
1250 "redphi", /* name */
1252 kill_redundant_phi_nodes
, /* execute */
1255 0, /* static_pass_number */
1257 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
1258 0, /* properties_provided */
1259 0, /* properties_destroyed */
1260 0, /* todo_flags_start */
1261 TODO_dump_func
| TODO_rename_vars
1262 | TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */
1266 /* Emit warnings for uninitialized variables. This is done in two passes.
1268 The first pass notices real uses of SSA names with default definitions.
1269 Such uses are unconditionally uninitialized, and we can be certain that
1270 such a use is a mistake. This pass is run before most optimizations,
1271 so that we catch as many as we can.
1273 The second pass follows PHI nodes to find uses that are potentially
1274 uninitialized. In this case we can't necessarily prove that the use
1275 is really uninitialized. This pass is run after most optimizations,
1276 so that we thread as many jumps and possible, and delete as much dead
1277 code as possible, in order to reduce false positives. We also look
1278 again for plain uninitialized variables, since optimization may have
1279 changed conditionally uninitialized to unconditionally uninitialized. */
1281 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1282 warning text is in MSGID and LOCUS may contain a location or be null. */
1285 warn_uninit (tree t
, const char *msgid
, location_t
*locus
)
1287 tree var
= SSA_NAME_VAR (t
);
1288 tree def
= SSA_NAME_DEF_STMT (t
);
1290 /* Default uses (indicated by an empty definition statement),
1291 are uninitialized. */
1292 if (!IS_EMPTY_STMT (def
))
1295 /* Except for PARMs of course, which are always initialized. */
1296 if (TREE_CODE (var
) == PARM_DECL
)
1299 /* Hard register variables get their initial value from the ether. */
1300 if (TREE_CODE (var
) == VAR_DECL
&& DECL_HARD_REGISTER (var
))
1303 /* TREE_NO_WARNING either means we already warned, or the front end
1304 wishes to suppress the warning. */
1305 if (TREE_NO_WARNING (var
))
1309 locus
= &DECL_SOURCE_LOCATION (var
);
1310 warning (msgid
, locus
, var
);
1311 TREE_NO_WARNING (var
) = 1;
1314 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1315 and warn about them. */
1318 warn_uninitialized_var (tree
*tp
, int *walk_subtrees
, void *data
)
1320 location_t
*locus
= data
;
1323 /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */
1324 if (TREE_CODE (t
) == SSA_NAME
)
1326 warn_uninit (t
, "%H%qD is used uninitialized in this function", locus
);
1329 else if (IS_TYPE_OR_DECL_P (t
))
1335 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1336 and warn about them. */
1339 warn_uninitialized_phi (tree phi
)
1341 int i
, n
= PHI_NUM_ARGS (phi
);
1343 /* Don't look at memory tags. */
1344 if (!is_gimple_reg (PHI_RESULT (phi
)))
1347 for (i
= 0; i
< n
; ++i
)
1349 tree op
= PHI_ARG_DEF (phi
, i
);
1350 if (TREE_CODE (op
) == SSA_NAME
)
1351 warn_uninit (op
, "%H%qD may be used uninitialized in this function",
1357 execute_early_warn_uninitialized (void)
1359 block_stmt_iterator bsi
;
1363 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1364 walk_tree (bsi_stmt_ptr (bsi
), warn_uninitialized_var
,
1365 EXPR_LOCUS (bsi_stmt (bsi
)), NULL
);
1369 execute_late_warn_uninitialized (void)
1374 /* Re-do the plain uninitialized variable check, as optimization may have
1375 straightened control flow. Do this first so that we don't accidentally
1376 get a "may be" warning when we'd have seen an "is" warning later. */
1377 execute_early_warn_uninitialized ();
1380 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1381 warn_uninitialized_phi (phi
);
1385 gate_warn_uninitialized (void)
1387 return warn_uninitialized
!= 0;
1390 struct tree_opt_pass pass_early_warn_uninitialized
=
1393 gate_warn_uninitialized
, /* gate */
1394 execute_early_warn_uninitialized
, /* execute */
1397 0, /* static_pass_number */
1399 PROP_ssa
, /* properties_required */
1400 0, /* properties_provided */
1401 0, /* properties_destroyed */
1402 0, /* todo_flags_start */
1403 0, /* todo_flags_finish */
1407 struct tree_opt_pass pass_late_warn_uninitialized
=
1410 gate_warn_uninitialized
, /* gate */
1411 execute_late_warn_uninitialized
, /* execute */
1414 0, /* static_pass_number */
1416 PROP_ssa
, /* properties_required */
1417 0, /* properties_provided */
1418 0, /* properties_destroyed */
1419 0, /* todo_flags_start */
1420 0, /* todo_flags_finish */