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"
48 /* Pointer map of variable mappings, keyed by edge. */
49 static struct pointer_map_t
*edge_var_maps
;
52 /* Add a mapping with PHI RESULT and PHI DEF associated with edge E. */
55 redirect_edge_var_map_add (edge e
, tree result
, tree def
, source_location locus
)
58 edge_var_map_vector old_head
, head
;
59 edge_var_map new_node
;
61 if (edge_var_maps
== NULL
)
62 edge_var_maps
= pointer_map_create ();
64 slot
= pointer_map_insert (edge_var_maps
, e
);
65 old_head
= head
= (edge_var_map_vector
) *slot
;
68 head
= VEC_alloc (edge_var_map
, heap
, 5);
72 new_node
.result
= result
;
73 new_node
.locus
= locus
;
75 VEC_safe_push (edge_var_map
, heap
, head
, &new_node
);
78 /* The push did some reallocation. Update the pointer map. */
84 /* Clear the var mappings in edge E. */
87 redirect_edge_var_map_clear (edge e
)
90 edge_var_map_vector head
;
95 slot
= pointer_map_contains (edge_var_maps
, e
);
99 head
= (edge_var_map_vector
) *slot
;
100 VEC_free (edge_var_map
, heap
, head
);
106 /* Duplicate the redirected var mappings in OLDE in NEWE.
108 Since we can't remove a mapping, let's just duplicate it. This assumes a
109 pointer_map can have multiple edges mapping to the same var_map (many to
110 one mapping), since we don't remove the previous mappings. */
113 redirect_edge_var_map_dup (edge newe
, edge olde
)
115 void **new_slot
, **old_slot
;
116 edge_var_map_vector head
;
121 new_slot
= pointer_map_insert (edge_var_maps
, newe
);
122 old_slot
= pointer_map_contains (edge_var_maps
, olde
);
125 head
= (edge_var_map_vector
) *old_slot
;
128 *new_slot
= VEC_copy (edge_var_map
, heap
, head
);
130 *new_slot
= VEC_alloc (edge_var_map
, heap
, 5);
134 /* Return the variable mappings for a given edge. If there is none, return
138 redirect_edge_var_map_vector (edge e
)
142 /* Hey, what kind of idiot would... you'd be surprised. */
146 slot
= pointer_map_contains (edge_var_maps
, e
);
150 return (edge_var_map_vector
) *slot
;
153 /* Used by redirect_edge_var_map_destroy to free all memory. */
156 free_var_map_entry (const void *key ATTRIBUTE_UNUSED
,
158 void *data ATTRIBUTE_UNUSED
)
160 edge_var_map_vector head
= (edge_var_map_vector
) *value
;
161 VEC_free (edge_var_map
, heap
, head
);
165 /* Clear the edge variable mappings. */
168 redirect_edge_var_map_destroy (void)
172 pointer_map_traverse (edge_var_maps
, free_var_map_entry
, NULL
);
173 pointer_map_destroy (edge_var_maps
);
174 edge_var_maps
= NULL
;
179 /* Remove the corresponding arguments from the PHI nodes in E's
180 destination block and redirect it to DEST. Return redirected edge.
181 The list of removed arguments is stored in a vector accessed
182 through edge_var_maps. */
185 ssa_redirect_edge (edge e
, basic_block dest
)
187 gimple_stmt_iterator gsi
;
190 redirect_edge_var_map_clear (e
);
192 /* Remove the appropriate PHI arguments in E's destination block. */
193 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
196 source_location locus
;
198 phi
= gsi_stmt (gsi
);
199 def
= gimple_phi_arg_def (phi
, e
->dest_idx
);
200 locus
= gimple_phi_arg_location (phi
, e
->dest_idx
);
202 if (def
== NULL_TREE
)
205 redirect_edge_var_map_add (e
, gimple_phi_result (phi
), def
, locus
);
208 e
= redirect_edge_succ_nodup (e
, dest
);
214 /* Add PHI arguments queued in PENDING_STMT list on edge E to edge
218 flush_pending_stmts (edge e
)
221 edge_var_map_vector v
;
224 gimple_stmt_iterator gsi
;
226 v
= redirect_edge_var_map_vector (e
);
230 for (gsi
= gsi_start_phis (e
->dest
), i
= 0;
231 !gsi_end_p (gsi
) && VEC_iterate (edge_var_map
, v
, i
, vm
);
232 gsi_next (&gsi
), i
++)
236 phi
= gsi_stmt (gsi
);
237 def
= redirect_edge_var_map_def (vm
);
238 add_phi_arg (phi
, def
, e
, redirect_edge_var_map_location (vm
));
241 redirect_edge_var_map_clear (e
);
244 /* Given a tree for an expression for which we might want to emit
245 locations or values in debug information (generally a variable, but
246 we might deal with other kinds of trees in the future), return the
247 tree that should be used as the variable of a DEBUG_BIND STMT or
248 VAR_LOCATION INSN or NOTE. Return NULL if VAR is not to be tracked. */
251 target_for_debug_bind (tree var
)
253 if (!MAY_HAVE_DEBUG_STMTS
)
256 if (TREE_CODE (var
) != VAR_DECL
257 && TREE_CODE (var
) != PARM_DECL
)
260 if (DECL_HAS_VALUE_EXPR_P (var
))
261 return target_for_debug_bind (DECL_VALUE_EXPR (var
));
263 if (DECL_IGNORED_P (var
))
266 if (!is_gimple_reg (var
))
272 /* Called via walk_tree, look for SSA_NAMEs that have already been
276 find_released_ssa_name (tree
*tp
, int *walk_subtrees
, void *data_
)
278 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data_
;
280 if (wi
&& wi
->is_lhs
)
283 if (TREE_CODE (*tp
) == SSA_NAME
)
285 if (SSA_NAME_IN_FREE_LIST (*tp
))
290 else if (IS_TYPE_OR_DECL_P (*tp
))
296 /* Insert a DEBUG BIND stmt before the DEF of VAR if VAR is referenced
297 by other DEBUG stmts, and replace uses of the DEF with the
298 newly-created debug temp. */
301 insert_debug_temp_for_var_def (gimple_stmt_iterator
*gsi
, tree var
)
303 imm_use_iterator imm_iter
;
306 gimple def_stmt
= NULL
;
310 if (!MAY_HAVE_DEBUG_STMTS
)
313 /* If this name has already been registered for replacement, do nothing
314 as anything that uses this name isn't in SSA form. */
315 if (name_registered_for_update_p (var
))
318 /* Check whether there are debug stmts that reference this variable and,
319 if there are, decide whether we should use a debug temp. */
320 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, var
)
322 stmt
= USE_STMT (use_p
);
324 if (!gimple_debug_bind_p (stmt
))
330 if (gimple_debug_bind_get_value (stmt
) != var
)
332 /* Count this as an additional use, so as to make sure we
333 use a temp unless VAR's definition has a SINGLE_RHS that
344 def_stmt
= gsi_stmt (*gsi
);
346 def_stmt
= SSA_NAME_DEF_STMT (var
);
348 /* If we didn't get an insertion point, and the stmt has already
349 been removed, we won't be able to insert the debug bind stmt, so
350 we'll have to drop debug information. */
351 if (gimple_code (def_stmt
) == GIMPLE_PHI
)
353 value
= degenerate_phi_result (def_stmt
);
354 if (value
&& walk_tree (&value
, find_released_ssa_name
, NULL
, NULL
))
356 /* error_mark_node is what fixup_noreturn_call changes PHI arguments
358 else if (value
== error_mark_node
)
361 else if (is_gimple_assign (def_stmt
))
363 bool no_value
= false;
365 if (!dom_info_available_p (CDI_DOMINATORS
))
367 struct walk_stmt_info wi
;
369 memset (&wi
, 0, sizeof (wi
));
371 /* When removing blocks without following reverse dominance
372 order, we may sometimes encounter SSA_NAMEs that have
373 already been released, referenced in other SSA_DEFs that
374 we're about to release. Consider:
383 If we deleted BB X first, propagating the value of w_2
384 won't do us any good. It's too late to recover their
385 original definition of v_1: when it was deleted, it was
386 only referenced in other DEFs, it couldn't possibly know
387 it should have been retained, and propagating every
388 single DEF just in case it might have to be propagated
389 into a DEBUG STMT would probably be too wasteful.
391 When dominator information is not readily available, we
392 check for and accept some loss of debug information. But
393 if it is available, there's no excuse for us to remove
394 blocks in the wrong order, so we don't even check for
395 dead SSA NAMEs. SSA verification shall catch any
397 if ((!gsi
&& !gimple_bb (def_stmt
))
398 || walk_gimple_op (def_stmt
, find_released_ssa_name
, &wi
))
403 value
= gimple_assign_rhs_to_tree (def_stmt
);
408 /* If there's a single use of VAR, and VAR is the entire debug
409 expression (usecount would have been incremented again
410 otherwise), and the definition involves only constants and
411 SSA names, then we can propagate VALUE into this single use,
414 We can also avoid using a temp if VALUE can be shared and
415 propagated into all uses, without generating expressions that
416 wouldn't be valid gimple RHSs.
418 Other cases that would require unsharing or non-gimple RHSs
419 are deferred to a debug temp, although we could avoid temps
420 at the expense of duplication of expressions. */
422 if (CONSTANT_CLASS_P (value
)
423 || gimple_code (def_stmt
) == GIMPLE_PHI
425 && (!gimple_assign_single_p (def_stmt
)
426 || is_gimple_min_invariant (value
)))
427 || is_gimple_reg (value
))
428 value
= unshare_expr (value
);
432 tree vexpr
= make_node (DEBUG_EXPR_DECL
);
434 def_temp
= gimple_build_debug_bind (vexpr
,
435 unshare_expr (value
),
438 DECL_ARTIFICIAL (vexpr
) = 1;
439 TREE_TYPE (vexpr
) = TREE_TYPE (value
);
441 DECL_MODE (vexpr
) = DECL_MODE (value
);
443 DECL_MODE (vexpr
) = TYPE_MODE (TREE_TYPE (value
));
446 gsi_insert_before (gsi
, def_temp
, GSI_SAME_STMT
);
449 gimple_stmt_iterator ngsi
= gsi_for_stmt (def_stmt
);
450 gsi_insert_before (&ngsi
, def_temp
, GSI_SAME_STMT
);
457 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, var
)
459 if (!gimple_debug_bind_p (stmt
))
464 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
465 /* unshare_expr is not needed here. vexpr is either a
466 SINGLE_RHS, that can be safely shared, some other RHS
467 that was unshared when we found it had a single debug
468 use, or a DEBUG_EXPR_DECL, that can be safely
470 SET_USE (use_p
, value
);
471 /* If we didn't replace uses with a debug decl fold the
472 resulting expression. Otherwise we end up with invalid IL. */
473 if (TREE_CODE (value
) != DEBUG_EXPR_DECL
)
474 fold_stmt_inplace (stmt
);
477 gimple_debug_bind_reset_value (stmt
);
484 /* Insert a DEBUG BIND stmt before STMT for each DEF referenced by
485 other DEBUG stmts, and replace uses of the DEF with the
486 newly-created debug temp. */
489 insert_debug_temps_for_defs (gimple_stmt_iterator
*gsi
)
495 if (!MAY_HAVE_DEBUG_STMTS
)
498 stmt
= gsi_stmt (*gsi
);
500 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
502 tree var
= DEF_FROM_PTR (def_p
);
504 if (TREE_CODE (var
) != SSA_NAME
)
507 insert_debug_temp_for_var_def (gsi
, var
);
511 /* Reset all debug stmts that use SSA_NAME(s) defined in STMT. */
514 reset_debug_uses (gimple stmt
)
518 imm_use_iterator imm_iter
;
521 if (!MAY_HAVE_DEBUG_STMTS
)
524 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
526 tree var
= DEF_FROM_PTR (def_p
);
528 if (TREE_CODE (var
) != SSA_NAME
)
531 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, var
)
533 if (!gimple_debug_bind_p (use_stmt
))
536 gimple_debug_bind_reset_value (use_stmt
);
537 update_stmt (use_stmt
);
542 /* Delete SSA DEFs for SSA versions in the TOREMOVE bitmap, removing
543 dominated stmts before their dominators, so that release_ssa_defs
544 stands a chance of propagating DEFs into debug bind stmts. */
547 release_defs_bitset (bitmap toremove
)
552 /* Performing a topological sort is probably overkill, this will
553 most likely run in slightly superlinear time, rather than the
554 pathological quadratic worst case. */
555 while (!bitmap_empty_p (toremove
))
556 EXECUTE_IF_SET_IN_BITMAP (toremove
, 0, j
, bi
)
558 bool remove_now
= true;
559 tree var
= ssa_name (j
);
561 imm_use_iterator uit
;
563 FOR_EACH_IMM_USE_STMT (stmt
, uit
, var
)
568 /* We can't propagate PHI nodes into debug stmts. */
569 if (gimple_code (stmt
) == GIMPLE_PHI
570 || is_gimple_debug (stmt
))
573 /* If we find another definition to remove that uses
574 the one we're looking at, defer the removal of this
575 one, so that it can be propagated into debug stmts
576 after the other is. */
577 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, dit
, SSA_OP_DEF
)
579 tree odef
= DEF_FROM_PTR (def_p
);
581 if (bitmap_bit_p (toremove
, SSA_NAME_VERSION (odef
)))
589 BREAK_FROM_IMM_USE_STMT (uit
);
594 gimple def
= SSA_NAME_DEF_STMT (var
);
595 gimple_stmt_iterator gsi
= gsi_for_stmt (def
);
597 if (gimple_code (def
) == GIMPLE_PHI
)
598 remove_phi_node (&gsi
, true);
601 gsi_remove (&gsi
, true);
605 bitmap_clear_bit (toremove
, j
);
610 /* Return true if SSA_NAME is malformed and mark it visited.
612 IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
616 verify_ssa_name (tree ssa_name
, bool is_virtual
)
618 if (TREE_CODE (ssa_name
) != SSA_NAME
)
620 error ("expected an SSA_NAME object");
624 if (TREE_TYPE (ssa_name
) != TREE_TYPE (SSA_NAME_VAR (ssa_name
)))
626 error ("type mismatch between an SSA_NAME and its symbol");
630 if (SSA_NAME_IN_FREE_LIST (ssa_name
))
632 error ("found an SSA_NAME that had been released into the free pool");
636 if (is_virtual
&& is_gimple_reg (ssa_name
))
638 error ("found a virtual definition for a GIMPLE register");
642 if (is_virtual
&& SSA_NAME_VAR (ssa_name
) != gimple_vop (cfun
))
644 error ("virtual SSA name for non-VOP decl");
648 if (!is_virtual
&& !is_gimple_reg (ssa_name
))
650 error ("found a real definition for a non-register");
654 if (SSA_NAME_IS_DEFAULT_DEF (ssa_name
)
655 && !gimple_nop_p (SSA_NAME_DEF_STMT (ssa_name
)))
657 error ("found a default name with a non-empty defining statement");
665 /* Return true if the definition of SSA_NAME at block BB is malformed.
667 STMT is the statement where SSA_NAME is created.
669 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
670 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
671 it means that the block in that array slot contains the
672 definition of SSA_NAME.
674 IS_VIRTUAL is true if SSA_NAME is created by a VDEF. */
677 verify_def (basic_block bb
, basic_block
*definition_block
, tree ssa_name
,
678 gimple stmt
, bool is_virtual
)
680 if (verify_ssa_name (ssa_name
, is_virtual
))
683 if (TREE_CODE (SSA_NAME_VAR (ssa_name
)) == RESULT_DECL
684 && DECL_BY_REFERENCE (SSA_NAME_VAR (ssa_name
)))
686 error ("RESULT_DECL should be read only when DECL_BY_REFERENCE is set");
690 if (definition_block
[SSA_NAME_VERSION (ssa_name
)])
692 error ("SSA_NAME created in two different blocks %i and %i",
693 definition_block
[SSA_NAME_VERSION (ssa_name
)]->index
, bb
->index
);
697 definition_block
[SSA_NAME_VERSION (ssa_name
)] = bb
;
699 if (SSA_NAME_DEF_STMT (ssa_name
) != stmt
)
701 error ("SSA_NAME_DEF_STMT is wrong");
702 fprintf (stderr
, "Expected definition statement:\n");
703 print_gimple_stmt (stderr
, SSA_NAME_DEF_STMT (ssa_name
), 4, TDF_VOPS
);
704 fprintf (stderr
, "\nActual definition statement:\n");
705 print_gimple_stmt (stderr
, stmt
, 4, TDF_VOPS
);
712 fprintf (stderr
, "while verifying SSA_NAME ");
713 print_generic_expr (stderr
, ssa_name
, 0);
714 fprintf (stderr
, " in statement\n");
715 print_gimple_stmt (stderr
, stmt
, 4, TDF_VOPS
);
721 /* Return true if the use of SSA_NAME at statement STMT in block BB is
724 DEF_BB is the block where SSA_NAME was found to be created.
726 IDOM contains immediate dominator information for the flowgraph.
728 CHECK_ABNORMAL is true if the caller wants to check whether this use
729 is flowing through an abnormal edge (only used when checking PHI
732 If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
733 that are defined before STMT in basic block BB. */
736 verify_use (basic_block bb
, basic_block def_bb
, use_operand_p use_p
,
737 gimple stmt
, bool check_abnormal
, bitmap names_defined_in_bb
)
740 tree ssa_name
= USE_FROM_PTR (use_p
);
742 if (!TREE_VISITED (ssa_name
))
743 if (verify_imm_links (stderr
, ssa_name
))
746 TREE_VISITED (ssa_name
) = 1;
748 if (gimple_nop_p (SSA_NAME_DEF_STMT (ssa_name
))
749 && SSA_NAME_IS_DEFAULT_DEF (ssa_name
))
750 ; /* Default definitions have empty statements. Nothing to do. */
753 error ("missing definition");
756 else if (bb
!= def_bb
757 && !dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
759 error ("definition in block %i does not dominate use in block %i",
760 def_bb
->index
, bb
->index
);
763 else if (bb
== def_bb
764 && names_defined_in_bb
!= NULL
765 && !bitmap_bit_p (names_defined_in_bb
, SSA_NAME_VERSION (ssa_name
)))
767 error ("definition in block %i follows the use", def_bb
->index
);
772 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name
))
774 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
778 /* Make sure the use is in an appropriate list by checking the previous
779 element to make sure it's the same. */
780 if (use_p
->prev
== NULL
)
782 error ("no immediate_use list");
788 if (use_p
->prev
->use
== NULL
)
789 listvar
= use_p
->prev
->loc
.ssa_name
;
791 listvar
= USE_FROM_PTR (use_p
->prev
);
792 if (listvar
!= ssa_name
)
794 error ("wrong immediate use list");
801 fprintf (stderr
, "for SSA_NAME: ");
802 print_generic_expr (stderr
, ssa_name
, TDF_VOPS
);
803 fprintf (stderr
, " in statement:\n");
804 print_gimple_stmt (stderr
, stmt
, 0, TDF_VOPS
);
811 /* Return true if any of the arguments for PHI node PHI at block BB is
814 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
815 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
816 it means that the block in that array slot contains the
817 definition of SSA_NAME. */
820 verify_phi_args (gimple phi
, basic_block bb
, basic_block
*definition_block
)
824 size_t i
, phi_num_args
= gimple_phi_num_args (phi
);
826 if (EDGE_COUNT (bb
->preds
) != phi_num_args
)
828 error ("incoming edge count does not match number of PHI arguments");
833 for (i
= 0; i
< phi_num_args
; i
++)
835 use_operand_p op_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
836 tree op
= USE_FROM_PTR (op_p
);
838 e
= EDGE_PRED (bb
, i
);
842 error ("PHI argument is missing for edge %d->%d",
849 if (TREE_CODE (op
) != SSA_NAME
&& !is_gimple_min_invariant (op
))
851 error ("PHI argument is not SSA_NAME, or invariant");
855 if (TREE_CODE (op
) == SSA_NAME
)
857 err
= verify_ssa_name (op
, !is_gimple_reg (gimple_phi_result (phi
)));
858 err
|= verify_use (e
->src
, definition_block
[SSA_NAME_VERSION (op
)],
859 op_p
, phi
, e
->flags
& EDGE_ABNORMAL
, NULL
);
862 if (TREE_CODE (op
) == ADDR_EXPR
)
864 tree base
= TREE_OPERAND (op
, 0);
865 while (handled_component_p (base
))
866 base
= TREE_OPERAND (base
, 0);
867 if ((TREE_CODE (base
) == VAR_DECL
868 || TREE_CODE (base
) == PARM_DECL
869 || TREE_CODE (base
) == RESULT_DECL
)
870 && !TREE_ADDRESSABLE (base
))
872 error ("address taken, but ADDRESSABLE bit not set");
879 error ("wrong edge %d->%d for PHI argument",
880 e
->src
->index
, e
->dest
->index
);
886 fprintf (stderr
, "PHI argument\n");
887 print_generic_stmt (stderr
, op
, TDF_VOPS
);
895 fprintf (stderr
, "for PHI node\n");
896 print_gimple_stmt (stderr
, phi
, 0, TDF_VOPS
|TDF_MEMSYMS
);
904 /* Verify common invariants in the SSA web.
905 TODO: verify the variable annotations. */
908 verify_ssa (bool check_modified_stmt
)
912 basic_block
*definition_block
= XCNEWVEC (basic_block
, num_ssa_names
);
915 enum dom_state orig_dom_state
= dom_info_state (CDI_DOMINATORS
);
916 bitmap names_defined_in_bb
= BITMAP_ALLOC (NULL
);
918 gcc_assert (!need_ssa_update_p (cfun
));
920 verify_gimple_in_cfg (cfun
);
922 timevar_push (TV_TREE_SSA_VERIFY
);
924 /* Keep track of SSA names present in the IL. */
925 for (i
= 1; i
< num_ssa_names
; i
++)
927 tree name
= ssa_name (i
);
931 TREE_VISITED (name
) = 0;
933 stmt
= SSA_NAME_DEF_STMT (name
);
934 if (!gimple_nop_p (stmt
))
936 basic_block bb
= gimple_bb (stmt
);
937 verify_def (bb
, definition_block
,
938 name
, stmt
, !is_gimple_reg (name
));
944 calculate_dominance_info (CDI_DOMINATORS
);
946 /* Now verify all the uses and make sure they agree with the definitions
947 found in the previous pass. */
953 gimple_stmt_iterator gsi
;
955 /* Make sure that all edges have a clear 'aux' field. */
956 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
960 error ("AUX pointer initialized for edge %d->%d", e
->src
->index
,
966 /* Verify the arguments for every PHI node in the block. */
967 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
969 phi
= gsi_stmt (gsi
);
970 if (verify_phi_args (phi
, bb
, definition_block
))
973 bitmap_set_bit (names_defined_in_bb
,
974 SSA_NAME_VERSION (gimple_phi_result (phi
)));
977 /* Now verify all the uses and vuses in every statement of the block. */
978 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
980 gimple stmt
= gsi_stmt (gsi
);
986 if (check_modified_stmt
&& gimple_modified_p (stmt
))
988 error ("stmt (%p) marked modified after optimization pass: ",
990 print_gimple_stmt (stderr
, stmt
, 0, TDF_VOPS
);
994 if (is_gimple_assign (stmt
)
995 && TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
997 tree lhs
, base_address
;
999 lhs
= gimple_assign_lhs (stmt
);
1000 base_address
= get_base_address (lhs
);
1003 && SSA_VAR_P (base_address
)
1004 && !gimple_vdef (stmt
)
1007 error ("statement makes a memory store, but has no VDEFS");
1008 print_gimple_stmt (stderr
, stmt
, 0, TDF_VOPS
);
1012 else if (gimple_debug_bind_p (stmt
)
1013 && !gimple_debug_bind_has_value_p (stmt
))
1016 /* Verify the single virtual operand and its constraints. */
1018 if (gimple_vdef (stmt
))
1020 if (gimple_vdef_op (stmt
) == NULL_DEF_OPERAND_P
)
1022 error ("statement has VDEF operand not in defs list");
1025 if (!gimple_vuse (stmt
))
1027 error ("statement has VDEF but no VUSE operand");
1030 else if (SSA_NAME_VAR (gimple_vdef (stmt
))
1031 != SSA_NAME_VAR (gimple_vuse (stmt
)))
1033 error ("VDEF and VUSE do not use the same symbol");
1036 has_err
|= verify_ssa_name (gimple_vdef (stmt
), true);
1038 if (gimple_vuse (stmt
))
1040 if (gimple_vuse_op (stmt
) == NULL_USE_OPERAND_P
)
1042 error ("statement has VUSE operand not in uses list");
1045 has_err
|= verify_ssa_name (gimple_vuse (stmt
), true);
1049 error ("in statement");
1050 print_gimple_stmt (stderr
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
);
1055 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
|SSA_OP_DEF
)
1057 if (verify_ssa_name (op
, false))
1059 error ("in statement");
1060 print_gimple_stmt (stderr
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
);
1066 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
1068 op
= gimple_op (stmt
, i
);
1069 if (op
&& TREE_CODE (op
) == SSA_NAME
&& --count
< 0)
1071 error ("number of operands and imm-links don%'t agree"
1073 print_gimple_stmt (stderr
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
);
1078 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
|SSA_OP_VUSE
)
1080 op
= USE_FROM_PTR (use_p
);
1081 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
1082 use_p
, stmt
, false, names_defined_in_bb
))
1086 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_ALL_DEFS
)
1088 if (SSA_NAME_DEF_STMT (op
) != stmt
)
1090 error ("SSA_NAME_DEF_STMT is wrong");
1091 fprintf (stderr
, "Expected definition statement:\n");
1092 print_gimple_stmt (stderr
, stmt
, 4, TDF_VOPS
);
1093 fprintf (stderr
, "\nActual definition statement:\n");
1094 print_gimple_stmt (stderr
, SSA_NAME_DEF_STMT (op
),
1098 bitmap_set_bit (names_defined_in_bb
, SSA_NAME_VERSION (op
));
1102 bitmap_clear (names_defined_in_bb
);
1105 free (definition_block
);
1107 /* Restore the dominance information to its prior known state, so
1108 that we do not perturb the compiler's subsequent behavior. */
1109 if (orig_dom_state
== DOM_NONE
)
1110 free_dominance_info (CDI_DOMINATORS
);
1112 set_dom_info_availability (CDI_DOMINATORS
, orig_dom_state
);
1114 BITMAP_FREE (names_defined_in_bb
);
1115 timevar_pop (TV_TREE_SSA_VERIFY
);
1119 internal_error ("verify_ssa failed");
1122 /* Return true if the uid in both int tree maps are equal. */
1125 int_tree_map_eq (const void *va
, const void *vb
)
1127 const struct int_tree_map
*a
= (const struct int_tree_map
*) va
;
1128 const struct int_tree_map
*b
= (const struct int_tree_map
*) vb
;
1129 return (a
->uid
== b
->uid
);
1132 /* Hash a UID in a int_tree_map. */
1135 int_tree_map_hash (const void *item
)
1137 return ((const struct int_tree_map
*)item
)->uid
;
1140 /* Return true if the DECL_UID in both trees are equal. */
1143 uid_decl_map_eq (const void *va
, const void *vb
)
1145 const_tree a
= (const_tree
) va
;
1146 const_tree b
= (const_tree
) vb
;
1147 return (a
->decl_minimal
.uid
== b
->decl_minimal
.uid
);
1150 /* Hash a tree in a uid_decl_map. */
1153 uid_decl_map_hash (const void *item
)
1155 return ((const_tree
)item
)->decl_minimal
.uid
;
1158 /* Return true if the DECL_UID in both trees are equal. */
1161 uid_ssaname_map_eq (const void *va
, const void *vb
)
1163 const_tree a
= (const_tree
) va
;
1164 const_tree b
= (const_tree
) vb
;
1165 return (a
->ssa_name
.var
->decl_minimal
.uid
== b
->ssa_name
.var
->decl_minimal
.uid
);
1168 /* Hash a tree in a uid_decl_map. */
1171 uid_ssaname_map_hash (const void *item
)
1173 return ((const_tree
)item
)->ssa_name
.var
->decl_minimal
.uid
;
1177 /* Initialize global DFA and SSA structures. */
1180 init_tree_ssa (struct function
*fn
)
1182 fn
->gimple_df
= ggc_alloc_cleared_gimple_df ();
1183 fn
->gimple_df
->referenced_vars
= htab_create_ggc (20, uid_decl_map_hash
,
1184 uid_decl_map_eq
, NULL
);
1185 fn
->gimple_df
->default_defs
= htab_create_ggc (20, uid_ssaname_map_hash
,
1186 uid_ssaname_map_eq
, NULL
);
1187 pt_solution_reset (&fn
->gimple_df
->escaped
);
1188 init_ssanames (fn
, 0);
1193 /* Deallocate memory associated with SSA data structures for FNDECL. */
1196 delete_tree_ssa (void)
1198 referenced_var_iterator rvi
;
1201 /* Remove annotations from every referenced local variable. */
1202 FOR_EACH_REFERENCED_VAR (cfun
, var
, rvi
)
1204 if (is_global_var (var
))
1208 ggc_free (var_ann (var
));
1209 *DECL_VAR_ANN_PTR (var
) = NULL
;
1212 htab_delete (gimple_referenced_vars (cfun
));
1213 cfun
->gimple_df
->referenced_vars
= NULL
;
1218 /* We no longer maintain the SSA operand cache at this point. */
1219 if (ssa_operands_active ())
1220 fini_ssa_operands ();
1222 htab_delete (cfun
->gimple_df
->default_defs
);
1223 cfun
->gimple_df
->default_defs
= NULL
;
1224 pt_solution_reset (&cfun
->gimple_df
->escaped
);
1225 if (cfun
->gimple_df
->decls_to_pointers
!= NULL
)
1226 pointer_map_destroy (cfun
->gimple_df
->decls_to_pointers
);
1227 cfun
->gimple_df
->decls_to_pointers
= NULL
;
1228 cfun
->gimple_df
->modified_noreturn_calls
= NULL
;
1229 cfun
->gimple_df
= NULL
;
1231 /* We no longer need the edge variable maps. */
1232 redirect_edge_var_map_destroy ();
1235 /* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a
1236 useless type conversion, otherwise return false.
1238 This function implicitly defines the middle-end type system. With
1239 the notion of 'a < b' meaning that useless_type_conversion_p (a, b)
1240 holds and 'a > b' meaning that useless_type_conversion_p (b, a) holds,
1241 the following invariants shall be fulfilled:
1243 1) useless_type_conversion_p is transitive.
1244 If a < b and b < c then a < c.
1246 2) useless_type_conversion_p is not symmetric.
1247 From a < b does not follow a > b.
1249 3) Types define the available set of operations applicable to values.
1250 A type conversion is useless if the operations for the target type
1251 is a subset of the operations for the source type. For example
1252 casts to void* are useless, casts from void* are not (void* can't
1253 be dereferenced or offsetted, but copied, hence its set of operations
1254 is a strict subset of that of all other data pointer types). Casts
1255 to const T* are useless (can't be written to), casts from const T*
1259 useless_type_conversion_p (tree outer_type
, tree inner_type
)
1261 /* Do the following before stripping toplevel qualifiers. */
1262 if (POINTER_TYPE_P (inner_type
)
1263 && POINTER_TYPE_P (outer_type
))
1265 /* Do not lose casts between pointers to different address spaces. */
1266 if (TYPE_ADDR_SPACE (TREE_TYPE (outer_type
))
1267 != TYPE_ADDR_SPACE (TREE_TYPE (inner_type
)))
1270 /* Do not lose casts to restrict qualified pointers. */
1271 if ((TYPE_RESTRICT (outer_type
)
1272 != TYPE_RESTRICT (inner_type
))
1273 && TYPE_RESTRICT (outer_type
))
1276 /* If the outer type is (void *), the conversion is not necessary. */
1277 if (VOID_TYPE_P (TREE_TYPE (outer_type
)))
1281 /* From now on qualifiers on value types do not matter. */
1282 inner_type
= TYPE_MAIN_VARIANT (inner_type
);
1283 outer_type
= TYPE_MAIN_VARIANT (outer_type
);
1285 if (inner_type
== outer_type
)
1288 /* If we know the canonical types, compare them. */
1289 if (TYPE_CANONICAL (inner_type
)
1290 && TYPE_CANONICAL (inner_type
) == TYPE_CANONICAL (outer_type
))
1293 /* Changes in machine mode are never useless conversions unless we
1294 deal with aggregate types in which case we defer to later checks. */
1295 if (TYPE_MODE (inner_type
) != TYPE_MODE (outer_type
)
1296 && !AGGREGATE_TYPE_P (inner_type
))
1299 /* If both the inner and outer types are integral types, then the
1300 conversion is not necessary if they have the same mode and
1301 signedness and precision, and both or neither are boolean. */
1302 if (INTEGRAL_TYPE_P (inner_type
)
1303 && INTEGRAL_TYPE_P (outer_type
))
1305 /* Preserve changes in signedness or precision. */
1306 if (TYPE_UNSIGNED (inner_type
) != TYPE_UNSIGNED (outer_type
)
1307 || TYPE_PRECISION (inner_type
) != TYPE_PRECISION (outer_type
))
1310 /* Preserve conversions to/from BOOLEAN_TYPE if types are not
1311 of precision one. */
1312 if (((TREE_CODE (inner_type
) == BOOLEAN_TYPE
)
1313 != (TREE_CODE (outer_type
) == BOOLEAN_TYPE
))
1314 && TYPE_PRECISION (outer_type
) != 1)
1317 /* We don't need to preserve changes in the types minimum or
1318 maximum value in general as these do not generate code
1319 unless the types precisions are different. */
1323 /* Scalar floating point types with the same mode are compatible. */
1324 else if (SCALAR_FLOAT_TYPE_P (inner_type
)
1325 && SCALAR_FLOAT_TYPE_P (outer_type
))
1328 /* Fixed point types with the same mode are compatible. */
1329 else if (FIXED_POINT_TYPE_P (inner_type
)
1330 && FIXED_POINT_TYPE_P (outer_type
))
1333 /* We need to take special care recursing to pointed-to types. */
1334 else if (POINTER_TYPE_P (inner_type
)
1335 && POINTER_TYPE_P (outer_type
))
1337 /* Do not lose casts to function pointer types. */
1338 if ((TREE_CODE (TREE_TYPE (outer_type
)) == FUNCTION_TYPE
1339 || TREE_CODE (TREE_TYPE (outer_type
)) == METHOD_TYPE
)
1340 && !(TREE_CODE (TREE_TYPE (inner_type
)) == FUNCTION_TYPE
1341 || TREE_CODE (TREE_TYPE (inner_type
)) == METHOD_TYPE
))
1344 /* We do not care for const qualification of the pointed-to types
1345 as const qualification has no semantic value to the middle-end. */
1347 /* Otherwise pointers/references are equivalent. */
1351 /* Recurse for complex types. */
1352 else if (TREE_CODE (inner_type
) == COMPLEX_TYPE
1353 && TREE_CODE (outer_type
) == COMPLEX_TYPE
)
1354 return useless_type_conversion_p (TREE_TYPE (outer_type
),
1355 TREE_TYPE (inner_type
));
1357 /* Recurse for vector types with the same number of subparts. */
1358 else if (TREE_CODE (inner_type
) == VECTOR_TYPE
1359 && TREE_CODE (outer_type
) == VECTOR_TYPE
1360 && TYPE_PRECISION (inner_type
) == TYPE_PRECISION (outer_type
))
1361 return useless_type_conversion_p (TREE_TYPE (outer_type
),
1362 TREE_TYPE (inner_type
));
1364 else if (TREE_CODE (inner_type
) == ARRAY_TYPE
1365 && TREE_CODE (outer_type
) == ARRAY_TYPE
)
1367 /* Preserve string attributes. */
1368 if (TYPE_STRING_FLAG (inner_type
) != TYPE_STRING_FLAG (outer_type
))
1371 /* Conversions from array types with unknown extent to
1372 array types with known extent are not useless. */
1373 if (!TYPE_DOMAIN (inner_type
)
1374 && TYPE_DOMAIN (outer_type
))
1377 /* Nor are conversions from array types with non-constant size to
1378 array types with constant size or to different size. */
1379 if (TYPE_SIZE (outer_type
)
1380 && TREE_CODE (TYPE_SIZE (outer_type
)) == INTEGER_CST
1381 && (!TYPE_SIZE (inner_type
)
1382 || TREE_CODE (TYPE_SIZE (inner_type
)) != INTEGER_CST
1383 || !tree_int_cst_equal (TYPE_SIZE (outer_type
),
1384 TYPE_SIZE (inner_type
))))
1387 /* Check conversions between arrays with partially known extents.
1388 If the array min/max values are constant they have to match.
1389 Otherwise allow conversions to unknown and variable extents.
1390 In particular this declares conversions that may change the
1391 mode to BLKmode as useless. */
1392 if (TYPE_DOMAIN (inner_type
)
1393 && TYPE_DOMAIN (outer_type
)
1394 && TYPE_DOMAIN (inner_type
) != TYPE_DOMAIN (outer_type
))
1396 tree inner_min
= TYPE_MIN_VALUE (TYPE_DOMAIN (inner_type
));
1397 tree outer_min
= TYPE_MIN_VALUE (TYPE_DOMAIN (outer_type
));
1398 tree inner_max
= TYPE_MAX_VALUE (TYPE_DOMAIN (inner_type
));
1399 tree outer_max
= TYPE_MAX_VALUE (TYPE_DOMAIN (outer_type
));
1401 /* After gimplification a variable min/max value carries no
1402 additional information compared to a NULL value. All that
1403 matters has been lowered to be part of the IL. */
1404 if (inner_min
&& TREE_CODE (inner_min
) != INTEGER_CST
)
1405 inner_min
= NULL_TREE
;
1406 if (outer_min
&& TREE_CODE (outer_min
) != INTEGER_CST
)
1407 outer_min
= NULL_TREE
;
1408 if (inner_max
&& TREE_CODE (inner_max
) != INTEGER_CST
)
1409 inner_max
= NULL_TREE
;
1410 if (outer_max
&& TREE_CODE (outer_max
) != INTEGER_CST
)
1411 outer_max
= NULL_TREE
;
1413 /* Conversions NULL / variable <- cst are useless, but not
1414 the other way around. */
1417 || !tree_int_cst_equal (inner_min
, outer_min
)))
1421 || !tree_int_cst_equal (inner_max
, outer_max
)))
1425 /* Recurse on the element check. */
1426 return useless_type_conversion_p (TREE_TYPE (outer_type
),
1427 TREE_TYPE (inner_type
));
1430 else if ((TREE_CODE (inner_type
) == FUNCTION_TYPE
1431 || TREE_CODE (inner_type
) == METHOD_TYPE
)
1432 && TREE_CODE (inner_type
) == TREE_CODE (outer_type
))
1434 tree outer_parm
, inner_parm
;
1436 /* If the return types are not compatible bail out. */
1437 if (!useless_type_conversion_p (TREE_TYPE (outer_type
),
1438 TREE_TYPE (inner_type
)))
1441 /* Method types should belong to a compatible base class. */
1442 if (TREE_CODE (inner_type
) == METHOD_TYPE
1443 && !useless_type_conversion_p (TYPE_METHOD_BASETYPE (outer_type
),
1444 TYPE_METHOD_BASETYPE (inner_type
)))
1447 /* A conversion to an unprototyped argument list is ok. */
1448 if (!prototype_p (outer_type
))
1451 /* If the unqualified argument types are compatible the conversion
1453 if (TYPE_ARG_TYPES (outer_type
) == TYPE_ARG_TYPES (inner_type
))
1456 for (outer_parm
= TYPE_ARG_TYPES (outer_type
),
1457 inner_parm
= TYPE_ARG_TYPES (inner_type
);
1458 outer_parm
&& inner_parm
;
1459 outer_parm
= TREE_CHAIN (outer_parm
),
1460 inner_parm
= TREE_CHAIN (inner_parm
))
1461 if (!useless_type_conversion_p
1462 (TYPE_MAIN_VARIANT (TREE_VALUE (outer_parm
)),
1463 TYPE_MAIN_VARIANT (TREE_VALUE (inner_parm
))))
1466 /* If there is a mismatch in the number of arguments the functions
1467 are not compatible. */
1468 if (outer_parm
|| inner_parm
)
1471 /* Defer to the target if necessary. */
1472 if (TYPE_ATTRIBUTES (inner_type
) || TYPE_ATTRIBUTES (outer_type
))
1473 return comp_type_attributes (outer_type
, inner_type
) != 0;
1478 /* For aggregates we rely on TYPE_CANONICAL exclusively and require
1479 explicit conversions for types involving to be structurally
1481 else if (AGGREGATE_TYPE_P (inner_type
)
1482 && TREE_CODE (inner_type
) == TREE_CODE (outer_type
))
1488 /* Return true if a conversion from either type of TYPE1 and TYPE2
1489 to the other is not required. Otherwise return false. */
1492 types_compatible_p (tree type1
, tree type2
)
1494 return (type1
== type2
1495 || (useless_type_conversion_p (type1
, type2
)
1496 && useless_type_conversion_p (type2
, type1
)));
1499 /* Return true if EXPR is a useless type conversion, otherwise return
1503 tree_ssa_useless_type_conversion (tree expr
)
1505 /* If we have an assignment that merely uses a NOP_EXPR to change
1506 the top of the RHS to the type of the LHS and the type conversion
1507 is "safe", then strip away the type conversion so that we can
1508 enter LHS = RHS into the const_and_copies table. */
1509 if (CONVERT_EXPR_P (expr
)
1510 || TREE_CODE (expr
) == VIEW_CONVERT_EXPR
1511 || TREE_CODE (expr
) == NON_LVALUE_EXPR
)
1512 return useless_type_conversion_p
1514 TREE_TYPE (TREE_OPERAND (expr
, 0)));
1519 /* Strip conversions from EXP according to
1520 tree_ssa_useless_type_conversion and return the resulting
1524 tree_ssa_strip_useless_type_conversions (tree exp
)
1526 while (tree_ssa_useless_type_conversion (exp
))
1527 exp
= TREE_OPERAND (exp
, 0);
1532 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
1533 described in walk_use_def_chains.
1535 VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
1536 infinite loops. We used to have a bitmap for this to just mark
1537 SSA versions we had visited. But non-sparse bitmaps are way too
1538 expensive, while sparse bitmaps may cause quadratic behavior.
1540 IS_DFS is true if the caller wants to perform a depth-first search
1541 when visiting PHI nodes. A DFS will visit each PHI argument and
1542 call FN after each one. Otherwise, all the arguments are
1543 visited first and then FN is called with each of the visited
1544 arguments in a separate pass. */
1547 walk_use_def_chains_1 (tree var
, walk_use_def_chains_fn fn
, void *data
,
1548 struct pointer_set_t
*visited
, bool is_dfs
)
1552 if (pointer_set_insert (visited
, var
))
1555 def_stmt
= SSA_NAME_DEF_STMT (var
);
1557 if (gimple_code (def_stmt
) != GIMPLE_PHI
)
1559 /* If we reached the end of the use-def chain, call FN. */
1560 return fn (var
, def_stmt
, data
);
1566 /* When doing a breadth-first search, call FN before following the
1567 use-def links for each argument. */
1569 for (i
= 0; i
< gimple_phi_num_args (def_stmt
); i
++)
1570 if (fn (gimple_phi_arg_def (def_stmt
, i
), def_stmt
, data
))
1573 /* Follow use-def links out of each PHI argument. */
1574 for (i
= 0; i
< gimple_phi_num_args (def_stmt
); i
++)
1576 tree arg
= gimple_phi_arg_def (def_stmt
, i
);
1578 /* ARG may be NULL for newly introduced PHI nodes. */
1580 && TREE_CODE (arg
) == SSA_NAME
1581 && walk_use_def_chains_1 (arg
, fn
, data
, visited
, is_dfs
))
1585 /* When doing a depth-first search, call FN after following the
1586 use-def links for each argument. */
1588 for (i
= 0; i
< gimple_phi_num_args (def_stmt
); i
++)
1589 if (fn (gimple_phi_arg_def (def_stmt
, i
), def_stmt
, data
))
1598 /* Walk use-def chains starting at the SSA variable VAR. Call
1599 function FN at each reaching definition found. FN takes three
1600 arguments: VAR, its defining statement (DEF_STMT) and a generic
1601 pointer to whatever state information that FN may want to maintain
1602 (DATA). FN is able to stop the walk by returning true, otherwise
1603 in order to continue the walk, FN should return false.
1605 Note, that if DEF_STMT is a PHI node, the semantics are slightly
1606 different. The first argument to FN is no longer the original
1607 variable VAR, but the PHI argument currently being examined. If FN
1608 wants to get at VAR, it should call PHI_RESULT (PHI).
1610 If IS_DFS is true, this function will:
1612 1- walk the use-def chains for all the PHI arguments, and,
1613 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
1615 If IS_DFS is false, the two steps above are done in reverse order
1616 (i.e., a breadth-first search). */
1619 walk_use_def_chains (tree var
, walk_use_def_chains_fn fn
, void *data
,
1624 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
1626 def_stmt
= SSA_NAME_DEF_STMT (var
);
1628 /* We only need to recurse if the reaching definition comes from a PHI
1630 if (gimple_code (def_stmt
) != GIMPLE_PHI
)
1631 (*fn
) (var
, def_stmt
, data
);
1634 struct pointer_set_t
*visited
= pointer_set_create ();
1635 walk_use_def_chains_1 (var
, fn
, data
, visited
, is_dfs
);
1636 pointer_set_destroy (visited
);
1641 /* Emit warnings for uninitialized variables. This is done in two passes.
1643 The first pass notices real uses of SSA names with undefined values.
1644 Such uses are unconditionally uninitialized, and we can be certain that
1645 such a use is a mistake. This pass is run before most optimizations,
1646 so that we catch as many as we can.
1648 The second pass follows PHI nodes to find uses that are potentially
1649 uninitialized. In this case we can't necessarily prove that the use
1650 is really uninitialized. This pass is run after most optimizations,
1651 so that we thread as many jumps and possible, and delete as much dead
1652 code as possible, in order to reduce false positives. We also look
1653 again for plain uninitialized variables, since optimization may have
1654 changed conditionally uninitialized to unconditionally uninitialized. */
1656 /* Emit a warning for EXPR based on variable VAR at the point in the
1657 program T, an SSA_NAME, is used being uninitialized. The exact
1658 warning text is in MSGID and LOCUS may contain a location or be null.
1659 WC is the warning code. */
1662 warn_uninit (enum opt_code wc
, tree t
,
1663 tree expr
, tree var
, const char *gmsgid
, void *data
)
1665 gimple context
= (gimple
) data
;
1666 location_t location
;
1667 expanded_location xloc
, floc
;
1669 if (!ssa_undefined_value_p (t
))
1672 /* TREE_NO_WARNING either means we already warned, or the front end
1673 wishes to suppress the warning. */
1675 && (gimple_no_warning_p (context
)
1676 || (gimple_assign_single_p (context
)
1677 && TREE_NO_WARNING (gimple_assign_rhs1 (context
)))))
1678 || TREE_NO_WARNING (expr
))
1681 location
= (context
!= NULL
&& gimple_has_location (context
))
1682 ? gimple_location (context
)
1683 : DECL_SOURCE_LOCATION (var
);
1684 xloc
= expand_location (location
);
1685 floc
= expand_location (DECL_SOURCE_LOCATION (cfun
->decl
));
1686 if (warning_at (location
, wc
, gmsgid
, expr
))
1688 TREE_NO_WARNING (expr
) = 1;
1690 if (location
== DECL_SOURCE_LOCATION (var
))
1692 if (xloc
.file
!= floc
.file
1693 || xloc
.line
< floc
.line
1694 || xloc
.line
> LOCATION_LINE (cfun
->function_end_locus
))
1695 inform (DECL_SOURCE_LOCATION (var
), "%qD was declared here", var
);
1700 warn_uninitialized_vars (bool warn_possibly_uninitialized
)
1702 gimple_stmt_iterator gsi
;
1707 bool always_executed
= dominated_by_p (CDI_POST_DOMINATORS
,
1708 single_succ (ENTRY_BLOCK_PTR
), bb
);
1709 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1711 gimple stmt
= gsi_stmt (gsi
);
1712 use_operand_p use_p
;
1713 ssa_op_iter op_iter
;
1716 if (is_gimple_debug (stmt
))
1719 /* We only do data flow with SSA_NAMEs, so that's all we
1721 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, op_iter
, SSA_OP_USE
)
1723 use
= USE_FROM_PTR (use_p
);
1724 if (always_executed
)
1725 warn_uninit (OPT_Wuninitialized
, use
,
1726 SSA_NAME_VAR (use
), SSA_NAME_VAR (use
),
1727 "%qD is used uninitialized in this function",
1729 else if (warn_possibly_uninitialized
)
1730 warn_uninit (OPT_Wuninitialized
, use
,
1731 SSA_NAME_VAR (use
), SSA_NAME_VAR (use
),
1732 "%qD may be used uninitialized in this function",
1736 /* For memory the only cheap thing we can do is see if we
1737 have a use of the default def of the virtual operand.
1738 ??? Note that at -O0 we do not have virtual operands.
1739 ??? Not so cheap would be to use the alias oracle via
1740 walk_aliased_vdefs, if we don't find any aliasing vdef
1741 warn as is-used-uninitialized, if we don't find an aliasing
1742 vdef that kills our use (stmt_kills_ref_p), warn as
1743 may-be-used-uninitialized. But this walk is quadratic and
1744 so must be limited which means we would miss warning
1746 use
= gimple_vuse (stmt
);
1748 && gimple_assign_single_p (stmt
)
1749 && !gimple_vdef (stmt
)
1750 && SSA_NAME_IS_DEFAULT_DEF (use
))
1752 tree rhs
= gimple_assign_rhs1 (stmt
);
1753 tree base
= get_base_address (rhs
);
1755 /* Do not warn if it can be initialized outside this function. */
1756 if (TREE_CODE (base
) != VAR_DECL
1757 || DECL_HARD_REGISTER (base
)
1758 || is_global_var (base
))
1761 if (always_executed
)
1762 warn_uninit (OPT_Wuninitialized
, use
, gimple_assign_rhs1 (stmt
),
1764 "%qE is used uninitialized in this function",
1766 else if (warn_possibly_uninitialized
)
1767 warn_uninit (OPT_Wuninitialized
, use
, gimple_assign_rhs1 (stmt
),
1769 "%qE may be used uninitialized in this function",
1779 execute_early_warn_uninitialized (void)
1781 /* Currently, this pass runs always but
1782 execute_late_warn_uninitialized only runs with optimization. With
1783 optimization we want to warn about possible uninitialized as late
1784 as possible, thus don't do it here. However, without
1785 optimization we need to warn here about "may be uninitialized".
1787 calculate_dominance_info (CDI_POST_DOMINATORS
);
1789 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize
);
1791 /* Post-dominator information can not be reliably updated. Free it
1794 free_dominance_info (CDI_POST_DOMINATORS
);
1799 gate_warn_uninitialized (void)
1801 return warn_uninitialized
!= 0;
1804 struct gimple_opt_pass pass_early_warn_uninitialized
=
1808 "*early_warn_uninitialized", /* name */
1809 gate_warn_uninitialized
, /* gate */
1810 execute_early_warn_uninitialized
, /* execute */
1813 0, /* static_pass_number */
1814 TV_TREE_UNINIT
, /* tv_id */
1815 PROP_ssa
, /* properties_required */
1816 0, /* properties_provided */
1817 0, /* properties_destroyed */
1818 0, /* todo_flags_start */
1819 0 /* todo_flags_finish */
1824 /* If necessary, rewrite the base of the reference tree *TP from
1825 a MEM_REF to a plain or converted symbol. */
1828 maybe_rewrite_mem_ref_base (tree
*tp
)
1832 while (handled_component_p (*tp
))
1833 tp
= &TREE_OPERAND (*tp
, 0);
1834 if (TREE_CODE (*tp
) == MEM_REF
1835 && TREE_CODE (TREE_OPERAND (*tp
, 0)) == ADDR_EXPR
1836 && (sym
= TREE_OPERAND (TREE_OPERAND (*tp
, 0), 0))
1838 && !TREE_ADDRESSABLE (sym
)
1839 && symbol_marked_for_renaming (sym
))
1841 if (TREE_CODE (TREE_TYPE (sym
)) == VECTOR_TYPE
1842 && useless_type_conversion_p (TREE_TYPE (*tp
),
1843 TREE_TYPE (TREE_TYPE (sym
)))
1844 && multiple_of_p (sizetype
, TREE_OPERAND (*tp
, 1),
1845 TYPE_SIZE_UNIT (TREE_TYPE (*tp
))))
1847 *tp
= build3 (BIT_FIELD_REF
, TREE_TYPE (*tp
), sym
,
1848 TYPE_SIZE (TREE_TYPE (*tp
)),
1849 int_const_binop (MULT_EXPR
,
1850 bitsize_int (BITS_PER_UNIT
),
1851 TREE_OPERAND (*tp
, 1)));
1853 else if (TREE_CODE (TREE_TYPE (sym
)) == COMPLEX_TYPE
1854 && useless_type_conversion_p (TREE_TYPE (*tp
),
1855 TREE_TYPE (TREE_TYPE (sym
))))
1857 *tp
= build1 (integer_zerop (TREE_OPERAND (*tp
, 1))
1858 ? REALPART_EXPR
: IMAGPART_EXPR
,
1859 TREE_TYPE (*tp
), sym
);
1861 else if (integer_zerop (TREE_OPERAND (*tp
, 1)))
1863 if (!useless_type_conversion_p (TREE_TYPE (*tp
),
1865 *tp
= build1 (VIEW_CONVERT_EXPR
,
1866 TREE_TYPE (*tp
), sym
);
1873 /* For a tree REF return its base if it is the base of a MEM_REF
1874 that cannot be rewritten into SSA form. Otherwise return NULL_TREE. */
1877 non_rewritable_mem_ref_base (tree ref
)
1881 /* A plain decl does not need it set. */
1885 while (handled_component_p (base
))
1886 base
= TREE_OPERAND (base
, 0);
1888 /* But watch out for MEM_REFs we cannot lower to a
1889 VIEW_CONVERT_EXPR or a BIT_FIELD_REF. */
1890 if (TREE_CODE (base
) == MEM_REF
1891 && TREE_CODE (TREE_OPERAND (base
, 0)) == ADDR_EXPR
)
1893 tree decl
= TREE_OPERAND (TREE_OPERAND (base
, 0), 0);
1894 if ((TREE_CODE (TREE_TYPE (decl
)) == VECTOR_TYPE
1895 || TREE_CODE (TREE_TYPE (decl
)) == COMPLEX_TYPE
)
1896 && useless_type_conversion_p (TREE_TYPE (base
),
1897 TREE_TYPE (TREE_TYPE (decl
)))
1898 && double_int_fits_in_uhwi_p (mem_ref_offset (base
))
1900 (tree_to_double_int (TYPE_SIZE_UNIT (TREE_TYPE (decl
))),
1901 mem_ref_offset (base
)) == 1
1902 && multiple_of_p (sizetype
, TREE_OPERAND (base
, 1),
1903 TYPE_SIZE_UNIT (TREE_TYPE (base
))))
1906 && (!integer_zerop (TREE_OPERAND (base
, 1))
1907 || (DECL_SIZE (decl
)
1908 != TYPE_SIZE (TREE_TYPE (base
)))
1909 || TREE_THIS_VOLATILE (decl
) != TREE_THIS_VOLATILE (base
)))
1916 /* For an lvalue tree LHS return true if it cannot be rewritten into SSA form.
1917 Otherwise return true. */
1920 non_rewritable_lvalue_p (tree lhs
)
1922 /* A plain decl is always rewritable. */
1926 /* A decl that is wrapped inside a MEM-REF that covers
1927 it full is also rewritable.
1928 ??? The following could be relaxed allowing component
1929 references that do not change the access size. */
1930 if (TREE_CODE (lhs
) == MEM_REF
1931 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == ADDR_EXPR
1932 && integer_zerop (TREE_OPERAND (lhs
, 1)))
1934 tree decl
= TREE_OPERAND (TREE_OPERAND (lhs
, 0), 0);
1936 && DECL_SIZE (decl
) == TYPE_SIZE (TREE_TYPE (lhs
))
1937 && (TREE_THIS_VOLATILE (decl
) == TREE_THIS_VOLATILE (lhs
)))
1944 /* When possible, clear TREE_ADDRESSABLE bit or set DECL_GIMPLE_REG_P bit and
1945 mark the variable VAR for conversion into SSA. Return true when updating
1946 stmts is required. */
1949 maybe_optimize_var (tree var
, bitmap addresses_taken
, bitmap not_reg_needs
)
1951 bool update_vops
= false;
1953 /* Global Variables, result decls cannot be changed. */
1954 if (is_global_var (var
)
1955 || TREE_CODE (var
) == RESULT_DECL
1956 || bitmap_bit_p (addresses_taken
, DECL_UID (var
)))
1959 /* If the variable is not in the list of referenced vars then we
1960 do not need to touch it nor can we rename it. */
1961 if (!referenced_var_lookup (cfun
, DECL_UID (var
)))
1964 if (TREE_ADDRESSABLE (var
)
1965 /* Do not change TREE_ADDRESSABLE if we need to preserve var as
1966 a non-register. Otherwise we are confused and forget to
1967 add virtual operands for it. */
1968 && (!is_gimple_reg_type (TREE_TYPE (var
))
1969 || !bitmap_bit_p (not_reg_needs
, DECL_UID (var
))))
1971 TREE_ADDRESSABLE (var
) = 0;
1972 if (is_gimple_reg (var
))
1973 mark_sym_for_renaming (var
);
1977 fprintf (dump_file
, "No longer having address taken: ");
1978 print_generic_expr (dump_file
, var
, 0);
1979 fprintf (dump_file
, "\n");
1983 if (!DECL_GIMPLE_REG_P (var
)
1984 && !bitmap_bit_p (not_reg_needs
, DECL_UID (var
))
1985 && (TREE_CODE (TREE_TYPE (var
)) == COMPLEX_TYPE
1986 || TREE_CODE (TREE_TYPE (var
)) == VECTOR_TYPE
)
1987 && !TREE_THIS_VOLATILE (var
)
1988 && (TREE_CODE (var
) != VAR_DECL
|| !DECL_HARD_REGISTER (var
)))
1990 DECL_GIMPLE_REG_P (var
) = 1;
1991 mark_sym_for_renaming (var
);
1995 fprintf (dump_file
, "Now a gimple register: ");
1996 print_generic_expr (dump_file
, var
, 0);
1997 fprintf (dump_file
, "\n");
2004 /* Compute TREE_ADDRESSABLE and DECL_GIMPLE_REG_P for local variables. */
2007 execute_update_addresses_taken (void)
2009 gimple_stmt_iterator gsi
;
2011 bitmap addresses_taken
= BITMAP_ALLOC (NULL
);
2012 bitmap not_reg_needs
= BITMAP_ALLOC (NULL
);
2013 bool update_vops
= false;
2017 timevar_push (TV_ADDRESS_TAKEN
);
2019 /* Collect into ADDRESSES_TAKEN all variables whose address is taken within
2020 the function body. */
2023 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2025 gimple stmt
= gsi_stmt (gsi
);
2026 enum gimple_code code
= gimple_code (stmt
);
2029 /* Note all addresses taken by the stmt. */
2030 gimple_ior_addresses_taken (addresses_taken
, stmt
);
2032 /* If we have a call or an assignment, see if the lhs contains
2033 a local decl that requires not to be a gimple register. */
2034 if (code
== GIMPLE_ASSIGN
|| code
== GIMPLE_CALL
)
2036 tree lhs
= gimple_get_lhs (stmt
);
2038 && TREE_CODE (lhs
) != SSA_NAME
2039 && non_rewritable_lvalue_p (lhs
))
2041 decl
= get_base_address (lhs
);
2043 bitmap_set_bit (not_reg_needs
, DECL_UID (decl
));
2047 if (gimple_assign_single_p (stmt
))
2049 tree rhs
= gimple_assign_rhs1 (stmt
);
2050 if ((decl
= non_rewritable_mem_ref_base (rhs
)))
2051 bitmap_set_bit (not_reg_needs
, DECL_UID (decl
));
2054 else if (code
== GIMPLE_CALL
)
2056 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
2058 tree arg
= gimple_call_arg (stmt
, i
);
2059 if ((decl
= non_rewritable_mem_ref_base (arg
)))
2060 bitmap_set_bit (not_reg_needs
, DECL_UID (decl
));
2064 else if (code
== GIMPLE_ASM
)
2066 for (i
= 0; i
< gimple_asm_noutputs (stmt
); ++i
)
2068 tree link
= gimple_asm_output_op (stmt
, i
);
2069 tree lhs
= TREE_VALUE (link
);
2070 if (TREE_CODE (lhs
) != SSA_NAME
)
2072 decl
= get_base_address (lhs
);
2074 && (non_rewritable_lvalue_p (lhs
)
2075 /* We cannot move required conversions from
2076 the lhs to the rhs in asm statements, so
2077 require we do not need any. */
2078 || !useless_type_conversion_p
2079 (TREE_TYPE (lhs
), TREE_TYPE (decl
))))
2080 bitmap_set_bit (not_reg_needs
, DECL_UID (decl
));
2083 for (i
= 0; i
< gimple_asm_ninputs (stmt
); ++i
)
2085 tree link
= gimple_asm_input_op (stmt
, i
);
2086 if ((decl
= non_rewritable_mem_ref_base (TREE_VALUE (link
))))
2087 bitmap_set_bit (not_reg_needs
, DECL_UID (decl
));
2092 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2095 gimple phi
= gsi_stmt (gsi
);
2097 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2099 tree op
= PHI_ARG_DEF (phi
, i
), var
;
2100 if (TREE_CODE (op
) == ADDR_EXPR
2101 && (var
= get_base_address (TREE_OPERAND (op
, 0))) != NULL
2103 bitmap_set_bit (addresses_taken
, DECL_UID (var
));
2108 /* We cannot iterate over all referenced vars because that can contain
2109 unused vars from BLOCK trees, which causes code generation differences
2111 for (var
= DECL_ARGUMENTS (cfun
->decl
); var
; var
= DECL_CHAIN (var
))
2112 update_vops
|= maybe_optimize_var (var
, addresses_taken
, not_reg_needs
);
2114 FOR_EACH_VEC_ELT (tree
, cfun
->local_decls
, i
, var
)
2115 update_vops
|= maybe_optimize_var (var
, addresses_taken
, not_reg_needs
);
2117 /* Operand caches need to be recomputed for operands referencing the updated
2122 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2124 gimple stmt
= gsi_stmt (gsi
);
2126 /* Re-write TARGET_MEM_REFs of symbols we want to
2127 rewrite into SSA form. */
2128 if (gimple_assign_single_p (stmt
))
2130 tree lhs
= gimple_assign_lhs (stmt
);
2131 tree rhs
, *rhsp
= gimple_assign_rhs1_ptr (stmt
);
2134 /* We shouldn't have any fancy wrapping of
2135 component-refs on the LHS, but look through
2136 VIEW_CONVERT_EXPRs as that is easy. */
2137 while (TREE_CODE (lhs
) == VIEW_CONVERT_EXPR
)
2138 lhs
= TREE_OPERAND (lhs
, 0);
2139 if (TREE_CODE (lhs
) == MEM_REF
2140 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == ADDR_EXPR
2141 && integer_zerop (TREE_OPERAND (lhs
, 1))
2142 && (sym
= TREE_OPERAND (TREE_OPERAND (lhs
, 0), 0))
2144 && !TREE_ADDRESSABLE (sym
)
2145 && symbol_marked_for_renaming (sym
))
2148 lhs
= gimple_assign_lhs (stmt
);
2150 /* Rewrite the RHS and make sure the resulting assignment
2151 is validly typed. */
2152 maybe_rewrite_mem_ref_base (rhsp
);
2153 rhs
= gimple_assign_rhs1 (stmt
);
2154 if (gimple_assign_lhs (stmt
) != lhs
2155 && !useless_type_conversion_p (TREE_TYPE (lhs
),
2157 rhs
= fold_build1 (VIEW_CONVERT_EXPR
,
2158 TREE_TYPE (lhs
), rhs
);
2160 if (gimple_assign_lhs (stmt
) != lhs
)
2161 gimple_assign_set_lhs (stmt
, lhs
);
2163 if (gimple_assign_rhs1 (stmt
) != rhs
)
2165 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
2166 gimple_assign_set_rhs_from_tree (&gsi
, rhs
);
2170 else if (gimple_code (stmt
) == GIMPLE_CALL
)
2173 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
2175 tree
*argp
= gimple_call_arg_ptr (stmt
, i
);
2176 maybe_rewrite_mem_ref_base (argp
);
2180 else if (gimple_code (stmt
) == GIMPLE_ASM
)
2183 for (i
= 0; i
< gimple_asm_noutputs (stmt
); ++i
)
2185 tree link
= gimple_asm_output_op (stmt
, i
);
2186 maybe_rewrite_mem_ref_base (&TREE_VALUE (link
));
2188 for (i
= 0; i
< gimple_asm_ninputs (stmt
); ++i
)
2190 tree link
= gimple_asm_input_op (stmt
, i
);
2191 maybe_rewrite_mem_ref_base (&TREE_VALUE (link
));
2195 else if (gimple_debug_bind_p (stmt
)
2196 && gimple_debug_bind_has_value_p (stmt
))
2198 tree
*valuep
= gimple_debug_bind_get_value_ptr (stmt
);
2200 maybe_rewrite_mem_ref_base (valuep
);
2201 decl
= non_rewritable_mem_ref_base (*valuep
);
2202 if (decl
&& symbol_marked_for_renaming (decl
))
2203 gimple_debug_bind_reset_value (stmt
);
2206 if (gimple_references_memory_p (stmt
)
2207 || is_gimple_debug (stmt
))
2211 /* Update SSA form here, we are called as non-pass as well. */
2212 if (number_of_loops () > 1 && loops_state_satisfies_p (LOOP_CLOSED_SSA
))
2213 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
2215 update_ssa (TODO_update_ssa
);
2218 BITMAP_FREE (not_reg_needs
);
2219 BITMAP_FREE (addresses_taken
);
2220 timevar_pop (TV_ADDRESS_TAKEN
);
2223 struct gimple_opt_pass pass_update_address_taken
=
2227 "addressables", /* name */
2232 0, /* static_pass_number */
2233 TV_ADDRESS_TAKEN
, /* tv_id */
2234 PROP_ssa
, /* properties_required */
2235 0, /* properties_provided */
2236 0, /* properties_destroyed */
2237 0, /* todo_flags_start */
2238 TODO_update_address_taken
/* todo_flags_finish */