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"
45 #include "tree-dump.h"
46 #include "tree-pass.h"
49 /* Remove edge E and remove the corresponding arguments from the PHI nodes
50 in E's destination block. */
53 ssa_remove_edge (edge e
)
57 /* Remove the appropriate PHI arguments in E's destination block. */
58 for (phi
= phi_nodes (e
->dest
); phi
; phi
= next
)
60 next
= PHI_CHAIN (phi
);
61 remove_phi_arg (phi
, e
->src
);
67 /* Remove the corresponding arguments from the PHI nodes in E's
68 destination block and redirect it to DEST. Return redirected edge.
69 The list of removed arguments is stored in PENDING_STMT (e). */
72 ssa_redirect_edge (edge e
, basic_block dest
)
75 tree list
= NULL
, *last
= &list
;
79 /* Remove the appropriate PHI arguments in E's destination block. */
80 for (phi
= phi_nodes (e
->dest
); phi
; phi
= next
)
82 next
= PHI_CHAIN (phi
);
84 i
= phi_arg_from_edge (phi
, e
);
88 src
= PHI_ARG_DEF (phi
, i
);
89 dst
= PHI_RESULT (phi
);
90 node
= build_tree_list (dst
, src
);
92 last
= &TREE_CHAIN (node
);
94 remove_phi_arg_num (phi
, i
);
97 e
= redirect_edge_succ_nodup (e
, dest
);
98 PENDING_STMT (e
) = list
;
104 /* Return true if SSA_NAME is malformed and mark it visited.
106 IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
110 verify_ssa_name (tree ssa_name
, bool is_virtual
)
112 TREE_VISITED (ssa_name
) = 1;
114 if (TREE_CODE (ssa_name
) != SSA_NAME
)
116 error ("Expected an SSA_NAME object");
120 if (TREE_TYPE (ssa_name
) != TREE_TYPE (SSA_NAME_VAR (ssa_name
)))
122 error ("Type mismatch between an SSA_NAME and its symbol.");
126 if (SSA_NAME_IN_FREE_LIST (ssa_name
))
128 error ("Found an SSA_NAME that had been released into the free pool");
132 if (is_virtual
&& is_gimple_reg (ssa_name
))
134 error ("Found a virtual definition for a GIMPLE register");
138 if (!is_virtual
&& !is_gimple_reg (ssa_name
))
140 error ("Found a real definition for a non-register");
148 /* Return true if the definition of SSA_NAME at block BB is malformed.
150 STMT is the statement where SSA_NAME is created.
152 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
153 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
154 it means that the block in that array slot contains the
155 definition of SSA_NAME.
157 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
161 verify_def (basic_block bb
, basic_block
*definition_block
, tree ssa_name
,
162 tree stmt
, bool is_virtual
)
164 if (verify_ssa_name (ssa_name
, is_virtual
))
167 if (definition_block
[SSA_NAME_VERSION (ssa_name
)])
169 error ("SSA_NAME created in two different blocks %i and %i",
170 definition_block
[SSA_NAME_VERSION (ssa_name
)]->index
, bb
->index
);
174 definition_block
[SSA_NAME_VERSION (ssa_name
)] = bb
;
176 if (SSA_NAME_DEF_STMT (ssa_name
) != stmt
)
178 error ("SSA_NAME_DEF_STMT is wrong");
179 fprintf (stderr
, "Expected definition statement:\n");
180 debug_generic_stmt (SSA_NAME_DEF_STMT (ssa_name
));
181 fprintf (stderr
, "\nActual definition statement:\n");
182 debug_generic_stmt (stmt
);
189 fprintf (stderr
, "while verifying SSA_NAME ");
190 print_generic_expr (stderr
, ssa_name
, 0);
191 fprintf (stderr
, " in statement\n");
192 debug_generic_stmt (stmt
);
198 /* Return true if the use of SSA_NAME at statement STMT in block BB is
201 DEF_BB is the block where SSA_NAME was found to be created.
203 IDOM contains immediate dominator information for the flowgraph.
205 CHECK_ABNORMAL is true if the caller wants to check whether this use
206 is flowing through an abnormal edge (only used when checking PHI
209 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
213 verify_use (basic_block bb
, basic_block def_bb
, tree ssa_name
,
214 tree stmt
, bool check_abnormal
, bool is_virtual
)
218 err
= verify_ssa_name (ssa_name
, is_virtual
);
220 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name
))
221 && var_ann (SSA_NAME_VAR (ssa_name
))->default_def
== ssa_name
)
222 ; /* Default definitions have empty statements. Nothing to do. */
225 error ("Missing definition");
228 else if (bb
!= def_bb
229 && !dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
231 error ("Definition in block %i does not dominate use in block %i",
232 def_bb
->index
, bb
->index
);
237 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name
))
239 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
245 fprintf (stderr
, "for SSA_NAME: ");
246 debug_generic_expr (ssa_name
);
247 fprintf (stderr
, "in statement:\n");
248 debug_generic_stmt (stmt
);
255 /* Return true if any of the arguments for PHI node PHI at block BB is
258 IDOM contains immediate dominator information for the flowgraph.
260 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
261 numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
262 block in that array slot contains the definition of SSA_NAME. */
265 verify_phi_args (tree phi
, basic_block bb
, basic_block
*definition_block
)
269 int i
, phi_num_args
= PHI_NUM_ARGS (phi
);
271 /* Mark all the incoming edges. */
272 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
275 for (i
= 0; i
< phi_num_args
; i
++)
277 tree op
= PHI_ARG_DEF (phi
, i
);
279 e
= PHI_ARG_EDGE (phi
, i
);
281 if (TREE_CODE (op
) == SSA_NAME
)
282 err
= verify_use (e
->src
, definition_block
[SSA_NAME_VERSION (op
)], op
,
283 phi
, e
->flags
& EDGE_ABNORMAL
,
284 !is_gimple_reg (PHI_RESULT (phi
)));
288 error ("Wrong edge %d->%d for PHI argument\n",
289 e
->src
->index
, e
->dest
->index
, bb
->index
);
293 if (e
->aux
== (void *) 0)
295 error ("PHI argument flowing through dead edge %d->%d\n",
296 e
->src
->index
, e
->dest
->index
);
300 if (e
->aux
== (void *) 2)
302 error ("PHI argument duplicated for edge %d->%d\n", e
->src
->index
,
309 fprintf (stderr
, "PHI argument\n");
310 debug_generic_stmt (op
);
317 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
319 if (e
->aux
!= (void *) 2)
321 error ("No argument flowing through edge %d->%d\n", e
->src
->index
,
332 fprintf (stderr
, "for PHI node\n");
333 debug_generic_stmt (phi
);
342 verify_flow_insensitive_alias_info (void)
346 bitmap visited
= BITMAP_XMALLOC ();
348 for (i
= 0; i
< num_referenced_vars
; i
++)
352 varray_type may_aliases
;
354 var
= referenced_var (i
);
356 may_aliases
= ann
->may_aliases
;
358 for (j
= 0; may_aliases
&& j
< VARRAY_ACTIVE_SIZE (may_aliases
); j
++)
360 tree alias
= VARRAY_TREE (may_aliases
, j
);
362 bitmap_set_bit (visited
, var_ann (alias
)->uid
);
364 if (!may_be_aliased (alias
))
366 error ("Non-addressable variable inside an alias set.");
367 debug_variable (alias
);
373 for (i
= 0; i
< num_referenced_vars
; i
++)
377 var
= referenced_var (i
);
380 if (ann
->mem_tag_kind
== NOT_A_TAG
382 && !bitmap_bit_p (visited
, ann
->uid
))
384 error ("Addressable variable that is an alias tag but is not in any alias set.");
389 BITMAP_XFREE (visited
);
393 debug_variable (var
);
394 internal_error ("verify_flow_insensitive_alias_info failed.");
399 verify_flow_sensitive_alias_info (void)
404 for (i
= 1; i
< num_ssa_names
; i
++)
407 struct ptr_info_def
*pi
;
410 ann
= var_ann (SSA_NAME_VAR (ptr
));
411 pi
= SSA_NAME_PTR_INFO (ptr
);
413 /* We only care for pointers that are actually referenced in the
415 if (!TREE_VISITED (ptr
) || !POINTER_TYPE_P (TREE_TYPE (ptr
)))
418 /* RESULT_DECL is special. If it's a GIMPLE register, then it
419 is only written-to only once in the return statement.
420 Otherwise, aggregate RESULT_DECLs may be written-to more than
421 once in virtual operands. */
422 if (TREE_CODE (SSA_NAME_VAR (ptr
)) == RESULT_DECL
423 && is_gimple_reg (ptr
))
429 if (pi
->is_dereferenced
&& !pi
->name_mem_tag
&& !ann
->type_mem_tag
)
431 error ("Dereferenced pointers should have a name or a type tag");
437 && (pi
->pt_vars
== NULL
438 || bitmap_first_set_bit (pi
->pt_vars
) < 0))
440 error ("Pointers with a memory tag, should have points-to sets or point to malloc");
444 if (pi
->value_escapes_p
446 && !is_call_clobbered (pi
->name_mem_tag
))
448 error ("Pointer escapes but its name tag is not call-clobbered.");
452 if (pi
->name_mem_tag
&& pi
->pt_vars
)
456 for (j
= i
+ 1; j
< num_ssa_names
; j
++)
458 tree ptr2
= ssa_name (j
);
459 struct ptr_info_def
*pi2
= SSA_NAME_PTR_INFO (ptr2
);
461 if (!TREE_VISITED (ptr2
) || !POINTER_TYPE_P (TREE_TYPE (ptr2
)))
467 && bitmap_first_set_bit (pi2
->pt_vars
) >= 0
468 && pi
->name_mem_tag
!= pi2
->name_mem_tag
469 && bitmap_equal_p (pi
->pt_vars
, pi2
->pt_vars
))
471 error ("Two pointers with different name tags and identical points-to sets");
472 debug_variable (ptr2
);
482 debug_variable (ptr
);
483 internal_error ("verify_flow_sensitive_alias_info failed.");
487 /* Verify the consistency of aliasing information. */
490 verify_alias_info (void)
492 verify_flow_sensitive_alias_info ();
493 verify_flow_insensitive_alias_info ();
497 /* Verify common invariants in the SSA web.
498 TODO: verify the variable annotations. */
505 basic_block
*definition_block
= xcalloc (num_ssa_names
, sizeof (basic_block
));
509 timevar_push (TV_TREE_SSA_VERIFY
);
511 /* Keep track of SSA names present in the IL. */
512 for (i
= 1; i
< num_ssa_names
; i
++)
513 TREE_VISITED (ssa_name (i
)) = 0;
515 calculate_dominance_info (CDI_DOMINATORS
);
517 /* Verify and register all the SSA_NAME definitions found in the
522 block_stmt_iterator bsi
;
524 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
525 if (verify_def (bb
, definition_block
, PHI_RESULT (phi
), phi
,
526 !is_gimple_reg (PHI_RESULT (phi
))))
529 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
533 stmt
= bsi_stmt (bsi
);
534 get_stmt_operands (stmt
);
536 if (stmt_ann (stmt
)->makes_aliased_stores
537 && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt
)) == 0)
539 error ("Statement makes aliased stores, but has no V_MAY_DEFS");
540 debug_generic_stmt (stmt
);
544 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
546 if (verify_def (bb
, definition_block
, op
, stmt
, true))
550 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
552 if (verify_def (bb
, definition_block
, op
, stmt
, false))
559 /* Now verify all the uses and make sure they agree with the definitions
560 found in the previous pass. */
565 block_stmt_iterator bsi
;
567 /* Make sure that all edges have a clear 'aux' field. */
568 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
572 error ("AUX pointer initialized for edge %d->%d\n", e
->src
->index
,
578 /* Verify the arguments for every PHI node in the block. */
579 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
580 if (verify_phi_args (phi
, bb
, definition_block
))
583 /* Now verify all the uses and vuses in every statement of the block. */
584 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
586 tree stmt
= bsi_stmt (bsi
);
588 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
590 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
591 op
, stmt
, false, true))
595 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
597 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
598 op
, stmt
, false, false))
604 /* Finally, verify alias information. */
605 verify_alias_info ();
607 free (definition_block
);
608 timevar_pop (TV_TREE_SSA_VERIFY
);
612 internal_error ("verify_ssa failed.");
616 /* Initialize global DFA and SSA structures. */
621 VARRAY_TREE_INIT (referenced_vars
, 20, "referenced_vars");
622 call_clobbered_vars
= BITMAP_XMALLOC ();
623 addressable_vars
= BITMAP_XMALLOC ();
624 init_ssa_operands ();
627 global_var
= NULL_TREE
;
631 /* Deallocate memory associated with SSA data structures for FNDECL. */
634 delete_tree_ssa (void)
638 block_stmt_iterator bsi
;
640 /* Remove annotations from every tree in the function. */
642 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
644 tree stmt
= bsi_stmt (bsi
);
646 ggc_free (stmt
->common
.ann
);
647 stmt
->common
.ann
= NULL
;
650 /* Remove annotations from every referenced variable. */
653 for (i
= 0; i
< num_referenced_vars
; i
++)
655 tree var
= referenced_var (i
);
656 ggc_free (var
->common
.ann
);
657 var
->common
.ann
= NULL
;
659 referenced_vars
= NULL
;
664 fini_ssa_operands ();
666 global_var
= NULL_TREE
;
667 BITMAP_XFREE (call_clobbered_vars
);
668 call_clobbered_vars
= NULL
;
669 BITMAP_XFREE (addressable_vars
);
670 addressable_vars
= NULL
;
674 /* Return true if EXPR is a useless type conversion, otherwise return
678 tree_ssa_useless_type_conversion_1 (tree outer_type
, tree inner_type
)
680 /* If the inner and outer types are effectively the same, then
681 strip the type conversion and enter the equivalence into
683 if (inner_type
== outer_type
684 || (lang_hooks
.types_compatible_p (inner_type
, outer_type
)))
687 /* If both types are pointers and the outer type is a (void *), then
688 the conversion is not necessary. The opposite is not true since
689 that conversion would result in a loss of information if the
690 equivalence was used. Consider an indirect function call where
691 we need to know the exact type of the function to correctly
692 implement the ABI. */
693 else if (POINTER_TYPE_P (inner_type
)
694 && POINTER_TYPE_P (outer_type
)
695 && TREE_CODE (TREE_TYPE (outer_type
)) == VOID_TYPE
)
698 /* Pointers and references are equivalent once we get to GENERIC,
699 so strip conversions that just switch between them. */
700 else if (POINTER_TYPE_P (inner_type
)
701 && POINTER_TYPE_P (outer_type
)
702 && lang_hooks
.types_compatible_p (TREE_TYPE (inner_type
),
703 TREE_TYPE (outer_type
)))
706 /* If both the inner and outer types are integral types, then the
707 conversion is not necessary if they have the same mode and
708 signedness and precision, and both or neither are boolean. Some
709 code assumes an invariant that boolean types stay boolean and do
710 not become 1-bit bit-field types. Note that types with precision
711 not using all bits of the mode (such as bit-field types in C)
712 mean that testing of precision is necessary. */
713 else if (INTEGRAL_TYPE_P (inner_type
)
714 && INTEGRAL_TYPE_P (outer_type
)
715 && TYPE_MODE (inner_type
) == TYPE_MODE (outer_type
)
716 && TYPE_UNSIGNED (inner_type
) == TYPE_UNSIGNED (outer_type
)
717 && TYPE_PRECISION (inner_type
) == TYPE_PRECISION (outer_type
))
719 bool first_boolean
= (TREE_CODE (inner_type
) == BOOLEAN_TYPE
);
720 bool second_boolean
= (TREE_CODE (outer_type
) == BOOLEAN_TYPE
);
721 if (first_boolean
== second_boolean
)
725 /* Recurse for complex types. */
726 else if (TREE_CODE (inner_type
) == COMPLEX_TYPE
727 && TREE_CODE (outer_type
) == COMPLEX_TYPE
728 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type
),
729 TREE_TYPE (inner_type
)))
735 /* Return true if EXPR is a useless type conversion, otherwise return
739 tree_ssa_useless_type_conversion (tree expr
)
741 /* If we have an assignment that merely uses a NOP_EXPR to change
742 the top of the RHS to the type of the LHS and the type conversion
743 is "safe", then strip away the type conversion so that we can
744 enter LHS = RHS into the const_and_copies table. */
745 if (TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
746 || TREE_CODE (expr
) == VIEW_CONVERT_EXPR
747 || TREE_CODE (expr
) == NON_LVALUE_EXPR
)
748 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr
),
749 TREE_TYPE (TREE_OPERAND (expr
,
757 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
758 described in walk_use_def_chains.
760 VISITED is a bitmap used to mark visited SSA_NAMEs to avoid
763 IS_DFS is true if the caller wants to perform a depth-first search
764 when visiting PHI nodes. A DFS will visit each PHI argument and
765 call FN after each one. Otherwise, all the arguments are
766 visited first and then FN is called with each of the visited
767 arguments in a separate pass. */
770 walk_use_def_chains_1 (tree var
, walk_use_def_chains_fn fn
, void *data
,
771 bitmap visited
, bool is_dfs
)
775 if (bitmap_bit_p (visited
, SSA_NAME_VERSION (var
)))
778 bitmap_set_bit (visited
, SSA_NAME_VERSION (var
));
780 def_stmt
= SSA_NAME_DEF_STMT (var
);
782 if (TREE_CODE (def_stmt
) != PHI_NODE
)
784 /* If we reached the end of the use-def chain, call FN. */
785 return fn (var
, def_stmt
, data
);
791 /* When doing a breadth-first search, call FN before following the
792 use-def links for each argument. */
794 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
795 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
798 /* Follow use-def links out of each PHI argument. */
799 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
801 tree arg
= PHI_ARG_DEF (def_stmt
, i
);
802 if (TREE_CODE (arg
) == SSA_NAME
803 && walk_use_def_chains_1 (arg
, fn
, data
, visited
, is_dfs
))
807 /* When doing a depth-first search, call FN after following the
808 use-def links for each argument. */
810 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
811 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
820 /* Walk use-def chains starting at the SSA variable VAR. Call
821 function FN at each reaching definition found. FN takes three
822 arguments: VAR, its defining statement (DEF_STMT) and a generic
823 pointer to whatever state information that FN may want to maintain
824 (DATA). FN is able to stop the walk by returning true, otherwise
825 in order to continue the walk, FN should return false.
827 Note, that if DEF_STMT is a PHI node, the semantics are slightly
828 different. The first argument to FN is no longer the original
829 variable VAR, but the PHI argument currently being examined. If FN
830 wants to get at VAR, it should call PHI_RESULT (PHI).
832 If IS_DFS is true, this function will:
834 1- walk the use-def chains for all the PHI arguments, and,
835 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
837 If IS_DFS is false, the two steps above are done in reverse order
838 (i.e., a breadth-first search). */
842 walk_use_def_chains (tree var
, walk_use_def_chains_fn fn
, void *data
,
847 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
849 def_stmt
= SSA_NAME_DEF_STMT (var
);
851 /* We only need to recurse if the reaching definition comes from a PHI
853 if (TREE_CODE (def_stmt
) != PHI_NODE
)
854 (*fn
) (var
, def_stmt
, data
);
857 bitmap visited
= BITMAP_XMALLOC ();
858 walk_use_def_chains_1 (var
, fn
, data
, visited
, is_dfs
);
859 BITMAP_XFREE (visited
);
864 /* Replaces VAR with REPL in memory reference expression *X in
868 propagate_into_addr (tree stmt
, tree var
, tree
*x
, tree repl
)
870 tree new_var
, ass_stmt
, addr_var
;
872 block_stmt_iterator bsi
;
874 /* There is nothing special to handle in the other cases. */
875 if (TREE_CODE (repl
) != ADDR_EXPR
)
877 addr_var
= TREE_OPERAND (repl
, 0);
879 while (handled_component_p (*x
)
880 || TREE_CODE (*x
) == REALPART_EXPR
881 || TREE_CODE (*x
) == IMAGPART_EXPR
)
882 x
= &TREE_OPERAND (*x
, 0);
884 if (TREE_CODE (*x
) != INDIRECT_REF
885 || TREE_OPERAND (*x
, 0) != var
)
888 if (TREE_TYPE (*x
) == TREE_TYPE (addr_var
))
891 mark_new_vars_to_rename (stmt
, vars_to_rename
);
896 /* Frontends sometimes produce expressions like *&a instead of a[0].
897 Create a temporary variable to handle this case. */
898 ass_stmt
= build2 (MODIFY_EXPR
, void_type_node
, NULL_TREE
, repl
);
899 new_var
= duplicate_ssa_name (var
, ass_stmt
);
900 TREE_OPERAND (*x
, 0) = new_var
;
901 TREE_OPERAND (ass_stmt
, 0) = new_var
;
903 bb
= bb_for_stmt (stmt
);
904 tree_block_label (bb
);
905 bsi
= bsi_after_labels (bb
);
906 bsi_insert_after (&bsi
, ass_stmt
, BSI_NEW_STMT
);
908 mark_new_vars_to_rename (stmt
, vars_to_rename
);
911 /* Replaces immediate uses of VAR by REPL. */
914 replace_immediate_uses (tree var
, tree repl
)
924 df
= get_immediate_uses (SSA_NAME_DEF_STMT (var
));
925 n
= num_immediate_uses (df
);
927 for (i
= 0; i
< n
; i
++)
929 stmt
= immediate_use (df
, i
);
930 ann
= stmt_ann (stmt
);
932 if (TREE_CODE (stmt
) == PHI_NODE
)
934 for (j
= 0; j
< PHI_NUM_ARGS (stmt
); j
++)
935 if (PHI_ARG_DEF (stmt
, j
) == var
)
937 SET_PHI_ARG_DEF (stmt
, j
, repl
);
938 if (TREE_CODE (repl
) == SSA_NAME
939 && PHI_ARG_EDGE (stmt
, j
)->flags
& EDGE_ABNORMAL
)
940 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl
) = 1;
946 get_stmt_operands (stmt
);
947 mark_new_vars
= false;
948 if (is_gimple_reg (SSA_NAME_VAR (var
)))
950 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
952 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 0), repl
);
953 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 1), repl
);
956 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
957 if (USE_FROM_PTR (use_p
) == var
)
959 propagate_value (use_p
, repl
);
960 mark_new_vars
= POINTER_TYPE_P (TREE_TYPE (repl
));
965 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
966 if (USE_FROM_PTR (use_p
) == var
)
967 propagate_value (use_p
, repl
);
970 /* If REPL is a pointer, it may have different memory tags associated
971 with it. For instance, VAR may have had a name tag while REPL
972 only had a type tag. In these cases, the virtual operands (if
973 any) in the statement will refer to different symbols which need
976 mark_new_vars_to_rename (stmt
, vars_to_rename
);
982 /* Gets the value VAR is equivalent to according to EQ_TO. */
985 get_eq_name (tree
*eq_to
, tree var
)
990 while (TREE_CODE (val
) == SSA_NAME
)
992 ver
= SSA_NAME_VERSION (val
);
999 while (TREE_CODE (var
) == SSA_NAME
)
1001 ver
= SSA_NAME_VERSION (var
);
1012 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1013 its result is redundant to to EQ_TO array. */
1016 check_phi_redundancy (tree phi
, tree
*eq_to
)
1018 tree val
= NULL_TREE
, def
, res
= PHI_RESULT (phi
), stmt
;
1019 unsigned i
, ver
= SSA_NAME_VERSION (res
), n
;
1022 /* It is unlikely that such large phi node would be redundant. */
1023 if (PHI_NUM_ARGS (phi
) > 16)
1026 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (phi
); i
++)
1028 def
= PHI_ARG_DEF (phi
, i
);
1030 if (TREE_CODE (def
) == SSA_NAME
)
1032 def
= get_eq_name (eq_to
, def
);
1038 && !operand_equal_p (val
, def
, 0))
1044 /* At least one of the arguments should not be equal to the result, or
1045 something strange is happening. */
1048 if (get_eq_name (eq_to
, res
) == val
)
1051 if (!may_propagate_copy (res
, val
))
1056 df
= get_immediate_uses (SSA_NAME_DEF_STMT (res
));
1057 n
= num_immediate_uses (df
);
1059 for (i
= 0; i
< n
; i
++)
1061 stmt
= immediate_use (df
, i
);
1063 if (TREE_CODE (stmt
) == PHI_NODE
)
1064 check_phi_redundancy (stmt
, eq_to
);
1068 /* Removes redundant phi nodes.
1070 A redundant PHI node is a PHI node where all of its PHI arguments
1071 are the same value, excluding any PHI arguments which are the same
1074 A redundant PHI node is effectively a copy, so we forward copy propagate
1075 which removes all uses of the destination of the PHI node then
1076 finally we delete the redundant PHI node.
1078 Note that if we can not copy propagate the PHI node, then the PHI
1079 will not be removed. Thus we do not have to worry about dependencies
1080 between PHIs and the problems serializing PHIs into copies creates.
1082 The most important effect of this pass is to remove degenerate PHI
1083 nodes created by removing unreachable code. */
1086 kill_redundant_phi_nodes (void)
1089 unsigned i
, old_num_ssa_names
;
1091 tree phi
, var
, repl
, stmt
;
1093 /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1094 replaced. If EQ_TO[VER] is ssa name and it is decided to replace it by
1095 other value, it may be necessary to follow the chain till the final value.
1096 We perform path shortening (replacing the entries of the EQ_TO array with
1097 heads of these chains) whenever we access the field to prevent quadratic
1098 complexity (probably would not occur in practice anyway, but let us play
1100 eq_to
= xcalloc (num_ssa_names
, sizeof (tree
));
1102 /* We have had cases where computing immediate uses takes a
1103 significant amount of compile time. If we run into such
1104 problems here, we may want to only compute immediate uses for
1105 a subset of all the SSA_NAMEs instead of computing it for
1106 all of the SSA_NAMEs. */
1107 compute_immediate_uses (TDFA_USE_OPS
| TDFA_USE_VOPS
, NULL
);
1108 old_num_ssa_names
= num_ssa_names
;
1112 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
1114 var
= PHI_RESULT (phi
);
1115 check_phi_redundancy (phi
, eq_to
);
1119 /* Now propagate the values. */
1120 for (i
= 0; i
< old_num_ssa_names
; i
++)
1125 repl
= get_eq_name (eq_to
, ssa_name (i
));
1126 if (repl
!= ssa_name (i
))
1127 replace_immediate_uses (ssa_name (i
), repl
);
1130 /* And remove the dead phis. */
1131 for (i
= 0; i
< old_num_ssa_names
; i
++)
1136 repl
= get_eq_name (eq_to
, ssa_name (i
));
1137 if (repl
!= ssa_name (i
))
1139 stmt
= SSA_NAME_DEF_STMT (ssa_name (i
));
1140 remove_phi_node (stmt
, NULL_TREE
, bb_for_stmt (stmt
));
1148 struct tree_opt_pass pass_redundant_phi
=
1150 "redphi", /* name */
1152 kill_redundant_phi_nodes
, /* execute */
1155 0, /* static_pass_number */
1157 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
1158 0, /* properties_provided */
1159 0, /* properties_destroyed */
1160 0, /* todo_flags_start */
1161 TODO_dump_func
| TODO_rename_vars
1162 | TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */
1166 /* Emit warnings for uninitialized variables. This is done in two passes.
1168 The first pass notices real uses of SSA names with default definitions.
1169 Such uses are unconditionally uninitialized, and we can be certain that
1170 such a use is a mistake. This pass is run before most optimizations,
1171 so that we catch as many as we can.
1173 The second pass follows PHI nodes to find uses that are potentially
1174 uninitialized. In this case we can't necessarily prove that the use
1175 is really uninitialized. This pass is run after most optimizations,
1176 so that we thread as many jumps and possible, and delete as much dead
1177 code as possible, in order to reduce false positives. We also look
1178 again for plain uninitialized variables, since optimization may have
1179 changed conditionally uninitialized to unconditionally uninitialized. */
1181 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1182 warning text is in MSGID and LOCUS may contain a location or be null. */
1185 warn_uninit (tree t
, const char *msgid
, location_t
*locus
)
1187 tree var
= SSA_NAME_VAR (t
);
1188 tree def
= SSA_NAME_DEF_STMT (t
);
1190 /* Default uses (indicated by an empty definition statement),
1191 are uninitialized. */
1192 if (!IS_EMPTY_STMT (def
))
1195 /* Except for PARMs of course, which are always initialized. */
1196 if (TREE_CODE (var
) == PARM_DECL
)
1199 /* Hard register variables get their initial value from the ether. */
1200 if (DECL_HARD_REGISTER (var
))
1203 /* TREE_NO_WARNING either means we already warned, or the front end
1204 wishes to suppress the warning. */
1205 if (TREE_NO_WARNING (var
))
1209 locus
= &DECL_SOURCE_LOCATION (var
);
1210 warning (msgid
, locus
, var
);
1211 TREE_NO_WARNING (var
) = 1;
1214 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1215 and warn about them. */
1218 warn_uninitialized_var (tree
*tp
, int *walk_subtrees
, void *data
)
1220 location_t
*locus
= data
;
1223 /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */
1224 if (TREE_CODE (t
) == SSA_NAME
)
1226 warn_uninit (t
, "%H'%D' is used uninitialized in this function", locus
);
1229 else if (DECL_P (t
) || TYPE_P (t
))
1235 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1236 and warn about them. */
1239 warn_uninitialized_phi (tree phi
)
1241 int i
, n
= PHI_NUM_ARGS (phi
);
1243 /* Don't look at memory tags. */
1244 if (!is_gimple_reg (PHI_RESULT (phi
)))
1247 for (i
= 0; i
< n
; ++i
)
1249 tree op
= PHI_ARG_DEF (phi
, i
);
1250 if (TREE_CODE (op
) == SSA_NAME
)
1251 warn_uninit (op
, "%H'%D' may be used uninitialized in this function",
1257 execute_early_warn_uninitialized (void)
1259 block_stmt_iterator bsi
;
1263 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1264 walk_tree (bsi_stmt_ptr (bsi
), warn_uninitialized_var
,
1265 EXPR_LOCUS (bsi_stmt (bsi
)), NULL
);
1269 execute_late_warn_uninitialized (void)
1274 /* Re-do the plain uninitialized variable check, as optimization may have
1275 straightened control flow. Do this first so that we don't accidentally
1276 get a "may be" warning when we'd have seen an "is" warning later. */
1277 execute_early_warn_uninitialized ();
1280 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1281 warn_uninitialized_phi (phi
);
1285 gate_warn_uninitialized (void)
1287 return warn_uninitialized
!= 0;
1290 struct tree_opt_pass pass_early_warn_uninitialized
=
1293 gate_warn_uninitialized
, /* gate */
1294 execute_early_warn_uninitialized
, /* execute */
1297 0, /* static_pass_number */
1299 PROP_ssa
, /* properties_required */
1300 0, /* properties_provided */
1301 0, /* properties_destroyed */
1302 0, /* todo_flags_start */
1303 0, /* todo_flags_finish */
1307 struct tree_opt_pass pass_late_warn_uninitialized
=
1310 gate_warn_uninitialized
, /* gate */
1311 execute_late_warn_uninitialized
, /* execute */
1314 0, /* static_pass_number */
1316 PROP_ssa
, /* properties_required */
1317 0, /* properties_provided */
1318 0, /* properties_destroyed */
1319 0, /* todo_flags_start */
1320 0, /* todo_flags_finish */