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 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
;
411 ann
= var_ann (SSA_NAME_VAR (ptr
));
412 pi
= SSA_NAME_PTR_INFO (ptr
);
414 /* We only care for pointers that are actually referenced in the
416 if (!TREE_VISITED (ptr
) || !POINTER_TYPE_P (TREE_TYPE (ptr
)))
419 /* RESULT_DECL is special. If it's a GIMPLE register, then it
420 is only written-to only once in the return statement.
421 Otherwise, aggregate RESULT_DECLs may be written-to more than
422 once in virtual operands. */
423 if (TREE_CODE (SSA_NAME_VAR (ptr
)) == RESULT_DECL
424 && is_gimple_reg (ptr
))
430 if (pi
->is_dereferenced
&& !pi
->name_mem_tag
&& !ann
->type_mem_tag
)
432 error ("Dereferenced pointers should have a name or a type tag");
438 && (pi
->pt_vars
== NULL
439 || bitmap_first_set_bit (pi
->pt_vars
) < 0))
441 error ("Pointers with a memory tag, should have points-to sets or point to malloc");
445 if (pi
->value_escapes_p
447 && !is_call_clobbered (pi
->name_mem_tag
))
449 error ("Pointer escapes but its name tag is not call-clobbered.");
453 if (pi
->name_mem_tag
&& pi
->pt_vars
)
457 for (j
= i
+ 1; j
< num_ssa_names
; j
++)
459 tree ptr2
= ssa_name (j
);
460 struct ptr_info_def
*pi2
= SSA_NAME_PTR_INFO (ptr2
);
462 if (!TREE_VISITED (ptr2
) || !POINTER_TYPE_P (TREE_TYPE (ptr2
)))
468 && bitmap_first_set_bit (pi2
->pt_vars
) >= 0
469 && pi
->name_mem_tag
!= pi2
->name_mem_tag
470 && bitmap_equal_p (pi
->pt_vars
, pi2
->pt_vars
))
472 error ("Two pointers with different name tags and identical points-to sets");
473 debug_variable (ptr2
);
483 debug_variable (ptr
);
484 internal_error ("verify_flow_sensitive_alias_info failed.");
488 /* Verify the consistency of aliasing information. */
491 verify_alias_info (void)
493 verify_flow_sensitive_alias_info ();
494 verify_flow_insensitive_alias_info ();
498 /* Verify common invariants in the SSA web.
499 TODO: verify the variable annotations. */
506 basic_block
*definition_block
= xcalloc (num_ssa_names
, sizeof (basic_block
));
510 timevar_push (TV_TREE_SSA_VERIFY
);
512 /* Keep track of SSA names present in the IL. */
513 for (i
= 1; i
< num_ssa_names
; i
++)
514 TREE_VISITED (ssa_name (i
)) = 0;
516 calculate_dominance_info (CDI_DOMINATORS
);
518 /* Verify and register all the SSA_NAME definitions found in the
523 block_stmt_iterator bsi
;
525 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
526 if (verify_def (bb
, definition_block
, PHI_RESULT (phi
), phi
,
527 !is_gimple_reg (PHI_RESULT (phi
))))
530 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
534 stmt
= bsi_stmt (bsi
);
535 get_stmt_operands (stmt
);
537 if (stmt_ann (stmt
)->makes_aliased_stores
538 && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt
)) == 0)
540 error ("Statement makes aliased stores, but has no V_MAY_DEFS");
541 debug_generic_stmt (stmt
);
545 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
547 if (verify_def (bb
, definition_block
, op
, stmt
, true))
551 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
553 if (verify_def (bb
, definition_block
, op
, stmt
, false))
560 /* Now verify all the uses and make sure they agree with the definitions
561 found in the previous pass. */
566 block_stmt_iterator bsi
;
568 /* Make sure that all edges have a clear 'aux' field. */
569 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
573 error ("AUX pointer initialized for edge %d->%d\n", e
->src
->index
,
579 /* Verify the arguments for every PHI node in the block. */
580 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
581 if (verify_phi_args (phi
, bb
, definition_block
))
584 /* Now verify all the uses and vuses in every statement of the block. */
585 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
587 tree stmt
= bsi_stmt (bsi
);
589 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
591 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
592 op
, stmt
, false, true))
596 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
598 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
599 op
, stmt
, false, false))
605 /* Finally, verify alias information. */
606 verify_alias_info ();
608 free (definition_block
);
609 timevar_pop (TV_TREE_SSA_VERIFY
);
613 internal_error ("verify_ssa failed.");
617 /* Initialize global DFA and SSA structures. */
622 VARRAY_TREE_INIT (referenced_vars
, 20, "referenced_vars");
623 call_clobbered_vars
= BITMAP_XMALLOC ();
624 addressable_vars
= BITMAP_XMALLOC ();
625 init_ssa_operands ();
628 global_var
= NULL_TREE
;
632 /* Deallocate memory associated with SSA data structures for FNDECL. */
635 delete_tree_ssa (void)
639 block_stmt_iterator bsi
;
641 /* Remove annotations from every tree in the function. */
643 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
645 tree stmt
= bsi_stmt (bsi
);
647 ggc_free (stmt
->common
.ann
);
648 stmt
->common
.ann
= NULL
;
651 /* Remove annotations from every referenced variable. */
654 for (i
= 0; i
< num_referenced_vars
; i
++)
656 tree var
= referenced_var (i
);
657 ggc_free (var
->common
.ann
);
658 var
->common
.ann
= NULL
;
660 referenced_vars
= NULL
;
665 fini_ssa_operands ();
667 global_var
= NULL_TREE
;
668 BITMAP_XFREE (call_clobbered_vars
);
669 call_clobbered_vars
= NULL
;
670 BITMAP_XFREE (addressable_vars
);
671 addressable_vars
= NULL
;
675 /* Return true if EXPR is a useless type conversion, otherwise return
679 tree_ssa_useless_type_conversion_1 (tree outer_type
, tree inner_type
)
681 /* If the inner and outer types are effectively the same, then
682 strip the type conversion and enter the equivalence into
684 if (inner_type
== outer_type
685 || (lang_hooks
.types_compatible_p (inner_type
, outer_type
)))
688 /* If both types are pointers and the outer type is a (void *), then
689 the conversion is not necessary. The opposite is not true since
690 that conversion would result in a loss of information if the
691 equivalence was used. Consider an indirect function call where
692 we need to know the exact type of the function to correctly
693 implement the ABI. */
694 else if (POINTER_TYPE_P (inner_type
)
695 && POINTER_TYPE_P (outer_type
)
696 && TREE_CODE (TREE_TYPE (outer_type
)) == VOID_TYPE
)
699 /* Pointers and references are equivalent once we get to GENERIC,
700 so strip conversions that just switch between them. */
701 else if (POINTER_TYPE_P (inner_type
)
702 && POINTER_TYPE_P (outer_type
)
703 && lang_hooks
.types_compatible_p (TREE_TYPE (inner_type
),
704 TREE_TYPE (outer_type
)))
707 /* If both the inner and outer types are integral types, then the
708 conversion is not necessary if they have the same mode and
709 signedness and precision, and both or neither are boolean. Some
710 code assumes an invariant that boolean types stay boolean and do
711 not become 1-bit bit-field types. Note that types with precision
712 not using all bits of the mode (such as bit-field types in C)
713 mean that testing of precision is necessary. */
714 else if (INTEGRAL_TYPE_P (inner_type
)
715 && INTEGRAL_TYPE_P (outer_type
)
716 && TYPE_MODE (inner_type
) == TYPE_MODE (outer_type
)
717 && TYPE_UNSIGNED (inner_type
) == TYPE_UNSIGNED (outer_type
)
718 && TYPE_PRECISION (inner_type
) == TYPE_PRECISION (outer_type
))
720 bool first_boolean
= (TREE_CODE (inner_type
) == BOOLEAN_TYPE
);
721 bool second_boolean
= (TREE_CODE (outer_type
) == BOOLEAN_TYPE
);
722 if (first_boolean
== second_boolean
)
726 /* Recurse for complex types. */
727 else if (TREE_CODE (inner_type
) == COMPLEX_TYPE
728 && TREE_CODE (outer_type
) == COMPLEX_TYPE
729 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type
),
730 TREE_TYPE (inner_type
)))
736 /* Return true if EXPR is a useless type conversion, otherwise return
740 tree_ssa_useless_type_conversion (tree expr
)
742 /* If we have an assignment that merely uses a NOP_EXPR to change
743 the top of the RHS to the type of the LHS and the type conversion
744 is "safe", then strip away the type conversion so that we can
745 enter LHS = RHS into the const_and_copies table. */
746 if (TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
747 || TREE_CODE (expr
) == VIEW_CONVERT_EXPR
748 || TREE_CODE (expr
) == NON_LVALUE_EXPR
)
749 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr
),
750 TREE_TYPE (TREE_OPERAND (expr
,
758 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
759 described in walk_use_def_chains.
761 VISITED is a bitmap used to mark visited SSA_NAMEs to avoid
764 IS_DFS is true if the caller wants to perform a depth-first search
765 when visiting PHI nodes. A DFS will visit each PHI argument and
766 call FN after each one. Otherwise, all the arguments are
767 visited first and then FN is called with each of the visited
768 arguments in a separate pass. */
771 walk_use_def_chains_1 (tree var
, walk_use_def_chains_fn fn
, void *data
,
772 bitmap visited
, bool is_dfs
)
776 if (bitmap_bit_p (visited
, SSA_NAME_VERSION (var
)))
779 bitmap_set_bit (visited
, SSA_NAME_VERSION (var
));
781 def_stmt
= SSA_NAME_DEF_STMT (var
);
783 if (TREE_CODE (def_stmt
) != PHI_NODE
)
785 /* If we reached the end of the use-def chain, call FN. */
786 return fn (var
, def_stmt
, data
);
792 /* When doing a breadth-first search, call FN before following the
793 use-def links for each argument. */
795 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
796 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
799 /* Follow use-def links out of each PHI argument. */
800 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
802 tree arg
= PHI_ARG_DEF (def_stmt
, i
);
803 if (TREE_CODE (arg
) == SSA_NAME
804 && walk_use_def_chains_1 (arg
, fn
, data
, visited
, is_dfs
))
808 /* When doing a depth-first search, call FN after following the
809 use-def links for each argument. */
811 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
812 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
821 /* Walk use-def chains starting at the SSA variable VAR. Call
822 function FN at each reaching definition found. FN takes three
823 arguments: VAR, its defining statement (DEF_STMT) and a generic
824 pointer to whatever state information that FN may want to maintain
825 (DATA). FN is able to stop the walk by returning true, otherwise
826 in order to continue the walk, FN should return false.
828 Note, that if DEF_STMT is a PHI node, the semantics are slightly
829 different. The first argument to FN is no longer the original
830 variable VAR, but the PHI argument currently being examined. If FN
831 wants to get at VAR, it should call PHI_RESULT (PHI).
833 If IS_DFS is true, this function will:
835 1- walk the use-def chains for all the PHI arguments, and,
836 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
838 If IS_DFS is false, the two steps above are done in reverse order
839 (i.e., a breadth-first search). */
843 walk_use_def_chains (tree var
, walk_use_def_chains_fn fn
, void *data
,
848 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
850 def_stmt
= SSA_NAME_DEF_STMT (var
);
852 /* We only need to recurse if the reaching definition comes from a PHI
854 if (TREE_CODE (def_stmt
) != PHI_NODE
)
855 (*fn
) (var
, def_stmt
, data
);
858 bitmap visited
= BITMAP_XMALLOC ();
859 walk_use_def_chains_1 (var
, fn
, data
, visited
, is_dfs
);
860 BITMAP_XFREE (visited
);
865 /* Replaces VAR with REPL in memory reference expression *X in
869 propagate_into_addr (tree stmt
, tree var
, tree
*x
, tree repl
)
871 tree new_var
, ass_stmt
, addr_var
;
873 block_stmt_iterator bsi
;
875 /* There is nothing special to handle in the other cases. */
876 if (TREE_CODE (repl
) != ADDR_EXPR
)
878 addr_var
= TREE_OPERAND (repl
, 0);
880 while (handled_component_p (*x
)
881 || TREE_CODE (*x
) == REALPART_EXPR
882 || TREE_CODE (*x
) == IMAGPART_EXPR
)
883 x
= &TREE_OPERAND (*x
, 0);
885 if (TREE_CODE (*x
) != INDIRECT_REF
886 || TREE_OPERAND (*x
, 0) != var
)
889 if (TREE_TYPE (*x
) == TREE_TYPE (addr_var
))
892 mark_new_vars_to_rename (stmt
, vars_to_rename
);
897 /* Frontends sometimes produce expressions like *&a instead of a[0].
898 Create a temporary variable to handle this case. */
899 ass_stmt
= build2 (MODIFY_EXPR
, void_type_node
, NULL_TREE
, repl
);
900 new_var
= duplicate_ssa_name (var
, ass_stmt
);
901 TREE_OPERAND (*x
, 0) = new_var
;
902 TREE_OPERAND (ass_stmt
, 0) = new_var
;
904 bb
= bb_for_stmt (stmt
);
905 tree_block_label (bb
);
906 bsi
= bsi_after_labels (bb
);
907 bsi_insert_after (&bsi
, ass_stmt
, BSI_NEW_STMT
);
909 mark_new_vars_to_rename (stmt
, vars_to_rename
);
912 /* Replaces immediate uses of VAR by REPL. */
915 replace_immediate_uses (tree var
, tree repl
)
925 df
= get_immediate_uses (SSA_NAME_DEF_STMT (var
));
926 n
= num_immediate_uses (df
);
928 for (i
= 0; i
< n
; i
++)
930 stmt
= immediate_use (df
, i
);
931 ann
= stmt_ann (stmt
);
933 if (TREE_CODE (stmt
) == PHI_NODE
)
935 for (j
= 0; j
< PHI_NUM_ARGS (stmt
); j
++)
936 if (PHI_ARG_DEF (stmt
, j
) == var
)
938 SET_PHI_ARG_DEF (stmt
, j
, repl
);
939 if (TREE_CODE (repl
) == SSA_NAME
940 && PHI_ARG_EDGE (stmt
, j
)->flags
& EDGE_ABNORMAL
)
941 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl
) = 1;
947 get_stmt_operands (stmt
);
948 mark_new_vars
= false;
949 if (is_gimple_reg (SSA_NAME_VAR (var
)))
951 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
953 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 0), repl
);
954 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 1), repl
);
957 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
958 if (USE_FROM_PTR (use_p
) == var
)
960 propagate_value (use_p
, repl
);
961 mark_new_vars
= POINTER_TYPE_P (TREE_TYPE (repl
));
966 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
967 if (USE_FROM_PTR (use_p
) == var
)
968 propagate_value (use_p
, repl
);
971 /* If REPL is a pointer, it may have different memory tags associated
972 with it. For instance, VAR may have had a name tag while REPL
973 only had a type tag. In these cases, the virtual operands (if
974 any) in the statement will refer to different symbols which need
977 mark_new_vars_to_rename (stmt
, vars_to_rename
);
983 /* Gets the value VAR is equivalent to according to EQ_TO. */
986 get_eq_name (tree
*eq_to
, tree var
)
991 while (TREE_CODE (val
) == SSA_NAME
)
993 ver
= SSA_NAME_VERSION (val
);
1000 while (TREE_CODE (var
) == SSA_NAME
)
1002 ver
= SSA_NAME_VERSION (var
);
1013 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1014 its result is redundant to to EQ_TO array. */
1017 check_phi_redundancy (tree phi
, tree
*eq_to
)
1019 tree val
= NULL_TREE
, def
, res
= PHI_RESULT (phi
), stmt
;
1020 unsigned i
, ver
= SSA_NAME_VERSION (res
), n
;
1023 /* It is unlikely that such large phi node would be redundant. */
1024 if (PHI_NUM_ARGS (phi
) > 16)
1027 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (phi
); i
++)
1029 def
= PHI_ARG_DEF (phi
, i
);
1031 if (TREE_CODE (def
) == SSA_NAME
)
1033 def
= get_eq_name (eq_to
, def
);
1039 && !operand_equal_p (val
, def
, 0))
1045 /* At least one of the arguments should not be equal to the result, or
1046 something strange is happening. */
1049 if (get_eq_name (eq_to
, res
) == val
)
1052 if (!may_propagate_copy (res
, val
))
1057 df
= get_immediate_uses (SSA_NAME_DEF_STMT (res
));
1058 n
= num_immediate_uses (df
);
1060 for (i
= 0; i
< n
; i
++)
1062 stmt
= immediate_use (df
, i
);
1064 if (TREE_CODE (stmt
) == PHI_NODE
)
1065 check_phi_redundancy (stmt
, eq_to
);
1069 /* Removes redundant phi nodes.
1071 A redundant PHI node is a PHI node where all of its PHI arguments
1072 are the same value, excluding any PHI arguments which are the same
1075 A redundant PHI node is effectively a copy, so we forward copy propagate
1076 which removes all uses of the destination of the PHI node then
1077 finally we delete the redundant PHI node.
1079 Note that if we can not copy propagate the PHI node, then the PHI
1080 will not be removed. Thus we do not have to worry about dependencies
1081 between PHIs and the problems serializing PHIs into copies creates.
1083 The most important effect of this pass is to remove degenerate PHI
1084 nodes created by removing unreachable code. */
1087 kill_redundant_phi_nodes (void)
1090 unsigned i
, old_num_ssa_names
;
1092 tree phi
, var
, repl
, stmt
;
1094 /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1095 replaced. If EQ_TO[VER] is ssa name and it is decided to replace it by
1096 other value, it may be necessary to follow the chain till the final value.
1097 We perform path shortening (replacing the entries of the EQ_TO array with
1098 heads of these chains) whenever we access the field to prevent quadratic
1099 complexity (probably would not occur in practice anyway, but let us play
1101 eq_to
= xcalloc (num_ssa_names
, sizeof (tree
));
1103 /* We have had cases where computing immediate uses takes a
1104 significant amount of compile time. If we run into such
1105 problems here, we may want to only compute immediate uses for
1106 a subset of all the SSA_NAMEs instead of computing it for
1107 all of the SSA_NAMEs. */
1108 compute_immediate_uses (TDFA_USE_OPS
| TDFA_USE_VOPS
, NULL
);
1109 old_num_ssa_names
= num_ssa_names
;
1113 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
1115 var
= PHI_RESULT (phi
);
1116 check_phi_redundancy (phi
, eq_to
);
1120 /* Now propagate the values. */
1121 for (i
= 0; i
< old_num_ssa_names
; i
++)
1126 repl
= get_eq_name (eq_to
, ssa_name (i
));
1127 if (repl
!= ssa_name (i
))
1128 replace_immediate_uses (ssa_name (i
), repl
);
1131 /* And remove the dead phis. */
1132 for (i
= 0; i
< old_num_ssa_names
; i
++)
1137 repl
= get_eq_name (eq_to
, ssa_name (i
));
1138 if (repl
!= ssa_name (i
))
1140 stmt
= SSA_NAME_DEF_STMT (ssa_name (i
));
1141 remove_phi_node (stmt
, NULL_TREE
, bb_for_stmt (stmt
));
1149 struct tree_opt_pass pass_redundant_phi
=
1151 "redphi", /* name */
1153 kill_redundant_phi_nodes
, /* execute */
1156 0, /* static_pass_number */
1158 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
1159 0, /* properties_provided */
1160 0, /* properties_destroyed */
1161 0, /* todo_flags_start */
1162 TODO_dump_func
| TODO_rename_vars
1163 | TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */
1167 /* Emit warnings for uninitialized variables. This is done in two passes.
1169 The first pass notices real uses of SSA names with default definitions.
1170 Such uses are unconditionally uninitialized, and we can be certain that
1171 such a use is a mistake. This pass is run before most optimizations,
1172 so that we catch as many as we can.
1174 The second pass follows PHI nodes to find uses that are potentially
1175 uninitialized. In this case we can't necessarily prove that the use
1176 is really uninitialized. This pass is run after most optimizations,
1177 so that we thread as many jumps and possible, and delete as much dead
1178 code as possible, in order to reduce false positives. We also look
1179 again for plain uninitialized variables, since optimization may have
1180 changed conditionally uninitialized to unconditionally uninitialized. */
1182 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1183 warning text is in MSGID and LOCUS may contain a location or be null. */
1186 warn_uninit (tree t
, const char *msgid
, location_t
*locus
)
1188 tree var
= SSA_NAME_VAR (t
);
1189 tree def
= SSA_NAME_DEF_STMT (t
);
1191 /* Default uses (indicated by an empty definition statement),
1192 are uninitialized. */
1193 if (!IS_EMPTY_STMT (def
))
1196 /* Except for PARMs of course, which are always initialized. */
1197 if (TREE_CODE (var
) == PARM_DECL
)
1200 /* Hard register variables get their initial value from the ether. */
1201 if (DECL_HARD_REGISTER (var
))
1204 /* TREE_NO_WARNING either means we already warned, or the front end
1205 wishes to suppress the warning. */
1206 if (TREE_NO_WARNING (var
))
1210 locus
= &DECL_SOURCE_LOCATION (var
);
1211 warning (msgid
, locus
, var
);
1212 TREE_NO_WARNING (var
) = 1;
1215 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1216 and warn about them. */
1219 warn_uninitialized_var (tree
*tp
, int *walk_subtrees
, void *data
)
1221 location_t
*locus
= data
;
1224 /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */
1225 if (TREE_CODE (t
) == SSA_NAME
)
1227 warn_uninit (t
, "%H'%D' is used uninitialized in this function", locus
);
1230 else if (DECL_P (t
) || TYPE_P (t
))
1236 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1237 and warn about them. */
1240 warn_uninitialized_phi (tree phi
)
1242 int i
, n
= PHI_NUM_ARGS (phi
);
1244 /* Don't look at memory tags. */
1245 if (!is_gimple_reg (PHI_RESULT (phi
)))
1248 for (i
= 0; i
< n
; ++i
)
1250 tree op
= PHI_ARG_DEF (phi
, i
);
1251 if (TREE_CODE (op
) == SSA_NAME
)
1252 warn_uninit (op
, "%H'%D' may be used uninitialized in this function",
1258 execute_early_warn_uninitialized (void)
1260 block_stmt_iterator bsi
;
1264 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1265 walk_tree (bsi_stmt_ptr (bsi
), warn_uninitialized_var
,
1266 EXPR_LOCUS (bsi_stmt (bsi
)), NULL
);
1270 execute_late_warn_uninitialized (void)
1275 /* Re-do the plain uninitialized variable check, as optimization may have
1276 straightened control flow. Do this first so that we don't accidentally
1277 get a "may be" warning when we'd have seen an "is" warning later. */
1278 execute_early_warn_uninitialized ();
1281 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1282 warn_uninitialized_phi (phi
);
1286 gate_warn_uninitialized (void)
1288 return warn_uninitialized
!= 0;
1291 struct tree_opt_pass pass_early_warn_uninitialized
=
1294 gate_warn_uninitialized
, /* gate */
1295 execute_early_warn_uninitialized
, /* execute */
1298 0, /* static_pass_number */
1300 PROP_ssa
, /* properties_required */
1301 0, /* properties_provided */
1302 0, /* properties_destroyed */
1303 0, /* todo_flags_start */
1304 0, /* todo_flags_finish */
1308 struct tree_opt_pass pass_late_warn_uninitialized
=
1311 gate_warn_uninitialized
, /* gate */
1312 execute_late_warn_uninitialized
, /* execute */
1315 0, /* static_pass_number */
1317 PROP_ssa
, /* properties_required */
1318 0, /* properties_provided */
1319 0, /* properties_destroyed */
1320 0, /* todo_flags_start */
1321 0, /* todo_flags_finish */