1 /* Data flow functions for trees.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
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"
26 #include "pointer-set.h"
30 #include "hard-reg-set.h"
31 #include "basic-block.h"
36 #include "langhooks.h"
39 #include "diagnostic.h"
40 #include "tree-dump.h"
41 #include "tree-gimple.h"
42 #include "tree-flow.h"
43 #include "tree-inline.h"
44 #include "tree-pass.h"
49 /* Build and maintain data flow information for trees. */
51 /* Counters used to display DFA and SSA statistics. */
66 /* Local functions. */
67 static void collect_dfa_stats (struct dfa_stats_d
*);
68 static tree
collect_dfa_stats_r (tree
*, int *, void *);
69 static tree
find_vars_r (tree
*, int *, void *);
72 /*---------------------------------------------------------------------------
73 Dataflow analysis (DFA) routines
74 ---------------------------------------------------------------------------*/
75 /* Find all the variables referenced in the function. This function
76 builds the global arrays REFERENCED_VARS and CALL_CLOBBERED_VARS.
78 Note that this function does not look for statement operands, it simply
79 determines what variables are referenced in the program and detects
80 various attributes for each variable used by alias analysis and the
84 find_referenced_vars (void)
87 block_stmt_iterator si
;
92 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
94 tree
*stmt_p
= bsi_stmt_ptr (si
);
95 walk_tree (stmt_p
, find_vars_r
, NULL
, NULL
);
98 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
100 int len
= PHI_NUM_ARGS (phi
);
103 walk_tree (&phi
, find_vars_r
, NULL
, NULL
);
105 for (i
= 0; i
< len
; i
++)
107 tree arg
= PHI_ARG_DEF (phi
, i
);
108 walk_tree (&arg
, find_vars_r
, NULL
, NULL
);
116 struct gimple_opt_pass pass_referenced_vars
=
122 find_referenced_vars
, /* execute */
125 0, /* static_pass_number */
126 TV_FIND_REFERENCED_VARS
, /* tv_id */
127 PROP_gimple_leh
| PROP_cfg
, /* properties_required */
128 PROP_referenced_vars
, /* properties_provided */
129 0, /* properties_destroyed */
130 TODO_dump_func
, /* todo_flags_start */
131 TODO_dump_func
/* todo_flags_finish */
136 /*---------------------------------------------------------------------------
138 ---------------------------------------------------------------------------*/
139 /* Create a new annotation for a _DECL node T. */
142 create_var_ann (tree t
)
147 gcc_assert (DECL_P (t
));
148 gcc_assert (!t
->base
.ann
|| t
->base
.ann
->common
.type
== VAR_ANN
);
150 ann
= GGC_CNEW (struct var_ann_d
);
151 ann
->common
.type
= VAR_ANN
;
152 t
->base
.ann
= (tree_ann_t
) ann
;
157 /* Create a new annotation for a FUNCTION_DECL node T. */
160 create_function_ann (tree t
)
165 gcc_assert (TREE_CODE (t
) == FUNCTION_DECL
);
166 gcc_assert (!t
->base
.ann
|| t
->base
.ann
->common
.type
== FUNCTION_ANN
);
168 ann
= ggc_alloc (sizeof (*ann
));
169 memset ((void *) ann
, 0, sizeof (*ann
));
171 ann
->common
.type
= FUNCTION_ANN
;
173 t
->base
.ann
= (tree_ann_t
) ann
;
178 /* Create a new annotation for a statement node T. */
181 create_stmt_ann (tree t
)
185 gcc_assert (is_gimple_stmt (t
));
186 gcc_assert (!t
->base
.ann
|| t
->base
.ann
->common
.type
== STMT_ANN
);
188 ann
= GGC_CNEW (struct stmt_ann_d
);
190 ann
->common
.type
= STMT_ANN
;
192 /* Since we just created the annotation, mark the statement modified. */
193 ann
->modified
= true;
195 ann
->uid
= inc_gimple_stmt_max_uid (cfun
);
196 t
->base
.ann
= (tree_ann_t
) ann
;
201 /* Renumber all of the gimple stmt uids. */
204 renumber_gimple_stmt_uids (void)
208 set_gimple_stmt_max_uid (cfun
, 0);
211 block_stmt_iterator bsi
;
212 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
214 tree stmt
= bsi_stmt (bsi
);
215 /* If the stmt has an annotation, then overwrite it, if not,
216 the process of getting it will set the number
218 if (has_stmt_ann (stmt
))
219 set_gimple_stmt_uid (stmt
, inc_gimple_stmt_max_uid (cfun
));
226 /* Create a new annotation for a tree T. */
229 create_tree_common_ann (tree t
)
231 tree_ann_common_t ann
;
234 gcc_assert (!t
->base
.ann
|| t
->base
.ann
->common
.type
== TREE_ANN_COMMON
);
236 ann
= GGC_CNEW (struct tree_ann_common_d
);
238 ann
->type
= TREE_ANN_COMMON
;
239 t
->base
.ann
= (tree_ann_t
) ann
;
244 /* Build a temporary. Make sure and register it to be renamed. */
247 make_rename_temp (tree type
, const char *prefix
)
249 tree t
= create_tmp_var (type
, prefix
);
251 if (TREE_CODE (TREE_TYPE (t
)) == COMPLEX_TYPE
252 || TREE_CODE (TREE_TYPE (t
)) == VECTOR_TYPE
)
253 DECL_GIMPLE_REG_P (t
) = 1;
255 if (gimple_referenced_vars (cfun
))
257 add_referenced_var (t
);
258 mark_sym_for_renaming (t
);
266 /*---------------------------------------------------------------------------
268 ---------------------------------------------------------------------------*/
269 /* Dump the list of all the referenced variables in the current function to
273 dump_referenced_vars (FILE *file
)
276 referenced_var_iterator rvi
;
278 fprintf (file
, "\nReferenced variables in %s: %u\n\n",
279 get_name (current_function_decl
), (unsigned) num_referenced_vars
);
281 FOR_EACH_REFERENCED_VAR (var
, rvi
)
283 fprintf (file
, "Variable: ");
284 dump_variable (file
, var
);
285 fprintf (file
, "\n");
290 /* Dump the list of all the referenced variables to stderr. */
293 debug_referenced_vars (void)
295 dump_referenced_vars (stderr
);
299 /* Dump variable VAR and its may-aliases to FILE. */
302 dump_variable (FILE *file
, tree var
)
306 if (TREE_CODE (var
) == SSA_NAME
)
308 if (POINTER_TYPE_P (TREE_TYPE (var
)))
309 dump_points_to_info_for (file
, var
);
310 var
= SSA_NAME_VAR (var
);
313 if (var
== NULL_TREE
)
315 fprintf (file
, "<nil>");
319 print_generic_expr (file
, var
, dump_flags
);
323 fprintf (file
, ", UID D.%u", (unsigned) DECL_UID (var
));
325 fprintf (file
, ", ");
326 print_generic_expr (file
, TREE_TYPE (var
), dump_flags
);
328 if (ann
&& ann
->symbol_mem_tag
)
330 fprintf (file
, ", symbol memory tag: ");
331 print_generic_expr (file
, ann
->symbol_mem_tag
, dump_flags
);
334 if (TREE_ADDRESSABLE (var
))
335 fprintf (file
, ", is addressable");
337 if (is_global_var (var
))
338 fprintf (file
, ", is global");
340 if (TREE_THIS_VOLATILE (var
))
341 fprintf (file
, ", is volatile");
343 dump_mem_sym_stats_for_var (file
, var
);
345 if (is_call_clobbered (var
))
348 var_ann_t va
= var_ann (var
);
349 unsigned int escape_mask
= va
->escape_mask
;
351 fprintf (file
, ", call clobbered");
352 fprintf (file
, " (");
353 if (escape_mask
& ESCAPE_STORED_IN_GLOBAL
)
354 { fprintf (file
, "%sstored in global", s
); s
= ", "; }
355 if (escape_mask
& ESCAPE_TO_ASM
)
356 { fprintf (file
, "%sgoes through ASM", s
); s
= ", "; }
357 if (escape_mask
& ESCAPE_TO_CALL
)
358 { fprintf (file
, "%spassed to call", s
); s
= ", "; }
359 if (escape_mask
& ESCAPE_BAD_CAST
)
360 { fprintf (file
, "%sbad cast", s
); s
= ", "; }
361 if (escape_mask
& ESCAPE_TO_RETURN
)
362 { fprintf (file
, "%sreturned from func", s
); s
= ", "; }
363 if (escape_mask
& ESCAPE_TO_PURE_CONST
)
364 { fprintf (file
, "%spassed to pure/const", s
); s
= ", "; }
365 if (escape_mask
& ESCAPE_IS_GLOBAL
)
366 { fprintf (file
, "%sis global var", s
); s
= ", "; }
367 if (escape_mask
& ESCAPE_IS_PARM
)
368 { fprintf (file
, "%sis incoming pointer", s
); s
= ", "; }
369 if (escape_mask
& ESCAPE_UNKNOWN
)
370 { fprintf (file
, "%sunknown escape", s
); s
= ", "; }
374 if (ann
->noalias_state
== NO_ALIAS
)
375 fprintf (file
, ", NO_ALIAS (does not alias other NO_ALIAS symbols)");
376 else if (ann
->noalias_state
== NO_ALIAS_GLOBAL
)
377 fprintf (file
, ", NO_ALIAS_GLOBAL (does not alias other NO_ALIAS symbols"
378 " and global vars)");
379 else if (ann
->noalias_state
== NO_ALIAS_ANYTHING
)
380 fprintf (file
, ", NO_ALIAS_ANYTHING (does not alias any other symbols)");
382 if (gimple_default_def (cfun
, var
))
384 fprintf (file
, ", default def: ");
385 print_generic_expr (file
, gimple_default_def (cfun
, var
), dump_flags
);
388 if (MTAG_P (var
) && may_aliases (var
))
390 fprintf (file
, ", may aliases: ");
391 dump_may_aliases_for (file
, var
);
394 if (!is_gimple_reg (var
))
396 if (memory_partition (var
))
398 fprintf (file
, ", belongs to partition: ");
399 print_generic_expr (file
, memory_partition (var
), dump_flags
);
402 if (TREE_CODE (var
) == MEMORY_PARTITION_TAG
)
404 fprintf (file
, ", partition symbols: ");
405 dump_decl_set (file
, MPT_SYMBOLS (var
));
409 fprintf (file
, "\n");
413 /* Dump variable VAR and its may-aliases to stderr. */
416 debug_variable (tree var
)
418 dump_variable (stderr
, var
);
422 /* Dump various DFA statistics to FILE. */
425 dump_dfa_stats (FILE *file
)
427 struct dfa_stats_d dfa_stats
;
429 unsigned long size
, total
= 0;
430 const char * const fmt_str
= "%-30s%-13s%12s\n";
431 const char * const fmt_str_1
= "%-30s%13lu%11lu%c\n";
432 const char * const fmt_str_3
= "%-43s%11lu%c\n";
434 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
436 collect_dfa_stats (&dfa_stats
);
438 fprintf (file
, "\nDFA Statistics for %s\n\n", funcname
);
440 fprintf (file
, "---------------------------------------------------------\n");
441 fprintf (file
, fmt_str
, "", " Number of ", "Memory");
442 fprintf (file
, fmt_str
, "", " instances ", "used ");
443 fprintf (file
, "---------------------------------------------------------\n");
445 size
= num_referenced_vars
* sizeof (tree
);
447 fprintf (file
, fmt_str_1
, "Referenced variables", (unsigned long)num_referenced_vars
,
448 SCALE (size
), LABEL (size
));
450 size
= dfa_stats
.num_stmt_anns
* sizeof (struct stmt_ann_d
);
452 fprintf (file
, fmt_str_1
, "Statements annotated", dfa_stats
.num_stmt_anns
,
453 SCALE (size
), LABEL (size
));
455 size
= dfa_stats
.num_var_anns
* sizeof (struct var_ann_d
);
457 fprintf (file
, fmt_str_1
, "Variables annotated", dfa_stats
.num_var_anns
,
458 SCALE (size
), LABEL (size
));
460 size
= dfa_stats
.num_uses
* sizeof (tree
*);
462 fprintf (file
, fmt_str_1
, "USE operands", dfa_stats
.num_uses
,
463 SCALE (size
), LABEL (size
));
465 size
= dfa_stats
.num_defs
* sizeof (tree
*);
467 fprintf (file
, fmt_str_1
, "DEF operands", dfa_stats
.num_defs
,
468 SCALE (size
), LABEL (size
));
470 size
= dfa_stats
.num_vuses
* sizeof (tree
*);
472 fprintf (file
, fmt_str_1
, "VUSE operands", dfa_stats
.num_vuses
,
473 SCALE (size
), LABEL (size
));
475 size
= dfa_stats
.num_vdefs
* sizeof (tree
*);
477 fprintf (file
, fmt_str_1
, "VDEF operands", dfa_stats
.num_vdefs
,
478 SCALE (size
), LABEL (size
));
480 size
= dfa_stats
.num_phis
* sizeof (struct tree_phi_node
);
482 fprintf (file
, fmt_str_1
, "PHI nodes", dfa_stats
.num_phis
,
483 SCALE (size
), LABEL (size
));
485 size
= dfa_stats
.num_phi_args
* sizeof (struct phi_arg_d
);
487 fprintf (file
, fmt_str_1
, "PHI arguments", dfa_stats
.num_phi_args
,
488 SCALE (size
), LABEL (size
));
490 fprintf (file
, "---------------------------------------------------------\n");
491 fprintf (file
, fmt_str_3
, "Total memory used by DFA/SSA data", SCALE (total
),
493 fprintf (file
, "---------------------------------------------------------\n");
494 fprintf (file
, "\n");
496 if (dfa_stats
.num_phis
)
497 fprintf (file
, "Average number of arguments per PHI node: %.1f (max: %d)\n",
498 (float) dfa_stats
.num_phi_args
/ (float) dfa_stats
.num_phis
,
499 dfa_stats
.max_num_phi_args
);
501 fprintf (file
, "\n");
505 /* Dump DFA statistics on stderr. */
508 debug_dfa_stats (void)
510 dump_dfa_stats (stderr
);
514 /* Collect DFA statistics and store them in the structure pointed to by
518 collect_dfa_stats (struct dfa_stats_d
*dfa_stats_p
)
520 struct pointer_set_t
*pset
;
522 block_stmt_iterator i
;
524 gcc_assert (dfa_stats_p
);
526 memset ((void *)dfa_stats_p
, 0, sizeof (struct dfa_stats_d
));
528 /* Walk all the trees in the function counting references. Start at
529 basic block NUM_FIXED_BLOCKS, but don't stop at block boundaries. */
530 pset
= pointer_set_create ();
532 for (i
= bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS
));
533 !bsi_end_p (i
); bsi_next (&i
))
534 walk_tree (bsi_stmt_ptr (i
), collect_dfa_stats_r
, (void *) dfa_stats_p
,
537 pointer_set_destroy (pset
);
542 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
544 dfa_stats_p
->num_phis
++;
545 dfa_stats_p
->num_phi_args
+= PHI_NUM_ARGS (phi
);
546 if (PHI_NUM_ARGS (phi
) > dfa_stats_p
->max_num_phi_args
)
547 dfa_stats_p
->max_num_phi_args
= PHI_NUM_ARGS (phi
);
553 /* Callback for walk_tree to collect DFA statistics for a tree and its
557 collect_dfa_stats_r (tree
*tp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
561 struct dfa_stats_d
*dfa_stats_p
= (struct dfa_stats_d
*)data
;
565 switch (ann_type (t
->base
.ann
))
569 dfa_stats_p
->num_stmt_anns
++;
570 dfa_stats_p
->num_defs
+= NUM_SSA_OPERANDS (t
, SSA_OP_DEF
);
571 dfa_stats_p
->num_uses
+= NUM_SSA_OPERANDS (t
, SSA_OP_USE
);
572 dfa_stats_p
->num_vdefs
+= NUM_SSA_OPERANDS (t
, SSA_OP_VDEF
);
573 dfa_stats_p
->num_vuses
+= NUM_SSA_OPERANDS (t
, SSA_OP_VUSE
);
578 dfa_stats_p
->num_var_anns
++;
590 /*---------------------------------------------------------------------------
591 Miscellaneous helpers
592 ---------------------------------------------------------------------------*/
593 /* Callback for walk_tree. Used to collect variables referenced in
597 find_vars_r (tree
*tp
, int *walk_subtrees
, void *data ATTRIBUTE_UNUSED
)
599 /* If we are reading the lto info back in, we need to rescan the
601 if (TREE_CODE (*tp
) == SSA_NAME
)
602 add_referenced_var (SSA_NAME_VAR (*tp
));
604 /* If T is a regular variable that the optimizers are interested
605 in, add it to the list of variables. */
606 else if (SSA_VAR_P (*tp
))
607 add_referenced_var (*tp
);
609 /* Type, _DECL and constant nodes have no interesting children.
611 else if (IS_TYPE_OR_DECL_P (*tp
) || CONSTANT_CLASS_P (*tp
))
617 /* Lookup UID in the referenced_vars hashtable and return the associated
621 referenced_var_lookup (unsigned int uid
)
624 struct tree_decl_minimal in
;
626 h
= (tree
) htab_find_with_hash (gimple_referenced_vars (cfun
), &in
, uid
);
627 gcc_assert (h
|| uid
== 0);
631 /* Check if TO is in the referenced_vars hash table and insert it if not.
632 Return true if it required insertion. */
635 referenced_var_check_and_insert (tree to
)
638 struct tree_decl_minimal in
;
639 unsigned int uid
= DECL_UID (to
);
642 h
= (tree
) htab_find_with_hash (gimple_referenced_vars (cfun
), &in
, uid
);
645 /* DECL_UID has already been entered in the table. Verify that it is
646 the same entry as TO. See PR 27793. */
647 gcc_assert (h
== to
);
651 loc
= (tree
*) htab_find_slot_with_hash (gimple_referenced_vars (cfun
),
657 /* Lookup VAR UID in the default_defs hashtable and return the associated
661 gimple_default_def (struct function
*fn
, tree var
)
663 struct tree_decl_minimal ind
;
664 struct tree_ssa_name in
;
665 gcc_assert (SSA_VAR_P (var
));
667 ind
.uid
= DECL_UID (var
);
668 return (tree
) htab_find_with_hash (DEFAULT_DEFS (fn
), &in
, DECL_UID (var
));
671 /* Insert the pair VAR's UID, DEF into the default_defs hashtable. */
674 set_default_def (tree var
, tree def
)
676 struct tree_decl_minimal ind
;
677 struct tree_ssa_name in
;
680 gcc_assert (SSA_VAR_P (var
));
682 ind
.uid
= DECL_UID (var
);
685 loc
= htab_find_slot_with_hash (DEFAULT_DEFS (cfun
), &in
,
686 DECL_UID (var
), INSERT
);
688 htab_remove_elt (DEFAULT_DEFS (cfun
), *loc
);
691 gcc_assert (TREE_CODE (def
) == SSA_NAME
&& SSA_NAME_VAR (def
) == var
);
692 loc
= htab_find_slot_with_hash (DEFAULT_DEFS (cfun
), &in
,
693 DECL_UID (var
), INSERT
);
695 /* Default definition might be changed by tail call optimization. */
697 SSA_NAME_IS_DEFAULT_DEF (*(tree
*) loc
) = false;
700 /* Mark DEF as the default definition for VAR. */
701 SSA_NAME_IS_DEFAULT_DEF (def
) = true;
704 /* Add VAR to the list of referenced variables if it isn't already there. */
707 add_referenced_var (tree var
)
711 v_ann
= get_var_ann (var
);
712 gcc_assert (DECL_P (var
));
714 /* Insert VAR into the referenced_vars has table if it isn't present. */
715 if (referenced_var_check_and_insert (var
))
717 /* This is the first time we found this variable, annotate it with
718 attributes that are intrinsic to the variable. */
720 /* Tag's don't have DECL_INITIAL. */
724 /* Scan DECL_INITIAL for pointer variables as they may contain
725 address arithmetic referencing the address of other
727 Even non-constant intializers need to be walked, because
728 IPA passes might prove that their are invariant later on. */
729 if (DECL_INITIAL (var
)
730 /* Initializers of external variables are not useful to the
732 && !DECL_EXTERNAL (var
))
733 walk_tree (&DECL_INITIAL (var
), find_vars_r
, NULL
, 0);
737 /* Remove VAR from the list. */
740 remove_referenced_var (tree var
)
743 struct tree_decl_minimal in
;
745 unsigned int uid
= DECL_UID (var
);
747 clear_call_clobbered (var
);
748 if ((v_ann
= var_ann (var
)))
750 /* Preserve var_anns of globals, but clear their alias info. */
752 || (!TREE_STATIC (var
) && !DECL_EXTERNAL (var
)))
755 var
->base
.ann
= NULL
;
759 v_ann
->mpt
= NULL_TREE
;
760 v_ann
->symbol_mem_tag
= NULL_TREE
;
763 gcc_assert (DECL_P (var
));
765 loc
= htab_find_slot_with_hash (gimple_referenced_vars (cfun
), &in
, uid
,
767 htab_clear_slot (gimple_referenced_vars (cfun
), loc
);
771 /* Return the virtual variable associated to the non-scalar variable VAR. */
774 get_virtual_var (tree var
)
778 if (TREE_CODE (var
) == SSA_NAME
)
779 var
= SSA_NAME_VAR (var
);
781 while (TREE_CODE (var
) == REALPART_EXPR
|| TREE_CODE (var
) == IMAGPART_EXPR
782 || handled_component_p (var
))
783 var
= TREE_OPERAND (var
, 0);
785 /* Treating GIMPLE registers as virtual variables makes no sense.
786 Also complain if we couldn't extract a _DECL out of the original
788 gcc_assert (SSA_VAR_P (var
));
789 gcc_assert (!is_gimple_reg (var
));
794 /* Mark all the naked symbols in STMT for SSA renaming.
796 NOTE: This function should only be used for brand new statements.
797 If the caller is modifying an existing statement, it should use the
798 combination push_stmt_changes/pop_stmt_changes. */
801 mark_symbols_for_renaming (tree stmt
)
808 /* Mark all the operands for renaming. */
809 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_ALL_OPERANDS
)
811 mark_sym_for_renaming (op
);
815 /* Find all variables within the gimplified statement that were not previously
816 visible to the function and add them to the referenced variables list. */
819 find_new_referenced_vars_1 (tree
*tp
, int *walk_subtrees
,
820 void *data ATTRIBUTE_UNUSED
)
824 if (TREE_CODE (t
) == VAR_DECL
&& !var_ann (t
))
826 add_referenced_var (t
);
827 mark_sym_for_renaming (t
);
830 if (IS_TYPE_OR_DECL_P (t
))
837 find_new_referenced_vars (tree
*stmt_p
)
839 walk_tree (stmt_p
, find_new_referenced_vars_1
, NULL
, NULL
);
843 /* If EXP is a handled component reference for a structure, return the
844 base variable. The access range is delimited by bit positions *POFFSET and
845 *POFFSET + *PMAX_SIZE. The access size is *PSIZE bits. If either
846 *PSIZE or *PMAX_SIZE is -1, they could not be determined. If *PSIZE
847 and *PMAX_SIZE are equal, the access is non-variable. */
850 get_ref_base_and_extent (tree exp
, HOST_WIDE_INT
*poffset
,
851 HOST_WIDE_INT
*psize
,
852 HOST_WIDE_INT
*pmax_size
)
854 HOST_WIDE_INT bitsize
= -1;
855 HOST_WIDE_INT maxsize
= -1;
856 tree size_tree
= NULL_TREE
;
857 HOST_WIDE_INT bit_offset
= 0;
858 bool seen_variable_array_ref
= false;
860 gcc_assert (!SSA_VAR_P (exp
));
862 /* First get the final access size from just the outermost expression. */
863 if (TREE_CODE (exp
) == COMPONENT_REF
)
864 size_tree
= DECL_SIZE (TREE_OPERAND (exp
, 1));
865 else if (TREE_CODE (exp
) == BIT_FIELD_REF
)
866 size_tree
= TREE_OPERAND (exp
, 1);
869 enum machine_mode mode
= TYPE_MODE (TREE_TYPE (exp
));
871 size_tree
= TYPE_SIZE (TREE_TYPE (exp
));
873 bitsize
= GET_MODE_BITSIZE (mode
);
875 if (size_tree
!= NULL_TREE
)
877 if (! host_integerp (size_tree
, 1))
880 bitsize
= TREE_INT_CST_LOW (size_tree
);
883 /* Initially, maxsize is the same as the accessed element size.
884 In the following it will only grow (or become -1). */
887 /* Compute cumulative bit-offset for nested component-refs and array-refs,
888 and find the ultimate containing object. */
891 switch (TREE_CODE (exp
))
894 bit_offset
+= tree_low_cst (TREE_OPERAND (exp
, 2), 0);
899 tree field
= TREE_OPERAND (exp
, 1);
900 tree this_offset
= component_ref_field_offset (exp
);
902 if (this_offset
&& TREE_CODE (this_offset
) == INTEGER_CST
)
904 HOST_WIDE_INT hthis_offset
= tree_low_cst (this_offset
, 0);
906 hthis_offset
*= BITS_PER_UNIT
;
907 bit_offset
+= hthis_offset
;
908 bit_offset
+= tree_low_cst (DECL_FIELD_BIT_OFFSET (field
), 0);
912 tree csize
= TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp
, 0)));
913 /* We need to adjust maxsize to the whole structure bitsize.
914 But we can subtract any constant offset seen sofar,
915 because that would get us out of the structure otherwise. */
916 if (maxsize
!= -1 && csize
&& host_integerp (csize
, 1))
917 maxsize
= TREE_INT_CST_LOW (csize
) - bit_offset
;
925 case ARRAY_RANGE_REF
:
927 tree index
= TREE_OPERAND (exp
, 1);
928 tree low_bound
= array_ref_low_bound (exp
);
929 tree unit_size
= array_ref_element_size (exp
);
931 /* If the resulting bit-offset is constant, track it. */
932 if (host_integerp (index
, 0)
933 && host_integerp (low_bound
, 0)
934 && host_integerp (unit_size
, 1))
936 HOST_WIDE_INT hindex
= tree_low_cst (index
, 0);
938 hindex
-= tree_low_cst (low_bound
, 0);
939 hindex
*= tree_low_cst (unit_size
, 1);
940 hindex
*= BITS_PER_UNIT
;
941 bit_offset
+= hindex
;
943 /* An array ref with a constant index up in the structure
944 hierarchy will constrain the size of any variable array ref
945 lower in the access hierarchy. */
946 seen_variable_array_ref
= false;
950 tree asize
= TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp
, 0)));
951 /* We need to adjust maxsize to the whole array bitsize.
952 But we can subtract any constant offset seen sofar,
953 because that would get us outside of the array otherwise. */
954 if (maxsize
!= -1 && asize
&& host_integerp (asize
, 1))
955 maxsize
= TREE_INT_CST_LOW (asize
) - bit_offset
;
959 /* Remember that we have seen an array ref with a variable
961 seen_variable_array_ref
= true;
970 bit_offset
+= bitsize
;
973 case VIEW_CONVERT_EXPR
:
974 /* ??? We probably should give up here and bail out. */
981 exp
= TREE_OPERAND (exp
, 0);
985 /* We need to deal with variable arrays ending structures such as
986 struct { int length; int a[1]; } x; x.a[d]
987 struct { struct { int a; int b; } a[1]; } x; x.a[d].a
988 struct { struct { int a[1]; } a[1]; } x; x.a[0][d], x.a[d][0]
989 where we do not know maxsize for variable index accesses to
990 the array. The simplest way to conservatively deal with this
991 is to punt in the case that offset + maxsize reaches the
992 base type boundary. */
993 if (seen_variable_array_ref
995 && host_integerp (TYPE_SIZE (TREE_TYPE (exp
)), 1)
996 && bit_offset
+ maxsize
997 == (signed)TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp
))))
1000 /* ??? Due to negative offsets in ARRAY_REF we can end up with
1001 negative bit_offset here. We might want to store a zero offset
1003 *poffset
= bit_offset
;
1005 *pmax_size
= maxsize
;
1010 /* Returns true if STMT references an SSA_NAME that has
1011 SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false. */
1014 stmt_references_abnormal_ssa_name (tree stmt
)
1017 use_operand_p use_p
;
1019 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, oi
, SSA_OP_USE
)
1021 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p
)))
1028 /* Return true, if the two memory references REF1 and REF2 may alias. */
1031 refs_may_alias_p (tree ref1
, tree ref2
)
1034 HOST_WIDE_INT offset1
= 0, offset2
= 0;
1035 HOST_WIDE_INT size1
= -1, size2
= -1;
1036 HOST_WIDE_INT max_size1
= -1, max_size2
= -1;
1037 bool strict_aliasing_applies
;
1039 gcc_assert ((SSA_VAR_P (ref1
)
1040 || handled_component_p (ref1
)
1041 || INDIRECT_REF_P (ref1
)
1042 || TREE_CODE (ref1
) == TARGET_MEM_REF
)
1043 && (SSA_VAR_P (ref2
)
1044 || handled_component_p (ref2
)
1045 || INDIRECT_REF_P (ref2
)
1046 || TREE_CODE (ref2
) == TARGET_MEM_REF
));
1048 /* Defer to TBAA if possible. */
1049 if (flag_strict_aliasing
1050 && !alias_sets_conflict_p (get_alias_set (ref1
), get_alias_set (ref2
)))
1053 /* Decompose the references into their base objects and the access. */
1055 if (handled_component_p (ref1
))
1056 base1
= get_ref_base_and_extent (ref1
, &offset1
, &size1
, &max_size1
);
1058 if (handled_component_p (ref2
))
1059 base2
= get_ref_base_and_extent (ref2
, &offset2
, &size2
, &max_size2
);
1061 /* If both references are based on different variables, they cannot alias.
1062 If both references are based on the same variable, they cannot alias if
1063 if the accesses do not overlap. */
1064 if (SSA_VAR_P (base1
)
1065 && SSA_VAR_P (base2
))
1067 if (!operand_equal_p (base1
, base2
, 0))
1069 return ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
);
1072 /* If one base is a ref-all pointer weird things are allowed. */
1073 strict_aliasing_applies
= (flag_strict_aliasing
1074 && (!INDIRECT_REF_P (base1
)
1075 || get_alias_set (base1
) != 0)
1076 && (!INDIRECT_REF_P (base2
)
1077 || get_alias_set (base2
) != 0));
1079 /* If strict aliasing applies the only way to access a scalar variable
1080 is through a pointer dereference or through a union (gcc extension). */
1081 if (strict_aliasing_applies
1082 && ((SSA_VAR_P (ref2
)
1083 && !AGGREGATE_TYPE_P (TREE_TYPE (ref2
))
1084 && !INDIRECT_REF_P (ref1
)
1085 && TREE_CODE (TREE_TYPE (base1
)) != UNION_TYPE
)
1086 || (SSA_VAR_P (ref1
)
1087 && !AGGREGATE_TYPE_P (TREE_TYPE (ref1
))
1088 && !INDIRECT_REF_P (ref2
)
1089 && TREE_CODE (TREE_TYPE (base2
)) != UNION_TYPE
)))
1092 /* If both references are through the same type, or if strict aliasing
1093 doesn't apply they are through two same pointers, they do not alias
1094 if the accesses do not overlap. */
1095 if ((strict_aliasing_applies
1096 && (TYPE_MAIN_VARIANT (TREE_TYPE (base1
))
1097 == TYPE_MAIN_VARIANT (TREE_TYPE (base2
))))
1098 || (TREE_CODE (base1
) == INDIRECT_REF
1099 && TREE_CODE (base2
) == INDIRECT_REF
1100 && operand_equal_p (TREE_OPERAND (base1
, 0),
1101 TREE_OPERAND (base2
, 0), 0)))
1102 return ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
);
1104 /* If both are component references through pointers try to find a
1105 common base and apply offset based disambiguation. This handles
1107 struct A { int i; int j; } *q;
1108 struct B { struct A a; int k; } *p;
1109 disambiguating q->i and p->a.j. */
1110 if (strict_aliasing_applies
1111 && (TREE_CODE (base1
) == INDIRECT_REF
1112 || TREE_CODE (base2
) == INDIRECT_REF
)
1113 && handled_component_p (ref1
)
1114 && handled_component_p (ref2
))
1117 /* Now search for the type of base1 in the access path of ref2. This
1118 would be a common base for doing offset based disambiguation on. */
1120 while (handled_component_p (*refp
)
1121 /* Note that the following is only conservative if there are
1122 never copies of types appearing as sub-structures. */
1123 && (TYPE_MAIN_VARIANT (TREE_TYPE (*refp
))
1124 != TYPE_MAIN_VARIANT (TREE_TYPE (base1
))))
1125 refp
= &TREE_OPERAND (*refp
, 0);
1126 if (TYPE_MAIN_VARIANT (TREE_TYPE (*refp
))
1127 == TYPE_MAIN_VARIANT (TREE_TYPE (base1
)))
1129 HOST_WIDE_INT offadj
, sztmp
, msztmp
;
1130 get_ref_base_and_extent (*refp
, &offadj
, &sztmp
, &msztmp
);
1132 return ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
);
1134 /* The other way around. */
1136 while (handled_component_p (*refp
)
1137 && (TYPE_MAIN_VARIANT (TREE_TYPE (*refp
))
1138 != TYPE_MAIN_VARIANT (TREE_TYPE (base2
))))
1139 refp
= &TREE_OPERAND (*refp
, 0);
1140 if (TYPE_MAIN_VARIANT (TREE_TYPE (*refp
))
1141 == TYPE_MAIN_VARIANT (TREE_TYPE (base2
)))
1143 HOST_WIDE_INT offadj
, sztmp
, msztmp
;
1144 get_ref_base_and_extent (*refp
, &offadj
, &sztmp
, &msztmp
);
1146 return ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
);
1148 /* If we can be sure to catch all equivalent types in the search
1149 for the common base then we could return false here. In that
1150 case we would be able to disambiguate q->i and p->k. */
1156 /* Given a stmt STMT that references memory, return the single stmt
1157 that is reached by following the VUSE -> VDEF link. Returns
1158 NULL_TREE, if there is no single stmt that defines all VUSEs of
1160 Note that for a stmt with a single virtual operand this may return
1161 a PHI node as well. Note that if all VUSEs are default definitions
1162 this function will return an empty statement. */
1165 get_single_def_stmt (tree stmt
)
1167 tree def_stmt
= NULL_TREE
;
1171 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
1173 tree tmp
= SSA_NAME_DEF_STMT (use
);
1175 /* ??? This is too simplistic for multiple virtual operands
1176 reaching different PHI nodes of the same basic blocks or for
1177 reaching all default definitions. */
1180 && !(IS_EMPTY_STMT (def_stmt
)
1181 && IS_EMPTY_STMT (tmp
)))
1190 /* Given a PHI node of virtual operands, tries to eliminate cyclic
1191 reached definitions if they do not alias REF and returns the
1192 defining statement of the single virtual operand that flows in
1193 from a non-backedge. Returns NULL_TREE if such statement within
1194 the above conditions cannot be found. */
1197 get_single_def_stmt_from_phi (tree ref
, tree phi
)
1199 tree def_arg
= NULL_TREE
;
1202 /* Find the single PHI argument that is not flowing in from a
1203 back edge and verify that the loop-carried definitions do
1204 not alias the reference we look for. */
1205 for (i
= 0; i
< PHI_NUM_ARGS (phi
); ++i
)
1207 tree arg
= PHI_ARG_DEF (phi
, i
);
1210 if (!(PHI_ARG_EDGE (phi
, i
)->flags
& EDGE_DFS_BACK
))
1212 /* Multiple non-back edges? Do not try to handle this. */
1219 /* Follow the definitions back to the original PHI node. Bail
1220 out once a definition is found that may alias REF. */
1221 def_stmt
= SSA_NAME_DEF_STMT (arg
);
1224 if (TREE_CODE (def_stmt
) != GIMPLE_MODIFY_STMT
1225 || refs_may_alias_p (ref
, GIMPLE_STMT_OPERAND (def_stmt
, 0)))
1227 /* ??? This will only work, reaching the PHI node again if
1228 there is a single virtual operand on def_stmt. */
1229 def_stmt
= get_single_def_stmt (def_stmt
);
1233 while (def_stmt
!= phi
);
1236 return SSA_NAME_DEF_STMT (def_arg
);
1239 /* Return the single reference statement defining all virtual uses
1240 on STMT or NULL_TREE, if there are multiple defining statements.
1241 Take into account only definitions that alias REF if following
1242 back-edges when looking through a loop PHI node. */
1245 get_single_def_stmt_with_phi (tree ref
, tree stmt
)
1247 switch (NUM_SSA_OPERANDS (stmt
, SSA_OP_VIRTUAL_USES
))
1254 tree def_stmt
= SSA_NAME_DEF_STMT (SINGLE_SSA_TREE_OPERAND
1255 (stmt
, SSA_OP_VIRTUAL_USES
));
1256 /* We can handle lookups over PHI nodes only for a single
1258 if (TREE_CODE (def_stmt
) == PHI_NODE
)
1259 return get_single_def_stmt_from_phi (ref
, def_stmt
);
1264 return get_single_def_stmt (stmt
);