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 the definition of SSA_NAME at block BB is malformed.
107 STMT is the statement where SSA_NAME is created.
109 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
110 numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
111 block in that array slot contains the definition of SSA_NAME. */
114 verify_def (basic_block bb
, basic_block
*definition_block
, tree ssa_name
,
119 if (TREE_CODE (ssa_name
) != SSA_NAME
)
121 error ("Expected an SSA_NAME object");
122 debug_generic_stmt (ssa_name
);
123 debug_generic_stmt (stmt
);
126 if (definition_block
[SSA_NAME_VERSION (ssa_name
)])
128 error ("SSA_NAME created in two different blocks %i and %i",
129 definition_block
[SSA_NAME_VERSION (ssa_name
)]->index
, bb
->index
);
130 fprintf (stderr
, "SSA_NAME: ");
131 debug_generic_stmt (ssa_name
);
132 debug_generic_stmt (stmt
);
136 definition_block
[SSA_NAME_VERSION (ssa_name
)] = bb
;
138 if (SSA_NAME_DEF_STMT (ssa_name
) != stmt
)
140 error ("SSA_NAME_DEF_STMT is wrong");
141 fprintf (stderr
, "SSA_NAME: ");
142 debug_generic_stmt (ssa_name
);
143 fprintf (stderr
, "Expected definition statement:\n");
144 debug_generic_stmt (SSA_NAME_DEF_STMT (ssa_name
));
145 fprintf (stderr
, "\nActual definition statement:\n");
146 debug_generic_stmt (stmt
);
154 /* Return true if the use of SSA_NAME at statement STMT in block BB is
157 DEF_BB is the block where SSA_NAME was found to be created.
159 IDOM contains immediate dominator information for the flowgraph.
161 CHECK_ABNORMAL is true if the caller wants to check whether this use
162 is flowing through an abnormal edge (only used when checking PHI
166 verify_use (basic_block bb
, basic_block def_bb
, tree ssa_name
,
167 tree stmt
, bool check_abnormal
)
171 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name
)))
172 ; /* Nothing to do. */
175 error ("Missing definition");
178 else if (bb
!= def_bb
179 && !dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
181 error ("Definition in block %i does not dominate use in block %i",
182 def_bb
->index
, bb
->index
);
187 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name
))
189 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
195 fprintf (stderr
, "for SSA_NAME: ");
196 debug_generic_stmt (ssa_name
);
197 fprintf (stderr
, "in statement:\n");
198 debug_generic_stmt (stmt
);
205 /* Return true if any of the arguments for PHI node PHI at block BB is
208 IDOM contains immediate dominator information for the flowgraph.
210 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
211 numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
212 block in that array slot contains the definition of SSA_NAME. */
215 verify_phi_args (tree phi
, basic_block bb
, basic_block
*definition_block
)
219 int i
, phi_num_args
= PHI_NUM_ARGS (phi
);
221 /* Mark all the incoming edges. */
222 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
225 for (i
= 0; i
< phi_num_args
; i
++)
227 tree op
= PHI_ARG_DEF (phi
, i
);
229 e
= PHI_ARG_EDGE (phi
, i
);
231 if (TREE_CODE (op
) == SSA_NAME
)
232 err
|= verify_use (e
->src
, definition_block
[SSA_NAME_VERSION (op
)], op
,
233 phi
, e
->flags
& EDGE_ABNORMAL
);
237 error ("Wrong edge %d->%d for PHI argument\n",
238 e
->src
->index
, e
->dest
->index
, bb
->index
);
242 if (e
->aux
== (void *) 0)
244 error ("PHI argument flowing through dead edge %d->%d\n",
245 e
->src
->index
, e
->dest
->index
);
249 if (e
->aux
== (void *) 2)
251 error ("PHI argument duplicated for edge %d->%d\n", e
->src
->index
,
258 fprintf (stderr
, "PHI argument\n");
259 debug_generic_stmt (op
);
265 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
267 if (e
->aux
!= (void *) 2)
269 error ("No argument flowing through edge %d->%d\n", e
->src
->index
,
278 fprintf (stderr
, "for PHI node\n");
279 debug_generic_stmt (phi
);
287 /* Verify common invariants in the SSA web.
288 TODO: verify the variable annotations. */
295 basic_block
*definition_block
= xcalloc (num_ssa_names
, sizeof (basic_block
));
297 timevar_push (TV_TREE_SSA_VERIFY
);
299 calculate_dominance_info (CDI_DOMINATORS
);
301 /* Verify and register all the SSA_NAME definitions found in the
306 block_stmt_iterator bsi
;
308 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
309 err
|= verify_def (bb
, definition_block
, PHI_RESULT (phi
), phi
);
311 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
316 v_may_def_optype v_may_defs
;
317 v_must_def_optype v_must_defs
;
320 stmt
= bsi_stmt (bsi
);
321 ann
= stmt_ann (stmt
);
322 get_stmt_operands (stmt
);
324 v_may_defs
= V_MAY_DEF_OPS (ann
);
325 if (ann
->makes_aliased_stores
&& NUM_V_MAY_DEFS (v_may_defs
) == 0)
326 error ("Makes aliased stores, but no V_MAY_DEFS");
328 for (j
= 0; j
< NUM_V_MAY_DEFS (v_may_defs
); j
++)
330 tree op
= V_MAY_DEF_RESULT (v_may_defs
, j
);
331 if (is_gimple_reg (op
))
333 error ("Found a virtual definition for a GIMPLE register");
334 debug_generic_stmt (op
);
335 debug_generic_stmt (stmt
);
338 err
|= verify_def (bb
, definition_block
, op
, stmt
);
341 v_must_defs
= STMT_V_MUST_DEF_OPS (stmt
);
342 for (j
= 0; j
< NUM_V_MUST_DEFS (v_must_defs
); j
++)
344 tree op
= V_MUST_DEF_OP (v_must_defs
, j
);
345 if (is_gimple_reg (op
))
347 error ("Found a virtual must-def for a GIMPLE register");
348 debug_generic_stmt (op
);
349 debug_generic_stmt (stmt
);
352 err
|= verify_def (bb
, definition_block
, op
, stmt
);
355 defs
= DEF_OPS (ann
);
356 for (j
= 0; j
< NUM_DEFS (defs
); j
++)
358 tree op
= DEF_OP (defs
, j
);
359 if (TREE_CODE (op
) == SSA_NAME
&& !is_gimple_reg (op
))
361 error ("Found a real definition for a non-GIMPLE register");
362 debug_generic_stmt (op
);
363 debug_generic_stmt (stmt
);
366 err
|= verify_def (bb
, definition_block
, op
, stmt
);
372 /* Now verify all the uses and make sure they agree with the definitions
373 found in the previous pass. */
378 block_stmt_iterator bsi
;
380 /* Make sure that all edges have a clear 'aux' field. */
381 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
385 error ("AUX pointer initialized for edge %d->%d\n", e
->src
->index
,
391 /* Verify the arguments for every PHI node in the block. */
392 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
393 err
|= verify_phi_args (phi
, bb
, definition_block
);
395 /* Now verify all the uses and vuses in every statement of the block.
397 Remember, the RHS of a V_MAY_DEF is a use as well. */
398 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
400 tree stmt
= bsi_stmt (bsi
);
401 stmt_ann_t ann
= stmt_ann (stmt
);
404 v_may_def_optype v_may_defs
;
407 vuses
= VUSE_OPS (ann
);
408 for (j
= 0; j
< NUM_VUSES (vuses
); j
++)
410 tree op
= VUSE_OP (vuses
, j
);
412 if (is_gimple_reg (op
))
414 error ("Found a virtual use for a GIMPLE register");
415 debug_generic_stmt (op
);
416 debug_generic_stmt (stmt
);
419 err
|= verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
423 v_may_defs
= V_MAY_DEF_OPS (ann
);
424 for (j
= 0; j
< NUM_V_MAY_DEFS (v_may_defs
); j
++)
426 tree op
= V_MAY_DEF_OP (v_may_defs
, j
);
428 if (is_gimple_reg (op
))
430 error ("Found a virtual use for a GIMPLE register");
431 debug_generic_stmt (op
);
432 debug_generic_stmt (stmt
);
435 err
|= verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
439 uses
= USE_OPS (ann
);
440 for (j
= 0; j
< NUM_USES (uses
); j
++)
442 tree op
= USE_OP (uses
, j
);
444 if (TREE_CODE (op
) == SSA_NAME
&& !is_gimple_reg (op
))
446 error ("Found a real use of a non-GIMPLE register");
447 debug_generic_stmt (op
);
448 debug_generic_stmt (stmt
);
451 err
|= verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
457 free (definition_block
);
459 timevar_pop (TV_TREE_SSA_VERIFY
);
462 internal_error ("verify_ssa failed.");
466 /* Set the USED bit in the annotation for T. */
476 if (TREE_CODE (t
) == REALPART_EXPR
|| TREE_CODE (t
) == IMAGPART_EXPR
)
477 t
= TREE_OPERAND (t
, 0);
479 while (handled_component_p (t
))
480 t
= TREE_OPERAND (t
, 0);
483 if (TREE_CODE (t
) == SSA_NAME
)
484 t
= SSA_NAME_VAR (t
);
486 var_ann (t
)->used
= 1;
490 /* Initialize global DFA and SSA structures. */
495 VARRAY_TREE_INIT (referenced_vars
, 20, "referenced_vars");
496 call_clobbered_vars
= BITMAP_XMALLOC ();
497 addressable_vars
= BITMAP_XMALLOC ();
498 init_ssa_operands ();
501 global_var
= NULL_TREE
;
502 aliases_computed_p
= false;
506 /* Deallocate memory associated with SSA data structures for FNDECL. */
509 delete_tree_ssa (void)
513 block_stmt_iterator bsi
;
515 /* Remove annotations from every tree in the function. */
517 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
518 bsi_stmt (bsi
)->common
.ann
= NULL
;
520 /* Remove annotations from every referenced variable. */
523 for (i
= 0; i
< num_referenced_vars
; i
++)
524 referenced_var (i
)->common
.ann
= NULL
;
525 referenced_vars
= NULL
;
530 fini_ssa_operands ();
532 global_var
= NULL_TREE
;
533 BITMAP_XFREE (call_clobbered_vars
);
534 call_clobbered_vars
= NULL
;
535 aliases_computed_p
= false;
536 BITMAP_XFREE (addressable_vars
);
537 addressable_vars
= NULL
;
541 /* Return true if EXPR is a useless type conversion, otherwise return
545 tree_ssa_useless_type_conversion_1 (tree outer_type
, tree inner_type
)
547 /* If the inner and outer types are effectively the same, then
548 strip the type conversion and enter the equivalence into
550 if (inner_type
== outer_type
551 || (lang_hooks
.types_compatible_p (inner_type
, outer_type
)))
554 /* If both types are pointers and the outer type is a (void *), then
555 the conversion is not necessary. The opposite is not true since
556 that conversion would result in a loss of information if the
557 equivalence was used. Consider an indirect function call where
558 we need to know the exact type of the function to correctly
559 implement the ABI. */
560 else if (POINTER_TYPE_P (inner_type
)
561 && POINTER_TYPE_P (outer_type
)
562 && TREE_CODE (TREE_TYPE (outer_type
)) == VOID_TYPE
)
565 /* Pointers and references are equivalent once we get to GENERIC,
566 so strip conversions that just switch between them. */
567 else if (POINTER_TYPE_P (inner_type
)
568 && POINTER_TYPE_P (outer_type
)
569 && lang_hooks
.types_compatible_p (TREE_TYPE (inner_type
),
570 TREE_TYPE (outer_type
)))
573 /* If both the inner and outer types are integral types, then the
574 conversion is not necessary if they have the same mode and
575 signedness and precision. Note that type _Bool can have size of
576 4 (only happens on powerpc-darwin right now but can happen on any
577 target that defines BOOL_TYPE_SIZE to be INT_TYPE_SIZE) and a
578 precision of 1 while unsigned int is the same expect for a
579 precision of 4 so testing of precision is necessary. */
580 else if (INTEGRAL_TYPE_P (inner_type
)
581 && INTEGRAL_TYPE_P (outer_type
)
582 && TYPE_MODE (inner_type
) == TYPE_MODE (outer_type
)
583 && TYPE_UNSIGNED (inner_type
) == TYPE_UNSIGNED (outer_type
)
584 && TYPE_PRECISION (inner_type
) == TYPE_PRECISION (outer_type
))
587 /* Recurse for complex types. */
588 else if (TREE_CODE (inner_type
) == COMPLEX_TYPE
589 && TREE_CODE (outer_type
) == COMPLEX_TYPE
590 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type
),
591 TREE_TYPE (inner_type
)))
597 /* Return true if EXPR is a useless type conversion, otherwise return
601 tree_ssa_useless_type_conversion (tree expr
)
603 /* If we have an assignment that merely uses a NOP_EXPR to change
604 the top of the RHS to the type of the LHS and the type conversion
605 is "safe", then strip away the type conversion so that we can
606 enter LHS = RHS into the const_and_copies table. */
607 if (TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
608 || TREE_CODE (expr
) == VIEW_CONVERT_EXPR
609 || TREE_CODE (expr
) == NON_LVALUE_EXPR
)
610 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr
),
611 TREE_TYPE (TREE_OPERAND (expr
,
619 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
620 described in walk_use_def_chains. VISITED is a bitmap used to mark
621 visited SSA_NAMEs to avoid infinite loops. */
624 walk_use_def_chains_1 (tree var
, walk_use_def_chains_fn fn
, void *data
,
629 if (bitmap_bit_p (visited
, SSA_NAME_VERSION (var
)))
632 bitmap_set_bit (visited
, SSA_NAME_VERSION (var
));
634 def_stmt
= SSA_NAME_DEF_STMT (var
);
636 if (TREE_CODE (def_stmt
) != PHI_NODE
)
638 /* If we reached the end of the use-def chain, call FN. */
639 return (*fn
) (var
, def_stmt
, data
);
645 /* Otherwise, follow use-def links out of each PHI argument and call
646 FN after visiting each one. */
647 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
649 tree arg
= PHI_ARG_DEF (def_stmt
, i
);
650 if (TREE_CODE (arg
) == SSA_NAME
651 && walk_use_def_chains_1 (arg
, fn
, data
, visited
))
654 if ((*fn
) (arg
, def_stmt
, data
))
663 /* Walk use-def chains starting at the SSA variable VAR. Call function FN
664 at each reaching definition found. FN takes three arguments: VAR, its
665 defining statement (DEF_STMT) and a generic pointer to whatever state
666 information that FN may want to maintain (DATA). FN is able to stop the
667 walk by returning true, otherwise in order to continue the walk, FN
670 Note, that if DEF_STMT is a PHI node, the semantics are slightly
671 different. For each argument ARG of the PHI node, this function will:
673 1- Walk the use-def chains for ARG.
674 2- Call (*FN) (ARG, PHI, DATA).
676 Note how the first argument to FN is no longer the original variable
677 VAR, but the PHI argument currently being examined. If FN wants to get
678 at VAR, it should call PHI_RESULT (PHI). */
681 walk_use_def_chains (tree var
, walk_use_def_chains_fn fn
, void *data
)
685 #if defined ENABLE_CHECKING
686 if (TREE_CODE (var
) != SSA_NAME
)
690 def_stmt
= SSA_NAME_DEF_STMT (var
);
692 /* We only need to recurse if the reaching definition comes from a PHI
694 if (TREE_CODE (def_stmt
) != PHI_NODE
)
695 (*fn
) (var
, def_stmt
, data
);
698 bitmap visited
= BITMAP_XMALLOC ();
699 walk_use_def_chains_1 (var
, fn
, data
, visited
);
700 BITMAP_XFREE (visited
);
704 /* Replaces VAR with REPL in memory reference expression *X in
708 propagate_into_addr (tree stmt
, tree var
, tree
*x
, tree repl
)
710 tree new_var
, ass_stmt
, addr_var
;
712 block_stmt_iterator bsi
;
714 /* There is nothing special to handle in the other cases. */
715 if (TREE_CODE (repl
) != ADDR_EXPR
)
717 addr_var
= TREE_OPERAND (repl
, 0);
719 while (TREE_CODE (*x
) == ARRAY_REF
720 || TREE_CODE (*x
) == COMPONENT_REF
721 || TREE_CODE (*x
) == BIT_FIELD_REF
)
722 x
= &TREE_OPERAND (*x
, 0);
724 if (TREE_CODE (*x
) != INDIRECT_REF
725 || TREE_OPERAND (*x
, 0) != var
)
729 if (TREE_TYPE (*x
) == TREE_TYPE (addr_var
))
732 mark_new_vars_to_rename (stmt
, vars_to_rename
);
736 /* Frontends sometimes produce expressions like *&a instead of a[0].
737 Create a temporary variable to handle this case. */
738 ass_stmt
= build2 (MODIFY_EXPR
, void_type_node
, NULL_TREE
, repl
);
739 new_var
= duplicate_ssa_name (var
, ass_stmt
);
740 TREE_OPERAND (*x
, 0) = new_var
;
741 TREE_OPERAND (ass_stmt
, 0) = new_var
;
743 bb
= bb_for_stmt (stmt
);
744 tree_block_label (bb
);
745 bsi
= bsi_after_labels (bb
);
746 bsi_insert_after (&bsi
, ass_stmt
, BSI_NEW_STMT
);
748 mark_new_vars_to_rename (stmt
, vars_to_rename
);
751 /* Replaces immediate uses of VAR by REPL. */
754 replace_immediate_uses (tree var
, tree repl
)
758 v_may_def_optype v_may_defs
;
765 df
= get_immediate_uses (SSA_NAME_DEF_STMT (var
));
766 n
= num_immediate_uses (df
);
768 for (i
= 0; i
< n
; i
++)
770 stmt
= immediate_use (df
, i
);
771 ann
= stmt_ann (stmt
);
773 if (TREE_CODE (stmt
) == PHI_NODE
)
775 for (j
= 0; j
< PHI_NUM_ARGS (stmt
); j
++)
776 if (PHI_ARG_DEF (stmt
, j
) == var
)
778 SET_PHI_ARG_DEF (stmt
, j
, repl
);
779 if (TREE_CODE (repl
) == SSA_NAME
780 && PHI_ARG_EDGE (stmt
, j
)->flags
& EDGE_ABNORMAL
)
781 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl
) = 1;
787 get_stmt_operands (stmt
);
788 mark_new_vars
= false;
789 if (is_gimple_reg (SSA_NAME_VAR (var
)))
791 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
793 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 0), repl
);
794 propagate_into_addr (stmt
, var
, &TREE_OPERAND (stmt
, 1), repl
);
797 uses
= USE_OPS (ann
);
798 for (j
= 0; j
< (int) NUM_USES (uses
); j
++)
799 if (USE_OP (uses
, j
) == var
)
801 propagate_value (USE_OP_PTR (uses
, j
), repl
);
802 mark_new_vars
= POINTER_TYPE_P (TREE_TYPE (repl
));
807 vuses
= VUSE_OPS (ann
);
808 for (j
= 0; j
< (int) NUM_VUSES (vuses
); j
++)
809 if (VUSE_OP (vuses
, j
) == var
)
810 propagate_value (VUSE_OP_PTR (vuses
, j
), repl
);
812 v_may_defs
= V_MAY_DEF_OPS (ann
);
813 for (j
= 0; j
< (int) NUM_V_MAY_DEFS (v_may_defs
); j
++)
814 if (V_MAY_DEF_OP (v_may_defs
, j
) == var
)
815 propagate_value (V_MAY_DEF_OP_PTR (v_may_defs
, j
), repl
);
818 /* If REPL is a pointer, it may have different memory tags associated
819 with it. For instance, VAR may have had a name tag while REPL
820 only had a type tag. In these cases, the virtual operands (if
821 any) in the statement will refer to different symbols which need
824 mark_new_vars_to_rename (stmt
, vars_to_rename
);
830 /* Gets the value VAR is equivalent to according to EQ_TO. */
833 get_eq_name (tree
*eq_to
, tree var
)
838 while (TREE_CODE (val
) == SSA_NAME
)
840 ver
= SSA_NAME_VERSION (val
);
847 while (TREE_CODE (var
) == SSA_NAME
)
849 ver
= SSA_NAME_VERSION (var
);
860 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
861 its result is redundant to to EQ_TO array. */
864 check_phi_redundancy (tree phi
, tree
*eq_to
)
866 tree val
= NULL_TREE
, def
, res
= PHI_RESULT (phi
), stmt
;
867 unsigned i
, ver
= SSA_NAME_VERSION (res
), n
;
870 /* It is unlikely that such large phi node would be redundant. */
871 if (PHI_NUM_ARGS (phi
) > 16)
874 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (phi
); i
++)
876 def
= PHI_ARG_DEF (phi
, i
);
878 if (TREE_CODE (def
) == SSA_NAME
)
880 def
= get_eq_name (eq_to
, def
);
886 && !operand_equal_p (val
, def
, 0))
892 /* At least one of the arguments should not be equal to the result, or
893 something strange is happening. */
897 if (get_eq_name (eq_to
, res
) == val
)
900 if (!may_propagate_copy (res
, val
))
905 df
= get_immediate_uses (SSA_NAME_DEF_STMT (res
));
906 n
= num_immediate_uses (df
);
908 for (i
= 0; i
< n
; i
++)
910 stmt
= immediate_use (df
, i
);
912 if (TREE_CODE (stmt
) == PHI_NODE
)
913 check_phi_redundancy (stmt
, eq_to
);
917 /* Removes redundant phi nodes.
919 A redundant PHI node is a PHI node where all of its PHI arguments
920 are the same value, excluding any PHI arguments which are the same
923 A redundant PHI node is effectively a copy, so we forward copy propagate
924 which removes all uses of the destination of the PHI node then
925 finally we delete the redundant PHI node.
927 Note that if we can not copy propagate the PHI node, then the PHI
928 will not be removed. Thus we do not have to worry about dependencies
929 between PHIs and the problems serializing PHIs into copies creates.
931 The most important effect of this pass is to remove degenerate PHI
932 nodes created by removing unreachable code. */
935 kill_redundant_phi_nodes (void)
938 unsigned i
, old_num_ssa_names
;
940 tree phi
, var
, repl
, stmt
;
942 /* The EQ_TO[VER] holds the value by that the ssa name VER should be
943 replaced. If EQ_TO[VER] is ssa name and it is decided to replace it by
944 other value, it may be necessary to follow the chain till the final value.
945 We perform path shortening (replacing the entries of the EQ_TO array with
946 heads of these chains) whenever we access the field to prevent quadratic
947 complexity (probably would not occur in practice anyway, but let us play
949 eq_to
= xcalloc (num_ssa_names
, sizeof (tree
));
951 /* We have had cases where computing immediate uses takes a
952 significant amount of compile time. If we run into such
953 problems here, we may want to only compute immediate uses for
954 a subset of all the SSA_NAMEs instead of computing it for
955 all of the SSA_NAMEs. */
956 compute_immediate_uses (TDFA_USE_OPS
| TDFA_USE_VOPS
, NULL
);
957 old_num_ssa_names
= num_ssa_names
;
961 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
963 var
= PHI_RESULT (phi
);
964 check_phi_redundancy (phi
, eq_to
);
968 /* Now propagate the values. */
969 for (i
= 0; i
< old_num_ssa_names
; i
++)
974 repl
= get_eq_name (eq_to
, ssa_name (i
));
975 if (repl
!= ssa_name (i
))
976 replace_immediate_uses (ssa_name (i
), repl
);
979 /* And remove the dead phis. */
980 for (i
= 0; i
< old_num_ssa_names
; i
++)
985 repl
= get_eq_name (eq_to
, ssa_name (i
));
986 if (repl
!= ssa_name (i
))
988 stmt
= SSA_NAME_DEF_STMT (ssa_name (i
));
989 remove_phi_node (stmt
, NULL_TREE
, bb_for_stmt (stmt
));
997 struct tree_opt_pass pass_redundant_phi
=
1001 kill_redundant_phi_nodes
, /* execute */
1004 0, /* static_pass_number */
1006 PROP_cfg
| PROP_ssa
, /* properties_required */
1007 0, /* properties_provided */
1008 0, /* properties_destroyed */
1009 0, /* todo_flags_start */
1010 TODO_dump_func
| TODO_rename_vars
1011 | TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */
1014 /* Emit warnings for uninitialized variables. This is done in two passes.
1016 The first pass notices real uses of SSA names with default definitions.
1017 Such uses are unconditionally uninitialized, and we can be certain that
1018 such a use is a mistake. This pass is run before most optimizations,
1019 so that we catch as many as we can.
1021 The second pass follows PHI nodes to find uses that are potentially
1022 uninitialized. In this case we can't necessarily prove that the use
1023 is really uninitialized. This pass is run after most optimizations,
1024 so that we thread as many jumps and possible, and delete as much dead
1025 code as possible, in order to reduce false positives. We also look
1026 again for plain uninitialized variables, since optimization may have
1027 changed conditionally uninitialized to unconditionally uninitialized. */
1029 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1030 warning text is in MSGID and LOCUS may contain a location or be null. */
1033 warn_uninit (tree t
, const char *msgid
, location_t
*locus
)
1035 tree var
= SSA_NAME_VAR (t
);
1036 tree def
= SSA_NAME_DEF_STMT (t
);
1038 /* Default uses (indicated by an empty definition statement),
1039 are uninitialized. */
1040 if (!IS_EMPTY_STMT (def
))
1043 /* Except for PARMs of course, which are always initialized. */
1044 if (TREE_CODE (var
) == PARM_DECL
)
1047 /* Hard register variables get their initial value from the ether. */
1048 if (DECL_HARD_REGISTER (var
))
1051 /* TREE_NO_WARNING either means we already warned, or the front end
1052 wishes to suppress the warning. */
1053 if (TREE_NO_WARNING (var
))
1057 locus
= &DECL_SOURCE_LOCATION (var
);
1058 warning (msgid
, locus
, var
);
1059 TREE_NO_WARNING (var
) = 1;
1062 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1063 and warn about them. */
1066 warn_uninitialized_var (tree
*tp
, int *walk_subtrees
, void *data
)
1068 location_t
*locus
= data
;
1071 /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */
1072 if (TREE_CODE (t
) == SSA_NAME
)
1074 warn_uninit (t
, "%H'%D' is used uninitialized in this function", locus
);
1077 else if (DECL_P (t
) || TYPE_P (t
))
1083 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1084 and warn about them. */
1087 warn_uninitialized_phi (tree phi
)
1089 int i
, n
= PHI_NUM_ARGS (phi
);
1091 /* Don't look at memory tags. */
1092 if (!is_gimple_reg (PHI_RESULT (phi
)))
1095 for (i
= 0; i
< n
; ++i
)
1097 tree op
= PHI_ARG_DEF (phi
, i
);
1098 if (TREE_CODE (op
) == SSA_NAME
)
1099 warn_uninit (op
, "%H'%D' may be used uninitialized in this function",
1105 execute_early_warn_uninitialized (void)
1107 block_stmt_iterator bsi
;
1111 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1112 walk_tree (bsi_stmt_ptr (bsi
), warn_uninitialized_var
,
1113 EXPR_LOCUS (bsi_stmt (bsi
)), NULL
);
1117 execute_late_warn_uninitialized (void)
1122 /* Re-do the plain uninitialized variable check, as optimization may have
1123 straightened control flow. Do this first so that we don't accidentally
1124 get a "may be" warning when we'd have seen an "is" warning later. */
1125 execute_early_warn_uninitialized ();
1128 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1129 warn_uninitialized_phi (phi
);
1133 gate_warn_uninitialized (void)
1135 return warn_uninitialized
!= 0;
1138 struct tree_opt_pass pass_early_warn_uninitialized
=
1141 gate_warn_uninitialized
, /* gate */
1142 execute_early_warn_uninitialized
, /* execute */
1145 0, /* static_pass_number */
1147 PROP_ssa
, /* properties_required */
1148 0, /* properties_provided */
1149 0, /* properties_destroyed */
1150 0, /* todo_flags_start */
1151 0 /* todo_flags_finish */
1154 struct tree_opt_pass pass_late_warn_uninitialized
=
1157 gate_warn_uninitialized
, /* gate */
1158 execute_late_warn_uninitialized
, /* execute */
1161 0, /* static_pass_number */
1163 PROP_ssa
, /* properties_required */
1164 0, /* properties_provided */
1165 0, /* properties_destroyed */
1166 0, /* todo_flags_start */
1167 0 /* todo_flags_finish */