1 /* Miscellaneous SSA utility functions.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009
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 "hard-reg-set.h"
32 #include "basic-block.h"
36 #include "diagnostic.h"
38 #include "pointer-set.h"
39 #include "tree-flow.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, source_location locus)
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;
74 new_node.locus = locus;
76 VEC_safe_push (edge_var_map, heap, head, &new_node);
79 /* The push did some reallocation. Update the pointer map. */
85 /* Clear the var mappings in edge E. */
88 redirect_edge_var_map_clear (edge e)
91 edge_var_map_vector head;
96 slot = pointer_map_contains (edge_var_maps, e);
100 head = (edge_var_map_vector) *slot;
101 VEC_free (edge_var_map, heap, head);
107 /* Duplicate the redirected var mappings in OLDE in NEWE.
109 Since we can't remove a mapping, let's just duplicate it. This assumes a
110 pointer_map can have multiple edges mapping to the same var_map (many to
111 one mapping), since we don't remove the previous mappings. */
114 redirect_edge_var_map_dup (edge newe, edge olde)
116 void **new_slot, **old_slot;
117 edge_var_map_vector head;
122 new_slot = pointer_map_insert (edge_var_maps, newe);
123 old_slot = pointer_map_contains (edge_var_maps, olde);
126 head = (edge_var_map_vector) *old_slot;
129 *new_slot = VEC_copy (edge_var_map, heap, head);
131 *new_slot = VEC_alloc (edge_var_map, heap, 5);
135 /* Return the variable mappings for a given edge. If there is none, return
139 redirect_edge_var_map_vector (edge e)
143 /* Hey, what kind of idiot would... you'd be surprised. */
147 slot = pointer_map_contains (edge_var_maps, e);
151 return (edge_var_map_vector) *slot;
154 /* Used by redirect_edge_var_map_destroy to free all memory. */
157 free_var_map_entry (const void *key ATTRIBUTE_UNUSED,
159 void *data ATTRIBUTE_UNUSED)
161 edge_var_map_vector head = (edge_var_map_vector) *value;
162 VEC_free (edge_var_map, heap, head);
166 /* Clear the edge variable mappings. */
169 redirect_edge_var_map_destroy (void)
173 pointer_map_traverse (edge_var_maps, free_var_map_entry, NULL);
174 pointer_map_destroy (edge_var_maps);
175 edge_var_maps = NULL;
180 /* Remove the corresponding arguments from the PHI nodes in E's
181 destination block and redirect it to DEST. Return redirected edge.
182 The list of removed arguments is stored in a vector accessed
183 through edge_var_maps. */
186 ssa_redirect_edge (edge e, basic_block dest)
188 gimple_stmt_iterator gsi;
191 redirect_edge_var_map_clear (e);
193 /* Remove the appropriate PHI arguments in E's destination block. */
194 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
197 source_location locus ;
199 phi = gsi_stmt (gsi);
200 def = gimple_phi_arg_def (phi, e->dest_idx);
201 locus = gimple_phi_arg_location (phi, e->dest_idx);
203 if (def == NULL_TREE)
206 redirect_edge_var_map_add (e, gimple_phi_result (phi), def, locus);
209 e = redirect_edge_succ_nodup (e, dest);
215 /* Add PHI arguments queued in PENDING_STMT list on edge E to edge
219 flush_pending_stmts (edge e)
222 edge_var_map_vector v;
225 gimple_stmt_iterator gsi;
227 v = redirect_edge_var_map_vector (e);
231 for (gsi = gsi_start_phis (e->dest), i = 0;
232 !gsi_end_p (gsi) && VEC_iterate (edge_var_map, v, i, vm);
233 gsi_next (&gsi), i++)
237 phi = gsi_stmt (gsi);
238 def = redirect_edge_var_map_def (vm);
239 add_phi_arg (phi, def, e, redirect_edge_var_map_location (vm));
242 redirect_edge_var_map_clear (e);
245 /* Return true if SSA_NAME is malformed and mark it visited.
247 IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
251 verify_ssa_name (tree ssa_name, bool is_virtual)
253 if (TREE_CODE (ssa_name) != SSA_NAME)
255 error ("expected an SSA_NAME object");
259 if (TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name)))
261 error ("type mismatch between an SSA_NAME and its symbol");
265 if (SSA_NAME_IN_FREE_LIST (ssa_name))
267 error ("found an SSA_NAME that had been released into the free pool");
271 if (is_virtual && is_gimple_reg (ssa_name))
273 error ("found a virtual definition for a GIMPLE register");
277 if (is_virtual && SSA_NAME_VAR (ssa_name) != gimple_vop (cfun))
279 error ("virtual SSA name for non-VOP decl");
283 if (!is_virtual && !is_gimple_reg (ssa_name))
285 error ("found a real definition for a non-register");
289 if (SSA_NAME_IS_DEFAULT_DEF (ssa_name)
290 && !gimple_nop_p (SSA_NAME_DEF_STMT (ssa_name)))
292 error ("found a default name with a non-empty defining statement");
300 /* Return true if the definition of SSA_NAME at block BB is malformed.
302 STMT is the statement where SSA_NAME is created.
304 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
305 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
306 it means that the block in that array slot contains the
307 definition of SSA_NAME.
309 IS_VIRTUAL is true if SSA_NAME is created by a VDEF. */
312 verify_def (basic_block bb, basic_block *definition_block, tree ssa_name,
313 gimple stmt, bool is_virtual)
315 if (verify_ssa_name (ssa_name, is_virtual))
318 if (definition_block[SSA_NAME_VERSION (ssa_name)])
320 error ("SSA_NAME created in two different blocks %i and %i",
321 definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index);
325 definition_block[SSA_NAME_VERSION (ssa_name)] = bb;
327 if (SSA_NAME_DEF_STMT (ssa_name) != stmt)
329 error ("SSA_NAME_DEF_STMT is wrong");
330 fprintf (stderr, "Expected definition statement:\n");
331 print_gimple_stmt (stderr, SSA_NAME_DEF_STMT (ssa_name), 4, TDF_VOPS);
332 fprintf (stderr, "\nActual definition statement:\n");
333 print_gimple_stmt (stderr, stmt, 4, TDF_VOPS);
340 fprintf (stderr, "while verifying SSA_NAME ");
341 print_generic_expr (stderr, ssa_name, 0);
342 fprintf (stderr, " in statement\n");
343 print_gimple_stmt (stderr, stmt, 4, TDF_VOPS);
349 /* Return true if the use of SSA_NAME at statement STMT in block BB is
352 DEF_BB is the block where SSA_NAME was found to be created.
354 IDOM contains immediate dominator information for the flowgraph.
356 CHECK_ABNORMAL is true if the caller wants to check whether this use
357 is flowing through an abnormal edge (only used when checking PHI
360 If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
361 that are defined before STMT in basic block BB. */
364 verify_use (basic_block bb, basic_block def_bb, use_operand_p use_p,
365 gimple stmt, bool check_abnormal, bitmap names_defined_in_bb)
368 tree ssa_name = USE_FROM_PTR (use_p);
370 if (!TREE_VISITED (ssa_name))
371 if (verify_imm_links (stderr, ssa_name))
374 TREE_VISITED (ssa_name) = 1;
376 if (gimple_nop_p (SSA_NAME_DEF_STMT (ssa_name))
377 && SSA_NAME_IS_DEFAULT_DEF (ssa_name))
378 ; /* Default definitions have empty statements. Nothing to do. */
381 error ("missing definition");
384 else if (bb != def_bb
385 && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
387 error ("definition in block %i does not dominate use in block %i",
388 def_bb->index, bb->index);
391 else if (bb == def_bb
392 && names_defined_in_bb != NULL
393 && !bitmap_bit_p (names_defined_in_bb, SSA_NAME_VERSION (ssa_name)))
395 error ("definition in block %i follows the use", def_bb->index);
400 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
402 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
406 /* Make sure the use is in an appropriate list by checking the previous
407 element to make sure it's the same. */
408 if (use_p->prev == NULL)
410 error ("no immediate_use list");
416 if (use_p->prev->use == NULL)
417 listvar = use_p->prev->loc.ssa_name;
419 listvar = USE_FROM_PTR (use_p->prev);
420 if (listvar != ssa_name)
422 error ("wrong immediate use list");
429 fprintf (stderr, "for SSA_NAME: ");
430 print_generic_expr (stderr, ssa_name, TDF_VOPS);
431 fprintf (stderr, " in statement:\n");
432 print_gimple_stmt (stderr, stmt, 0, TDF_VOPS);
439 /* Return true if any of the arguments for PHI node PHI at block BB is
442 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
443 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
444 it means that the block in that array slot contains the
445 definition of SSA_NAME. */
448 verify_phi_args (gimple phi, basic_block bb, basic_block *definition_block)
452 size_t i, phi_num_args = gimple_phi_num_args (phi);
454 if (EDGE_COUNT (bb->preds) != phi_num_args)
456 error ("incoming edge count does not match number of PHI arguments");
461 for (i = 0; i < phi_num_args; i++)
463 use_operand_p op_p = gimple_phi_arg_imm_use_ptr (phi, i);
464 tree op = USE_FROM_PTR (op_p);
466 e = EDGE_PRED (bb, i);
470 error ("PHI argument is missing for edge %d->%d",
477 if (TREE_CODE (op) != SSA_NAME && !is_gimple_min_invariant (op))
479 error ("PHI argument is not SSA_NAME, or invariant");
483 if (TREE_CODE (op) == SSA_NAME)
485 err = verify_ssa_name (op, !is_gimple_reg (gimple_phi_result (phi)));
486 err |= verify_use (e->src, definition_block[SSA_NAME_VERSION (op)],
487 op_p, phi, e->flags & EDGE_ABNORMAL, NULL);
490 if (TREE_CODE (op) == ADDR_EXPR)
492 tree base = TREE_OPERAND (op, 0);
493 while (handled_component_p (base))
494 base = TREE_OPERAND (base, 0);
495 if ((TREE_CODE (base) == VAR_DECL
496 || TREE_CODE (base) == PARM_DECL
497 || TREE_CODE (base) == RESULT_DECL)
498 && !TREE_ADDRESSABLE (base))
500 error ("address taken, but ADDRESSABLE bit not set");
507 error ("wrong edge %d->%d for PHI argument",
508 e->src->index, e->dest->index);
514 fprintf (stderr, "PHI argument\n");
515 print_generic_stmt (stderr, op, TDF_VOPS);
523 fprintf (stderr, "for PHI node\n");
524 print_gimple_stmt (stderr, phi, 0, TDF_VOPS|TDF_MEMSYMS);
532 /* Verify common invariants in the SSA web.
533 TODO: verify the variable annotations. */
536 verify_ssa (bool check_modified_stmt)
540 basic_block *definition_block = XCNEWVEC (basic_block, num_ssa_names);
543 enum dom_state orig_dom_state = dom_info_state (CDI_DOMINATORS);
544 bitmap names_defined_in_bb = BITMAP_ALLOC (NULL);
546 gcc_assert (!need_ssa_update_p (cfun));
550 timevar_push (TV_TREE_SSA_VERIFY);
552 /* Keep track of SSA names present in the IL. */
553 for (i = 1; i < num_ssa_names; i++)
555 tree name = ssa_name (i);
559 TREE_VISITED (name) = 0;
561 stmt = SSA_NAME_DEF_STMT (name);
562 if (!gimple_nop_p (stmt))
564 basic_block bb = gimple_bb (stmt);
565 verify_def (bb, definition_block,
566 name, stmt, !is_gimple_reg (name));
572 calculate_dominance_info (CDI_DOMINATORS);
574 /* Now verify all the uses and make sure they agree with the definitions
575 found in the previous pass. */
581 gimple_stmt_iterator gsi;
583 /* Make sure that all edges have a clear 'aux' field. */
584 FOR_EACH_EDGE (e, ei, bb->preds)
588 error ("AUX pointer initialized for edge %d->%d", e->src->index,
594 /* Verify the arguments for every PHI node in the block. */
595 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
597 phi = gsi_stmt (gsi);
598 if (verify_phi_args (phi, bb, definition_block))
601 bitmap_set_bit (names_defined_in_bb,
602 SSA_NAME_VERSION (gimple_phi_result (phi)));
605 /* Now verify all the uses and vuses in every statement of the block. */
606 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
608 gimple stmt = gsi_stmt (gsi);
612 if (check_modified_stmt && gimple_modified_p (stmt))
614 error ("stmt (%p) marked modified after optimization pass: ",
616 print_gimple_stmt (stderr, stmt, 0, TDF_VOPS);
620 if (is_gimple_assign (stmt)
621 && TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
623 tree lhs, base_address;
625 lhs = gimple_assign_lhs (stmt);
626 base_address = get_base_address (lhs);
629 && SSA_VAR_P (base_address)
630 && !gimple_vdef (stmt)
633 error ("statement makes a memory store, but has no VDEFS");
634 print_gimple_stmt (stderr, stmt, 0, TDF_VOPS);
639 /* Verify the single virtual operand and its constraints. */
641 if (gimple_vdef (stmt))
643 if (gimple_vdef_op (stmt) == NULL_DEF_OPERAND_P)
645 error ("statement has VDEF operand not in defs list");
648 if (!gimple_vuse (stmt))
650 error ("statement has VDEF but no VUSE operand");
653 else if (SSA_NAME_VAR (gimple_vdef (stmt))
654 != SSA_NAME_VAR (gimple_vuse (stmt)))
656 error ("VDEF and VUSE do not use the same symbol");
659 has_err |= verify_ssa_name (gimple_vdef (stmt), true);
661 if (gimple_vuse (stmt))
663 if (gimple_vuse_op (stmt) == NULL_USE_OPERAND_P)
665 error ("statement has VUSE operand not in uses list");
668 has_err |= verify_ssa_name (gimple_vuse (stmt), true);
672 error ("in statement");
673 print_gimple_stmt (stderr, stmt, 0, TDF_VOPS|TDF_MEMSYMS);
677 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE|SSA_OP_DEF)
679 if (verify_ssa_name (op, false))
681 error ("in statement");
682 print_gimple_stmt (stderr, stmt, 0, TDF_VOPS|TDF_MEMSYMS);
687 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE|SSA_OP_VUSE)
689 op = USE_FROM_PTR (use_p);
690 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
691 use_p, stmt, false, names_defined_in_bb))
695 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
697 if (SSA_NAME_DEF_STMT (op) != stmt)
699 error ("SSA_NAME_DEF_STMT is wrong");
700 fprintf (stderr, "Expected definition statement:\n");
701 print_gimple_stmt (stderr, stmt, 4, TDF_VOPS);
702 fprintf (stderr, "\nActual definition statement:\n");
703 print_gimple_stmt (stderr, SSA_NAME_DEF_STMT (op),
707 bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
711 bitmap_clear (names_defined_in_bb);
714 free (definition_block);
716 /* Restore the dominance information to its prior known state, so
717 that we do not perturb the compiler's subsequent behavior. */
718 if (orig_dom_state == DOM_NONE)
719 free_dominance_info (CDI_DOMINATORS);
721 set_dom_info_availability (CDI_DOMINATORS, orig_dom_state);
723 BITMAP_FREE (names_defined_in_bb);
724 timevar_pop (TV_TREE_SSA_VERIFY);
728 internal_error ("verify_ssa failed");
731 /* Return true if the uid in both int tree maps are equal. */
734 int_tree_map_eq (const void *va, const void *vb)
736 const struct int_tree_map *a = (const struct int_tree_map *) va;
737 const struct int_tree_map *b = (const struct int_tree_map *) vb;
738 return (a->uid == b->uid);
741 /* Hash a UID in a int_tree_map. */
744 int_tree_map_hash (const void *item)
746 return ((const struct int_tree_map *)item)->uid;
749 /* Return true if the DECL_UID in both trees are equal. */
752 uid_decl_map_eq (const void *va, const void *vb)
754 const_tree a = (const_tree) va;
755 const_tree b = (const_tree) vb;
756 return (a->decl_minimal.uid == b->decl_minimal.uid);
759 /* Hash a tree in a uid_decl_map. */
762 uid_decl_map_hash (const void *item)
764 return ((const_tree)item)->decl_minimal.uid;
767 /* Return true if the DECL_UID in both trees are equal. */
770 uid_ssaname_map_eq (const void *va, const void *vb)
772 const_tree a = (const_tree) va;
773 const_tree b = (const_tree) vb;
774 return (a->ssa_name.var->decl_minimal.uid == b->ssa_name.var->decl_minimal.uid);
777 /* Hash a tree in a uid_decl_map. */
780 uid_ssaname_map_hash (const void *item)
782 return ((const_tree)item)->ssa_name.var->decl_minimal.uid;
786 /* Initialize global DFA and SSA structures. */
789 init_tree_ssa (struct function *fn)
791 fn->gimple_df = GGC_CNEW (struct gimple_df);
792 fn->gimple_df->referenced_vars = htab_create_ggc (20, uid_decl_map_hash,
793 uid_decl_map_eq, NULL);
794 fn->gimple_df->default_defs = htab_create_ggc (20, uid_ssaname_map_hash,
795 uid_ssaname_map_eq, NULL);
796 pt_solution_reset (&fn->gimple_df->escaped);
797 pt_solution_reset (&fn->gimple_df->callused);
798 init_ssanames (fn, 0);
803 /* Deallocate memory associated with SSA data structures for FNDECL. */
806 delete_tree_ssa (void)
808 referenced_var_iterator rvi;
811 /* Remove annotations from every referenced local variable. */
812 FOR_EACH_REFERENCED_VAR (var, rvi)
814 if (is_global_var (var))
817 ggc_free (var->base.ann);
818 var->base.ann = NULL;
820 htab_delete (gimple_referenced_vars (cfun));
821 cfun->gimple_df->referenced_vars = NULL;
826 /* We no longer maintain the SSA operand cache at this point. */
827 if (ssa_operands_active ())
828 fini_ssa_operands ();
830 delete_alias_heapvars ();
832 htab_delete (cfun->gimple_df->default_defs);
833 cfun->gimple_df->default_defs = NULL;
834 pt_solution_reset (&cfun->gimple_df->escaped);
835 pt_solution_reset (&cfun->gimple_df->callused);
836 if (cfun->gimple_df->decls_to_pointers != NULL)
837 pointer_map_destroy (cfun->gimple_df->decls_to_pointers);
838 cfun->gimple_df->decls_to_pointers = NULL;
839 cfun->gimple_df->modified_noreturn_calls = NULL;
840 cfun->gimple_df = NULL;
842 /* We no longer need the edge variable maps. */
843 redirect_edge_var_map_destroy ();
846 /* Helper function for useless_type_conversion_p. */
849 useless_type_conversion_p_1 (tree outer_type, tree inner_type)
851 /* Do the following before stripping toplevel qualifiers. */
852 if (POINTER_TYPE_P (inner_type)
853 && POINTER_TYPE_P (outer_type))
855 /* Do not lose casts to restrict qualified pointers. */
856 if ((TYPE_RESTRICT (outer_type)
857 != TYPE_RESTRICT (inner_type))
858 && TYPE_RESTRICT (outer_type))
862 /* From now on qualifiers on value types do not matter. */
863 inner_type = TYPE_MAIN_VARIANT (inner_type);
864 outer_type = TYPE_MAIN_VARIANT (outer_type);
866 if (inner_type == outer_type)
869 /* If we know the canonical types, compare them. */
870 if (TYPE_CANONICAL (inner_type)
871 && TYPE_CANONICAL (inner_type) == TYPE_CANONICAL (outer_type))
874 /* Changes in machine mode are never useless conversions. */
875 if (TYPE_MODE (inner_type) != TYPE_MODE (outer_type))
878 /* If both the inner and outer types are integral types, then the
879 conversion is not necessary if they have the same mode and
880 signedness and precision, and both or neither are boolean. */
881 if (INTEGRAL_TYPE_P (inner_type)
882 && INTEGRAL_TYPE_P (outer_type))
884 /* Preserve changes in signedness or precision. */
885 if (TYPE_UNSIGNED (inner_type) != TYPE_UNSIGNED (outer_type)
886 || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
889 /* We don't need to preserve changes in the types minimum or
890 maximum value in general as these do not generate code
891 unless the types precisions are different. */
895 /* Scalar floating point types with the same mode are compatible. */
896 else if (SCALAR_FLOAT_TYPE_P (inner_type)
897 && SCALAR_FLOAT_TYPE_P (outer_type))
900 /* Fixed point types with the same mode are compatible. */
901 else if (FIXED_POINT_TYPE_P (inner_type)
902 && FIXED_POINT_TYPE_P (outer_type))
905 /* We need to take special care recursing to pointed-to types. */
906 else if (POINTER_TYPE_P (inner_type)
907 && POINTER_TYPE_P (outer_type))
909 /* Don't lose casts between pointers to volatile and non-volatile
910 qualified types. Doing so would result in changing the semantics
911 of later accesses. For function types the volatile qualifier
912 is used to indicate noreturn functions. */
913 if (TREE_CODE (TREE_TYPE (outer_type)) != FUNCTION_TYPE
914 && TREE_CODE (TREE_TYPE (outer_type)) != METHOD_TYPE
915 && TREE_CODE (TREE_TYPE (inner_type)) != FUNCTION_TYPE
916 && TREE_CODE (TREE_TYPE (inner_type)) != METHOD_TYPE
917 && (TYPE_VOLATILE (TREE_TYPE (outer_type))
918 != TYPE_VOLATILE (TREE_TYPE (inner_type)))
919 && TYPE_VOLATILE (TREE_TYPE (outer_type)))
922 /* Do not lose casts between pointers that when dereferenced access
923 memory with different alias sets. */
924 if (get_deref_alias_set (inner_type) != get_deref_alias_set (outer_type))
927 /* We do not care for const qualification of the pointed-to types
928 as const qualification has no semantic value to the middle-end. */
930 /* Otherwise pointers/references are equivalent if their pointed
931 to types are effectively the same. We can strip qualifiers
932 on pointed-to types for further comparison, which is done in
934 return useless_type_conversion_p_1 (TREE_TYPE (outer_type),
935 TREE_TYPE (inner_type));
938 /* Recurse for complex types. */
939 else if (TREE_CODE (inner_type) == COMPLEX_TYPE
940 && TREE_CODE (outer_type) == COMPLEX_TYPE)
941 return useless_type_conversion_p (TREE_TYPE (outer_type),
942 TREE_TYPE (inner_type));
944 /* Recurse for vector types with the same number of subparts. */
945 else if (TREE_CODE (inner_type) == VECTOR_TYPE
946 && TREE_CODE (outer_type) == VECTOR_TYPE
947 && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
948 return useless_type_conversion_p (TREE_TYPE (outer_type),
949 TREE_TYPE (inner_type));
951 /* For aggregates we may need to fall back to structural equality
953 else if (AGGREGATE_TYPE_P (inner_type)
954 && AGGREGATE_TYPE_P (outer_type))
956 /* Different types of aggregates are incompatible. */
957 if (TREE_CODE (inner_type) != TREE_CODE (outer_type))
960 /* Conversions from array types with unknown extent to
961 array types with known extent are not useless. */
962 if (TREE_CODE (inner_type) == ARRAY_TYPE
963 && !TYPE_DOMAIN (inner_type)
964 && TYPE_DOMAIN (outer_type))
967 /* ??? This seems to be necessary even for aggregates that don't
968 have TYPE_STRUCTURAL_EQUALITY_P set. */
970 /* ??? This should eventually just return false. */
971 return lang_hooks.types_compatible_p (inner_type, outer_type);
973 /* Also for functions and possibly other types with
974 TYPE_STRUCTURAL_EQUALITY_P set. */
975 else if (TYPE_STRUCTURAL_EQUALITY_P (inner_type)
976 && TYPE_STRUCTURAL_EQUALITY_P (outer_type))
977 return lang_hooks.types_compatible_p (inner_type, outer_type);
982 /* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a
983 useless type conversion, otherwise return false.
985 This function implicitly defines the middle-end type system. With
986 the notion of 'a < b' meaning that useless_type_conversion_p (a, b)
987 holds and 'a > b' meaning that useless_type_conversion_p (b, a) holds,
988 the following invariants shall be fulfilled:
990 1) useless_type_conversion_p is transitive.
991 If a < b and b < c then a < c.
993 2) useless_type_conversion_p is not symmetric.
994 From a < b does not follow a > b.
996 3) Types define the available set of operations applicable to values.
997 A type conversion is useless if the operations for the target type
998 is a subset of the operations for the source type. For example
999 casts to void* are useless, casts from void* are not (void* can't
1000 be dereferenced or offsetted, but copied, hence its set of operations
1001 is a strict subset of that of all other data pointer types). Casts
1002 to const T* are useless (can't be written to), casts from const T*
1006 useless_type_conversion_p (tree outer_type, tree inner_type)
1008 /* If the outer type is (void *) or a pointer to an incomplete record type,
1009 then the conversion is not necessary.
1010 We have to make sure to not apply this while recursing though. */
1011 if (POINTER_TYPE_P (inner_type)
1012 && POINTER_TYPE_P (outer_type)
1013 && (VOID_TYPE_P (TREE_TYPE (outer_type))
1014 || (AGGREGATE_TYPE_P (TREE_TYPE (outer_type))
1015 && TREE_CODE (TREE_TYPE (outer_type)) != ARRAY_TYPE
1016 && (TREE_CODE (TREE_TYPE (outer_type))
1017 == TREE_CODE (TREE_TYPE (inner_type)))
1018 && !COMPLETE_TYPE_P (TREE_TYPE (outer_type)))))
1021 return useless_type_conversion_p_1 (outer_type, inner_type);
1024 /* Return true if a conversion from either type of TYPE1 and TYPE2
1025 to the other is not required. Otherwise return false. */
1028 types_compatible_p (tree type1, tree type2)
1030 return (type1 == type2
1031 || (useless_type_conversion_p (type1, type2)
1032 && useless_type_conversion_p (type2, type1)));
1035 /* Return true if EXPR is a useless type conversion, otherwise return
1039 tree_ssa_useless_type_conversion (tree expr)
1041 /* If we have an assignment that merely uses a NOP_EXPR to change
1042 the top of the RHS to the type of the LHS and the type conversion
1043 is "safe", then strip away the type conversion so that we can
1044 enter LHS = RHS into the const_and_copies table. */
1045 if (CONVERT_EXPR_P (expr)
1046 || TREE_CODE (expr) == VIEW_CONVERT_EXPR
1047 || TREE_CODE (expr) == NON_LVALUE_EXPR)
1048 return useless_type_conversion_p
1050 TREE_TYPE (TREE_OPERAND (expr, 0)));
1055 /* Strip conversions from EXP according to
1056 tree_ssa_useless_type_conversion and return the resulting
1060 tree_ssa_strip_useless_type_conversions (tree exp)
1062 while (tree_ssa_useless_type_conversion (exp))
1063 exp = TREE_OPERAND (exp, 0);
1068 /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
1069 described in walk_use_def_chains.
1071 VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
1072 infinite loops. We used to have a bitmap for this to just mark
1073 SSA versions we had visited. But non-sparse bitmaps are way too
1074 expensive, while sparse bitmaps may cause quadratic behavior.
1076 IS_DFS is true if the caller wants to perform a depth-first search
1077 when visiting PHI nodes. A DFS will visit each PHI argument and
1078 call FN after each one. Otherwise, all the arguments are
1079 visited first and then FN is called with each of the visited
1080 arguments in a separate pass. */
1083 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
1084 struct pointer_set_t *visited, bool is_dfs)
1088 if (pointer_set_insert (visited, var))
1091 def_stmt = SSA_NAME_DEF_STMT (var);
1093 if (gimple_code (def_stmt) != GIMPLE_PHI)
1095 /* If we reached the end of the use-def chain, call FN. */
1096 return fn (var, def_stmt, data);
1102 /* When doing a breadth-first search, call FN before following the
1103 use-def links for each argument. */
1105 for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
1106 if (fn (gimple_phi_arg_def (def_stmt, i), def_stmt, data))
1109 /* Follow use-def links out of each PHI argument. */
1110 for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
1112 tree arg = gimple_phi_arg_def (def_stmt, i);
1114 /* ARG may be NULL for newly introduced PHI nodes. */
1116 && TREE_CODE (arg) == SSA_NAME
1117 && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
1121 /* When doing a depth-first search, call FN after following the
1122 use-def links for each argument. */
1124 for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
1125 if (fn (gimple_phi_arg_def (def_stmt, i), def_stmt, data))
1134 /* Walk use-def chains starting at the SSA variable VAR. Call
1135 function FN at each reaching definition found. FN takes three
1136 arguments: VAR, its defining statement (DEF_STMT) and a generic
1137 pointer to whatever state information that FN may want to maintain
1138 (DATA). FN is able to stop the walk by returning true, otherwise
1139 in order to continue the walk, FN should return false.
1141 Note, that if DEF_STMT is a PHI node, the semantics are slightly
1142 different. The first argument to FN is no longer the original
1143 variable VAR, but the PHI argument currently being examined. If FN
1144 wants to get at VAR, it should call PHI_RESULT (PHI).
1146 If IS_DFS is true, this function will:
1148 1- walk the use-def chains for all the PHI arguments, and,
1149 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
1151 If IS_DFS is false, the two steps above are done in reverse order
1152 (i.e., a breadth-first search). */
1155 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
1160 gcc_assert (TREE_CODE (var) == SSA_NAME);
1162 def_stmt = SSA_NAME_DEF_STMT (var);
1164 /* We only need to recurse if the reaching definition comes from a PHI
1166 if (gimple_code (def_stmt) != GIMPLE_PHI)
1167 (*fn) (var, def_stmt, data);
1170 struct pointer_set_t *visited = pointer_set_create ();
1171 walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
1172 pointer_set_destroy (visited);
1177 /* Return true if T, an SSA_NAME, has an undefined value. */
1180 ssa_undefined_value_p (tree t)
1182 tree var = SSA_NAME_VAR (t);
1184 /* Parameters get their initial value from the function entry. */
1185 if (TREE_CODE (var) == PARM_DECL)
1188 /* Hard register variables get their initial value from the ether. */
1189 if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1192 /* The value is undefined iff its definition statement is empty. */
1193 return gimple_nop_p (SSA_NAME_DEF_STMT (t));
1196 /* Emit warnings for uninitialized variables. This is done in two passes.
1198 The first pass notices real uses of SSA names with undefined values.
1199 Such uses are unconditionally uninitialized, and we can be certain that
1200 such a use is a mistake. This pass is run before most optimizations,
1201 so that we catch as many as we can.
1203 The second pass follows PHI nodes to find uses that are potentially
1204 uninitialized. In this case we can't necessarily prove that the use
1205 is really uninitialized. This pass is run after most optimizations,
1206 so that we thread as many jumps and possible, and delete as much dead
1207 code as possible, in order to reduce false positives. We also look
1208 again for plain uninitialized variables, since optimization may have
1209 changed conditionally uninitialized to unconditionally uninitialized. */
1211 /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact
1212 warning text is in MSGID and LOCUS may contain a location or be null. */
1215 warn_uninit (tree t, const char *gmsgid, void *data)
1217 tree var = SSA_NAME_VAR (t);
1218 gimple context = (gimple) data;
1219 location_t location;
1220 expanded_location xloc, floc;
1222 if (!ssa_undefined_value_p (t))
1225 /* TREE_NO_WARNING either means we already warned, or the front end
1226 wishes to suppress the warning. */
1227 if (TREE_NO_WARNING (var))
1230 /* Do not warn if it can be initialized outside this module. */
1231 if (is_global_var (var))
1234 location = (context != NULL && gimple_has_location (context))
1235 ? gimple_location (context)
1236 : DECL_SOURCE_LOCATION (var);
1237 xloc = expand_location (location);
1238 floc = expand_location (DECL_SOURCE_LOCATION (cfun->decl));
1239 if (warning_at (location, OPT_Wuninitialized, gmsgid, var))
1241 TREE_NO_WARNING (var) = 1;
1243 if (xloc.file != floc.file
1244 || xloc.line < floc.line
1245 || xloc.line > LOCATION_LINE (cfun->function_end_locus))
1246 inform (DECL_SOURCE_LOCATION (var), "%qD was declared here", var);
1252 bool always_executed;
1253 bool warn_possibly_uninitialized;
1256 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1257 and warn about them. */
1260 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data_)
1262 struct walk_stmt_info *wi = (struct walk_stmt_info *) data_;
1263 struct walk_data *data = (struct walk_data *) wi->info;
1266 /* We do not care about LHS. */
1269 /* Except for operands of INDIRECT_REF. */
1270 if (!INDIRECT_REF_P (t))
1272 t = TREE_OPERAND (t, 0);
1275 switch (TREE_CODE (t))
1278 /* Taking the address of an uninitialized variable does not
1279 count as using it. */
1285 /* A VAR_DECL in the RHS of a gimple statement may mean that
1286 this variable is loaded from memory. */
1290 /* If there is not gimple stmt,
1291 or alias information has not been computed,
1292 then we cannot check VUSE ops. */
1293 if (data->stmt == NULL)
1296 /* If the load happens as part of a call do not warn about it. */
1297 if (is_gimple_call (data->stmt))
1300 vuse = gimple_vuse_op (data->stmt);
1301 if (vuse == NULL_USE_OPERAND_P)
1304 op = USE_FROM_PTR (vuse);
1305 if (t != SSA_NAME_VAR (op)
1306 || !SSA_NAME_IS_DEFAULT_DEF (op))
1308 /* If this is a VUSE of t and it is the default definition,
1309 then warn about op. */
1311 /* Fall through into SSA_NAME. */
1315 /* We only do data flow with SSA_NAMEs, so that's all we
1317 if (data->always_executed)
1318 warn_uninit (t, "%qD is used uninitialized in this function",
1320 else if (data->warn_possibly_uninitialized)
1321 warn_uninit (t, "%qD may be used uninitialized in this function",
1328 /* The total store transformation performed during gimplification
1329 creates uninitialized variable uses. If all is well, these will
1330 be optimized away, so don't warn now. */
1331 if (TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
1336 if (IS_TYPE_OR_DECL_P (t))
1344 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1345 and warn about them. */
1348 warn_uninitialized_phi (gimple phi)
1350 size_t i, n = gimple_phi_num_args (phi);
1352 /* Don't look at memory tags. */
1353 if (!is_gimple_reg (gimple_phi_result (phi)))
1356 for (i = 0; i < n; ++i)
1358 tree op = gimple_phi_arg_def (phi, i);
1359 if (TREE_CODE (op) == SSA_NAME)
1360 warn_uninit (op, "%qD may be used uninitialized in this function",
1366 warn_uninitialized_vars (bool warn_possibly_uninitialized)
1368 gimple_stmt_iterator gsi;
1370 struct walk_data data;
1372 data.warn_possibly_uninitialized = warn_possibly_uninitialized;
1374 calculate_dominance_info (CDI_POST_DOMINATORS);
1378 data.always_executed = dominated_by_p (CDI_POST_DOMINATORS,
1379 single_succ (ENTRY_BLOCK_PTR), bb);
1380 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1382 struct walk_stmt_info wi;
1383 data.stmt = gsi_stmt (gsi);
1384 memset (&wi, 0, sizeof (wi));
1386 walk_gimple_op (gsi_stmt (gsi), warn_uninitialized_var, &wi);
1390 /* Post-dominator information can not be reliably updated. Free it
1393 free_dominance_info (CDI_POST_DOMINATORS);
1398 execute_early_warn_uninitialized (void)
1400 /* Currently, this pass runs always but
1401 execute_late_warn_uninitialized only runs with optimization. With
1402 optimization we want to warn about possible uninitialized as late
1403 as possible, thus don't do it here. However, without
1404 optimization we need to warn here about "may be uninitialized".
1406 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize);
1411 execute_late_warn_uninitialized (void)
1414 gimple_stmt_iterator gsi;
1416 /* Re-do the plain uninitialized variable check, as optimization may have
1417 straightened control flow. Do this first so that we don't accidentally
1418 get a "may be" warning when we'd have seen an "is" warning later. */
1419 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
1422 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1423 warn_uninitialized_phi (gsi_stmt (gsi));
1429 gate_warn_uninitialized (void)
1431 return warn_uninitialized != 0;
1434 struct gimple_opt_pass pass_early_warn_uninitialized =
1439 gate_warn_uninitialized, /* gate */
1440 execute_early_warn_uninitialized, /* execute */
1443 0, /* static_pass_number */
1444 TV_NONE, /* tv_id */
1445 PROP_ssa, /* properties_required */
1446 0, /* properties_provided */
1447 0, /* properties_destroyed */
1448 0, /* todo_flags_start */
1449 0 /* todo_flags_finish */
1453 struct gimple_opt_pass pass_late_warn_uninitialized =
1458 gate_warn_uninitialized, /* gate */
1459 execute_late_warn_uninitialized, /* execute */
1462 0, /* static_pass_number */
1463 TV_NONE, /* tv_id */
1464 PROP_ssa, /* properties_required */
1465 0, /* properties_provided */
1466 0, /* properties_destroyed */
1467 0, /* todo_flags_start */
1468 0 /* todo_flags_finish */
1472 /* Compute TREE_ADDRESSABLE and DECL_GIMPLE_REG_P for local variables. */
1475 execute_update_addresses_taken (bool do_optimize)
1478 referenced_var_iterator rvi;
1479 gimple_stmt_iterator gsi;
1481 bitmap addresses_taken = BITMAP_ALLOC (NULL);
1482 bitmap not_reg_needs = BITMAP_ALLOC (NULL);
1483 bool update_vops = false;
1485 /* Collect into ADDRESSES_TAKEN all variables whose address is taken within
1486 the function body. */
1489 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1491 gimple stmt = gsi_stmt (gsi);
1492 enum gimple_code code = gimple_code (stmt);
1494 /* Note all addresses taken by the stmt. */
1495 gimple_ior_addresses_taken (addresses_taken, stmt);
1497 /* If we have a call or an assignment, see if the lhs contains
1498 a local decl that requires not to be a gimple register. */
1499 if (code == GIMPLE_ASSIGN || code == GIMPLE_CALL)
1501 tree lhs = gimple_get_lhs (stmt);
1503 /* We may not rewrite TMR_SYMBOL to SSA. */
1504 if (lhs && TREE_CODE (lhs) == TARGET_MEM_REF
1505 && TMR_SYMBOL (lhs))
1506 bitmap_set_bit (not_reg_needs, DECL_UID (TMR_SYMBOL (lhs)));
1508 /* A plain decl does not need it set. */
1509 else if (lhs && handled_component_p (lhs))
1511 var = get_base_address (lhs);
1513 bitmap_set_bit (not_reg_needs, DECL_UID (var));
1518 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1521 gimple phi = gsi_stmt (gsi);
1523 for (i = 0; i < gimple_phi_num_args (phi); i++)
1525 tree op = PHI_ARG_DEF (phi, i), var;
1526 if (TREE_CODE (op) == ADDR_EXPR
1527 && (var = get_base_address (TREE_OPERAND (op, 0))) != NULL
1529 bitmap_set_bit (addresses_taken, DECL_UID (var));
1534 /* When possible, clear ADDRESSABLE bit or set the REGISTER bit
1535 and mark variable for conversion into SSA. */
1536 if (optimize && do_optimize)
1537 FOR_EACH_REFERENCED_VAR (var, rvi)
1539 /* Global Variables, result decls cannot be changed. */
1540 if (is_global_var (var)
1541 || TREE_CODE (var) == RESULT_DECL
1542 || bitmap_bit_p (addresses_taken, DECL_UID (var)))
1545 if (TREE_ADDRESSABLE (var)
1546 /* Do not change TREE_ADDRESSABLE if we need to preserve var as
1547 a non-register. Otherwise we are confused and forget to
1548 add virtual operands for it. */
1549 && (!is_gimple_reg_type (TREE_TYPE (var))
1550 || !bitmap_bit_p (not_reg_needs, DECL_UID (var))))
1552 TREE_ADDRESSABLE (var) = 0;
1553 if (is_gimple_reg (var))
1554 mark_sym_for_renaming (var);
1558 fprintf (dump_file, "No longer having address taken ");
1559 print_generic_expr (dump_file, var, 0);
1560 fprintf (dump_file, "\n");
1563 if (!DECL_GIMPLE_REG_P (var)
1564 && !bitmap_bit_p (not_reg_needs, DECL_UID (var))
1565 && (TREE_CODE (TREE_TYPE (var)) == COMPLEX_TYPE
1566 || TREE_CODE (TREE_TYPE (var)) == VECTOR_TYPE)
1567 && !TREE_THIS_VOLATILE (var)
1568 && (TREE_CODE (var) != VAR_DECL || !DECL_HARD_REGISTER (var)))
1570 DECL_GIMPLE_REG_P (var) = 1;
1571 mark_sym_for_renaming (var);
1575 fprintf (dump_file, "Decl is now a gimple register ");
1576 print_generic_expr (dump_file, var, 0);
1577 fprintf (dump_file, "\n");
1582 /* Operand caches needs to be recomputed for operands referencing the updated
1587 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1589 gimple stmt = gsi_stmt (gsi);
1591 if (gimple_references_memory_p (stmt))
1595 /* Update SSA form here, we are called as non-pass as well. */
1596 update_ssa (TODO_update_ssa);
1599 BITMAP_FREE (not_reg_needs);
1600 BITMAP_FREE (addresses_taken);
1603 struct gimple_opt_pass pass_update_address_taken =
1607 "addressables", /* name */
1612 0, /* static_pass_number */
1613 TV_NONE, /* tv_id */
1614 PROP_ssa, /* properties_required */
1615 0, /* properties_provided */
1616 0, /* properties_destroyed */
1617 0, /* todo_flags_start */
1618 TODO_update_address_taken
1619 | TODO_dump_func /* todo_flags_finish */