1 /* Miscellaneous SSA utility functions.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008 Free Software
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 "hard-reg-set.h"
32 #include "basic-block.h"
36 #include "diagnostic.h"
38 #include "pointer-set.h"
39 #include "tree-flow.h"
40 #include "tree-gimple.h"
41 #include "tree-inline.h"
45 #include "tree-dump.h"
46 #include "tree-pass.h"
49 /* Pointer map of variable mappings, keyed by edge. */
50 static struct pointer_map_t
*edge_var_maps
;
53 /* Add a mapping with PHI RESULT and PHI DEF associated with edge E. */
56 redirect_edge_var_map_add (edge e
, tree result
, tree def
)
59 edge_var_map_vector old_head
, head
;
60 edge_var_map new_node
;
62 if (edge_var_maps
== NULL
)
63 edge_var_maps
= pointer_map_create ();
65 slot
= pointer_map_insert (edge_var_maps
, e
);
66 old_head
= head
= (edge_var_map_vector
) *slot
;
69 head
= VEC_alloc (edge_var_map
, heap
, 5);
73 new_node
.result
= result
;
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
; 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
;
153 /* Clear the edge variable mappings. */
156 redirect_edge_var_map_destroy (void)
160 pointer_map_destroy (edge_var_maps
);
161 edge_var_maps
= NULL
;
166 /* Remove the corresponding arguments from the PHI nodes in E's
167 destination block and redirect it to DEST. Return redirected edge.
168 The list of removed arguments is stored in a vector accessed
169 through edge_var_maps. */
172 ssa_redirect_edge (edge e
, basic_block dest
)
176 redirect_edge_var_map_clear (e
);
178 /* Remove the appropriate PHI arguments in E's destination block. */
179 for (phi
= phi_nodes (e
->dest
); phi
; phi
= PHI_CHAIN (phi
))
181 tree def
= PHI_ARG_DEF (phi
, e
->dest_idx
);
183 if (def
== NULL_TREE
)
186 redirect_edge_var_map_add (e
, PHI_RESULT (phi
), def
);
189 e
= redirect_edge_succ_nodup (e
, dest
);
194 /* Add PHI arguments queued in PENDING_STMT list on edge E to edge
198 flush_pending_stmts (edge e
)
201 edge_var_map_vector v
;
205 v
= redirect_edge_var_map_vector (e
);
209 for (phi
= phi_nodes (e
->dest
), i
= 0;
210 phi
&& VEC_iterate (edge_var_map
, v
, i
, vm
);
211 phi
= PHI_CHAIN (phi
), i
++)
213 tree def
= redirect_edge_var_map_def (vm
);
214 add_phi_arg (phi
, def
, e
);
217 redirect_edge_var_map_clear (e
);
220 /* Return true if SSA_NAME is malformed and mark it visited.
222 IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
226 verify_ssa_name (tree ssa_name
, bool is_virtual
)
228 if (TREE_CODE (ssa_name
) != SSA_NAME
)
230 error ("expected an SSA_NAME object");
234 if (TREE_TYPE (ssa_name
) != TREE_TYPE (SSA_NAME_VAR (ssa_name
)))
236 error ("type mismatch between an SSA_NAME and its symbol");
240 if (SSA_NAME_IN_FREE_LIST (ssa_name
))
242 error ("found an SSA_NAME that had been released into the free pool");
246 if (is_virtual
&& is_gimple_reg (ssa_name
))
248 error ("found a virtual definition for a GIMPLE register");
252 if (!is_virtual
&& !is_gimple_reg (ssa_name
))
254 error ("found a real definition for a non-register");
258 if (SSA_NAME_IS_DEFAULT_DEF (ssa_name
)
259 && !IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name
)))
261 error ("found a default name with a non-empty defining statement");
269 /* Return true if the definition of SSA_NAME at block BB is malformed.
271 STMT is the statement where SSA_NAME is created.
273 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
274 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
275 it means that the block in that array slot contains the
276 definition of SSA_NAME.
278 IS_VIRTUAL is true if SSA_NAME is created by a VDEF. */
281 verify_def (basic_block bb
, basic_block
*definition_block
, tree ssa_name
,
282 tree stmt
, bool is_virtual
)
284 if (verify_ssa_name (ssa_name
, is_virtual
))
287 if (definition_block
[SSA_NAME_VERSION (ssa_name
)])
289 error ("SSA_NAME created in two different blocks %i and %i",
290 definition_block
[SSA_NAME_VERSION (ssa_name
)]->index
, bb
->index
);
294 definition_block
[SSA_NAME_VERSION (ssa_name
)] = bb
;
296 if (SSA_NAME_DEF_STMT (ssa_name
) != stmt
)
298 error ("SSA_NAME_DEF_STMT is wrong");
299 fprintf (stderr
, "Expected definition statement:\n");
300 print_generic_stmt (stderr
, SSA_NAME_DEF_STMT (ssa_name
), TDF_VOPS
);
301 fprintf (stderr
, "\nActual definition statement:\n");
302 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
309 fprintf (stderr
, "while verifying SSA_NAME ");
310 print_generic_expr (stderr
, ssa_name
, 0);
311 fprintf (stderr
, " in statement\n");
312 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
318 /* Return true if the use of SSA_NAME at statement STMT in block BB is
321 DEF_BB is the block where SSA_NAME was found to be created.
323 IDOM contains immediate dominator information for the flowgraph.
325 CHECK_ABNORMAL is true if the caller wants to check whether this use
326 is flowing through an abnormal edge (only used when checking PHI
329 If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
330 that are defined before STMT in basic block BB. */
333 verify_use (basic_block bb
, basic_block def_bb
, use_operand_p use_p
,
334 tree stmt
, bool check_abnormal
, bitmap names_defined_in_bb
)
337 tree ssa_name
= USE_FROM_PTR (use_p
);
339 if (!TREE_VISITED (ssa_name
))
340 if (verify_imm_links (stderr
, ssa_name
))
343 TREE_VISITED (ssa_name
) = 1;
345 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name
))
346 && SSA_NAME_IS_DEFAULT_DEF (ssa_name
))
347 ; /* Default definitions have empty statements. Nothing to do. */
350 error ("missing definition");
353 else if (bb
!= def_bb
354 && !dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
356 error ("definition in block %i does not dominate use in block %i",
357 def_bb
->index
, bb
->index
);
360 else if (bb
== def_bb
361 && names_defined_in_bb
!= NULL
362 && !bitmap_bit_p (names_defined_in_bb
, SSA_NAME_VERSION (ssa_name
)))
364 error ("definition in block %i follows the use", def_bb
->index
);
369 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name
))
371 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
375 /* Make sure the use is in an appropriate list by checking the previous
376 element to make sure it's the same. */
377 if (use_p
->prev
== NULL
)
379 error ("no immediate_use list");
385 if (use_p
->prev
->use
== NULL
)
386 listvar
= use_p
->prev
->stmt
;
388 listvar
= USE_FROM_PTR (use_p
->prev
);
389 if (listvar
!= ssa_name
)
391 error ("wrong immediate use list");
398 fprintf (stderr
, "for SSA_NAME: ");
399 print_generic_expr (stderr
, ssa_name
, TDF_VOPS
);
400 fprintf (stderr
, " in statement:\n");
401 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
408 /* Return true if any of the arguments for PHI node PHI at block BB is
411 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
412 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
413 it means that the block in that array slot contains the
414 definition of SSA_NAME. */
417 verify_phi_args (tree phi
, basic_block bb
, basic_block
*definition_block
)
421 unsigned i
, phi_num_args
= PHI_NUM_ARGS (phi
);
423 if (EDGE_COUNT (bb
->preds
) != phi_num_args
)
425 error ("incoming edge count does not match number of PHI arguments");
430 for (i
= 0; i
< phi_num_args
; i
++)
432 use_operand_p op_p
= PHI_ARG_DEF_PTR (phi
, i
);
433 tree op
= USE_FROM_PTR (op_p
);
435 e
= EDGE_PRED (bb
, i
);
439 error ("PHI argument is missing for edge %d->%d",
446 if (TREE_CODE (op
) != SSA_NAME
&& !is_gimple_min_invariant (op
))
448 error ("PHI argument is not SSA_NAME, or invariant");
452 if (TREE_CODE (op
) == SSA_NAME
)
454 err
= verify_ssa_name (op
, !is_gimple_reg (PHI_RESULT (phi
)));
455 err
|= verify_use (e
->src
, definition_block
[SSA_NAME_VERSION (op
)],
456 op_p
, phi
, e
->flags
& EDGE_ABNORMAL
, NULL
);
461 error ("wrong edge %d->%d for PHI argument",
462 e
->src
->index
, e
->dest
->index
);
468 fprintf (stderr
, "PHI argument\n");
469 print_generic_stmt (stderr
, op
, TDF_VOPS
);
477 fprintf (stderr
, "for PHI node\n");
478 print_generic_stmt (stderr
, phi
, TDF_VOPS
|TDF_MEMSYMS
);
487 verify_flow_insensitive_alias_info (void)
490 referenced_var_iterator rvi
;
492 FOR_EACH_REFERENCED_VAR (var
, rvi
)
499 if (!MTAG_P (var
) || !MTAG_ALIASES (var
))
502 aliases
= MTAG_ALIASES (var
);
504 EXECUTE_IF_SET_IN_BITMAP (aliases
, 0, j
, bi
)
506 alias
= referenced_var (j
);
508 if (TREE_CODE (alias
) != MEMORY_PARTITION_TAG
509 && !may_be_aliased (alias
))
511 error ("non-addressable variable inside an alias set");
512 debug_variable (alias
);
521 debug_variable (var
);
522 internal_error ("verify_flow_insensitive_alias_info failed");
527 verify_flow_sensitive_alias_info (void)
532 for (i
= 1; i
< num_ssa_names
; i
++)
536 struct ptr_info_def
*pi
;
543 /* We only care for pointers that are actually referenced in the
545 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)) || !TREE_VISITED (ptr
))
548 /* RESULT_DECL is special. If it's a GIMPLE register, then it
549 is only written-to only once in the return statement.
550 Otherwise, aggregate RESULT_DECLs may be written-to more than
551 once in virtual operands. */
552 var
= SSA_NAME_VAR (ptr
);
553 if (TREE_CODE (var
) == RESULT_DECL
554 && is_gimple_reg (ptr
))
557 pi
= SSA_NAME_PTR_INFO (ptr
);
562 if (pi
->memory_tag_needed
&& !pi
->name_mem_tag
&& !ann
->symbol_mem_tag
)
564 error ("dereferenced pointers should have a name or a symbol tag");
569 && (pi
->pt_vars
== NULL
|| bitmap_empty_p (pi
->pt_vars
)))
571 error ("pointers with a memory tag, should have points-to sets");
575 if (pi
->value_escapes_p
576 && pi
->escape_mask
& ~ESCAPE_TO_RETURN
579 tree t
= memory_partition (pi
->name_mem_tag
);
581 t
= pi
->name_mem_tag
;
583 if (!is_call_clobbered (t
))
585 error ("pointer escapes but its name tag is not call-clobbered");
594 debug_variable (ptr
);
595 internal_error ("verify_flow_sensitive_alias_info failed");
599 /* Verify the consistency of call clobbering information. */
602 verify_call_clobbering (void)
607 referenced_var_iterator rvi
;
609 /* At all times, the result of the call_clobbered flag should
610 match the result of the call_clobbered_vars bitmap. Verify both
611 that everything in call_clobbered_vars is marked
612 call_clobbered, and that everything marked
613 call_clobbered is in call_clobbered_vars. */
614 EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun
), 0, i
, bi
)
616 var
= referenced_var (i
);
618 if (memory_partition (var
))
619 var
= memory_partition (var
);
621 if (!MTAG_P (var
) && !var_ann (var
)->call_clobbered
)
623 error ("variable in call_clobbered_vars but not marked "
625 debug_variable (var
);
630 FOR_EACH_REFERENCED_VAR (var
, rvi
)
632 if (is_gimple_reg (var
))
635 if (memory_partition (var
))
636 var
= memory_partition (var
);
639 && var_ann (var
)->call_clobbered
640 && !bitmap_bit_p (gimple_call_clobbered_vars (cfun
), DECL_UID (var
)))
642 error ("variable marked call_clobbered but not in "
643 "call_clobbered_vars bitmap.");
644 debug_variable (var
);
652 internal_error ("verify_call_clobbering failed");
656 /* Verify invariants in memory partitions. */
659 verify_memory_partitions (void)
663 VEC(tree
,heap
) *mpt_table
= gimple_ssa_operands (cfun
)->mpt_table
;
664 struct pointer_set_t
*partitioned_syms
= pointer_set_create ();
666 for (i
= 0; VEC_iterate (tree
, mpt_table
, i
, mpt
); i
++)
671 if (MPT_SYMBOLS (mpt
) == NULL
)
673 error ("Memory partitions should have at least one symbol");
674 debug_variable (mpt
);
678 EXECUTE_IF_SET_IN_BITMAP (MPT_SYMBOLS (mpt
), 0, j
, bj
)
680 tree var
= referenced_var (j
);
681 if (pointer_set_insert (partitioned_syms
, var
))
683 error ("Partitioned symbols should belong to exactly one "
685 debug_variable (var
);
691 pointer_set_destroy (partitioned_syms
);
696 internal_error ("verify_memory_partitions failed");
700 /* Verify the consistency of aliasing information. */
703 verify_alias_info (void)
705 verify_flow_sensitive_alias_info ();
706 verify_call_clobbering ();
707 verify_flow_insensitive_alias_info ();
708 verify_memory_partitions ();
712 /* Verify common invariants in the SSA web.
713 TODO: verify the variable annotations. */
716 verify_ssa (bool check_modified_stmt
)
720 basic_block
*definition_block
= XCNEWVEC (basic_block
, num_ssa_names
);
723 enum dom_state orig_dom_state
= dom_info_state (CDI_DOMINATORS
);
724 bitmap names_defined_in_bb
= BITMAP_ALLOC (NULL
);
726 gcc_assert (!need_ssa_update_p ());
730 timevar_push (TV_TREE_SSA_VERIFY
);
732 /* Keep track of SSA names present in the IL. */
733 for (i
= 1; i
< num_ssa_names
; i
++)
735 tree name
= ssa_name (i
);
739 TREE_VISITED (name
) = 0;
741 stmt
= SSA_NAME_DEF_STMT (name
);
742 if (!IS_EMPTY_STMT (stmt
))
744 basic_block bb
= bb_for_stmt (stmt
);
745 verify_def (bb
, definition_block
,
746 name
, stmt
, !is_gimple_reg (name
));
752 calculate_dominance_info (CDI_DOMINATORS
);
754 /* Now verify all the uses and make sure they agree with the definitions
755 found in the previous pass. */
761 block_stmt_iterator bsi
;
763 /* Make sure that all edges have a clear 'aux' field. */
764 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
768 error ("AUX pointer initialized for edge %d->%d", e
->src
->index
,
774 /* Verify the arguments for every PHI node in the block. */
775 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
777 if (verify_phi_args (phi
, bb
, definition_block
))
780 bitmap_set_bit (names_defined_in_bb
,
781 SSA_NAME_VERSION (PHI_RESULT (phi
)));
784 /* Now verify all the uses and vuses in every statement of the block. */
785 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
787 tree stmt
= bsi_stmt (bsi
);
790 if (check_modified_stmt
&& stmt_modified_p (stmt
))
792 error ("stmt (%p) marked modified after optimization pass: ",
794 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
798 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
799 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 0)) != SSA_NAME
)
801 tree lhs
, base_address
;
803 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
804 base_address
= get_base_address (lhs
);
807 && gimple_aliases_computed_p (cfun
)
808 && SSA_VAR_P (base_address
)
809 && !stmt_ann (stmt
)->has_volatile_ops
810 && ZERO_SSA_OPERANDS (stmt
, SSA_OP_VDEF
))
812 error ("statement makes a memory store, but has no VDEFS");
813 print_generic_stmt (stderr
, stmt
, TDF_VOPS
);
818 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_ALL_VIRTUALS
)
820 if (verify_ssa_name (op
, true))
822 error ("in statement");
823 print_generic_stmt (stderr
, stmt
, TDF_VOPS
|TDF_MEMSYMS
);
828 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
|SSA_OP_DEF
)
830 if (verify_ssa_name (op
, false))
832 error ("in statement");
833 print_generic_stmt (stderr
, stmt
, TDF_VOPS
|TDF_MEMSYMS
);
838 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
|SSA_OP_VUSE
)
840 op
= USE_FROM_PTR (use_p
);
841 if (verify_use (bb
, definition_block
[SSA_NAME_VERSION (op
)],
842 use_p
, stmt
, false, names_defined_in_bb
))
846 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_ALL_DEFS
)
847 bitmap_set_bit (names_defined_in_bb
, SSA_NAME_VERSION (op
));
850 bitmap_clear (names_defined_in_bb
);
853 /* Finally, verify alias information. */
854 if (gimple_aliases_computed_p (cfun
))
855 verify_alias_info ();
857 free (definition_block
);
859 /* Restore the dominance information to its prior known state, so
860 that we do not perturb the compiler's subsequent behavior. */
861 if (orig_dom_state
== DOM_NONE
)
862 free_dominance_info (CDI_DOMINATORS
);
864 set_dom_info_availability (CDI_DOMINATORS
, orig_dom_state
);
866 BITMAP_FREE (names_defined_in_bb
);
867 timevar_pop (TV_TREE_SSA_VERIFY
);
871 internal_error ("verify_ssa failed");
874 /* Return true if the uid in both int tree maps are equal. */
877 int_tree_map_eq (const void *va
, const void *vb
)
879 const struct int_tree_map
*a
= (const struct int_tree_map
*) va
;
880 const struct int_tree_map
*b
= (const struct int_tree_map
*) vb
;
881 return (a
->uid
== b
->uid
);
884 /* Hash a UID in a int_tree_map. */
887 int_tree_map_hash (const void *item
)
889 return ((const struct int_tree_map
*)item
)->uid
;
892 /* Return true if the DECL_UID in both trees are equal. */
895 uid_decl_map_eq (const void *va
, const void *vb
)
897 const_tree a
= (const_tree
) va
;
898 const_tree b
= (const_tree
) vb
;
899 return (a
->decl_minimal
.uid
== b
->decl_minimal
.uid
);
902 /* Hash a tree in a uid_decl_map. */
905 uid_decl_map_hash (const void *item
)
907 return ((const_tree
)item
)->decl_minimal
.uid
;
910 /* Return true if the DECL_UID in both trees are equal. */
913 uid_ssaname_map_eq (const void *va
, const void *vb
)
915 const_tree a
= (const_tree
) va
;
916 const_tree b
= (const_tree
) vb
;
917 return (a
->ssa_name
.var
->decl_minimal
.uid
== b
->ssa_name
.var
->decl_minimal
.uid
);
920 /* Hash a tree in a uid_decl_map. */
923 uid_ssaname_map_hash (const void *item
)
925 return ((const_tree
)item
)->ssa_name
.var
->decl_minimal
.uid
;
929 /* Initialize global DFA and SSA structures. */
932 init_tree_ssa (struct function
*fn
)
934 fn
->gimple_df
= GGC_CNEW (struct gimple_df
);
935 fn
->gimple_df
->referenced_vars
= htab_create_ggc (20, uid_decl_map_hash
,
936 uid_decl_map_eq
, NULL
);
937 fn
->gimple_df
->default_defs
= htab_create_ggc (20, uid_ssaname_map_hash
,
938 uid_ssaname_map_eq
, NULL
);
939 fn
->gimple_df
->call_clobbered_vars
= BITMAP_GGC_ALLOC ();
940 fn
->gimple_df
->call_used_vars
= BITMAP_GGC_ALLOC ();
941 fn
->gimple_df
->addressable_vars
= BITMAP_GGC_ALLOC ();
942 init_ssanames (fn
, 0);
947 /* Deallocate memory associated with SSA data structures for FNDECL. */
950 delete_tree_ssa (void)
954 block_stmt_iterator bsi
;
955 referenced_var_iterator rvi
;
958 /* Release any ssa_names still in use. */
959 for (i
= 0; i
< num_ssa_names
; i
++)
961 tree var
= ssa_name (i
);
962 if (var
&& TREE_CODE (var
) == SSA_NAME
)
964 SSA_NAME_IMM_USE_NODE (var
).prev
= &(SSA_NAME_IMM_USE_NODE (var
));
965 SSA_NAME_IMM_USE_NODE (var
).next
= &(SSA_NAME_IMM_USE_NODE (var
));
967 release_ssa_name (var
);
970 /* Remove annotations from every tree in the function. */
973 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
975 tree stmt
= bsi_stmt (bsi
);
976 stmt_ann_t ann
= get_stmt_ann (stmt
);
978 free_ssa_operands (&ann
->operands
);
979 ann
->addresses_taken
= 0;
980 mark_stmt_modified (stmt
);
982 set_phi_nodes (bb
, NULL
);
985 /* Remove annotations from every referenced local variable. */
986 FOR_EACH_REFERENCED_VAR (var
, rvi
)
989 && (TREE_STATIC (var
) || DECL_EXTERNAL (var
)))
991 var_ann (var
)->mpt
= NULL_TREE
;
992 var_ann (var
)->symbol_mem_tag
= NULL_TREE
;
996 ggc_free (var
->base
.ann
);
997 var
->base
.ann
= NULL
;
999 htab_delete (gimple_referenced_vars (cfun
));
1000 cfun
->gimple_df
->referenced_vars
= NULL
;
1004 /* we no longer maintain the SSA operand cache at this point. */
1005 if (ssa_operands_active ())
1006 fini_ssa_operands ();
1008 cfun
->gimple_df
->global_var
= NULL_TREE
;
1010 htab_delete (cfun
->gimple_df
->default_defs
);
1011 cfun
->gimple_df
->default_defs
= NULL
;
1012 cfun
->gimple_df
->call_clobbered_vars
= NULL
;
1013 cfun
->gimple_df
->call_used_vars
= NULL
;
1014 cfun
->gimple_df
->addressable_vars
= NULL
;
1015 cfun
->gimple_df
->modified_noreturn_calls
= NULL
;
1016 if (gimple_aliases_computed_p (cfun
))
1018 delete_alias_heapvars ();
1019 gcc_assert (!need_ssa_update_p ());
1021 cfun
->gimple_df
->aliases_computed_p
= false;
1022 delete_mem_ref_stats (cfun
);
1024 cfun
->gimple_df
= NULL
;
1026 /* We no longer need the edge variable maps. */
1027 redirect_edge_var_map_destroy ();
1030 /* Helper function for useless_type_conversion_p. */
1033 useless_type_conversion_p_1 (tree outer_type
, tree inner_type
)
1035 /* Qualifiers on value types do not matter. */
1036 inner_type
= TYPE_MAIN_VARIANT (inner_type
);
1037 outer_type
= TYPE_MAIN_VARIANT (outer_type
);
1039 if (inner_type
== outer_type
)
1042 /* If we know the canonical types, compare them. */
1043 if (TYPE_CANONICAL (inner_type
)
1044 && TYPE_CANONICAL (inner_type
) == TYPE_CANONICAL (outer_type
))
1047 /* Changes in machine mode are never useless conversions. */
1048 if (TYPE_MODE (inner_type
) != TYPE_MODE (outer_type
))
1051 /* If both the inner and outer types are integral types, then the
1052 conversion is not necessary if they have the same mode and
1053 signedness and precision, and both or neither are boolean. */
1054 if (INTEGRAL_TYPE_P (inner_type
)
1055 && INTEGRAL_TYPE_P (outer_type
))
1057 /* Preserve changes in signedness or precision. */
1058 if (TYPE_UNSIGNED (inner_type
) != TYPE_UNSIGNED (outer_type
)
1059 || TYPE_PRECISION (inner_type
) != TYPE_PRECISION (outer_type
))
1062 /* Conversions from a non-base to a base type are not useless.
1063 This way we preserve the invariant to do arithmetic in
1065 if (TREE_TYPE (inner_type
)
1066 && TREE_TYPE (inner_type
) != inner_type
1067 && (TREE_TYPE (outer_type
) == outer_type
1068 || TREE_TYPE (outer_type
) == NULL_TREE
))
1071 /* We don't need to preserve changes in the types minimum or
1072 maximum value in general as these do not generate code
1073 unless the types precisions are different. */
1078 /* Scalar floating point types with the same mode are compatible. */
1079 else if (SCALAR_FLOAT_TYPE_P (inner_type
)
1080 && SCALAR_FLOAT_TYPE_P (outer_type
))
1083 /* We need to take special care recursing to pointed-to types. */
1084 else if (POINTER_TYPE_P (inner_type
)
1085 && POINTER_TYPE_P (outer_type
))
1087 /* Don't lose casts between pointers to volatile and non-volatile
1088 qualified types. Doing so would result in changing the semantics
1089 of later accesses. */
1090 if ((TYPE_VOLATILE (TREE_TYPE (outer_type
))
1091 != TYPE_VOLATILE (TREE_TYPE (inner_type
)))
1092 && TYPE_VOLATILE (TREE_TYPE (outer_type
)))
1095 /* Do not lose casts between pointers with different
1096 TYPE_REF_CAN_ALIAS_ALL setting or alias sets. */
1097 if ((TYPE_REF_CAN_ALIAS_ALL (inner_type
)
1098 != TYPE_REF_CAN_ALIAS_ALL (outer_type
))
1099 || (get_alias_set (TREE_TYPE (inner_type
))
1100 != get_alias_set (TREE_TYPE (outer_type
))))
1103 /* We do not care for const qualification of the pointed-to types
1104 as const qualification has no semantic value to the middle-end. */
1106 /* Do not lose casts to restrict qualified pointers. */
1107 if ((TYPE_RESTRICT (outer_type
)
1108 != TYPE_RESTRICT (inner_type
))
1109 && TYPE_RESTRICT (outer_type
))
1112 /* Otherwise pointers/references are equivalent if their pointed
1113 to types are effectively the same. We can strip qualifiers
1114 on pointed-to types for further comparison, which is done in
1116 return useless_type_conversion_p_1 (TREE_TYPE (outer_type
),
1117 TREE_TYPE (inner_type
));
1120 /* Recurse for complex types. */
1121 else if (TREE_CODE (inner_type
) == COMPLEX_TYPE
1122 && TREE_CODE (outer_type
) == COMPLEX_TYPE
)
1123 return useless_type_conversion_p_1 (TREE_TYPE (outer_type
),
1124 TREE_TYPE (inner_type
));
1126 /* Recurse for vector types with the same number of subparts. */
1127 else if (TREE_CODE (inner_type
) == VECTOR_TYPE
1128 && TREE_CODE (outer_type
) == VECTOR_TYPE
1129 && TYPE_PRECISION (inner_type
) == TYPE_PRECISION (outer_type
))
1130 return useless_type_conversion_p_1 (TREE_TYPE (outer_type
),
1131 TREE_TYPE (inner_type
));
1133 /* For aggregates we may need to fall back to structural equality
1135 else if (AGGREGATE_TYPE_P (inner_type
)
1136 && AGGREGATE_TYPE_P (outer_type
))
1138 /* Different types of aggregates are incompatible. */
1139 if (TREE_CODE (inner_type
) != TREE_CODE (outer_type
))
1142 /* ??? Add structural equivalence check. */
1144 /* ??? This should eventually just return false. */
1145 return lang_hooks
.types_compatible_p (inner_type
, outer_type
);
1151 /* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a
1152 useless type conversion, otherwise return false.
1154 This function implicitly defines the middle-end type system. With
1155 the notion of 'a < b' meaning that useless_type_conversion_p (a, b)
1156 holds and 'a > b' meaning that useless_type_conversion_p (b, a) holds,
1157 the following invariants shall be fulfilled:
1159 1) useless_type_conversion_p is transitive.
1160 If a < b and b < c then a < c.
1162 2) useless_type_conversion_p is not symmetric.
1163 From a < b does not follow a > b.
1165 3) Types define the available set of operations applicable to values.
1166 A type conversion is useless if the operations for the target type
1167 is a subset of the operations for the source type. For example
1168 casts to void* are useless, casts from void* are not (void* can't
1169 be dereferenced or offsetted, but copied, hence its set of operations
1170 is a strict subset of that of all other data pointer types). Casts
1171 to const T* are useless (can't be written to), casts from const T*
1175 useless_type_conversion_p (tree outer_type
, tree inner_type
)
1177 /* If the outer type is (void *), then the conversion is not
1178 necessary. We have to make sure to not apply this while
1179 recursing though. */
1180 if (POINTER_TYPE_P (inner_type
)
1181 && POINTER_TYPE_P (outer_type
)
1182 && TREE_CODE (TREE_TYPE (outer_type
)) == VOID_TYPE
)
1185 return useless_type_conversion_p_1 (outer_type
, inner_type
);
1188 /* Return true if a conversion from either type of TYPE1 and TYPE2
1189 to the other is not required. Otherwise return false. */
1192 types_compatible_p (tree type1
, tree type2
)
1194 return (type1
== type2
1195 || (useless_type_conversion_p (type1
, type2
)
1196 && useless_type_conversion_p (type2
, type1
)));
1199 /* Return true if EXPR is a useless type conversion, otherwise return
1203 tree_ssa_useless_type_conversion (tree expr
)
1205 /* If we have an assignment that merely uses a NOP_EXPR to change
1206 the top of the RHS to the type of the LHS and the type conversion
1207 is "safe", then strip away the type conversion so that we can
1208 enter LHS = RHS into the const_and_copies table. */
1209 if (CONVERT_EXPR_P (expr
)
1210 || TREE_CODE (expr
) == VIEW_CONVERT_EXPR
1211 || TREE_CODE (expr
) == NON_LVALUE_EXPR
)
1212 /* FIXME: Use of GENERIC_TREE_TYPE here is a temporary measure to work
1213 around known bugs with GIMPLE_MODIFY_STMTs appearing in places
1214 they shouldn't. See PR 30391. */
1215 return useless_type_conversion_p
1217 GENERIC_TREE_TYPE (TREE_OPERAND (expr
, 0)));
1223 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
1224 described in walk_use_def_chains.
1226 VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
1227 infinite loops. We used to have a bitmap for this to just mark
1228 SSA versions we had visited. But non-sparse bitmaps are way too
1229 expensive, while sparse bitmaps may cause quadratic behavior.
1231 IS_DFS is true if the caller wants to perform a depth-first search
1232 when visiting PHI nodes. A DFS will visit each PHI argument and
1233 call FN after each one. Otherwise, all the arguments are
1234 visited first and then FN is called with each of the visited
1235 arguments in a separate pass. */
1238 walk_use_def_chains_1 (tree var
, walk_use_def_chains_fn fn
, void *data
,
1239 struct pointer_set_t
*visited
, bool is_dfs
)
1243 if (pointer_set_insert (visited
, var
))
1246 def_stmt
= SSA_NAME_DEF_STMT (var
);
1248 if (TREE_CODE (def_stmt
) != PHI_NODE
)
1250 /* If we reached the end of the use-def chain, call FN. */
1251 return fn (var
, def_stmt
, data
);
1257 /* When doing a breadth-first search, call FN before following the
1258 use-def links for each argument. */
1260 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
1261 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
1264 /* Follow use-def links out of each PHI argument. */
1265 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
1267 tree arg
= PHI_ARG_DEF (def_stmt
, i
);
1269 /* ARG may be NULL for newly introduced PHI nodes. */
1271 && TREE_CODE (arg
) == SSA_NAME
1272 && walk_use_def_chains_1 (arg
, fn
, data
, visited
, is_dfs
))
1276 /* When doing a depth-first search, call FN after following the
1277 use-def links for each argument. */
1279 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
1280 if (fn (PHI_ARG_DEF (def_stmt
, i
), def_stmt
, data
))
1289 /* Walk use-def chains starting at the SSA variable VAR. Call
1290 function FN at each reaching definition found. FN takes three
1291 arguments: VAR, its defining statement (DEF_STMT) and a generic
1292 pointer to whatever state information that FN may want to maintain
1293 (DATA). FN is able to stop the walk by returning true, otherwise
1294 in order to continue the walk, FN should return false.
1296 Note, that if DEF_STMT is a PHI node, the semantics are slightly
1297 different. The first argument to FN is no longer the original
1298 variable VAR, but the PHI argument currently being examined. If FN
1299 wants to get at VAR, it should call PHI_RESULT (PHI).
1301 If IS_DFS is true, this function will:
1303 1- walk the use-def chains for all the PHI arguments, and,
1304 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
1306 If IS_DFS is false, the two steps above are done in reverse order
1307 (i.e., a breadth-first search). */
1310 walk_use_def_chains (tree var
, walk_use_def_chains_fn fn
, void *data
,
1315 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
1317 def_stmt
= SSA_NAME_DEF_STMT (var
);
1319 /* We only need to recurse if the reaching definition comes from a PHI
1321 if (TREE_CODE (def_stmt
) != PHI_NODE
)
1322 (*fn
) (var
, def_stmt
, data
);
1325 struct pointer_set_t
*visited
= pointer_set_create ();
1326 walk_use_def_chains_1 (var
, fn
, data
, visited
, is_dfs
);
1327 pointer_set_destroy (visited
);
1332 /* Return true if T, an SSA_NAME, has an undefined value. */
1335 ssa_undefined_value_p (tree t
)
1337 tree var
= SSA_NAME_VAR (t
);
1339 /* Parameters get their initial value from the function entry. */
1340 if (TREE_CODE (var
) == PARM_DECL
)
1343 /* Hard register variables get their initial value from the ether. */
1344 if (TREE_CODE (var
) == VAR_DECL
&& DECL_HARD_REGISTER (var
))
1347 /* The value is undefined iff its definition statement is empty. */
1348 return IS_EMPTY_STMT (SSA_NAME_DEF_STMT (t
));
1351 /* Emit warnings for uninitialized variables. This is done in two passes.
1353 The first pass notices real uses of SSA names with undefined values.
1354 Such uses are unconditionally uninitialized, and we can be certain that
1355 such a use is a mistake. This pass is run before most optimizations,
1356 so that we catch as many as we can.
1358 The second pass follows PHI nodes to find uses that are potentially
1359 uninitialized. In this case we can't necessarily prove that the use
1360 is really uninitialized. This pass is run after most optimizations,
1361 so that we thread as many jumps and possible, and delete as much dead
1362 code as possible, in order to reduce false positives. We also look
1363 again for plain uninitialized variables, since optimization may have
1364 changed conditionally uninitialized to unconditionally uninitialized. */
1366 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1367 warning text is in MSGID and LOCUS may contain a location or be null. */
1370 warn_uninit (tree t
, const char *gmsgid
, void *data
)
1372 tree var
= SSA_NAME_VAR (t
);
1373 tree context
= (tree
) data
;
1375 expanded_location xloc
, floc
;
1377 if (!ssa_undefined_value_p (t
))
1380 /* TREE_NO_WARNING either means we already warned, or the front end
1381 wishes to suppress the warning. */
1382 if (TREE_NO_WARNING (var
))
1385 locus
= (context
!= NULL
&& EXPR_HAS_LOCATION (context
)
1386 ? EXPR_LOCUS (context
)
1387 : &DECL_SOURCE_LOCATION (var
));
1388 warning (OPT_Wuninitialized
, gmsgid
, locus
, var
);
1389 xloc
= expand_location (*locus
);
1390 floc
= expand_location (DECL_SOURCE_LOCATION (cfun
->decl
));
1391 if (xloc
.file
!= floc
.file
1392 || xloc
.line
< floc
.line
1393 || xloc
.line
> LOCATION_LINE (cfun
->function_end_locus
))
1394 inform ("%J%qD was declared here", var
, var
);
1396 TREE_NO_WARNING (var
) = 1;
1401 bool always_executed
;
1404 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1405 and warn about them. */
1408 warn_uninitialized_var (tree
*tp
, int *walk_subtrees
, void *data_
)
1410 struct walk_data
*data
= (struct walk_data
*)data_
;
1413 switch (TREE_CODE (t
))
1416 /* We only do data flow with SSA_NAMEs, so that's all we
1418 if (data
->always_executed
)
1419 warn_uninit (t
, "%H%qD is used uninitialized in this function",
1422 warn_uninit (t
, "%H%qD may be used uninitialized in this function",
1429 /* The total store transformation performed during gimplification
1430 creates uninitialized variable uses. If all is well, these will
1431 be optimized away, so don't warn now. */
1432 if (TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
)
1437 if (IS_TYPE_OR_DECL_P (t
))
1445 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1446 and warn about them. */
1449 warn_uninitialized_phi (tree phi
)
1451 int i
, n
= PHI_NUM_ARGS (phi
);
1453 /* Don't look at memory tags. */
1454 if (!is_gimple_reg (PHI_RESULT (phi
)))
1457 for (i
= 0; i
< n
; ++i
)
1459 tree op
= PHI_ARG_DEF (phi
, i
);
1460 if (TREE_CODE (op
) == SSA_NAME
)
1461 warn_uninit (op
, "%H%qD may be used uninitialized in this function",
1467 execute_early_warn_uninitialized (void)
1469 block_stmt_iterator bsi
;
1471 struct walk_data data
;
1473 calculate_dominance_info (CDI_POST_DOMINATORS
);
1477 data
.always_executed
= dominated_by_p (CDI_POST_DOMINATORS
,
1478 single_succ (ENTRY_BLOCK_PTR
), bb
);
1479 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1481 data
.stmt
= bsi_stmt (bsi
);
1482 walk_tree (bsi_stmt_ptr (bsi
), warn_uninitialized_var
,
1490 execute_late_warn_uninitialized (void)
1495 /* Re-do the plain uninitialized variable check, as optimization may have
1496 straightened control flow. Do this first so that we don't accidentally
1497 get a "may be" warning when we'd have seen an "is" warning later. */
1498 execute_early_warn_uninitialized ();
1501 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1502 warn_uninitialized_phi (phi
);
1507 gate_warn_uninitialized (void)
1509 return warn_uninitialized
!= 0;
1512 struct gimple_opt_pass pass_early_warn_uninitialized
=
1517 gate_warn_uninitialized
, /* gate */
1518 execute_early_warn_uninitialized
, /* execute */
1521 0, /* static_pass_number */
1523 PROP_ssa
, /* properties_required */
1524 0, /* properties_provided */
1525 0, /* properties_destroyed */
1526 0, /* todo_flags_start */
1527 0 /* todo_flags_finish */
1531 struct gimple_opt_pass pass_late_warn_uninitialized
=
1536 gate_warn_uninitialized
, /* gate */
1537 execute_late_warn_uninitialized
, /* execute */
1540 0, /* static_pass_number */
1542 PROP_ssa
, /* properties_required */
1543 0, /* properties_provided */
1544 0, /* properties_destroyed */
1545 0, /* todo_flags_start */
1546 0 /* todo_flags_finish */
1550 /* Compute TREE_ADDRESSABLE for local variables. */
1553 execute_update_addresses_taken (void)
1556 referenced_var_iterator rvi
;
1557 block_stmt_iterator bsi
;
1559 bitmap addresses_taken
= BITMAP_ALLOC (NULL
);
1560 bitmap vars_updated
= BITMAP_ALLOC (NULL
);
1561 bool update_vops
= false;
1564 /* Collect into ADDRESSES_TAKEN all variables whose address is taken within
1565 the function body. */
1568 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1570 stmt_ann_t s_ann
= stmt_ann (bsi_stmt (bsi
));
1572 if (s_ann
->addresses_taken
)
1573 bitmap_ior_into (addresses_taken
, s_ann
->addresses_taken
);
1575 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1577 unsigned i
, phi_num_args
= PHI_NUM_ARGS (phi
);
1578 for (i
= 0; i
< phi_num_args
; i
++)
1580 tree op
= PHI_ARG_DEF (phi
, i
), var
;
1581 if (TREE_CODE (op
) == ADDR_EXPR
1582 && (var
= get_base_address (TREE_OPERAND (op
, 0))) != NULL_TREE
1584 bitmap_set_bit (addresses_taken
, DECL_UID (var
));
1589 /* When possible, clear ADDRESSABLE bit and mark variable for conversion into
1591 FOR_EACH_REFERENCED_VAR (var
, rvi
)
1592 if (!is_global_var (var
)
1593 && TREE_CODE (var
) != RESULT_DECL
1594 && TREE_ADDRESSABLE (var
)
1595 && !bitmap_bit_p (addresses_taken
, DECL_UID (var
)))
1597 TREE_ADDRESSABLE (var
) = 0;
1598 if (is_gimple_reg (var
))
1599 mark_sym_for_renaming (var
);
1601 bitmap_set_bit (vars_updated
, DECL_UID (var
));
1604 fprintf (dump_file
, "No longer having address taken ");
1605 print_generic_expr (dump_file
, var
, 0);
1606 fprintf (dump_file
, "\n");
1610 /* Operand caches needs to be recomputed for operands referencing the updated
1614 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1616 tree stmt
= bsi_stmt (bsi
);
1618 if ((LOADED_SYMS (stmt
)
1619 && bitmap_intersect_p (LOADED_SYMS (stmt
), vars_updated
))
1620 || (STORED_SYMS (stmt
)
1621 && bitmap_intersect_p (STORED_SYMS (stmt
), vars_updated
)))
1624 BITMAP_FREE (addresses_taken
);
1625 BITMAP_FREE (vars_updated
);
1629 struct gimple_opt_pass pass_update_address_taken
=
1633 "addressables", /* name */
1635 execute_update_addresses_taken
, /* execute */
1638 0, /* static_pass_number */
1640 PROP_ssa
, /* properties_required */
1641 0, /* properties_provided */
1642 0, /* properties_destroyed */
1643 0, /* todo_flags_start */
1644 TODO_update_ssa
/* todo_flags_finish */