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
));
508 enum dom_state orig_dom_state
= dom_computed
[CDI_DOMINATORS
];
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 /* Restore the dominance infomation to its prior known state, so
610 that we do not perturb the compiler's subsequent behaviour. */
611 if (orig_dom_state
== DOM_NONE
)
612 free_dominance_info (CDI_DOMINATORS
);
614 dom_computed
[CDI_DOMINATORS
] = orig_dom_state
;
616 timevar_pop (TV_TREE_SSA_VERIFY
);
620 internal_error ("verify_ssa failed.");
624 /* Initialize global DFA and SSA structures. */
629 VARRAY_TREE_INIT (referenced_vars
, 20, "referenced_vars");
630 call_clobbered_vars
= BITMAP_XMALLOC ();
631 addressable_vars
= BITMAP_XMALLOC ();
632 init_ssa_operands ();
635 global_var
= NULL_TREE
;
639 /* Deallocate memory associated with SSA data structures for FNDECL. */
642 delete_tree_ssa (void)
646 block_stmt_iterator bsi
;
648 /* Remove annotations from every tree in the function. */
650 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
652 tree stmt
= bsi_stmt (bsi
);
654 ggc_free (stmt
->common
.ann
);
655 stmt
->common
.ann
= NULL
;
658 /* Remove annotations from every referenced variable. */
661 for (i
= 0; i
< num_referenced_vars
; i
++)
663 tree var
= referenced_var (i
);
664 ggc_free (var
->common
.ann
);
665 var
->common
.ann
= NULL
;
667 referenced_vars
= NULL
;
672 fini_ssa_operands ();
674 global_var
= NULL_TREE
;
675 BITMAP_XFREE (call_clobbered_vars
);
676 call_clobbered_vars
= NULL
;
677 BITMAP_XFREE (addressable_vars
);
678 addressable_vars
= NULL
;
682 /* Return true if EXPR is a useless type conversion, otherwise return
686 tree_ssa_useless_type_conversion_1 (tree outer_type
, tree inner_type
)
688 /* If the inner and outer types are effectively the same, then
689 strip the type conversion and enter the equivalence into
691 if (inner_type
== outer_type
692 || (lang_hooks
.types_compatible_p (inner_type
, outer_type
)))
695 /* If both types are pointers and the outer type is a (void *), then
696 the conversion is not necessary. The opposite is not true since
697 that conversion would result in a loss of information if the
698 equivalence was used. Consider an indirect function call where
699 we need to know the exact type of the function to correctly
700 implement the ABI. */
701 else if (POINTER_TYPE_P (inner_type
)
702 && POINTER_TYPE_P (outer_type
)
703 && TREE_CODE (TREE_TYPE (outer_type
)) == VOID_TYPE
)
706 /* Pointers and references are equivalent once we get to GENERIC,
707 so strip conversions that just switch between them. */
708 else if (POINTER_TYPE_P (inner_type
)
709 && POINTER_TYPE_P (outer_type
)
710 && lang_hooks
.types_compatible_p (TREE_TYPE (inner_type
),
711 TREE_TYPE (outer_type
)))
714 /* If both the inner and outer types are integral types, then the
715 conversion is not necessary if they have the same mode and
716 signedness and precision, and both or neither are boolean. Some
717 code assumes an invariant that boolean types stay boolean and do
718 not become 1-bit bit-field types. Note that types with precision
719 not using all bits of the mode (such as bit-field types in C)
720 mean that testing of precision is necessary. */
721 else if (INTEGRAL_TYPE_P (inner_type
)
722 && INTEGRAL_TYPE_P (outer_type
)
723 && TYPE_MODE (inner_type
) == TYPE_MODE (outer_type
)
724 && TYPE_UNSIGNED (inner_type
) == TYPE_UNSIGNED (outer_type
)
725 && TYPE_PRECISION (inner_type
) == TYPE_PRECISION (outer_type
))
727 bool first_boolean
= (TREE_CODE (inner_type
) == BOOLEAN_TYPE
);
728 bool second_boolean
= (TREE_CODE (outer_type
) == BOOLEAN_TYPE
);
729 if (first_boolean
== second_boolean
)
733 /* Recurse for complex types. */
734 else if (TREE_CODE (inner_type
) == COMPLEX_TYPE
735 && TREE_CODE (outer_type
) == COMPLEX_TYPE
736 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type
),
737 TREE_TYPE (inner_type
)))
743 /* Return true if EXPR is a useless type conversion, otherwise return
747 tree_ssa_useless_type_conversion (tree expr
)
749 /* If we have an assignment that merely uses a NOP_EXPR to change
750 the top of the RHS to the type of the LHS and the type conversion
751 is "safe", then strip away the type conversion so that we can
752 enter LHS = RHS into the const_and_copies table. */
753 if (TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
754 || TREE_CODE (expr
) == VIEW_CONVERT_EXPR
755 || TREE_CODE (expr
) == NON_LVALUE_EXPR
)
756 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr
),
757 TREE_TYPE (TREE_OPERAND (expr
,
765 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
766 described in walk_use_def_chains.
768 VISITED is a bitmap used to mark visited SSA_NAMEs to avoid
771 IS_DFS is true if the caller wants to perform a depth-first search
772 when visiting PHI nodes. A DFS will visit each PHI argument and
773 call FN after each one. Otherwise, all the arguments are
774 visited first and then FN is called with each of the visited
775 arguments in a separate pass. */
778 walk_use_def_chains_1 (tree var
, walk_use_def_chains_fn fn
, void *data
,
779 bitmap visited
, bool is_dfs
)
783 if (bitmap_bit_p (visited
, SSA_NAME_VERSION (var
)))
786 bitmap_set_bit (visited
, SSA_NAME_VERSION (var
));
788 def_stmt
= SSA_NAME_DEF_STMT (var
);
790 if (TREE_CODE (def_stmt
) != PHI_NODE
)
792 /* If we reached the end of the use-def chain, call FN. */
793 return fn (var
, def_stmt
, data
);
799 /* When doing a breadth-first search, call FN before 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
))
806 /* Follow use-def links out of each PHI argument. */
807 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
809 tree arg
= PHI_ARG_DEF (def_stmt
, i
);
810 if (TREE_CODE (arg
) == SSA_NAME
811 && walk_use_def_chains_1 (arg
, fn
, data
, visited
, is_dfs
))
815 /* When doing a depth-first search, call FN after following the
816 use-def links for each argument. */
818 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
819 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
828 /* Walk use-def chains starting at the SSA variable VAR. Call
829 function FN at each reaching definition found. FN takes three
830 arguments: VAR, its defining statement (DEF_STMT) and a generic
831 pointer to whatever state information that FN may want to maintain
832 (DATA). FN is able to stop the walk by returning true, otherwise
833 in order to continue the walk, FN should return false.
835 Note, that if DEF_STMT is a PHI node, the semantics are slightly
836 different. The first argument to FN is no longer the original
837 variable VAR, but the PHI argument currently being examined. If FN
838 wants to get at VAR, it should call PHI_RESULT (PHI).
840 If IS_DFS is true, this function will:
842 1- walk the use-def chains for all the PHI arguments, and,
843 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
845 If IS_DFS is false, the two steps above are done in reverse order
846 (i.e., a breadth-first search). */
850 walk_use_def_chains (tree var
, walk_use_def_chains_fn fn
, void *data
,
855 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
857 def_stmt
= SSA_NAME_DEF_STMT (var
);
859 /* We only need to recurse if the reaching definition comes from a PHI
861 if (TREE_CODE (def_stmt
) != PHI_NODE
)
862 (*fn
) (var
, def_stmt
, data
);
865 bitmap visited
= BITMAP_XMALLOC ();
866 walk_use_def_chains_1 (var
, fn
, data
, visited
, is_dfs
);
867 BITMAP_XFREE (visited
);
872 /* Replaces VAR with REPL in memory reference expression *X in
876 propagate_into_addr (tree stmt
, tree var
, tree
*x
, tree repl
)
878 tree new_var
, ass_stmt
, addr_var
;
880 block_stmt_iterator bsi
;
882 /* There is nothing special to handle in the other cases. */
883 if (TREE_CODE (repl
) != ADDR_EXPR
)
885 addr_var
= TREE_OPERAND (repl
, 0);
887 while (handled_component_p (*x
)
888 || TREE_CODE (*x
) == REALPART_EXPR
889 || TREE_CODE (*x
) == IMAGPART_EXPR
)
890 x
= &TREE_OPERAND (*x
, 0);
892 if (TREE_CODE (*x
) != INDIRECT_REF
893 || TREE_OPERAND (*x
, 0) != var
)
896 if (TREE_TYPE (*x
) == TREE_TYPE (addr_var
))
899 mark_new_vars_to_rename (stmt
, vars_to_rename
);
904 /* Frontends sometimes produce expressions like *&a instead of a[0].
905 Create a temporary variable to handle this case. */
906 ass_stmt
= build2 (MODIFY_EXPR
, void_type_node
, NULL_TREE
, repl
);
907 new_var
= duplicate_ssa_name (var
, ass_stmt
);
908 TREE_OPERAND (*x
, 0) = new_var
;
909 TREE_OPERAND (ass_stmt
, 0) = new_var
;
911 bb
= bb_for_stmt (stmt
);
912 tree_block_label (bb
);
913 bsi
= bsi_after_labels (bb
);
914 bsi_insert_after (&bsi
, ass_stmt
, BSI_NEW_STMT
);
916 mark_new_vars_to_rename (stmt
, vars_to_rename
);
919 /* Replaces immediate uses of VAR by REPL. */
922 replace_immediate_uses (tree var
, tree repl
)
931 df
= get_immediate_uses (SSA_NAME_DEF_STMT (var
));
932 n
= num_immediate_uses (df
);
934 for (i
= 0; i
< n
; i
++)
936 stmt
= immediate_use (df
, i
);
938 if (TREE_CODE (stmt
) == PHI_NODE
)
940 for (j
= 0; j
< PHI_NUM_ARGS (stmt
); j
++)
941 if (PHI_ARG_DEF (stmt
, j
) == var
)
943 SET_PHI_ARG_DEF (stmt
, j
, repl
);
944 if (TREE_CODE (repl
) == SSA_NAME
945 && PHI_ARG_EDGE (stmt
, j
)->flags
& EDGE_ABNORMAL
)
946 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl
) = 1;
952 get_stmt_operands (stmt
);
953 mark_new_vars
= false;
954 if (is_gimple_reg (SSA_NAME_VAR (var
)))
956 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
958 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 0), repl
);
959 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 1), repl
);
962 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
963 if (USE_FROM_PTR (use_p
) == var
)
965 propagate_value (use_p
, repl
);
966 mark_new_vars
= POINTER_TYPE_P (TREE_TYPE (repl
));
971 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
972 if (USE_FROM_PTR (use_p
) == var
)
973 propagate_value (use_p
, repl
);
976 /* If REPL is a pointer, it may have different memory tags associated
977 with it. For instance, VAR may have had a name tag while REPL
978 only had a type tag. In these cases, the virtual operands (if
979 any) in the statement will refer to different symbols which need
982 mark_new_vars_to_rename (stmt
, vars_to_rename
);
988 /* Gets the value VAR is equivalent to according to EQ_TO. */
991 get_eq_name (tree
*eq_to
, tree var
)
996 while (TREE_CODE (val
) == SSA_NAME
)
998 ver
= SSA_NAME_VERSION (val
);
1005 while (TREE_CODE (var
) == SSA_NAME
)
1007 ver
= SSA_NAME_VERSION (var
);
1018 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1019 its result is redundant to to EQ_TO array. */
1022 check_phi_redundancy (tree phi
, tree
*eq_to
)
1024 tree val
= NULL_TREE
, def
, res
= PHI_RESULT (phi
), stmt
;
1025 unsigned i
, ver
= SSA_NAME_VERSION (res
), n
;
1028 /* It is unlikely that such large phi node would be redundant. */
1029 if (PHI_NUM_ARGS (phi
) > 16)
1032 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (phi
); i
++)
1034 def
= PHI_ARG_DEF (phi
, i
);
1036 if (TREE_CODE (def
) == SSA_NAME
)
1038 def
= get_eq_name (eq_to
, def
);
1044 && !operand_equal_p (val
, def
, 0))
1050 /* At least one of the arguments should not be equal to the result, or
1051 something strange is happening. */
1054 if (get_eq_name (eq_to
, res
) == val
)
1057 if (!may_propagate_copy (res
, val
))
1062 df
= get_immediate_uses (SSA_NAME_DEF_STMT (res
));
1063 n
= num_immediate_uses (df
);
1065 for (i
= 0; i
< n
; i
++)
1067 stmt
= immediate_use (df
, i
);
1069 if (TREE_CODE (stmt
) == PHI_NODE
)
1070 check_phi_redundancy (stmt
, eq_to
);
1074 /* Removes redundant phi nodes.
1076 A redundant PHI node is a PHI node where all of its PHI arguments
1077 are the same value, excluding any PHI arguments which are the same
1080 A redundant PHI node is effectively a copy, so we forward copy propagate
1081 which removes all uses of the destination of the PHI node then
1082 finally we delete the redundant PHI node.
1084 Note that if we can not copy propagate the PHI node, then the PHI
1085 will not be removed. Thus we do not have to worry about dependencies
1086 between PHIs and the problems serializing PHIs into copies creates.
1088 The most important effect of this pass is to remove degenerate PHI
1089 nodes created by removing unreachable code. */
1092 kill_redundant_phi_nodes (void)
1095 unsigned i
, old_num_ssa_names
;
1097 tree phi
, var
, repl
, stmt
;
1099 /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1100 replaced. If EQ_TO[VER] is ssa name and it is decided to replace it by
1101 other value, it may be necessary to follow the chain till the final value.
1102 We perform path shortening (replacing the entries of the EQ_TO array with
1103 heads of these chains) whenever we access the field to prevent quadratic
1104 complexity (probably would not occur in practice anyway, but let us play
1106 eq_to
= xcalloc (num_ssa_names
, sizeof (tree
));
1108 /* We have had cases where computing immediate uses takes a
1109 significant amount of compile time. If we run into such
1110 problems here, we may want to only compute immediate uses for
1111 a subset of all the SSA_NAMEs instead of computing it for
1112 all of the SSA_NAMEs. */
1113 compute_immediate_uses (TDFA_USE_OPS
| TDFA_USE_VOPS
, NULL
);
1114 old_num_ssa_names
= num_ssa_names
;
1118 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
1120 var
= PHI_RESULT (phi
);
1121 check_phi_redundancy (phi
, eq_to
);
1125 /* Now propagate the values. */
1126 for (i
= 0; i
< old_num_ssa_names
; i
++)
1131 repl
= get_eq_name (eq_to
, ssa_name (i
));
1132 if (repl
!= ssa_name (i
))
1133 replace_immediate_uses (ssa_name (i
), repl
);
1136 /* And remove the dead phis. */
1137 for (i
= 0; i
< old_num_ssa_names
; i
++)
1142 repl
= get_eq_name (eq_to
, ssa_name (i
));
1143 if (repl
!= ssa_name (i
))
1145 stmt
= SSA_NAME_DEF_STMT (ssa_name (i
));
1146 remove_phi_node (stmt
, NULL_TREE
, bb_for_stmt (stmt
));
1154 struct tree_opt_pass pass_redundant_phi
=
1156 "redphi", /* name */
1158 kill_redundant_phi_nodes
, /* execute */
1161 0, /* static_pass_number */
1163 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
1164 0, /* properties_provided */
1165 0, /* properties_destroyed */
1166 0, /* todo_flags_start */
1167 TODO_dump_func
| TODO_rename_vars
1168 | TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */
1172 /* Emit warnings for uninitialized variables. This is done in two passes.
1174 The first pass notices real uses of SSA names with default definitions.
1175 Such uses are unconditionally uninitialized, and we can be certain that
1176 such a use is a mistake. This pass is run before most optimizations,
1177 so that we catch as many as we can.
1179 The second pass follows PHI nodes to find uses that are potentially
1180 uninitialized. In this case we can't necessarily prove that the use
1181 is really uninitialized. This pass is run after most optimizations,
1182 so that we thread as many jumps and possible, and delete as much dead
1183 code as possible, in order to reduce false positives. We also look
1184 again for plain uninitialized variables, since optimization may have
1185 changed conditionally uninitialized to unconditionally uninitialized. */
1187 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1188 warning text is in MSGID and LOCUS may contain a location or be null. */
1191 warn_uninit (tree t
, const char *msgid
, location_t
*locus
)
1193 tree var
= SSA_NAME_VAR (t
);
1194 tree def
= SSA_NAME_DEF_STMT (t
);
1196 /* Default uses (indicated by an empty definition statement),
1197 are uninitialized. */
1198 if (!IS_EMPTY_STMT (def
))
1201 /* Except for PARMs of course, which are always initialized. */
1202 if (TREE_CODE (var
) == PARM_DECL
)
1205 /* Hard register variables get their initial value from the ether. */
1206 if (DECL_HARD_REGISTER (var
))
1209 /* TREE_NO_WARNING either means we already warned, or the front end
1210 wishes to suppress the warning. */
1211 if (TREE_NO_WARNING (var
))
1215 locus
= &DECL_SOURCE_LOCATION (var
);
1216 warning (msgid
, locus
, var
);
1217 TREE_NO_WARNING (var
) = 1;
1220 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1221 and warn about them. */
1224 warn_uninitialized_var (tree
*tp
, int *walk_subtrees
, void *data
)
1226 location_t
*locus
= data
;
1229 /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */
1230 if (TREE_CODE (t
) == SSA_NAME
)
1232 warn_uninit (t
, "%H'%D' is used uninitialized in this function", locus
);
1235 else if (DECL_P (t
) || TYPE_P (t
))
1241 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1242 and warn about them. */
1245 warn_uninitialized_phi (tree phi
)
1247 int i
, n
= PHI_NUM_ARGS (phi
);
1249 /* Don't look at memory tags. */
1250 if (!is_gimple_reg (PHI_RESULT (phi
)))
1253 for (i
= 0; i
< n
; ++i
)
1255 tree op
= PHI_ARG_DEF (phi
, i
);
1256 if (TREE_CODE (op
) == SSA_NAME
)
1257 warn_uninit (op
, "%H'%D' may be used uninitialized in this function",
1263 execute_early_warn_uninitialized (void)
1265 block_stmt_iterator bsi
;
1269 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1270 walk_tree (bsi_stmt_ptr (bsi
), warn_uninitialized_var
,
1271 EXPR_LOCUS (bsi_stmt (bsi
)), NULL
);
1275 execute_late_warn_uninitialized (void)
1280 /* Re-do the plain uninitialized variable check, as optimization may have
1281 straightened control flow. Do this first so that we don't accidentally
1282 get a "may be" warning when we'd have seen an "is" warning later. */
1283 execute_early_warn_uninitialized ();
1286 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1287 warn_uninitialized_phi (phi
);
1291 gate_warn_uninitialized (void)
1293 return warn_uninitialized
!= 0;
1296 struct tree_opt_pass pass_early_warn_uninitialized
=
1299 gate_warn_uninitialized
, /* gate */
1300 execute_early_warn_uninitialized
, /* execute */
1303 0, /* static_pass_number */
1305 PROP_ssa
, /* properties_required */
1306 0, /* properties_provided */
1307 0, /* properties_destroyed */
1308 0, /* todo_flags_start */
1309 0, /* todo_flags_finish */
1313 struct tree_opt_pass pass_late_warn_uninitialized
=
1316 gate_warn_uninitialized
, /* gate */
1317 execute_late_warn_uninitialized
, /* execute */
1320 0, /* static_pass_number */
1322 PROP_ssa
, /* properties_required */
1323 0, /* properties_provided */
1324 0, /* properties_destroyed */
1325 0, /* todo_flags_start */
1326 0, /* todo_flags_finish */