1 /* Miscellaneous SSA utility functions.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
30 #include "langhooks.h"
31 #include "basic-block.h"
34 #include "tree-pretty-print.h"
35 #include "gimple-pretty-print.h"
37 #include "pointer-set.h"
38 #include "tree-flow.h"
40 #include "tree-inline.h"
43 #include "tree-dump.h"
44 #include "tree-pass.h"
45 #include "diagnostic-core.h"
47 /* Pointer map of variable mappings, keyed by edge. */
48 static struct pointer_map_t
*edge_var_maps
;
51 /* Add a mapping with PHI RESULT and PHI DEF associated with edge E. */
54 redirect_edge_var_map_add (edge e
, tree result
, tree def
, source_location locus
)
57 edge_var_map_vector old_head
, head
;
58 edge_var_map new_node
;
60 if (edge_var_maps
== NULL
)
61 edge_var_maps
= pointer_map_create ();
63 slot
= pointer_map_insert (edge_var_maps
, e
);
64 old_head
= head
= (edge_var_map_vector
) *slot
;
67 head
= VEC_alloc (edge_var_map
, heap
, 5);
71 new_node
.result
= result
;
72 new_node
.locus
= locus
;
74 VEC_safe_push (edge_var_map
, heap
, head
, &new_node
);
77 /* The push did some reallocation. Update the pointer map. */
83 /* Clear the var mappings in edge E. */
86 redirect_edge_var_map_clear (edge e
)
89 edge_var_map_vector head
;
94 slot
= pointer_map_contains (edge_var_maps
, e
);
98 head
= (edge_var_map_vector
) *slot
;
99 VEC_free (edge_var_map
, heap
, head
);
105 /* Duplicate the redirected var mappings in OLDE in NEWE.
107 Since we can't remove a mapping, let's just duplicate it. This assumes a
108 pointer_map can have multiple edges mapping to the same var_map (many to
109 one mapping), since we don't remove the previous mappings. */
112 redirect_edge_var_map_dup (edge newe
, edge olde
)
114 void **new_slot
, **old_slot
;
115 edge_var_map_vector head
;
120 new_slot
= pointer_map_insert (edge_var_maps
, newe
);
121 old_slot
= pointer_map_contains (edge_var_maps
, olde
);
124 head
= (edge_var_map_vector
) *old_slot
;
127 *new_slot
= VEC_copy (edge_var_map
, heap
, head
);
129 *new_slot
= VEC_alloc (edge_var_map
, heap
, 5);
133 /* Return the variable mappings for a given edge. If there is none, return
137 redirect_edge_var_map_vector (edge e
)
141 /* Hey, what kind of idiot would... you'd be surprised. */
145 slot
= pointer_map_contains (edge_var_maps
, e
);
149 return (edge_var_map_vector
) *slot
;
152 /* Used by redirect_edge_var_map_destroy to free all memory. */
155 free_var_map_entry (const void *key ATTRIBUTE_UNUSED
,
157 void *data ATTRIBUTE_UNUSED
)
159 edge_var_map_vector head
= (edge_var_map_vector
) *value
;
160 VEC_free (edge_var_map
, heap
, head
);
164 /* Clear the edge variable mappings. */
167 redirect_edge_var_map_destroy (void)
171 pointer_map_traverse (edge_var_maps
, free_var_map_entry
, NULL
);
172 pointer_map_destroy (edge_var_maps
);
173 edge_var_maps
= NULL
;
178 /* Remove the corresponding arguments from the PHI nodes in E's
179 destination block and redirect it to DEST. Return redirected edge.
180 The list of removed arguments is stored in a vector accessed
181 through edge_var_maps. */
184 ssa_redirect_edge (edge e
, basic_block dest
)
186 gimple_stmt_iterator gsi
;
189 redirect_edge_var_map_clear (e
);
191 /* Remove the appropriate PHI arguments in E's destination block. */
192 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
195 source_location locus
;
197 phi
= gsi_stmt (gsi
);
198 def
= gimple_phi_arg_def (phi
, e
->dest_idx
);
199 locus
= gimple_phi_arg_location (phi
, e
->dest_idx
);
201 if (def
== NULL_TREE
)
204 redirect_edge_var_map_add (e
, gimple_phi_result (phi
), def
, locus
);
207 e
= redirect_edge_succ_nodup (e
, dest
);
213 /* Add PHI arguments queued in PENDING_STMT list on edge E to edge
217 flush_pending_stmts (edge e
)
220 edge_var_map_vector v
;
223 gimple_stmt_iterator gsi
;
225 v
= redirect_edge_var_map_vector (e
);
229 for (gsi
= gsi_start_phis (e
->dest
), i
= 0;
230 !gsi_end_p (gsi
) && VEC_iterate (edge_var_map
, v
, i
, vm
);
231 gsi_next (&gsi
), i
++)
235 phi
= gsi_stmt (gsi
);
236 def
= redirect_edge_var_map_def (vm
);
237 add_phi_arg (phi
, def
, e
, redirect_edge_var_map_location (vm
));
240 redirect_edge_var_map_clear (e
);
243 /* Given a tree for an expression for which we might want to emit
244 locations or values in debug information (generally a variable, but
245 we might deal with other kinds of trees in the future), return the
246 tree that should be used as the variable of a DEBUG_BIND STMT or
247 VAR_LOCATION INSN or NOTE. Return NULL if VAR is not to be tracked. */
250 target_for_debug_bind (tree var
)
252 if (!MAY_HAVE_DEBUG_STMTS
)
255 if (TREE_CODE (var
) != VAR_DECL
256 && TREE_CODE (var
) != PARM_DECL
)
259 if (DECL_HAS_VALUE_EXPR_P (var
))
260 return target_for_debug_bind (DECL_VALUE_EXPR (var
));
262 if (DECL_IGNORED_P (var
))
265 if (!is_gimple_reg (var
))
271 /* Called via walk_tree, look for SSA_NAMEs that have already been
275 find_released_ssa_name (tree
*tp
, int *walk_subtrees
, void *data_
)
277 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data_
;
279 if (wi
&& wi
->is_lhs
)
282 if (TREE_CODE (*tp
) == SSA_NAME
)
284 if (SSA_NAME_IN_FREE_LIST (*tp
))
289 else if (IS_TYPE_OR_DECL_P (*tp
))
295 /* Insert a DEBUG BIND stmt before the DEF of VAR if VAR is referenced
296 by other DEBUG stmts, and replace uses of the DEF with the
297 newly-created debug temp. */
300 insert_debug_temp_for_var_def (gimple_stmt_iterator
*gsi
, tree var
)
302 imm_use_iterator imm_iter
;
305 gimple def_stmt
= NULL
;
309 if (!MAY_HAVE_DEBUG_STMTS
)
312 /* If this name has already been registered for replacement, do nothing
313 as anything that uses this name isn't in SSA form. */
314 if (name_registered_for_update_p (var
))
317 /* Check whether there are debug stmts that reference this variable and,
318 if there are, decide whether we should use a debug temp. */
319 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, var
)
321 stmt
= USE_STMT (use_p
);
323 if (!gimple_debug_bind_p (stmt
))
329 if (gimple_debug_bind_get_value (stmt
) != var
)
331 /* Count this as an additional use, so as to make sure we
332 use a temp unless VAR's definition has a SINGLE_RHS that
343 def_stmt
= gsi_stmt (*gsi
);
345 def_stmt
= SSA_NAME_DEF_STMT (var
);
347 /* If we didn't get an insertion point, and the stmt has already
348 been removed, we won't be able to insert the debug bind stmt, so
349 we'll have to drop debug information. */
350 if (gimple_code (def_stmt
) == GIMPLE_PHI
)
352 value
= degenerate_phi_result (def_stmt
);
353 if (value
&& walk_tree (&value
, find_released_ssa_name
, NULL
, NULL
))
355 /* error_mark_node is what fixup_noreturn_call changes PHI arguments
357 else if (value
== error_mark_node
)
360 else if (is_gimple_assign (def_stmt
))
362 bool no_value
= false;
364 if (!dom_info_available_p (CDI_DOMINATORS
))
366 struct walk_stmt_info wi
;
368 memset (&wi
, 0, sizeof (wi
));
370 /* When removing blocks without following reverse dominance
371 order, we may sometimes encounter SSA_NAMEs that have
372 already been released, referenced in other SSA_DEFs that
373 we're about to release. Consider:
382 If we deleted BB X first, propagating the value of w_2
383 won't do us any good. It's too late to recover their
384 original definition of v_1: when it was deleted, it was
385 only referenced in other DEFs, it couldn't possibly know
386 it should have been retained, and propagating every
387 single DEF just in case it might have to be propagated
388 into a DEBUG STMT would probably be too wasteful.
390 When dominator information is not readily available, we
391 check for and accept some loss of debug information. But
392 if it is available, there's no excuse for us to remove
393 blocks in the wrong order, so we don't even check for
394 dead SSA NAMEs. SSA verification shall catch any
396 if ((!gsi
&& !gimple_bb (def_stmt
))
397 || walk_gimple_op (def_stmt
, find_released_ssa_name
, &wi
))
402 value
= gimple_assign_rhs_to_tree (def_stmt
);
407 /* If there's a single use of VAR, and VAR is the entire debug
408 expression (usecount would have been incremented again
409 otherwise), and the definition involves only constants and
410 SSA names, then we can propagate VALUE into this single use,
413 We can also avoid using a temp if VALUE can be shared and
414 propagated into all uses, without generating expressions that
415 wouldn't be valid gimple RHSs.
417 Other cases that would require unsharing or non-gimple RHSs
418 are deferred to a debug temp, although we could avoid temps
419 at the expense of duplication of expressions. */
421 if (CONSTANT_CLASS_P (value
)
422 || gimple_code (def_stmt
) == GIMPLE_PHI
424 && (!gimple_assign_single_p (def_stmt
)
425 || is_gimple_min_invariant (value
)))
426 || is_gimple_reg (value
))
427 value
= unshare_expr (value
);
431 tree vexpr
= make_node (DEBUG_EXPR_DECL
);
433 def_temp
= gimple_build_debug_bind (vexpr
,
434 unshare_expr (value
),
437 DECL_ARTIFICIAL (vexpr
) = 1;
438 TREE_TYPE (vexpr
) = TREE_TYPE (value
);
440 DECL_MODE (vexpr
) = DECL_MODE (value
);
442 DECL_MODE (vexpr
) = TYPE_MODE (TREE_TYPE (value
));
445 gsi_insert_before (gsi
, def_temp
, GSI_SAME_STMT
);
448 gimple_stmt_iterator ngsi
= gsi_for_stmt (def_stmt
);
449 gsi_insert_before (&ngsi
, def_temp
, GSI_SAME_STMT
);
456 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, var
)
458 if (!gimple_debug_bind_p (stmt
))
463 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
464 /* unshare_expr is not needed here. vexpr is either a
465 SINGLE_RHS, that can be safely shared, some other RHS
466 that was unshared when we found it had a single debug
467 use, or a DEBUG_EXPR_DECL, that can be safely
469 SET_USE (use_p
, value
);
470 /* If we didn't replace uses with a debug decl fold the
471 resulting expression. Otherwise we end up with invalid IL. */
472 if (TREE_CODE (value
) != DEBUG_EXPR_DECL
)
473 fold_stmt_inplace (stmt
);
476 gimple_debug_bind_reset_value (stmt
);
483 /* Insert a DEBUG BIND stmt before STMT for each DEF referenced by
484 other DEBUG stmts, and replace uses of the DEF with the
485 newly-created debug temp. */
488 insert_debug_temps_for_defs (gimple_stmt_iterator
*gsi
)
494 if (!MAY_HAVE_DEBUG_STMTS
)
497 stmt
= gsi_stmt (*gsi
);
499 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
501 tree var
= DEF_FROM_PTR (def_p
);
503 if (TREE_CODE (var
) != SSA_NAME
)
506 insert_debug_temp_for_var_def (gsi
, var
);
510 /* Reset all debug stmts that use SSA_NAME(s) defined in STMT. */
513 reset_debug_uses (gimple stmt
)
517 imm_use_iterator imm_iter
;
520 if (!MAY_HAVE_DEBUG_STMTS
)
523 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
525 tree var
= DEF_FROM_PTR (def_p
);
527 if (TREE_CODE (var
) != SSA_NAME
)
530 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, var
)
532 if (!gimple_debug_bind_p (use_stmt
))
535 gimple_debug_bind_reset_value (use_stmt
);
536 update_stmt (use_stmt
);
541 /* Delete SSA DEFs for SSA versions in the TOREMOVE bitmap, removing
542 dominated stmts before their dominators, so that release_ssa_defs
543 stands a chance of propagating DEFs into debug bind stmts. */
546 release_defs_bitset (bitmap toremove
)
551 /* Performing a topological sort is probably overkill, this will
552 most likely run in slightly superlinear time, rather than the
553 pathological quadratic worst case. */
554 while (!bitmap_empty_p (toremove
))
555 EXECUTE_IF_SET_IN_BITMAP (toremove
, 0, j
, bi
)
557 bool remove_now
= true;
558 tree var
= ssa_name (j
);
560 imm_use_iterator uit
;
562 FOR_EACH_IMM_USE_STMT (stmt
, uit
, var
)
567 /* We can't propagate PHI nodes into debug stmts. */
568 if (gimple_code (stmt
) == GIMPLE_PHI
569 || is_gimple_debug (stmt
))
572 /* If we find another definition to remove that uses
573 the one we're looking at, defer the removal of this
574 one, so that it can be propagated into debug stmts
575 after the other is. */
576 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, dit
, SSA_OP_DEF
)
578 tree odef
= DEF_FROM_PTR (def_p
);
580 if (bitmap_bit_p (toremove
, SSA_NAME_VERSION (odef
)))
588 BREAK_FROM_IMM_USE_STMT (uit
);
593 gimple def
= SSA_NAME_DEF_STMT (var
);
594 gimple_stmt_iterator gsi
= gsi_for_stmt (def
);
596 if (gimple_code (def
) == GIMPLE_PHI
)
597 remove_phi_node (&gsi
, true);
600 gsi_remove (&gsi
, true);
604 bitmap_clear_bit (toremove
, j
);
609 /* Return true if SSA_NAME is malformed and mark it visited.
611 IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
615 verify_ssa_name (tree ssa_name
, bool is_virtual
)
617 if (TREE_CODE (ssa_name
) != SSA_NAME
)
619 error ("expected an SSA_NAME object");
623 if (TREE_TYPE (ssa_name
) != TREE_TYPE (SSA_NAME_VAR (ssa_name
)))
625 error ("type mismatch between an SSA_NAME and its symbol");
629 if (SSA_NAME_IN_FREE_LIST (ssa_name
))
631 error ("found an SSA_NAME that had been released into the free pool");
635 if (is_virtual
&& is_gimple_reg (ssa_name
))
637 error ("found a virtual definition for a GIMPLE register");
641 if (is_virtual
&& SSA_NAME_VAR (ssa_name
) != gimple_vop (cfun
))
643 error ("virtual SSA name for non-VOP decl");
647 if (!is_virtual
&& !is_gimple_reg (ssa_name
))
649 error ("found a real definition for a non-register");
653 if (SSA_NAME_IS_DEFAULT_DEF (ssa_name
)
654 && !gimple_nop_p (SSA_NAME_DEF_STMT (ssa_name
)))
656 error ("found a default name with a non-empty defining statement");
664 /* Return true if the definition of SSA_NAME at block BB is malformed.
666 STMT is the statement where SSA_NAME is created.
668 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
669 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
670 it means that the block in that array slot contains the
671 definition of SSA_NAME.
673 IS_VIRTUAL is true if SSA_NAME is created by a VDEF. */
676 verify_def (basic_block bb
, basic_block
*definition_block
, tree ssa_name
,
677 gimple stmt
, bool is_virtual
)
679 if (verify_ssa_name (ssa_name
, is_virtual
))
682 if (TREE_CODE (SSA_NAME_VAR (ssa_name
)) == RESULT_DECL
683 && DECL_BY_REFERENCE (SSA_NAME_VAR (ssa_name
)))
685 error ("RESULT_DECL should be read only when DECL_BY_REFERENCE is set");
689 if (definition_block
[SSA_NAME_VERSION (ssa_name
)])
691 error ("SSA_NAME created in two different blocks %i and %i",
692 definition_block
[SSA_NAME_VERSION (ssa_name
)]->index
, bb
->index
);
696 definition_block
[SSA_NAME_VERSION (ssa_name
)] = bb
;
698 if (SSA_NAME_DEF_STMT (ssa_name
) != stmt
)
700 error ("SSA_NAME_DEF_STMT is wrong");
701 fprintf (stderr
, "Expected definition statement:\n");
702 print_gimple_stmt (stderr
, SSA_NAME_DEF_STMT (ssa_name
), 4, TDF_VOPS
);
703 fprintf (stderr
, "\nActual definition statement:\n");
704 print_gimple_stmt (stderr
, stmt
, 4, TDF_VOPS
);
711 fprintf (stderr
, "while verifying SSA_NAME ");
712 print_generic_expr (stderr
, ssa_name
, 0);
713 fprintf (stderr
, " in statement\n");
714 print_gimple_stmt (stderr
, stmt
, 4, TDF_VOPS
);
720 /* Return true if the use of SSA_NAME at statement STMT in block BB is
723 DEF_BB is the block where SSA_NAME was found to be created.
725 IDOM contains immediate dominator information for the flowgraph.
727 CHECK_ABNORMAL is true if the caller wants to check whether this use
728 is flowing through an abnormal edge (only used when checking PHI
731 If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
732 that are defined before STMT in basic block BB. */
735 verify_use (basic_block bb
, basic_block def_bb
, use_operand_p use_p
,
736 gimple stmt
, bool check_abnormal
, bitmap names_defined_in_bb
)
739 tree ssa_name
= USE_FROM_PTR (use_p
);
741 if (!TREE_VISITED (ssa_name
))
742 if (verify_imm_links (stderr
, ssa_name
))
745 TREE_VISITED (ssa_name
) = 1;
747 if (gimple_nop_p (SSA_NAME_DEF_STMT (ssa_name
))
748 && SSA_NAME_IS_DEFAULT_DEF (ssa_name
))
749 ; /* Default definitions have empty statements. Nothing to do. */
752 error ("missing definition");
755 else if (bb
!= def_bb
756 && !dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
758 error ("definition in block %i does not dominate use in block %i",
759 def_bb
->index
, bb
->index
);
762 else if (bb
== def_bb
763 && names_defined_in_bb
!= NULL
764 && !bitmap_bit_p (names_defined_in_bb
, SSA_NAME_VERSION (ssa_name
)))
766 error ("definition in block %i follows the use", def_bb
->index
);
771 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name
))
773 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
777 /* Make sure the use is in an appropriate list by checking the previous
778 element to make sure it's the same. */
779 if (use_p
->prev
== NULL
)
781 error ("no immediate_use list");
787 if (use_p
->prev
->use
== NULL
)
788 listvar
= use_p
->prev
->loc
.ssa_name
;
790 listvar
= USE_FROM_PTR (use_p
->prev
);
791 if (listvar
!= ssa_name
)
793 error ("wrong immediate use list");
800 fprintf (stderr
, "for SSA_NAME: ");
801 print_generic_expr (stderr
, ssa_name
, TDF_VOPS
);
802 fprintf (stderr
, " in statement:\n");
803 print_gimple_stmt (stderr
, stmt
, 0, TDF_VOPS
);
810 /* Return true if any of the arguments for PHI node PHI at block BB is
813 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
814 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
815 it means that the block in that array slot contains the
816 definition of SSA_NAME. */
819 verify_phi_args (gimple phi
, basic_block bb
, basic_block
*definition_block
)
823 size_t i
, phi_num_args
= gimple_phi_num_args (phi
);
825 if (EDGE_COUNT (bb
->preds
) != phi_num_args
)
827 error ("incoming edge count does not match number of PHI arguments");
832 for (i
= 0; i
< phi_num_args
; i
++)
834 use_operand_p op_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
835 tree op
= USE_FROM_PTR (op_p
);
837 e
= EDGE_PRED (bb
, i
);
841 error ("PHI argument is missing for edge %d->%d",
848 if (TREE_CODE (op
) != SSA_NAME
&& !is_gimple_min_invariant (op
))
850 error ("PHI argument is not SSA_NAME, or invariant");
854 if (TREE_CODE (op
) == SSA_NAME
)
856 err
= verify_ssa_name (op
, !is_gimple_reg (gimple_phi_result (phi
)));
857 err
|= verify_use (e
->src
, definition_block
[SSA_NAME_VERSION (op
)],
858 op_p
, phi
, e
->flags
& EDGE_ABNORMAL
, NULL
);
861 if (TREE_CODE (op
) == ADDR_EXPR
)
863 tree base
= TREE_OPERAND (op
, 0);
864 while (handled_component_p (base
))
865 base
= TREE_OPERAND (base
, 0);
866 if ((TREE_CODE (base
) == VAR_DECL
867 || TREE_CODE (base
) == PARM_DECL
868 || TREE_CODE (base
) == RESULT_DECL
)
869 && !TREE_ADDRESSABLE (base
))
871 error ("address taken, but ADDRESSABLE bit not set");
878 error ("wrong edge %d->%d for PHI argument",
879 e
->src
->index
, e
->dest
->index
);
885 fprintf (stderr
, "PHI argument\n");
886 print_generic_stmt (stderr
, op
, TDF_VOPS
);
894 fprintf (stderr
, "for PHI node\n");
895 print_gimple_stmt (stderr
, phi
, 0, TDF_VOPS
|TDF_MEMSYMS
);
903 /* Verify common invariants in the SSA web.
904 TODO: verify the variable annotations. */
907 verify_ssa (bool check_modified_stmt
)
911 basic_block
*definition_block
= XCNEWVEC (basic_block
, num_ssa_names
);
914 enum dom_state orig_dom_state
= dom_info_state (CDI_DOMINATORS
);
915 bitmap names_defined_in_bb
= BITMAP_ALLOC (NULL
);
917 gcc_assert (!need_ssa_update_p (cfun
));
919 verify_gimple_in_cfg (cfun
);
921 timevar_push (TV_TREE_SSA_VERIFY
);
923 /* Keep track of SSA names present in the IL. */
924 for (i
= 1; i
< num_ssa_names
; i
++)
926 tree name
= ssa_name (i
);
930 TREE_VISITED (name
) = 0;
932 stmt
= SSA_NAME_DEF_STMT (name
);
933 if (!gimple_nop_p (stmt
))
935 basic_block bb
= gimple_bb (stmt
);
936 verify_def (bb
, definition_block
,
937 name
, stmt
, !is_gimple_reg (name
));
943 calculate_dominance_info (CDI_DOMINATORS
);
945 /* Now verify all the uses and make sure they agree with the definitions
946 found in the previous pass. */
952 gimple_stmt_iterator gsi
;
954 /* Make sure that all edges have a clear 'aux' field. */
955 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
959 error ("AUX pointer initialized for edge %d->%d", e
->src
->index
,
965 /* Verify the arguments for every PHI node in the block. */
966 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
968 phi
= gsi_stmt (gsi
);
969 if (verify_phi_args (phi
, bb
, definition_block
))
972 bitmap_set_bit (names_defined_in_bb
,
973 SSA_NAME_VERSION (gimple_phi_result (phi
)));
976 /* Now verify all the uses and vuses in every statement of the block. */
977 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
979 gimple stmt
= gsi_stmt (gsi
);
985 if (check_modified_stmt
&& gimple_modified_p (stmt
))
987 error ("stmt (%p) marked modified after optimization pass: ",
989 print_gimple_stmt (stderr
, stmt
, 0, TDF_VOPS
);
993 if (is_gimple_assign (stmt
)
994 && TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
996 tree lhs
, base_address
;
998 lhs
= gimple_assign_lhs (stmt
);
999 base_address
= get_base_address (lhs
);
1002 && SSA_VAR_P (base_address
)
1003 && !gimple_vdef (stmt
)
1006 error ("statement makes a memory store, but has no VDEFS");
1007 print_gimple_stmt (stderr
, stmt
, 0, TDF_VOPS
);
1011 else if (gimple_debug_bind_p (stmt
)
1012 && !gimple_debug_bind_has_value_p (stmt
))
1015 /* Verify the single virtual operand and its constraints. */
1017 if (gimple_vdef (stmt
))
1019 if (gimple_vdef_op (stmt
) == NULL_DEF_OPERAND_P
)
1021 error ("statement has VDEF operand not in defs list");
1024 if (!gimple_vuse (stmt
))
1026 error ("statement has VDEF but no VUSE operand");
1029 else if (SSA_NAME_VAR (gimple_vdef (stmt
))
1030 != SSA_NAME_VAR (gimple_vuse (stmt
)))
1032 error ("VDEF and VUSE do not use the same symbol");
1035 has_err
|= verify_ssa_name (gimple_vdef (stmt
), true);
1037 if (gimple_vuse (stmt
))
1039 if (gimple_vuse_op (stmt
) == NULL_USE_OPERAND_P
)
1041 error ("statement has VUSE operand not in uses list");
1044 has_err
|= verify_ssa_name (gimple_vuse (stmt
), true);
1048 error ("in statement");
1049 print_gimple_stmt (stderr
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
);
1054 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
|SSA_OP_DEF
)
1056 if (verify_ssa_name (op
, false))
1058 error ("in statement");
1059 print_gimple_stmt (stderr
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
);
1065 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
1067 op
= gimple_op (stmt
, i
);
1068 if (op
&& TREE_CODE (op
) == SSA_NAME
&& --count
< 0)
1070 error ("number of operands and imm-links don%'t agree"
1072 print_gimple_stmt (stderr
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
);
1077 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
|SSA_OP_VUSE
)
1079 op
= USE_FROM_PTR (use_p
);
1080 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
1081 use_p
, stmt
, false, names_defined_in_bb
))
1085 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_ALL_DEFS
)
1087 if (SSA_NAME_DEF_STMT (op
) != stmt
)
1089 error ("SSA_NAME_DEF_STMT is wrong");
1090 fprintf (stderr
, "Expected definition statement:\n");
1091 print_gimple_stmt (stderr
, stmt
, 4, TDF_VOPS
);
1092 fprintf (stderr
, "\nActual definition statement:\n");
1093 print_gimple_stmt (stderr
, SSA_NAME_DEF_STMT (op
),
1097 bitmap_set_bit (names_defined_in_bb
, SSA_NAME_VERSION (op
));
1101 bitmap_clear (names_defined_in_bb
);
1104 free (definition_block
);
1106 /* Restore the dominance information to its prior known state, so
1107 that we do not perturb the compiler's subsequent behavior. */
1108 if (orig_dom_state
== DOM_NONE
)
1109 free_dominance_info (CDI_DOMINATORS
);
1111 set_dom_info_availability (CDI_DOMINATORS
, orig_dom_state
);
1113 BITMAP_FREE (names_defined_in_bb
);
1114 timevar_pop (TV_TREE_SSA_VERIFY
);
1118 internal_error ("verify_ssa failed");
1121 /* Return true if the uid in both int tree maps are equal. */
1124 int_tree_map_eq (const void *va
, const void *vb
)
1126 const struct int_tree_map
*a
= (const struct int_tree_map
*) va
;
1127 const struct int_tree_map
*b
= (const struct int_tree_map
*) vb
;
1128 return (a
->uid
== b
->uid
);
1131 /* Hash a UID in a int_tree_map. */
1134 int_tree_map_hash (const void *item
)
1136 return ((const struct int_tree_map
*)item
)->uid
;
1139 /* Return true if the DECL_UID in both trees are equal. */
1142 uid_decl_map_eq (const void *va
, const void *vb
)
1144 const_tree a
= (const_tree
) va
;
1145 const_tree b
= (const_tree
) vb
;
1146 return (a
->decl_minimal
.uid
== b
->decl_minimal
.uid
);
1149 /* Hash a tree in a uid_decl_map. */
1152 uid_decl_map_hash (const void *item
)
1154 return ((const_tree
)item
)->decl_minimal
.uid
;
1157 /* Return true if the DECL_UID in both trees are equal. */
1160 uid_ssaname_map_eq (const void *va
, const void *vb
)
1162 const_tree a
= (const_tree
) va
;
1163 const_tree b
= (const_tree
) vb
;
1164 return (a
->ssa_name
.var
->decl_minimal
.uid
== b
->ssa_name
.var
->decl_minimal
.uid
);
1167 /* Hash a tree in a uid_decl_map. */
1170 uid_ssaname_map_hash (const void *item
)
1172 return ((const_tree
)item
)->ssa_name
.var
->decl_minimal
.uid
;
1176 /* Initialize global DFA and SSA structures. */
1179 init_tree_ssa (struct function
*fn
)
1181 fn
->gimple_df
= ggc_alloc_cleared_gimple_df ();
1182 fn
->gimple_df
->referenced_vars
= htab_create_ggc (20, uid_decl_map_hash
,
1183 uid_decl_map_eq
, NULL
);
1184 fn
->gimple_df
->default_defs
= htab_create_ggc (20, uid_ssaname_map_hash
,
1185 uid_ssaname_map_eq
, NULL
);
1186 pt_solution_reset (&fn
->gimple_df
->escaped
);
1187 init_ssanames (fn
, 0);
1192 /* Deallocate memory associated with SSA data structures for FNDECL. */
1195 delete_tree_ssa (void)
1197 referenced_var_iterator rvi
;
1200 /* Remove annotations from every referenced local variable. */
1201 FOR_EACH_REFERENCED_VAR (cfun
, var
, rvi
)
1203 if (is_global_var (var
))
1207 ggc_free (var_ann (var
));
1208 *DECL_VAR_ANN_PTR (var
) = NULL
;
1211 htab_delete (gimple_referenced_vars (cfun
));
1212 cfun
->gimple_df
->referenced_vars
= NULL
;
1217 /* We no longer maintain the SSA operand cache at this point. */
1218 if (ssa_operands_active ())
1219 fini_ssa_operands ();
1221 htab_delete (cfun
->gimple_df
->default_defs
);
1222 cfun
->gimple_df
->default_defs
= NULL
;
1223 pt_solution_reset (&cfun
->gimple_df
->escaped
);
1224 if (cfun
->gimple_df
->decls_to_pointers
!= NULL
)
1225 pointer_map_destroy (cfun
->gimple_df
->decls_to_pointers
);
1226 cfun
->gimple_df
->decls_to_pointers
= NULL
;
1227 cfun
->gimple_df
->modified_noreturn_calls
= NULL
;
1228 cfun
->gimple_df
= NULL
;
1230 /* We no longer need the edge variable maps. */
1231 redirect_edge_var_map_destroy ();
1234 /* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a
1235 useless type conversion, otherwise return false.
1237 This function implicitly defines the middle-end type system. With
1238 the notion of 'a < b' meaning that useless_type_conversion_p (a, b)
1239 holds and 'a > b' meaning that useless_type_conversion_p (b, a) holds,
1240 the following invariants shall be fulfilled:
1242 1) useless_type_conversion_p is transitive.
1243 If a < b and b < c then a < c.
1245 2) useless_type_conversion_p is not symmetric.
1246 From a < b does not follow a > b.
1248 3) Types define the available set of operations applicable to values.
1249 A type conversion is useless if the operations for the target type
1250 is a subset of the operations for the source type. For example
1251 casts to void* are useless, casts from void* are not (void* can't
1252 be dereferenced or offsetted, but copied, hence its set of operations
1253 is a strict subset of that of all other data pointer types). Casts
1254 to const T* are useless (can't be written to), casts from const T*
1258 useless_type_conversion_p (tree outer_type
, tree inner_type
)
1260 /* Do the following before stripping toplevel qualifiers. */
1261 if (POINTER_TYPE_P (inner_type
)
1262 && POINTER_TYPE_P (outer_type
))
1264 /* Do not lose casts between pointers to different address spaces. */
1265 if (TYPE_ADDR_SPACE (TREE_TYPE (outer_type
))
1266 != TYPE_ADDR_SPACE (TREE_TYPE (inner_type
)))
1269 /* Do not lose casts to restrict qualified pointers. */
1270 if ((TYPE_RESTRICT (outer_type
)
1271 != TYPE_RESTRICT (inner_type
))
1272 && TYPE_RESTRICT (outer_type
))
1275 /* If the outer type is (void *), the conversion is not necessary. */
1276 if (VOID_TYPE_P (TREE_TYPE (outer_type
)))
1280 /* From now on qualifiers on value types do not matter. */
1281 inner_type
= TYPE_MAIN_VARIANT (inner_type
);
1282 outer_type
= TYPE_MAIN_VARIANT (outer_type
);
1284 if (inner_type
== outer_type
)
1287 /* If we know the canonical types, compare them. */
1288 if (TYPE_CANONICAL (inner_type
)
1289 && TYPE_CANONICAL (inner_type
) == TYPE_CANONICAL (outer_type
))
1292 /* Changes in machine mode are never useless conversions unless we
1293 deal with aggregate types in which case we defer to later checks. */
1294 if (TYPE_MODE (inner_type
) != TYPE_MODE (outer_type
)
1295 && !AGGREGATE_TYPE_P (inner_type
))
1298 /* If both the inner and outer types are integral types, then the
1299 conversion is not necessary if they have the same mode and
1300 signedness and precision, and both or neither are boolean. */
1301 if (INTEGRAL_TYPE_P (inner_type
)
1302 && INTEGRAL_TYPE_P (outer_type
))
1304 /* Preserve changes in signedness or precision. */
1305 if (TYPE_UNSIGNED (inner_type
) != TYPE_UNSIGNED (outer_type
)
1306 || TYPE_PRECISION (inner_type
) != TYPE_PRECISION (outer_type
))
1309 /* We don't need to preserve changes in the types minimum or
1310 maximum value in general as these do not generate code
1311 unless the types precisions are different. */
1315 /* Scalar floating point types with the same mode are compatible. */
1316 else if (SCALAR_FLOAT_TYPE_P (inner_type
)
1317 && SCALAR_FLOAT_TYPE_P (outer_type
))
1320 /* Fixed point types with the same mode are compatible. */
1321 else if (FIXED_POINT_TYPE_P (inner_type
)
1322 && FIXED_POINT_TYPE_P (outer_type
))
1325 /* We need to take special care recursing to pointed-to types. */
1326 else if (POINTER_TYPE_P (inner_type
)
1327 && POINTER_TYPE_P (outer_type
))
1329 /* Do not lose casts to function pointer types. */
1330 if ((TREE_CODE (TREE_TYPE (outer_type
)) == FUNCTION_TYPE
1331 || TREE_CODE (TREE_TYPE (outer_type
)) == METHOD_TYPE
)
1332 && !(TREE_CODE (TREE_TYPE (inner_type
)) == FUNCTION_TYPE
1333 || TREE_CODE (TREE_TYPE (inner_type
)) == METHOD_TYPE
))
1336 /* We do not care for const qualification of the pointed-to types
1337 as const qualification has no semantic value to the middle-end. */
1339 /* Otherwise pointers/references are equivalent. */
1343 /* Recurse for complex types. */
1344 else if (TREE_CODE (inner_type
) == COMPLEX_TYPE
1345 && TREE_CODE (outer_type
) == COMPLEX_TYPE
)
1346 return useless_type_conversion_p (TREE_TYPE (outer_type
),
1347 TREE_TYPE (inner_type
));
1349 /* Recurse for vector types with the same number of subparts. */
1350 else if (TREE_CODE (inner_type
) == VECTOR_TYPE
1351 && TREE_CODE (outer_type
) == VECTOR_TYPE
1352 && TYPE_PRECISION (inner_type
) == TYPE_PRECISION (outer_type
))
1353 return useless_type_conversion_p (TREE_TYPE (outer_type
),
1354 TREE_TYPE (inner_type
));
1356 else if (TREE_CODE (inner_type
) == ARRAY_TYPE
1357 && TREE_CODE (outer_type
) == ARRAY_TYPE
)
1359 /* Preserve string attributes. */
1360 if (TYPE_STRING_FLAG (inner_type
) != TYPE_STRING_FLAG (outer_type
))
1363 /* Conversions from array types with unknown extent to
1364 array types with known extent are not useless. */
1365 if (!TYPE_DOMAIN (inner_type
)
1366 && TYPE_DOMAIN (outer_type
))
1369 /* Nor are conversions from array types with non-constant size to
1370 array types with constant size or to different size. */
1371 if (TYPE_SIZE (outer_type
)
1372 && TREE_CODE (TYPE_SIZE (outer_type
)) == INTEGER_CST
1373 && (!TYPE_SIZE (inner_type
)
1374 || TREE_CODE (TYPE_SIZE (inner_type
)) != INTEGER_CST
1375 || !tree_int_cst_equal (TYPE_SIZE (outer_type
),
1376 TYPE_SIZE (inner_type
))))
1379 /* Check conversions between arrays with partially known extents.
1380 If the array min/max values are constant they have to match.
1381 Otherwise allow conversions to unknown and variable extents.
1382 In particular this declares conversions that may change the
1383 mode to BLKmode as useless. */
1384 if (TYPE_DOMAIN (inner_type
)
1385 && TYPE_DOMAIN (outer_type
)
1386 && TYPE_DOMAIN (inner_type
) != TYPE_DOMAIN (outer_type
))
1388 tree inner_min
= TYPE_MIN_VALUE (TYPE_DOMAIN (inner_type
));
1389 tree outer_min
= TYPE_MIN_VALUE (TYPE_DOMAIN (outer_type
));
1390 tree inner_max
= TYPE_MAX_VALUE (TYPE_DOMAIN (inner_type
));
1391 tree outer_max
= TYPE_MAX_VALUE (TYPE_DOMAIN (outer_type
));
1393 /* After gimplification a variable min/max value carries no
1394 additional information compared to a NULL value. All that
1395 matters has been lowered to be part of the IL. */
1396 if (inner_min
&& TREE_CODE (inner_min
) != INTEGER_CST
)
1397 inner_min
= NULL_TREE
;
1398 if (outer_min
&& TREE_CODE (outer_min
) != INTEGER_CST
)
1399 outer_min
= NULL_TREE
;
1400 if (inner_max
&& TREE_CODE (inner_max
) != INTEGER_CST
)
1401 inner_max
= NULL_TREE
;
1402 if (outer_max
&& TREE_CODE (outer_max
) != INTEGER_CST
)
1403 outer_max
= NULL_TREE
;
1405 /* Conversions NULL / variable <- cst are useless, but not
1406 the other way around. */
1409 || !tree_int_cst_equal (inner_min
, outer_min
)))
1413 || !tree_int_cst_equal (inner_max
, outer_max
)))
1417 /* Recurse on the element check. */
1418 return useless_type_conversion_p (TREE_TYPE (outer_type
),
1419 TREE_TYPE (inner_type
));
1422 else if ((TREE_CODE (inner_type
) == FUNCTION_TYPE
1423 || TREE_CODE (inner_type
) == METHOD_TYPE
)
1424 && TREE_CODE (inner_type
) == TREE_CODE (outer_type
))
1426 tree outer_parm
, inner_parm
;
1428 /* If the return types are not compatible bail out. */
1429 if (!useless_type_conversion_p (TREE_TYPE (outer_type
),
1430 TREE_TYPE (inner_type
)))
1433 /* Method types should belong to a compatible base class. */
1434 if (TREE_CODE (inner_type
) == METHOD_TYPE
1435 && !useless_type_conversion_p (TYPE_METHOD_BASETYPE (outer_type
),
1436 TYPE_METHOD_BASETYPE (inner_type
)))
1439 /* A conversion to an unprototyped argument list is ok. */
1440 if (!prototype_p (outer_type
))
1443 /* If the unqualified argument types are compatible the conversion
1445 if (TYPE_ARG_TYPES (outer_type
) == TYPE_ARG_TYPES (inner_type
))
1448 for (outer_parm
= TYPE_ARG_TYPES (outer_type
),
1449 inner_parm
= TYPE_ARG_TYPES (inner_type
);
1450 outer_parm
&& inner_parm
;
1451 outer_parm
= TREE_CHAIN (outer_parm
),
1452 inner_parm
= TREE_CHAIN (inner_parm
))
1453 if (!useless_type_conversion_p
1454 (TYPE_MAIN_VARIANT (TREE_VALUE (outer_parm
)),
1455 TYPE_MAIN_VARIANT (TREE_VALUE (inner_parm
))))
1458 /* If there is a mismatch in the number of arguments the functions
1459 are not compatible. */
1460 if (outer_parm
|| inner_parm
)
1463 /* Defer to the target if necessary. */
1464 if (TYPE_ATTRIBUTES (inner_type
) || TYPE_ATTRIBUTES (outer_type
))
1465 return comp_type_attributes (outer_type
, inner_type
) != 0;
1470 /* For aggregates we rely on TYPE_CANONICAL exclusively and require
1471 explicit conversions for types involving to be structurally
1473 else if (AGGREGATE_TYPE_P (inner_type
)
1474 && TREE_CODE (inner_type
) == TREE_CODE (outer_type
))
1480 /* Return true if a conversion from either type of TYPE1 and TYPE2
1481 to the other is not required. Otherwise return false. */
1484 types_compatible_p (tree type1
, tree type2
)
1486 return (type1
== type2
1487 || (useless_type_conversion_p (type1
, type2
)
1488 && useless_type_conversion_p (type2
, type1
)));
1491 /* Return true if EXPR is a useless type conversion, otherwise return
1495 tree_ssa_useless_type_conversion (tree expr
)
1497 /* If we have an assignment that merely uses a NOP_EXPR to change
1498 the top of the RHS to the type of the LHS and the type conversion
1499 is "safe", then strip away the type conversion so that we can
1500 enter LHS = RHS into the const_and_copies table. */
1501 if (CONVERT_EXPR_P (expr
)
1502 || TREE_CODE (expr
) == VIEW_CONVERT_EXPR
1503 || TREE_CODE (expr
) == NON_LVALUE_EXPR
)
1504 return useless_type_conversion_p
1506 TREE_TYPE (TREE_OPERAND (expr
, 0)));
1511 /* Strip conversions from EXP according to
1512 tree_ssa_useless_type_conversion and return the resulting
1516 tree_ssa_strip_useless_type_conversions (tree exp
)
1518 while (tree_ssa_useless_type_conversion (exp
))
1519 exp
= TREE_OPERAND (exp
, 0);
1524 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
1525 described in walk_use_def_chains.
1527 VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
1528 infinite loops. We used to have a bitmap for this to just mark
1529 SSA versions we had visited. But non-sparse bitmaps are way too
1530 expensive, while sparse bitmaps may cause quadratic behavior.
1532 IS_DFS is true if the caller wants to perform a depth-first search
1533 when visiting PHI nodes. A DFS will visit each PHI argument and
1534 call FN after each one. Otherwise, all the arguments are
1535 visited first and then FN is called with each of the visited
1536 arguments in a separate pass. */
1539 walk_use_def_chains_1 (tree var
, walk_use_def_chains_fn fn
, void *data
,
1540 struct pointer_set_t
*visited
, bool is_dfs
)
1544 if (pointer_set_insert (visited
, var
))
1547 def_stmt
= SSA_NAME_DEF_STMT (var
);
1549 if (gimple_code (def_stmt
) != GIMPLE_PHI
)
1551 /* If we reached the end of the use-def chain, call FN. */
1552 return fn (var
, def_stmt
, data
);
1558 /* When doing a breadth-first search, call FN before following the
1559 use-def links for each argument. */
1561 for (i
= 0; i
< gimple_phi_num_args (def_stmt
); i
++)
1562 if (fn (gimple_phi_arg_def (def_stmt
, i
), def_stmt
, data
))
1565 /* Follow use-def links out of each PHI argument. */
1566 for (i
= 0; i
< gimple_phi_num_args (def_stmt
); i
++)
1568 tree arg
= gimple_phi_arg_def (def_stmt
, i
);
1570 /* ARG may be NULL for newly introduced PHI nodes. */
1572 && TREE_CODE (arg
) == SSA_NAME
1573 && walk_use_def_chains_1 (arg
, fn
, data
, visited
, is_dfs
))
1577 /* When doing a depth-first search, call FN after following the
1578 use-def links for each argument. */
1580 for (i
= 0; i
< gimple_phi_num_args (def_stmt
); i
++)
1581 if (fn (gimple_phi_arg_def (def_stmt
, i
), def_stmt
, data
))
1590 /* Walk use-def chains starting at the SSA variable VAR. Call
1591 function FN at each reaching definition found. FN takes three
1592 arguments: VAR, its defining statement (DEF_STMT) and a generic
1593 pointer to whatever state information that FN may want to maintain
1594 (DATA). FN is able to stop the walk by returning true, otherwise
1595 in order to continue the walk, FN should return false.
1597 Note, that if DEF_STMT is a PHI node, the semantics are slightly
1598 different. The first argument to FN is no longer the original
1599 variable VAR, but the PHI argument currently being examined. If FN
1600 wants to get at VAR, it should call PHI_RESULT (PHI).
1602 If IS_DFS is true, this function will:
1604 1- walk the use-def chains for all the PHI arguments, and,
1605 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
1607 If IS_DFS is false, the two steps above are done in reverse order
1608 (i.e., a breadth-first search). */
1611 walk_use_def_chains (tree var
, walk_use_def_chains_fn fn
, void *data
,
1616 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
1618 def_stmt
= SSA_NAME_DEF_STMT (var
);
1620 /* We only need to recurse if the reaching definition comes from a PHI
1622 if (gimple_code (def_stmt
) != GIMPLE_PHI
)
1623 (*fn
) (var
, def_stmt
, data
);
1626 struct pointer_set_t
*visited
= pointer_set_create ();
1627 walk_use_def_chains_1 (var
, fn
, data
, visited
, is_dfs
);
1628 pointer_set_destroy (visited
);
1633 /* Emit warnings for uninitialized variables. This is done in two passes.
1635 The first pass notices real uses of SSA names with undefined values.
1636 Such uses are unconditionally uninitialized, and we can be certain that
1637 such a use is a mistake. This pass is run before most optimizations,
1638 so that we catch as many as we can.
1640 The second pass follows PHI nodes to find uses that are potentially
1641 uninitialized. In this case we can't necessarily prove that the use
1642 is really uninitialized. This pass is run after most optimizations,
1643 so that we thread as many jumps and possible, and delete as much dead
1644 code as possible, in order to reduce false positives. We also look
1645 again for plain uninitialized variables, since optimization may have
1646 changed conditionally uninitialized to unconditionally uninitialized. */
1648 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1649 warning text is in MSGID and LOCUS may contain a location or be null.
1650 WC is the warning code. */
1653 warn_uninit (enum opt_code wc
, tree t
, const char *gmsgid
, void *data
)
1655 tree var
= SSA_NAME_VAR (t
);
1656 gimple context
= (gimple
) data
;
1657 location_t location
;
1658 expanded_location xloc
, floc
;
1660 if (!ssa_undefined_value_p (t
))
1663 /* TREE_NO_WARNING either means we already warned, or the front end
1664 wishes to suppress the warning. */
1665 if (TREE_NO_WARNING (var
))
1668 /* Do not warn if it can be initialized outside this module. */
1669 if (is_global_var (var
))
1672 location
= (context
!= NULL
&& gimple_has_location (context
))
1673 ? gimple_location (context
)
1674 : DECL_SOURCE_LOCATION (var
);
1675 xloc
= expand_location (location
);
1676 floc
= expand_location (DECL_SOURCE_LOCATION (cfun
->decl
));
1677 if (warning_at (location
, wc
, gmsgid
, var
))
1679 TREE_NO_WARNING (var
) = 1;
1681 if (location
== DECL_SOURCE_LOCATION (var
))
1683 if (xloc
.file
!= floc
.file
1684 || xloc
.line
< floc
.line
1685 || xloc
.line
> LOCATION_LINE (cfun
->function_end_locus
))
1686 inform (DECL_SOURCE_LOCATION (var
), "%qD was declared here", var
);
1692 bool always_executed
;
1693 bool warn_possibly_uninitialized
;
1696 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1697 and warn about them. */
1700 warn_uninitialized_var (tree
*tp
, int *walk_subtrees
, void *data_
)
1702 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data_
;
1703 struct walk_data
*data
= (struct walk_data
*) wi
->info
;
1706 /* We do not care about LHS. */
1709 /* Except for operands of dereferences. */
1710 if (!INDIRECT_REF_P (t
)
1711 && TREE_CODE (t
) != MEM_REF
)
1713 t
= TREE_OPERAND (t
, 0);
1716 switch (TREE_CODE (t
))
1719 /* Taking the address of an uninitialized variable does not
1720 count as using it. */
1726 /* A VAR_DECL in the RHS of a gimple statement may mean that
1727 this variable is loaded from memory. */
1731 /* If there is not gimple stmt,
1732 or alias information has not been computed,
1733 then we cannot check VUSE ops. */
1734 if (data
->stmt
== NULL
)
1737 /* If the load happens as part of a call do not warn about it. */
1738 if (is_gimple_call (data
->stmt
))
1741 vuse
= gimple_vuse_op (data
->stmt
);
1742 if (vuse
== NULL_USE_OPERAND_P
)
1745 op
= USE_FROM_PTR (vuse
);
1746 if (t
!= SSA_NAME_VAR (op
)
1747 || !SSA_NAME_IS_DEFAULT_DEF (op
))
1749 /* If this is a VUSE of t and it is the default definition,
1750 then warn about op. */
1752 /* Fall through into SSA_NAME. */
1756 /* We only do data flow with SSA_NAMEs, so that's all we
1758 if (data
->always_executed
)
1759 warn_uninit (OPT_Wuninitialized
,
1760 t
, "%qD is used uninitialized in this function",
1762 else if (data
->warn_possibly_uninitialized
)
1763 warn_uninit (OPT_Wuninitialized
,
1764 t
, "%qD may be used uninitialized in this function",
1771 /* The total store transformation performed during gimplification
1772 creates uninitialized variable uses. If all is well, these will
1773 be optimized away, so don't warn now. */
1774 if (TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
)
1779 if (IS_TYPE_OR_DECL_P (t
))
1788 warn_uninitialized_vars (bool warn_possibly_uninitialized
)
1790 gimple_stmt_iterator gsi
;
1792 struct walk_data data
;
1794 data
.warn_possibly_uninitialized
= warn_possibly_uninitialized
;
1799 data
.always_executed
= dominated_by_p (CDI_POST_DOMINATORS
,
1800 single_succ (ENTRY_BLOCK_PTR
), bb
);
1801 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1803 struct walk_stmt_info wi
;
1804 data
.stmt
= gsi_stmt (gsi
);
1805 if (is_gimple_debug (data
.stmt
))
1807 memset (&wi
, 0, sizeof (wi
));
1809 walk_gimple_op (gsi_stmt (gsi
), warn_uninitialized_var
, &wi
);
1817 execute_early_warn_uninitialized (void)
1819 /* Currently, this pass runs always but
1820 execute_late_warn_uninitialized only runs with optimization. With
1821 optimization we want to warn about possible uninitialized as late
1822 as possible, thus don't do it here. However, without
1823 optimization we need to warn here about "may be uninitialized".
1825 calculate_dominance_info (CDI_POST_DOMINATORS
);
1827 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize
);
1829 /* Post-dominator information can not be reliably updated. Free it
1832 free_dominance_info (CDI_POST_DOMINATORS
);
1837 gate_warn_uninitialized (void)
1839 return warn_uninitialized
!= 0;
1842 struct gimple_opt_pass pass_early_warn_uninitialized
=
1846 "*early_warn_uninitialized", /* name */
1847 gate_warn_uninitialized
, /* gate */
1848 execute_early_warn_uninitialized
, /* execute */
1851 0, /* static_pass_number */
1852 TV_TREE_UNINIT
, /* tv_id */
1853 PROP_ssa
, /* properties_required */
1854 0, /* properties_provided */
1855 0, /* properties_destroyed */
1856 0, /* todo_flags_start */
1857 0 /* todo_flags_finish */
1862 /* If necessary, rewrite the base of the reference tree *TP from
1863 a MEM_REF to a plain or converted symbol. */
1866 maybe_rewrite_mem_ref_base (tree
*tp
)
1870 while (handled_component_p (*tp
))
1871 tp
= &TREE_OPERAND (*tp
, 0);
1872 if (TREE_CODE (*tp
) == MEM_REF
1873 && TREE_CODE (TREE_OPERAND (*tp
, 0)) == ADDR_EXPR
1874 && (sym
= TREE_OPERAND (TREE_OPERAND (*tp
, 0), 0))
1876 && !TREE_ADDRESSABLE (sym
)
1877 && symbol_marked_for_renaming (sym
))
1879 if (TREE_CODE (TREE_TYPE (sym
)) == VECTOR_TYPE
1880 && useless_type_conversion_p (TREE_TYPE (*tp
),
1881 TREE_TYPE (TREE_TYPE (sym
)))
1882 && multiple_of_p (sizetype
, TREE_OPERAND (*tp
, 1),
1883 TYPE_SIZE_UNIT (TREE_TYPE (*tp
))))
1885 *tp
= build3 (BIT_FIELD_REF
, TREE_TYPE (*tp
), sym
,
1886 TYPE_SIZE (TREE_TYPE (*tp
)),
1887 int_const_binop (MULT_EXPR
,
1888 bitsize_int (BITS_PER_UNIT
),
1889 TREE_OPERAND (*tp
, 1)));
1891 else if (TREE_CODE (TREE_TYPE (sym
)) == COMPLEX_TYPE
1892 && useless_type_conversion_p (TREE_TYPE (*tp
),
1893 TREE_TYPE (TREE_TYPE (sym
))))
1895 *tp
= build1 (integer_zerop (TREE_OPERAND (*tp
, 1))
1896 ? REALPART_EXPR
: IMAGPART_EXPR
,
1897 TREE_TYPE (*tp
), sym
);
1899 else if (integer_zerop (TREE_OPERAND (*tp
, 1)))
1901 if (!useless_type_conversion_p (TREE_TYPE (*tp
),
1903 *tp
= build1 (VIEW_CONVERT_EXPR
,
1904 TREE_TYPE (*tp
), sym
);
1911 /* For a tree REF return its base if it is the base of a MEM_REF
1912 that cannot be rewritten into SSA form. Otherwise return NULL_TREE. */
1915 non_rewritable_mem_ref_base (tree ref
)
1919 /* A plain decl does not need it set. */
1923 while (handled_component_p (base
))
1924 base
= TREE_OPERAND (base
, 0);
1926 /* But watch out for MEM_REFs we cannot lower to a
1927 VIEW_CONVERT_EXPR or a BIT_FIELD_REF. */
1928 if (TREE_CODE (base
) == MEM_REF
1929 && TREE_CODE (TREE_OPERAND (base
, 0)) == ADDR_EXPR
)
1931 tree decl
= TREE_OPERAND (TREE_OPERAND (base
, 0), 0);
1932 if ((TREE_CODE (TREE_TYPE (decl
)) == VECTOR_TYPE
1933 || TREE_CODE (TREE_TYPE (decl
)) == COMPLEX_TYPE
)
1934 && useless_type_conversion_p (TREE_TYPE (base
),
1935 TREE_TYPE (TREE_TYPE (decl
)))
1936 && double_int_fits_in_uhwi_p (mem_ref_offset (base
))
1938 (tree_to_double_int (TYPE_SIZE_UNIT (TREE_TYPE (decl
))),
1939 mem_ref_offset (base
)) == 1
1940 && multiple_of_p (sizetype
, TREE_OPERAND (base
, 1),
1941 TYPE_SIZE_UNIT (TREE_TYPE (base
))))
1944 && (!integer_zerop (TREE_OPERAND (base
, 1))
1945 || (DECL_SIZE (decl
)
1946 != TYPE_SIZE (TREE_TYPE (base
)))
1947 || TREE_THIS_VOLATILE (decl
) != TREE_THIS_VOLATILE (base
)))
1954 /* For an lvalue tree LHS return true if it cannot be rewritten into SSA form.
1955 Otherwise return true. */
1958 non_rewritable_lvalue_p (tree lhs
)
1960 /* A plain decl is always rewritable. */
1964 /* A decl that is wrapped inside a MEM-REF that covers
1965 it full is also rewritable.
1966 ??? The following could be relaxed allowing component
1967 references that do not change the access size. */
1968 if (TREE_CODE (lhs
) == MEM_REF
1969 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == ADDR_EXPR
1970 && integer_zerop (TREE_OPERAND (lhs
, 1)))
1972 tree decl
= TREE_OPERAND (TREE_OPERAND (lhs
, 0), 0);
1974 && DECL_SIZE (decl
) == TYPE_SIZE (TREE_TYPE (lhs
))
1975 && (TREE_THIS_VOLATILE (decl
) == TREE_THIS_VOLATILE (lhs
)))
1982 /* When possible, clear TREE_ADDRESSABLE bit or set DECL_GIMPLE_REG_P bit and
1983 mark the variable VAR for conversion into SSA. Return true when updating
1984 stmts is required. */
1987 maybe_optimize_var (tree var
, bitmap addresses_taken
, bitmap not_reg_needs
)
1989 bool update_vops
= false;
1991 /* Global Variables, result decls cannot be changed. */
1992 if (is_global_var (var
)
1993 || TREE_CODE (var
) == RESULT_DECL
1994 || bitmap_bit_p (addresses_taken
, DECL_UID (var
)))
1997 /* If the variable is not in the list of referenced vars then we
1998 do not need to touch it nor can we rename it. */
1999 if (!referenced_var_lookup (cfun
, DECL_UID (var
)))
2002 if (TREE_ADDRESSABLE (var
)
2003 /* Do not change TREE_ADDRESSABLE if we need to preserve var as
2004 a non-register. Otherwise we are confused and forget to
2005 add virtual operands for it. */
2006 && (!is_gimple_reg_type (TREE_TYPE (var
))
2007 || !bitmap_bit_p (not_reg_needs
, DECL_UID (var
))))
2009 TREE_ADDRESSABLE (var
) = 0;
2010 if (is_gimple_reg (var
))
2011 mark_sym_for_renaming (var
);
2015 fprintf (dump_file
, "No longer having address taken: ");
2016 print_generic_expr (dump_file
, var
, 0);
2017 fprintf (dump_file
, "\n");
2021 if (!DECL_GIMPLE_REG_P (var
)
2022 && !bitmap_bit_p (not_reg_needs
, DECL_UID (var
))
2023 && (TREE_CODE (TREE_TYPE (var
)) == COMPLEX_TYPE
2024 || TREE_CODE (TREE_TYPE (var
)) == VECTOR_TYPE
)
2025 && !TREE_THIS_VOLATILE (var
)
2026 && (TREE_CODE (var
) != VAR_DECL
|| !DECL_HARD_REGISTER (var
)))
2028 DECL_GIMPLE_REG_P (var
) = 1;
2029 mark_sym_for_renaming (var
);
2033 fprintf (dump_file
, "Now a gimple register: ");
2034 print_generic_expr (dump_file
, var
, 0);
2035 fprintf (dump_file
, "\n");
2042 /* Compute TREE_ADDRESSABLE and DECL_GIMPLE_REG_P for local variables. */
2045 execute_update_addresses_taken (void)
2047 gimple_stmt_iterator gsi
;
2049 bitmap addresses_taken
= BITMAP_ALLOC (NULL
);
2050 bitmap not_reg_needs
= BITMAP_ALLOC (NULL
);
2051 bool update_vops
= false;
2055 timevar_push (TV_ADDRESS_TAKEN
);
2057 /* Collect into ADDRESSES_TAKEN all variables whose address is taken within
2058 the function body. */
2061 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2063 gimple stmt
= gsi_stmt (gsi
);
2064 enum gimple_code code
= gimple_code (stmt
);
2067 /* Note all addresses taken by the stmt. */
2068 gimple_ior_addresses_taken (addresses_taken
, stmt
);
2070 /* If we have a call or an assignment, see if the lhs contains
2071 a local decl that requires not to be a gimple register. */
2072 if (code
== GIMPLE_ASSIGN
|| code
== GIMPLE_CALL
)
2074 tree lhs
= gimple_get_lhs (stmt
);
2076 && TREE_CODE (lhs
) != SSA_NAME
2077 && non_rewritable_lvalue_p (lhs
))
2079 decl
= get_base_address (lhs
);
2081 bitmap_set_bit (not_reg_needs
, DECL_UID (decl
));
2085 if (gimple_assign_single_p (stmt
))
2087 tree rhs
= gimple_assign_rhs1 (stmt
);
2088 if ((decl
= non_rewritable_mem_ref_base (rhs
)))
2089 bitmap_set_bit (not_reg_needs
, DECL_UID (decl
));
2092 else if (code
== GIMPLE_CALL
)
2094 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
2096 tree arg
= gimple_call_arg (stmt
, i
);
2097 if ((decl
= non_rewritable_mem_ref_base (arg
)))
2098 bitmap_set_bit (not_reg_needs
, DECL_UID (decl
));
2102 else if (code
== GIMPLE_ASM
)
2104 for (i
= 0; i
< gimple_asm_noutputs (stmt
); ++i
)
2106 tree link
= gimple_asm_output_op (stmt
, i
);
2107 tree lhs
= TREE_VALUE (link
);
2108 if (TREE_CODE (lhs
) != SSA_NAME
)
2110 decl
= get_base_address (lhs
);
2112 && (non_rewritable_lvalue_p (lhs
)
2113 /* We cannot move required conversions from
2114 the lhs to the rhs in asm statements, so
2115 require we do not need any. */
2116 || !useless_type_conversion_p
2117 (TREE_TYPE (lhs
), TREE_TYPE (decl
))))
2118 bitmap_set_bit (not_reg_needs
, DECL_UID (decl
));
2121 for (i
= 0; i
< gimple_asm_ninputs (stmt
); ++i
)
2123 tree link
= gimple_asm_input_op (stmt
, i
);
2124 if ((decl
= non_rewritable_mem_ref_base (TREE_VALUE (link
))))
2125 bitmap_set_bit (not_reg_needs
, DECL_UID (decl
));
2130 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2133 gimple phi
= gsi_stmt (gsi
);
2135 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2137 tree op
= PHI_ARG_DEF (phi
, i
), var
;
2138 if (TREE_CODE (op
) == ADDR_EXPR
2139 && (var
= get_base_address (TREE_OPERAND (op
, 0))) != NULL
2141 bitmap_set_bit (addresses_taken
, DECL_UID (var
));
2146 /* We cannot iterate over all referenced vars because that can contain
2147 unused vars from BLOCK trees, which causes code generation differences
2149 for (var
= DECL_ARGUMENTS (cfun
->decl
); var
; var
= DECL_CHAIN (var
))
2150 update_vops
|= maybe_optimize_var (var
, addresses_taken
, not_reg_needs
);
2152 FOR_EACH_VEC_ELT (tree
, cfun
->local_decls
, i
, var
)
2153 update_vops
|= maybe_optimize_var (var
, addresses_taken
, not_reg_needs
);
2155 /* Operand caches need to be recomputed for operands referencing the updated
2160 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2162 gimple stmt
= gsi_stmt (gsi
);
2164 /* Re-write TARGET_MEM_REFs of symbols we want to
2165 rewrite into SSA form. */
2166 if (gimple_assign_single_p (stmt
))
2168 tree lhs
= gimple_assign_lhs (stmt
);
2169 tree rhs
, *rhsp
= gimple_assign_rhs1_ptr (stmt
);
2172 /* We shouldn't have any fancy wrapping of
2173 component-refs on the LHS, but look through
2174 VIEW_CONVERT_EXPRs as that is easy. */
2175 while (TREE_CODE (lhs
) == VIEW_CONVERT_EXPR
)
2176 lhs
= TREE_OPERAND (lhs
, 0);
2177 if (TREE_CODE (lhs
) == MEM_REF
2178 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == ADDR_EXPR
2179 && integer_zerop (TREE_OPERAND (lhs
, 1))
2180 && (sym
= TREE_OPERAND (TREE_OPERAND (lhs
, 0), 0))
2182 && !TREE_ADDRESSABLE (sym
)
2183 && symbol_marked_for_renaming (sym
))
2186 lhs
= gimple_assign_lhs (stmt
);
2188 /* Rewrite the RHS and make sure the resulting assignment
2189 is validly typed. */
2190 maybe_rewrite_mem_ref_base (rhsp
);
2191 rhs
= gimple_assign_rhs1 (stmt
);
2192 if (gimple_assign_lhs (stmt
) != lhs
2193 && !useless_type_conversion_p (TREE_TYPE (lhs
),
2195 rhs
= fold_build1 (VIEW_CONVERT_EXPR
,
2196 TREE_TYPE (lhs
), rhs
);
2198 if (gimple_assign_lhs (stmt
) != lhs
)
2199 gimple_assign_set_lhs (stmt
, lhs
);
2201 if (gimple_assign_rhs1 (stmt
) != rhs
)
2203 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
2204 gimple_assign_set_rhs_from_tree (&gsi
, rhs
);
2208 else if (gimple_code (stmt
) == GIMPLE_CALL
)
2211 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
2213 tree
*argp
= gimple_call_arg_ptr (stmt
, i
);
2214 maybe_rewrite_mem_ref_base (argp
);
2218 else if (gimple_code (stmt
) == GIMPLE_ASM
)
2221 for (i
= 0; i
< gimple_asm_noutputs (stmt
); ++i
)
2223 tree link
= gimple_asm_output_op (stmt
, i
);
2224 maybe_rewrite_mem_ref_base (&TREE_VALUE (link
));
2226 for (i
= 0; i
< gimple_asm_ninputs (stmt
); ++i
)
2228 tree link
= gimple_asm_input_op (stmt
, i
);
2229 maybe_rewrite_mem_ref_base (&TREE_VALUE (link
));
2233 if (gimple_references_memory_p (stmt
)
2234 || is_gimple_debug (stmt
))
2238 /* Update SSA form here, we are called as non-pass as well. */
2239 update_ssa (TODO_update_ssa
);
2242 BITMAP_FREE (not_reg_needs
);
2243 BITMAP_FREE (addresses_taken
);
2244 timevar_pop (TV_ADDRESS_TAKEN
);
2247 struct gimple_opt_pass pass_update_address_taken
=
2251 "addressables", /* name */
2256 0, /* static_pass_number */
2257 TV_ADDRESS_TAKEN
, /* tv_id */
2258 PROP_ssa
, /* properties_required */
2259 0, /* properties_provided */
2260 0, /* properties_destroyed */
2261 0, /* todo_flags_start */
2262 TODO_update_address_taken
2263 | TODO_dump_func
/* todo_flags_finish */