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
))
644 bsi_stmt (bsi
)->common
.ann
= NULL
;
646 /* Remove annotations from every referenced variable. */
649 for (i
= 0; i
< num_referenced_vars
; i
++)
650 referenced_var (i
)->common
.ann
= NULL
;
651 referenced_vars
= NULL
;
656 fini_ssa_operands ();
658 global_var
= NULL_TREE
;
659 BITMAP_XFREE (call_clobbered_vars
);
660 call_clobbered_vars
= NULL
;
661 BITMAP_XFREE (addressable_vars
);
662 addressable_vars
= NULL
;
666 /* Return true if EXPR is a useless type conversion, otherwise return
670 tree_ssa_useless_type_conversion_1 (tree outer_type
, tree inner_type
)
672 /* If the inner and outer types are effectively the same, then
673 strip the type conversion and enter the equivalence into
675 if (inner_type
== outer_type
676 || (lang_hooks
.types_compatible_p (inner_type
, outer_type
)))
679 /* If both types are pointers and the outer type is a (void *), then
680 the conversion is not necessary. The opposite is not true since
681 that conversion would result in a loss of information if the
682 equivalence was used. Consider an indirect function call where
683 we need to know the exact type of the function to correctly
684 implement the ABI. */
685 else if (POINTER_TYPE_P (inner_type
)
686 && POINTER_TYPE_P (outer_type
)
687 && TREE_CODE (TREE_TYPE (outer_type
)) == VOID_TYPE
)
690 /* Pointers and references are equivalent once we get to GENERIC,
691 so strip conversions that just switch between them. */
692 else if (POINTER_TYPE_P (inner_type
)
693 && POINTER_TYPE_P (outer_type
)
694 && lang_hooks
.types_compatible_p (TREE_TYPE (inner_type
),
695 TREE_TYPE (outer_type
)))
698 /* If both the inner and outer types are integral types, then the
699 conversion is not necessary if they have the same mode and
700 signedness and precision, and both or neither are boolean. Some
701 code assumes an invariant that boolean types stay boolean and do
702 not become 1-bit bit-field types. Note that types with precision
703 not using all bits of the mode (such as bit-field types in C)
704 mean that testing of precision is necessary. */
705 else if (INTEGRAL_TYPE_P (inner_type
)
706 && INTEGRAL_TYPE_P (outer_type
)
707 && TYPE_MODE (inner_type
) == TYPE_MODE (outer_type
)
708 && TYPE_UNSIGNED (inner_type
) == TYPE_UNSIGNED (outer_type
)
709 && TYPE_PRECISION (inner_type
) == TYPE_PRECISION (outer_type
))
711 bool first_boolean
= (TREE_CODE (inner_type
) == BOOLEAN_TYPE
);
712 bool second_boolean
= (TREE_CODE (outer_type
) == BOOLEAN_TYPE
);
713 if (first_boolean
== second_boolean
)
717 /* Recurse for complex types. */
718 else if (TREE_CODE (inner_type
) == COMPLEX_TYPE
719 && TREE_CODE (outer_type
) == COMPLEX_TYPE
720 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type
),
721 TREE_TYPE (inner_type
)))
727 /* Return true if EXPR is a useless type conversion, otherwise return
731 tree_ssa_useless_type_conversion (tree expr
)
733 /* If we have an assignment that merely uses a NOP_EXPR to change
734 the top of the RHS to the type of the LHS and the type conversion
735 is "safe", then strip away the type conversion so that we can
736 enter LHS = RHS into the const_and_copies table. */
737 if (TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
738 || TREE_CODE (expr
) == VIEW_CONVERT_EXPR
739 || TREE_CODE (expr
) == NON_LVALUE_EXPR
)
740 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr
),
741 TREE_TYPE (TREE_OPERAND (expr
,
749 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
750 described in walk_use_def_chains.
752 VISITED is a bitmap used to mark visited SSA_NAMEs to avoid
755 IS_DFS is true if the caller wants to perform a depth-first search
756 when visiting PHI nodes. A DFS will visit each PHI argument and
757 call FN after each one. Otherwise, all the arguments are
758 visited first and then FN is called with each of the visited
759 arguments in a separate pass. */
762 walk_use_def_chains_1 (tree var
, walk_use_def_chains_fn fn
, void *data
,
763 bitmap visited
, bool is_dfs
)
767 if (bitmap_bit_p (visited
, SSA_NAME_VERSION (var
)))
770 bitmap_set_bit (visited
, SSA_NAME_VERSION (var
));
772 def_stmt
= SSA_NAME_DEF_STMT (var
);
774 if (TREE_CODE (def_stmt
) != PHI_NODE
)
776 /* If we reached the end of the use-def chain, call FN. */
777 return fn (var
, def_stmt
, data
);
783 /* When doing a breadth-first search, call FN before following the
784 use-def links for each argument. */
786 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
787 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
790 /* Follow use-def links out of each PHI argument. */
791 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
793 tree arg
= PHI_ARG_DEF (def_stmt
, i
);
794 if (TREE_CODE (arg
) == SSA_NAME
795 && walk_use_def_chains_1 (arg
, fn
, data
, visited
, is_dfs
))
799 /* When doing a depth-first search, call FN after following the
800 use-def links for each argument. */
802 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
803 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
812 /* Walk use-def chains starting at the SSA variable VAR. Call
813 function FN at each reaching definition found. FN takes three
814 arguments: VAR, its defining statement (DEF_STMT) and a generic
815 pointer to whatever state information that FN may want to maintain
816 (DATA). FN is able to stop the walk by returning true, otherwise
817 in order to continue the walk, FN should return false.
819 Note, that if DEF_STMT is a PHI node, the semantics are slightly
820 different. The first argument to FN is no longer the original
821 variable VAR, but the PHI argument currently being examined. If FN
822 wants to get at VAR, it should call PHI_RESULT (PHI).
824 If IS_DFS is true, this function will:
826 1- walk the use-def chains for all the PHI arguments, and,
827 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
829 If IS_DFS is false, the two steps above are done in reverse order
830 (i.e., a breadth-first search). */
834 walk_use_def_chains (tree var
, walk_use_def_chains_fn fn
, void *data
,
839 #if defined ENABLE_CHECKING
840 if (TREE_CODE (var
) != SSA_NAME
)
844 def_stmt
= SSA_NAME_DEF_STMT (var
);
846 /* We only need to recurse if the reaching definition comes from a PHI
848 if (TREE_CODE (def_stmt
) != PHI_NODE
)
849 (*fn
) (var
, def_stmt
, data
);
852 bitmap visited
= BITMAP_XMALLOC ();
853 walk_use_def_chains_1 (var
, fn
, data
, visited
, is_dfs
);
854 BITMAP_XFREE (visited
);
859 /* Replaces VAR with REPL in memory reference expression *X in
863 propagate_into_addr (tree stmt
, tree var
, tree
*x
, tree repl
)
865 tree new_var
, ass_stmt
, addr_var
;
867 block_stmt_iterator bsi
;
869 /* There is nothing special to handle in the other cases. */
870 if (TREE_CODE (repl
) != ADDR_EXPR
)
872 addr_var
= TREE_OPERAND (repl
, 0);
874 while (handled_component_p (*x
)
875 || TREE_CODE (*x
) == REALPART_EXPR
876 || TREE_CODE (*x
) == IMAGPART_EXPR
)
877 x
= &TREE_OPERAND (*x
, 0);
879 if (TREE_CODE (*x
) != INDIRECT_REF
880 || TREE_OPERAND (*x
, 0) != var
)
883 if (TREE_TYPE (*x
) == TREE_TYPE (addr_var
))
886 mark_new_vars_to_rename (stmt
, vars_to_rename
);
891 /* Frontends sometimes produce expressions like *&a instead of a[0].
892 Create a temporary variable to handle this case. */
893 ass_stmt
= build2 (MODIFY_EXPR
, void_type_node
, NULL_TREE
, repl
);
894 new_var
= duplicate_ssa_name (var
, ass_stmt
);
895 TREE_OPERAND (*x
, 0) = new_var
;
896 TREE_OPERAND (ass_stmt
, 0) = new_var
;
898 bb
= bb_for_stmt (stmt
);
899 tree_block_label (bb
);
900 bsi
= bsi_after_labels (bb
);
901 bsi_insert_after (&bsi
, ass_stmt
, BSI_NEW_STMT
);
903 mark_new_vars_to_rename (stmt
, vars_to_rename
);
906 /* Replaces immediate uses of VAR by REPL. */
909 replace_immediate_uses (tree var
, tree repl
)
919 df
= get_immediate_uses (SSA_NAME_DEF_STMT (var
));
920 n
= num_immediate_uses (df
);
922 for (i
= 0; i
< n
; i
++)
924 stmt
= immediate_use (df
, i
);
925 ann
= stmt_ann (stmt
);
927 if (TREE_CODE (stmt
) == PHI_NODE
)
929 for (j
= 0; j
< PHI_NUM_ARGS (stmt
); j
++)
930 if (PHI_ARG_DEF (stmt
, j
) == var
)
932 SET_PHI_ARG_DEF (stmt
, j
, repl
);
933 if (TREE_CODE (repl
) == SSA_NAME
934 && PHI_ARG_EDGE (stmt
, j
)->flags
& EDGE_ABNORMAL
)
935 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl
) = 1;
941 get_stmt_operands (stmt
);
942 mark_new_vars
= false;
943 if (is_gimple_reg (SSA_NAME_VAR (var
)))
945 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
947 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 0), repl
);
948 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 1), repl
);
951 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
952 if (USE_FROM_PTR (use_p
) == var
)
954 propagate_value (use_p
, repl
);
955 mark_new_vars
= POINTER_TYPE_P (TREE_TYPE (repl
));
960 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
961 if (USE_FROM_PTR (use_p
) == var
)
962 propagate_value (use_p
, repl
);
965 /* If REPL is a pointer, it may have different memory tags associated
966 with it. For instance, VAR may have had a name tag while REPL
967 only had a type tag. In these cases, the virtual operands (if
968 any) in the statement will refer to different symbols which need
971 mark_new_vars_to_rename (stmt
, vars_to_rename
);
977 /* Gets the value VAR is equivalent to according to EQ_TO. */
980 get_eq_name (tree
*eq_to
, tree var
)
985 while (TREE_CODE (val
) == SSA_NAME
)
987 ver
= SSA_NAME_VERSION (val
);
994 while (TREE_CODE (var
) == SSA_NAME
)
996 ver
= SSA_NAME_VERSION (var
);
1007 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1008 its result is redundant to to EQ_TO array. */
1011 check_phi_redundancy (tree phi
, tree
*eq_to
)
1013 tree val
= NULL_TREE
, def
, res
= PHI_RESULT (phi
), stmt
;
1014 unsigned i
, ver
= SSA_NAME_VERSION (res
), n
;
1017 /* It is unlikely that such large phi node would be redundant. */
1018 if (PHI_NUM_ARGS (phi
) > 16)
1021 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (phi
); i
++)
1023 def
= PHI_ARG_DEF (phi
, i
);
1025 if (TREE_CODE (def
) == SSA_NAME
)
1027 def
= get_eq_name (eq_to
, def
);
1033 && !operand_equal_p (val
, def
, 0))
1039 /* At least one of the arguments should not be equal to the result, or
1040 something strange is happening. */
1044 if (get_eq_name (eq_to
, res
) == val
)
1047 if (!may_propagate_copy (res
, val
))
1052 df
= get_immediate_uses (SSA_NAME_DEF_STMT (res
));
1053 n
= num_immediate_uses (df
);
1055 for (i
= 0; i
< n
; i
++)
1057 stmt
= immediate_use (df
, i
);
1059 if (TREE_CODE (stmt
) == PHI_NODE
)
1060 check_phi_redundancy (stmt
, eq_to
);
1064 /* Removes redundant phi nodes.
1066 A redundant PHI node is a PHI node where all of its PHI arguments
1067 are the same value, excluding any PHI arguments which are the same
1070 A redundant PHI node is effectively a copy, so we forward copy propagate
1071 which removes all uses of the destination of the PHI node then
1072 finally we delete the redundant PHI node.
1074 Note that if we can not copy propagate the PHI node, then the PHI
1075 will not be removed. Thus we do not have to worry about dependencies
1076 between PHIs and the problems serializing PHIs into copies creates.
1078 The most important effect of this pass is to remove degenerate PHI
1079 nodes created by removing unreachable code. */
1082 kill_redundant_phi_nodes (void)
1085 unsigned i
, old_num_ssa_names
;
1087 tree phi
, var
, repl
, stmt
;
1089 /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1090 replaced. If EQ_TO[VER] is ssa name and it is decided to replace it by
1091 other value, it may be necessary to follow the chain till the final value.
1092 We perform path shortening (replacing the entries of the EQ_TO array with
1093 heads of these chains) whenever we access the field to prevent quadratic
1094 complexity (probably would not occur in practice anyway, but let us play
1096 eq_to
= xcalloc (num_ssa_names
, sizeof (tree
));
1098 /* We have had cases where computing immediate uses takes a
1099 significant amount of compile time. If we run into such
1100 problems here, we may want to only compute immediate uses for
1101 a subset of all the SSA_NAMEs instead of computing it for
1102 all of the SSA_NAMEs. */
1103 compute_immediate_uses (TDFA_USE_OPS
| TDFA_USE_VOPS
, NULL
);
1104 old_num_ssa_names
= num_ssa_names
;
1108 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
1110 var
= PHI_RESULT (phi
);
1111 check_phi_redundancy (phi
, eq_to
);
1115 /* Now propagate the values. */
1116 for (i
= 0; i
< old_num_ssa_names
; i
++)
1121 repl
= get_eq_name (eq_to
, ssa_name (i
));
1122 if (repl
!= ssa_name (i
))
1123 replace_immediate_uses (ssa_name (i
), repl
);
1126 /* And remove the dead phis. */
1127 for (i
= 0; i
< old_num_ssa_names
; i
++)
1132 repl
= get_eq_name (eq_to
, ssa_name (i
));
1133 if (repl
!= ssa_name (i
))
1135 stmt
= SSA_NAME_DEF_STMT (ssa_name (i
));
1136 remove_phi_node (stmt
, NULL_TREE
, bb_for_stmt (stmt
));
1144 struct tree_opt_pass pass_redundant_phi
=
1146 "redphi", /* name */
1148 kill_redundant_phi_nodes
, /* execute */
1151 0, /* static_pass_number */
1153 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
1154 0, /* properties_provided */
1155 0, /* properties_destroyed */
1156 0, /* todo_flags_start */
1157 TODO_dump_func
| TODO_rename_vars
1158 | TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */
1161 /* Emit warnings for uninitialized variables. This is done in two passes.
1163 The first pass notices real uses of SSA names with default definitions.
1164 Such uses are unconditionally uninitialized, and we can be certain that
1165 such a use is a mistake. This pass is run before most optimizations,
1166 so that we catch as many as we can.
1168 The second pass follows PHI nodes to find uses that are potentially
1169 uninitialized. In this case we can't necessarily prove that the use
1170 is really uninitialized. This pass is run after most optimizations,
1171 so that we thread as many jumps and possible, and delete as much dead
1172 code as possible, in order to reduce false positives. We also look
1173 again for plain uninitialized variables, since optimization may have
1174 changed conditionally uninitialized to unconditionally uninitialized. */
1176 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1177 warning text is in MSGID and LOCUS may contain a location or be null. */
1180 warn_uninit (tree t
, const char *msgid
, location_t
*locus
)
1182 tree var
= SSA_NAME_VAR (t
);
1183 tree def
= SSA_NAME_DEF_STMT (t
);
1185 /* Default uses (indicated by an empty definition statement),
1186 are uninitialized. */
1187 if (!IS_EMPTY_STMT (def
))
1190 /* Except for PARMs of course, which are always initialized. */
1191 if (TREE_CODE (var
) == PARM_DECL
)
1194 /* Hard register variables get their initial value from the ether. */
1195 if (DECL_HARD_REGISTER (var
))
1198 /* TREE_NO_WARNING either means we already warned, or the front end
1199 wishes to suppress the warning. */
1200 if (TREE_NO_WARNING (var
))
1204 locus
= &DECL_SOURCE_LOCATION (var
);
1205 warning (msgid
, locus
, var
);
1206 TREE_NO_WARNING (var
) = 1;
1209 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1210 and warn about them. */
1213 warn_uninitialized_var (tree
*tp
, int *walk_subtrees
, void *data
)
1215 location_t
*locus
= data
;
1218 /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */
1219 if (TREE_CODE (t
) == SSA_NAME
)
1221 warn_uninit (t
, "%H'%D' is used uninitialized in this function", locus
);
1224 else if (DECL_P (t
) || TYPE_P (t
))
1230 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1231 and warn about them. */
1234 warn_uninitialized_phi (tree phi
)
1236 int i
, n
= PHI_NUM_ARGS (phi
);
1238 /* Don't look at memory tags. */
1239 if (!is_gimple_reg (PHI_RESULT (phi
)))
1242 for (i
= 0; i
< n
; ++i
)
1244 tree op
= PHI_ARG_DEF (phi
, i
);
1245 if (TREE_CODE (op
) == SSA_NAME
)
1246 warn_uninit (op
, "%H'%D' may be used uninitialized in this function",
1252 execute_early_warn_uninitialized (void)
1254 block_stmt_iterator bsi
;
1258 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1259 walk_tree (bsi_stmt_ptr (bsi
), warn_uninitialized_var
,
1260 EXPR_LOCUS (bsi_stmt (bsi
)), NULL
);
1264 execute_late_warn_uninitialized (void)
1269 /* Re-do the plain uninitialized variable check, as optimization may have
1270 straightened control flow. Do this first so that we don't accidentally
1271 get a "may be" warning when we'd have seen an "is" warning later. */
1272 execute_early_warn_uninitialized ();
1275 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1276 warn_uninitialized_phi (phi
);
1280 gate_warn_uninitialized (void)
1282 return warn_uninitialized
!= 0;
1285 struct tree_opt_pass pass_early_warn_uninitialized
=
1288 gate_warn_uninitialized
, /* gate */
1289 execute_early_warn_uninitialized
, /* execute */
1292 0, /* static_pass_number */
1294 PROP_ssa
, /* properties_required */
1295 0, /* properties_provided */
1296 0, /* properties_destroyed */
1297 0, /* todo_flags_start */
1298 0 /* todo_flags_finish */
1301 struct tree_opt_pass pass_late_warn_uninitialized
=
1304 gate_warn_uninitialized
, /* gate */
1305 execute_late_warn_uninitialized
, /* execute */
1308 0, /* static_pass_number */
1310 PROP_ssa
, /* properties_required */
1311 0, /* properties_provided */
1312 0, /* properties_destroyed */
1313 0, /* todo_flags_start */
1314 0 /* todo_flags_finish */