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 "tree-flow.h"
40 #include "tree-gimple.h"
41 #include "tree-inline.h"
44 #include "tree-alias-common.h"
46 #include "tree-dump.h"
47 #include "tree-pass.h"
50 /* Remove edge E and remove the corresponding arguments from the PHI nodes
51 in E's destination block. */
54 ssa_remove_edge (edge e
)
58 /* Remove the appropriate PHI arguments in E's destination block. */
59 for (phi
= phi_nodes (e
->dest
); phi
; phi
= next
)
61 next
= PHI_CHAIN (phi
);
62 remove_phi_arg (phi
, e
->src
);
68 /* Remove the corresponding arguments from the PHI nodes in E's
69 destination block and redirect it to DEST. Return redirected edge.
70 The list of removed arguments is stored in PENDING_STMT (e). */
73 ssa_redirect_edge (edge e
, basic_block dest
)
76 tree list
= NULL
, *last
= &list
;
80 /* Remove the appropriate PHI arguments in E's destination block. */
81 for (phi
= phi_nodes (e
->dest
); phi
; phi
= next
)
83 next
= PHI_CHAIN (phi
);
85 i
= phi_arg_from_edge (phi
, e
);
89 src
= PHI_ARG_DEF (phi
, i
);
90 dst
= PHI_RESULT (phi
);
91 node
= build_tree_list (dst
, src
);
93 last
= &TREE_CHAIN (node
);
95 remove_phi_arg_num (phi
, i
);
98 e
= redirect_edge_succ_nodup (e
, dest
);
99 PENDING_STMT (e
) = list
;
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 debug_generic_stmt (SSA_NAME_DEF_STMT (ssa_name
));
182 fprintf (stderr
, "\nActual definition statement:\n");
183 debug_generic_stmt (stmt
);
190 fprintf (stderr
, "while verifying SSA_NAME ");
191 print_generic_expr (stderr
, ssa_name
, 0);
192 fprintf (stderr
, " in statement\n");
193 debug_generic_stmt (stmt
);
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
214 verify_use (basic_block bb
, basic_block def_bb
, tree ssa_name
,
215 tree stmt
, bool check_abnormal
, bool is_virtual
)
219 err
= verify_ssa_name (ssa_name
, is_virtual
);
221 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name
))
222 && var_ann (SSA_NAME_VAR (ssa_name
))->default_def
== ssa_name
)
223 ; /* Default definitions have empty statements. Nothing to do. */
226 error ("Missing definition");
229 else if (bb
!= def_bb
230 && !dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
232 error ("Definition in block %i does not dominate use in block %i",
233 def_bb
->index
, bb
->index
);
238 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name
))
240 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
246 fprintf (stderr
, "for SSA_NAME: ");
247 debug_generic_expr (ssa_name
);
248 fprintf (stderr
, "in statement:\n");
249 debug_generic_stmt (stmt
);
256 /* Return true if any of the arguments for PHI node PHI at block BB is
259 IDOM contains immediate dominator information for the flowgraph.
261 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
262 numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
263 block in that array slot contains the definition of SSA_NAME. */
266 verify_phi_args (tree phi
, basic_block bb
, basic_block
*definition_block
)
270 int i
, phi_num_args
= PHI_NUM_ARGS (phi
);
272 /* Mark all the incoming edges. */
273 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
276 for (i
= 0; i
< phi_num_args
; i
++)
278 tree op
= PHI_ARG_DEF (phi
, i
);
280 e
= PHI_ARG_EDGE (phi
, i
);
282 if (TREE_CODE (op
) == SSA_NAME
)
283 err
= verify_use (e
->src
, definition_block
[SSA_NAME_VERSION (op
)], op
,
284 phi
, e
->flags
& EDGE_ABNORMAL
,
285 !is_gimple_reg (PHI_RESULT (phi
)));
289 error ("Wrong edge %d->%d for PHI argument\n",
290 e
->src
->index
, e
->dest
->index
, bb
->index
);
294 if (e
->aux
== (void *) 0)
296 error ("PHI argument flowing through dead edge %d->%d\n",
297 e
->src
->index
, e
->dest
->index
);
301 if (e
->aux
== (void *) 2)
303 error ("PHI argument duplicated for edge %d->%d\n", e
->src
->index
,
310 fprintf (stderr
, "PHI argument\n");
311 debug_generic_stmt (op
);
318 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
320 if (e
->aux
!= (void *) 2)
322 error ("No argument flowing through edge %d->%d\n", e
->src
->index
,
333 fprintf (stderr
, "for PHI node\n");
334 debug_generic_stmt (phi
);
343 verify_flow_insensitive_alias_info (void)
347 bitmap visited
= BITMAP_XMALLOC ();
349 for (i
= 0; i
< num_referenced_vars
; i
++)
353 var
= referenced_var (i
);
356 if (ann
->mem_tag_kind
== TYPE_TAG
|| ann
->mem_tag_kind
== NAME_TAG
)
359 varray_type may_aliases
= ann
->may_aliases
;
361 for (j
= 0; may_aliases
&& j
< VARRAY_ACTIVE_SIZE (may_aliases
); j
++)
363 tree alias
= VARRAY_TREE (may_aliases
, j
);
365 bitmap_set_bit (visited
, var_ann (alias
)->uid
);
367 if (!may_be_aliased (alias
))
369 error ("Non-addressable variable inside an alias set.");
370 debug_variable (alias
);
377 for (i
= 0; i
< num_referenced_vars
; i
++)
381 var
= referenced_var (i
);
384 if (ann
->mem_tag_kind
== NOT_A_TAG
386 && !bitmap_bit_p (visited
, ann
->uid
))
388 error ("Addressable variable that is an alias tag but is not in any alias set.");
393 BITMAP_XFREE (visited
);
397 debug_variable (var
);
398 internal_error ("verify_flow_insensitive_alias_info failed.");
403 verify_flow_sensitive_alias_info (void)
408 for (i
= 1; i
< num_ssa_names
; i
++)
411 struct ptr_info_def
*pi
;
414 ann
= var_ann (SSA_NAME_VAR (ptr
));
415 pi
= SSA_NAME_PTR_INFO (ptr
);
417 /* We only care for pointers that are actually referenced in the
419 if (!TREE_VISITED (ptr
) || !POINTER_TYPE_P (TREE_TYPE (ptr
)))
422 /* RESULT_DECL is special. If it's a GIMPLE register, then it
423 is only written-to only once in the return statement.
424 Otherwise, aggregate RESULT_DECLs may be written-to more than
425 once in virtual operands. */
426 if (TREE_CODE (SSA_NAME_VAR (ptr
)) == RESULT_DECL
427 && is_gimple_reg (ptr
))
433 if (pi
->is_dereferenced
&& !pi
->name_mem_tag
&& !ann
->type_mem_tag
)
435 error ("Dereferenced pointers should have a name or a type tag");
439 if (pi
->pt_anything
&& (pi
->pt_malloc
|| pi
->pt_vars
))
441 error ("Pointers that point to anything should not point to malloc or other vars");
445 if (pi
->pt_malloc
&& pi
->pt_vars
)
447 error ("Pointers pointing to malloc get a unique tag and cannot point to other vars");
453 && (pi
->pt_vars
== NULL
454 || bitmap_first_set_bit (pi
->pt_vars
) < 0))
456 error ("Pointers with a memory tag, should have points-to sets or point to malloc");
460 if (pi
->value_escapes_p
462 && !is_call_clobbered (pi
->name_mem_tag
))
464 error ("Pointer escapes but its name tag is not call-clobbered.");
468 if (pi
->name_mem_tag
&& pi
->pt_vars
)
472 for (j
= i
+ 1; j
< num_ssa_names
; j
++)
474 tree ptr2
= ssa_name (j
);
475 struct ptr_info_def
*pi2
= SSA_NAME_PTR_INFO (ptr2
);
477 if (!POINTER_TYPE_P (TREE_TYPE (ptr2
)))
483 && bitmap_first_set_bit (pi2
->pt_vars
) >= 0
484 && pi
->name_mem_tag
!= pi2
->name_mem_tag
485 && bitmap_equal_p (pi
->pt_vars
, pi2
->pt_vars
))
487 error ("Two pointers with different name tags and identical points-to sets");
488 debug_variable (ptr2
);
498 debug_variable (ptr
);
499 internal_error ("verify_flow_sensitive_alias_info failed.");
503 /* Verify the consistency of aliasing information. */
506 verify_alias_info (void)
508 verify_flow_sensitive_alias_info ();
509 verify_flow_insensitive_alias_info ();
513 /* Verify common invariants in the SSA web.
514 TODO: verify the variable annotations. */
521 basic_block
*definition_block
= xcalloc (num_ssa_names
, sizeof (basic_block
));
523 timevar_push (TV_TREE_SSA_VERIFY
);
525 /* Keep track of SSA names present in the IL. */
526 for (i
= 1; i
< num_ssa_names
; i
++)
527 TREE_VISITED (ssa_name (i
)) = 0;
529 calculate_dominance_info (CDI_DOMINATORS
);
531 /* Verify and register all the SSA_NAME definitions found in the
536 block_stmt_iterator bsi
;
538 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
539 if (verify_def (bb
, definition_block
, PHI_RESULT (phi
), phi
,
540 !is_gimple_reg (PHI_RESULT (phi
))))
543 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
548 v_may_def_optype v_may_defs
;
549 v_must_def_optype v_must_defs
;
552 stmt
= bsi_stmt (bsi
);
553 ann
= stmt_ann (stmt
);
554 get_stmt_operands (stmt
);
556 v_may_defs
= V_MAY_DEF_OPS (ann
);
557 if (ann
->makes_aliased_stores
&& NUM_V_MAY_DEFS (v_may_defs
) == 0)
559 error ("Statement makes aliased stores, but has no V_MAY_DEFS");
560 debug_generic_stmt (stmt
);
564 for (j
= 0; j
< NUM_V_MAY_DEFS (v_may_defs
); j
++)
566 tree op
= V_MAY_DEF_RESULT (v_may_defs
, j
);
567 if (verify_def (bb
, definition_block
, op
, stmt
, true))
571 v_must_defs
= STMT_V_MUST_DEF_OPS (stmt
);
572 for (j
= 0; j
< NUM_V_MUST_DEFS (v_must_defs
); j
++)
574 tree op
= V_MUST_DEF_OP (v_must_defs
, j
);
575 if (verify_def (bb
, definition_block
, op
, stmt
, true))
579 defs
= DEF_OPS (ann
);
580 for (j
= 0; j
< NUM_DEFS (defs
); j
++)
582 tree op
= DEF_OP (defs
, j
);
583 if (verify_def (bb
, definition_block
, op
, stmt
, false))
590 /* Now verify all the uses and make sure they agree with the definitions
591 found in the previous pass. */
596 block_stmt_iterator bsi
;
598 /* Make sure that all edges have a clear 'aux' field. */
599 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
603 error ("AUX pointer initialized for edge %d->%d\n", e
->src
->index
,
609 /* Verify the arguments for every PHI node in the block. */
610 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
611 if (verify_phi_args (phi
, bb
, definition_block
))
614 /* Now verify all the uses and vuses in every statement of the block. */
615 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
617 tree stmt
= bsi_stmt (bsi
);
618 stmt_ann_t ann
= stmt_ann (stmt
);
621 v_may_def_optype v_may_defs
;
624 vuses
= VUSE_OPS (ann
);
625 for (j
= 0; j
< NUM_VUSES (vuses
); j
++)
627 tree op
= VUSE_OP (vuses
, j
);
628 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
629 op
, stmt
, false, true))
633 v_may_defs
= V_MAY_DEF_OPS (ann
);
634 for (j
= 0; j
< NUM_V_MAY_DEFS (v_may_defs
); j
++)
636 tree op
= V_MAY_DEF_OP (v_may_defs
, j
);
637 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
638 op
, stmt
, false, true))
642 uses
= USE_OPS (ann
);
643 for (j
= 0; j
< NUM_USES (uses
); j
++)
645 tree op
= USE_OP (uses
, j
);
646 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
647 op
, stmt
, false, false))
653 /* Finally, verify alias information. */
654 verify_alias_info ();
656 free (definition_block
);
657 timevar_pop (TV_TREE_SSA_VERIFY
);
661 internal_error ("verify_ssa failed.");
665 /* Initialize global DFA and SSA structures. */
670 VARRAY_TREE_INIT (referenced_vars
, 20, "referenced_vars");
671 call_clobbered_vars
= BITMAP_XMALLOC ();
672 addressable_vars
= BITMAP_XMALLOC ();
673 init_ssa_operands ();
676 global_var
= NULL_TREE
;
680 /* Deallocate memory associated with SSA data structures for FNDECL. */
683 delete_tree_ssa (void)
687 block_stmt_iterator bsi
;
689 /* Remove annotations from every tree in the function. */
691 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
692 bsi_stmt (bsi
)->common
.ann
= NULL
;
694 /* Remove annotations from every referenced variable. */
697 for (i
= 0; i
< num_referenced_vars
; i
++)
698 referenced_var (i
)->common
.ann
= NULL
;
699 referenced_vars
= NULL
;
704 fini_ssa_operands ();
706 global_var
= NULL_TREE
;
707 BITMAP_XFREE (call_clobbered_vars
);
708 call_clobbered_vars
= NULL
;
709 BITMAP_XFREE (addressable_vars
);
710 addressable_vars
= NULL
;
714 /* Return true if EXPR is a useless type conversion, otherwise return
718 tree_ssa_useless_type_conversion_1 (tree outer_type
, tree inner_type
)
720 /* If the inner and outer types are effectively the same, then
721 strip the type conversion and enter the equivalence into
723 if (inner_type
== outer_type
724 || (lang_hooks
.types_compatible_p (inner_type
, outer_type
)))
727 /* If both types are pointers and the outer type is a (void *), then
728 the conversion is not necessary. The opposite is not true since
729 that conversion would result in a loss of information if the
730 equivalence was used. Consider an indirect function call where
731 we need to know the exact type of the function to correctly
732 implement the ABI. */
733 else if (POINTER_TYPE_P (inner_type
)
734 && POINTER_TYPE_P (outer_type
)
735 && TREE_CODE (TREE_TYPE (outer_type
)) == VOID_TYPE
)
738 /* Pointers and references are equivalent once we get to GENERIC,
739 so strip conversions that just switch between them. */
740 else if (POINTER_TYPE_P (inner_type
)
741 && POINTER_TYPE_P (outer_type
)
742 && lang_hooks
.types_compatible_p (TREE_TYPE (inner_type
),
743 TREE_TYPE (outer_type
)))
746 /* If both the inner and outer types are integral types, then the
747 conversion is not necessary if they have the same mode and
748 signedness and precision, and both or neither are boolean. Some
749 code assumes an invariant that boolean types stay boolean and do
750 not become 1-bit bit-field types. Note that types with precision
751 not using all bits of the mode (such as bit-field types in C)
752 mean that testing of precision is necessary. */
753 else if (INTEGRAL_TYPE_P (inner_type
)
754 && INTEGRAL_TYPE_P (outer_type
)
755 && TYPE_MODE (inner_type
) == TYPE_MODE (outer_type
)
756 && TYPE_UNSIGNED (inner_type
) == TYPE_UNSIGNED (outer_type
)
757 && TYPE_PRECISION (inner_type
) == TYPE_PRECISION (outer_type
))
759 bool first_boolean
= (TREE_CODE (inner_type
) == BOOLEAN_TYPE
);
760 bool second_boolean
= (TREE_CODE (outer_type
) == BOOLEAN_TYPE
);
761 if (first_boolean
== second_boolean
)
765 /* Recurse for complex types. */
766 else if (TREE_CODE (inner_type
) == COMPLEX_TYPE
767 && TREE_CODE (outer_type
) == COMPLEX_TYPE
768 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type
),
769 TREE_TYPE (inner_type
)))
775 /* Return true if EXPR is a useless type conversion, otherwise return
779 tree_ssa_useless_type_conversion (tree expr
)
781 /* If we have an assignment that merely uses a NOP_EXPR to change
782 the top of the RHS to the type of the LHS and the type conversion
783 is "safe", then strip away the type conversion so that we can
784 enter LHS = RHS into the const_and_copies table. */
785 if (TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
786 || TREE_CODE (expr
) == VIEW_CONVERT_EXPR
787 || TREE_CODE (expr
) == NON_LVALUE_EXPR
)
788 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr
),
789 TREE_TYPE (TREE_OPERAND (expr
,
797 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
798 described in walk_use_def_chains.
800 VISITED is a bitmap used to mark visited SSA_NAMEs to avoid
803 IS_DFS is true if the caller wants to perform a depth-first search
804 when visiting PHI nodes. A DFS will visit each PHI argument and
805 call FN after each one. Otherwise, all the arguments are
806 visited first and then FN is called with each of the visited
807 arguments in a separate pass. */
810 walk_use_def_chains_1 (tree var
, walk_use_def_chains_fn fn
, void *data
,
811 bitmap visited
, bool is_dfs
)
815 if (bitmap_bit_p (visited
, SSA_NAME_VERSION (var
)))
818 bitmap_set_bit (visited
, SSA_NAME_VERSION (var
));
820 def_stmt
= SSA_NAME_DEF_STMT (var
);
822 if (TREE_CODE (def_stmt
) != PHI_NODE
)
824 /* If we reached the end of the use-def chain, call FN. */
825 return fn (var
, def_stmt
, data
);
831 /* When doing a breadth-first search, call FN before following the
832 use-def links for each argument. */
834 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
835 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
838 /* Follow use-def links out of each PHI argument. */
839 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
841 tree arg
= PHI_ARG_DEF (def_stmt
, i
);
842 if (TREE_CODE (arg
) == SSA_NAME
843 && walk_use_def_chains_1 (arg
, fn
, data
, visited
, is_dfs
))
847 /* When doing a depth-first search, call FN after following the
848 use-def links for each argument. */
850 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
851 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
860 /* Walk use-def chains starting at the SSA variable VAR. Call
861 function FN at each reaching definition found. FN takes three
862 arguments: VAR, its defining statement (DEF_STMT) and a generic
863 pointer to whatever state information that FN may want to maintain
864 (DATA). FN is able to stop the walk by returning true, otherwise
865 in order to continue the walk, FN should return false.
867 Note, that if DEF_STMT is a PHI node, the semantics are slightly
868 different. The first argument to FN is no longer the original
869 variable VAR, but the PHI argument currently being examined. If FN
870 wants to get at VAR, it should call PHI_RESULT (PHI).
872 If IS_DFS is true, this function will:
874 1- walk the use-def chains for all the PHI arguments, and,
875 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
877 If IS_DFS is false, the two steps above are done in reverse order
878 (i.e., a breadth-first search). */
882 walk_use_def_chains (tree var
, walk_use_def_chains_fn fn
, void *data
,
887 #if defined ENABLE_CHECKING
888 if (TREE_CODE (var
) != SSA_NAME
)
892 def_stmt
= SSA_NAME_DEF_STMT (var
);
894 /* We only need to recurse if the reaching definition comes from a PHI
896 if (TREE_CODE (def_stmt
) != PHI_NODE
)
897 (*fn
) (var
, def_stmt
, data
);
900 bitmap visited
= BITMAP_XMALLOC ();
901 walk_use_def_chains_1 (var
, fn
, data
, visited
, is_dfs
);
902 BITMAP_XFREE (visited
);
907 /* Replaces VAR with REPL in memory reference expression *X in
911 propagate_into_addr (tree stmt
, tree var
, tree
*x
, tree repl
)
913 tree new_var
, ass_stmt
, addr_var
;
915 block_stmt_iterator bsi
;
917 /* There is nothing special to handle in the other cases. */
918 if (TREE_CODE (repl
) != ADDR_EXPR
)
920 addr_var
= TREE_OPERAND (repl
, 0);
922 while (TREE_CODE (*x
) == ARRAY_REF
923 || TREE_CODE (*x
) == COMPONENT_REF
924 || TREE_CODE (*x
) == BIT_FIELD_REF
)
925 x
= &TREE_OPERAND (*x
, 0);
927 if (TREE_CODE (*x
) != INDIRECT_REF
928 || TREE_OPERAND (*x
, 0) != var
)
932 if (TREE_TYPE (*x
) == TREE_TYPE (addr_var
))
935 mark_new_vars_to_rename (stmt
, vars_to_rename
);
939 /* Frontends sometimes produce expressions like *&a instead of a[0].
940 Create a temporary variable to handle this case. */
941 ass_stmt
= build2 (MODIFY_EXPR
, void_type_node
, NULL_TREE
, repl
);
942 new_var
= duplicate_ssa_name (var
, ass_stmt
);
943 TREE_OPERAND (*x
, 0) = new_var
;
944 TREE_OPERAND (ass_stmt
, 0) = new_var
;
946 bb
= bb_for_stmt (stmt
);
947 tree_block_label (bb
);
948 bsi
= bsi_after_labels (bb
);
949 bsi_insert_after (&bsi
, ass_stmt
, BSI_NEW_STMT
);
951 mark_new_vars_to_rename (stmt
, vars_to_rename
);
954 /* Replaces immediate uses of VAR by REPL. */
957 replace_immediate_uses (tree var
, tree repl
)
961 v_may_def_optype v_may_defs
;
968 df
= get_immediate_uses (SSA_NAME_DEF_STMT (var
));
969 n
= num_immediate_uses (df
);
971 for (i
= 0; i
< n
; i
++)
973 stmt
= immediate_use (df
, i
);
974 ann
= stmt_ann (stmt
);
976 if (TREE_CODE (stmt
) == PHI_NODE
)
978 for (j
= 0; j
< PHI_NUM_ARGS (stmt
); j
++)
979 if (PHI_ARG_DEF (stmt
, j
) == var
)
981 SET_PHI_ARG_DEF (stmt
, j
, repl
);
982 if (TREE_CODE (repl
) == SSA_NAME
983 && PHI_ARG_EDGE (stmt
, j
)->flags
& EDGE_ABNORMAL
)
984 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl
) = 1;
990 get_stmt_operands (stmt
);
991 mark_new_vars
= false;
992 if (is_gimple_reg (SSA_NAME_VAR (var
)))
994 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
996 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 0), repl
);
997 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 1), repl
);
1000 uses
= USE_OPS (ann
);
1001 for (j
= 0; j
< (int) NUM_USES (uses
); j
++)
1002 if (USE_OP (uses
, j
) == var
)
1004 propagate_value (USE_OP_PTR (uses
, j
), repl
);
1005 mark_new_vars
= POINTER_TYPE_P (TREE_TYPE (repl
));
1010 vuses
= VUSE_OPS (ann
);
1011 for (j
= 0; j
< (int) NUM_VUSES (vuses
); j
++)
1012 if (VUSE_OP (vuses
, j
) == var
)
1013 propagate_value (VUSE_OP_PTR (vuses
, j
), repl
);
1015 v_may_defs
= V_MAY_DEF_OPS (ann
);
1016 for (j
= 0; j
< (int) NUM_V_MAY_DEFS (v_may_defs
); j
++)
1017 if (V_MAY_DEF_OP (v_may_defs
, j
) == var
)
1018 propagate_value (V_MAY_DEF_OP_PTR (v_may_defs
, j
), repl
);
1021 /* If REPL is a pointer, it may have different memory tags associated
1022 with it. For instance, VAR may have had a name tag while REPL
1023 only had a type tag. In these cases, the virtual operands (if
1024 any) in the statement will refer to different symbols which need
1027 mark_new_vars_to_rename (stmt
, vars_to_rename
);
1033 /* Gets the value VAR is equivalent to according to EQ_TO. */
1036 get_eq_name (tree
*eq_to
, tree var
)
1041 while (TREE_CODE (val
) == SSA_NAME
)
1043 ver
= SSA_NAME_VERSION (val
);
1050 while (TREE_CODE (var
) == SSA_NAME
)
1052 ver
= SSA_NAME_VERSION (var
);
1063 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1064 its result is redundant to to EQ_TO array. */
1067 check_phi_redundancy (tree phi
, tree
*eq_to
)
1069 tree val
= NULL_TREE
, def
, res
= PHI_RESULT (phi
), stmt
;
1070 unsigned i
, ver
= SSA_NAME_VERSION (res
), n
;
1073 /* It is unlikely that such large phi node would be redundant. */
1074 if (PHI_NUM_ARGS (phi
) > 16)
1077 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (phi
); i
++)
1079 def
= PHI_ARG_DEF (phi
, i
);
1081 if (TREE_CODE (def
) == SSA_NAME
)
1083 def
= get_eq_name (eq_to
, def
);
1089 && !operand_equal_p (val
, def
, 0))
1095 /* At least one of the arguments should not be equal to the result, or
1096 something strange is happening. */
1100 if (get_eq_name (eq_to
, res
) == val
)
1103 if (!may_propagate_copy (res
, val
))
1108 df
= get_immediate_uses (SSA_NAME_DEF_STMT (res
));
1109 n
= num_immediate_uses (df
);
1111 for (i
= 0; i
< n
; i
++)
1113 stmt
= immediate_use (df
, i
);
1115 if (TREE_CODE (stmt
) == PHI_NODE
)
1116 check_phi_redundancy (stmt
, eq_to
);
1120 /* Removes redundant phi nodes.
1122 A redundant PHI node is a PHI node where all of its PHI arguments
1123 are the same value, excluding any PHI arguments which are the same
1126 A redundant PHI node is effectively a copy, so we forward copy propagate
1127 which removes all uses of the destination of the PHI node then
1128 finally we delete the redundant PHI node.
1130 Note that if we can not copy propagate the PHI node, then the PHI
1131 will not be removed. Thus we do not have to worry about dependencies
1132 between PHIs and the problems serializing PHIs into copies creates.
1134 The most important effect of this pass is to remove degenerate PHI
1135 nodes created by removing unreachable code. */
1138 kill_redundant_phi_nodes (void)
1141 unsigned i
, old_num_ssa_names
;
1143 tree phi
, var
, repl
, stmt
;
1145 /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1146 replaced. If EQ_TO[VER] is ssa name and it is decided to replace it by
1147 other value, it may be necessary to follow the chain till the final value.
1148 We perform path shortening (replacing the entries of the EQ_TO array with
1149 heads of these chains) whenever we access the field to prevent quadratic
1150 complexity (probably would not occur in practice anyway, but let us play
1152 eq_to
= xcalloc (num_ssa_names
, sizeof (tree
));
1154 /* We have had cases where computing immediate uses takes a
1155 significant amount of compile time. If we run into such
1156 problems here, we may want to only compute immediate uses for
1157 a subset of all the SSA_NAMEs instead of computing it for
1158 all of the SSA_NAMEs. */
1159 compute_immediate_uses (TDFA_USE_OPS
| TDFA_USE_VOPS
, NULL
);
1160 old_num_ssa_names
= num_ssa_names
;
1164 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
1166 var
= PHI_RESULT (phi
);
1167 check_phi_redundancy (phi
, eq_to
);
1171 /* Now propagate the values. */
1172 for (i
= 0; i
< old_num_ssa_names
; i
++)
1177 repl
= get_eq_name (eq_to
, ssa_name (i
));
1178 if (repl
!= ssa_name (i
))
1179 replace_immediate_uses (ssa_name (i
), repl
);
1182 /* And remove the dead phis. */
1183 for (i
= 0; i
< old_num_ssa_names
; i
++)
1188 repl
= get_eq_name (eq_to
, ssa_name (i
));
1189 if (repl
!= ssa_name (i
))
1191 stmt
= SSA_NAME_DEF_STMT (ssa_name (i
));
1192 remove_phi_node (stmt
, NULL_TREE
, bb_for_stmt (stmt
));
1200 struct tree_opt_pass pass_redundant_phi
=
1202 "redphi", /* name */
1204 kill_redundant_phi_nodes
, /* execute */
1207 0, /* static_pass_number */
1209 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
1210 0, /* properties_provided */
1211 0, /* properties_destroyed */
1212 0, /* todo_flags_start */
1213 TODO_dump_func
| TODO_rename_vars
1214 | TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */
1217 /* Emit warnings for uninitialized variables. This is done in two passes.
1219 The first pass notices real uses of SSA names with default definitions.
1220 Such uses are unconditionally uninitialized, and we can be certain that
1221 such a use is a mistake. This pass is run before most optimizations,
1222 so that we catch as many as we can.
1224 The second pass follows PHI nodes to find uses that are potentially
1225 uninitialized. In this case we can't necessarily prove that the use
1226 is really uninitialized. This pass is run after most optimizations,
1227 so that we thread as many jumps and possible, and delete as much dead
1228 code as possible, in order to reduce false positives. We also look
1229 again for plain uninitialized variables, since optimization may have
1230 changed conditionally uninitialized to unconditionally uninitialized. */
1232 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1233 warning text is in MSGID and LOCUS may contain a location or be null. */
1236 warn_uninit (tree t
, const char *msgid
, location_t
*locus
)
1238 tree var
= SSA_NAME_VAR (t
);
1239 tree def
= SSA_NAME_DEF_STMT (t
);
1241 /* Default uses (indicated by an empty definition statement),
1242 are uninitialized. */
1243 if (!IS_EMPTY_STMT (def
))
1246 /* Except for PARMs of course, which are always initialized. */
1247 if (TREE_CODE (var
) == PARM_DECL
)
1250 /* Hard register variables get their initial value from the ether. */
1251 if (DECL_HARD_REGISTER (var
))
1254 /* TREE_NO_WARNING either means we already warned, or the front end
1255 wishes to suppress the warning. */
1256 if (TREE_NO_WARNING (var
))
1260 locus
= &DECL_SOURCE_LOCATION (var
);
1261 warning (msgid
, locus
, var
);
1262 TREE_NO_WARNING (var
) = 1;
1265 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1266 and warn about them. */
1269 warn_uninitialized_var (tree
*tp
, int *walk_subtrees
, void *data
)
1271 location_t
*locus
= data
;
1274 /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */
1275 if (TREE_CODE (t
) == SSA_NAME
)
1277 warn_uninit (t
, "%H'%D' is used uninitialized in this function", locus
);
1280 else if (DECL_P (t
) || TYPE_P (t
))
1286 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1287 and warn about them. */
1290 warn_uninitialized_phi (tree phi
)
1292 int i
, n
= PHI_NUM_ARGS (phi
);
1294 /* Don't look at memory tags. */
1295 if (!is_gimple_reg (PHI_RESULT (phi
)))
1298 for (i
= 0; i
< n
; ++i
)
1300 tree op
= PHI_ARG_DEF (phi
, i
);
1301 if (TREE_CODE (op
) == SSA_NAME
)
1302 warn_uninit (op
, "%H'%D' may be used uninitialized in this function",
1308 execute_early_warn_uninitialized (void)
1310 block_stmt_iterator bsi
;
1314 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1315 walk_tree (bsi_stmt_ptr (bsi
), warn_uninitialized_var
,
1316 EXPR_LOCUS (bsi_stmt (bsi
)), NULL
);
1320 execute_late_warn_uninitialized (void)
1325 /* Re-do the plain uninitialized variable check, as optimization may have
1326 straightened control flow. Do this first so that we don't accidentally
1327 get a "may be" warning when we'd have seen an "is" warning later. */
1328 execute_early_warn_uninitialized ();
1331 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1332 warn_uninitialized_phi (phi
);
1336 gate_warn_uninitialized (void)
1338 return warn_uninitialized
!= 0;
1341 struct tree_opt_pass pass_early_warn_uninitialized
=
1344 gate_warn_uninitialized
, /* gate */
1345 execute_early_warn_uninitialized
, /* execute */
1348 0, /* static_pass_number */
1350 PROP_ssa
, /* properties_required */
1351 0, /* properties_provided */
1352 0, /* properties_destroyed */
1353 0, /* todo_flags_start */
1354 0 /* todo_flags_finish */
1357 struct tree_opt_pass pass_late_warn_uninitialized
=
1360 gate_warn_uninitialized
, /* gate */
1361 execute_late_warn_uninitialized
, /* execute */
1364 0, /* static_pass_number */
1366 PROP_ssa
, /* properties_required */
1367 0, /* properties_provided */
1368 0, /* properties_destroyed */
1369 0, /* todo_flags_start */
1370 0 /* todo_flags_finish */