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
)
145 struct static_var_ann_d
*sann
= NULL
;
148 gcc_assert (DECL_P (t
));
149 gcc_assert (!t
->base
.ann
|| t
->base
.ann
->common
.type
== VAR_ANN
);
151 if (!MTAG_P (t
) && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
153 sann
= GGC_CNEW (struct static_var_ann_d
);
157 ann
= GGC_CNEW (struct var_ann_d
);
159 ann
->common
.type
= VAR_ANN
;
161 if (!MTAG_P (t
) && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
164 sann
->uid
= DECL_UID (t
);
165 slot
= htab_find_slot_with_hash (gimple_var_anns (cfun
),
166 t
, DECL_UID (t
), INSERT
);
171 t
->base
.ann
= (tree_ann_t
) ann
;
176 /* Create a new annotation for a FUNCTION_DECL node T. */
179 create_function_ann (tree t
)
184 gcc_assert (TREE_CODE (t
) == FUNCTION_DECL
);
185 gcc_assert (!t
->base
.ann
|| t
->base
.ann
->common
.type
== FUNCTION_ANN
);
187 ann
= ggc_alloc (sizeof (*ann
));
188 memset ((void *) ann
, 0, sizeof (*ann
));
190 ann
->common
.type
= FUNCTION_ANN
;
192 t
->base
.ann
= (tree_ann_t
) ann
;
197 /* Create a new annotation for a statement node T. */
200 create_stmt_ann (tree t
)
204 gcc_assert (is_gimple_stmt (t
));
205 gcc_assert (!t
->base
.ann
|| t
->base
.ann
->common
.type
== STMT_ANN
);
207 ann
= GGC_CNEW (struct stmt_ann_d
);
209 ann
->common
.type
= STMT_ANN
;
211 /* Since we just created the annotation, mark the statement modified. */
212 ann
->modified
= true;
214 ann
->uid
= inc_gimple_stmt_max_uid (cfun
);
215 t
->base
.ann
= (tree_ann_t
) ann
;
220 /* Renumber all of the gimple stmt uids. */
223 renumber_gimple_stmt_uids (void)
227 set_gimple_stmt_max_uid (cfun
, 0);
230 block_stmt_iterator bsi
;
231 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
233 tree stmt
= bsi_stmt (bsi
);
234 /* If the stmt has an annotation, then overwrite it, if not,
235 the process of getting it will set the number
237 if (has_stmt_ann (stmt
))
238 set_gimple_stmt_uid (stmt
, inc_gimple_stmt_max_uid (cfun
));
245 /* Create a new annotation for a tree T. */
248 create_tree_common_ann (tree t
)
250 tree_ann_common_t ann
;
253 gcc_assert (!t
->base
.ann
|| t
->base
.ann
->common
.type
== TREE_ANN_COMMON
);
255 ann
= GGC_CNEW (struct tree_ann_common_d
);
257 ann
->type
= TREE_ANN_COMMON
;
258 t
->base
.ann
= (tree_ann_t
) ann
;
263 /* Build a temporary. Make sure and register it to be renamed. */
266 make_rename_temp (tree type
, const char *prefix
)
268 tree t
= create_tmp_var (type
, prefix
);
270 if (TREE_CODE (TREE_TYPE (t
)) == COMPLEX_TYPE
271 || TREE_CODE (TREE_TYPE (t
)) == VECTOR_TYPE
)
272 DECL_GIMPLE_REG_P (t
) = 1;
274 if (gimple_referenced_vars (cfun
))
276 add_referenced_var (t
);
277 mark_sym_for_renaming (t
);
285 /*---------------------------------------------------------------------------
287 ---------------------------------------------------------------------------*/
288 /* Dump the list of all the referenced variables in the current function to
292 dump_referenced_vars (FILE *file
)
295 referenced_var_iterator rvi
;
297 fprintf (file
, "\nReferenced variables in %s: %u\n\n",
298 get_name (current_function_decl
), (unsigned) num_referenced_vars
);
300 FOR_EACH_REFERENCED_VAR (var
, rvi
)
302 fprintf (file
, "Variable: ");
303 dump_variable (file
, var
);
304 fprintf (file
, "\n");
309 /* Dump the list of all the referenced variables to stderr. */
312 debug_referenced_vars (void)
314 dump_referenced_vars (stderr
);
318 /* Dump variable VAR and its may-aliases to FILE. */
321 dump_variable (FILE *file
, tree var
)
325 if (TREE_CODE (var
) == SSA_NAME
)
327 if (POINTER_TYPE_P (TREE_TYPE (var
)))
328 dump_points_to_info_for (file
, var
);
329 var
= SSA_NAME_VAR (var
);
332 if (var
== NULL_TREE
)
334 fprintf (file
, "<nil>");
338 print_generic_expr (file
, var
, dump_flags
);
342 fprintf (file
, ", UID D.%u", (unsigned) DECL_UID (var
));
344 fprintf (file
, ", ");
345 print_generic_expr (file
, TREE_TYPE (var
), dump_flags
);
347 if (ann
&& ann
->symbol_mem_tag
)
349 fprintf (file
, ", symbol memory tag: ");
350 print_generic_expr (file
, ann
->symbol_mem_tag
, dump_flags
);
353 if (TREE_ADDRESSABLE (var
))
354 fprintf (file
, ", is addressable");
356 if (is_global_var (var
))
357 fprintf (file
, ", is global");
359 if (TREE_THIS_VOLATILE (var
))
360 fprintf (file
, ", is volatile");
362 dump_mem_sym_stats_for_var (file
, var
);
364 if (is_call_clobbered (var
))
367 var_ann_t va
= var_ann (var
);
368 unsigned int escape_mask
= va
->escape_mask
;
370 fprintf (file
, ", call clobbered");
371 fprintf (file
, " (");
372 if (escape_mask
& ESCAPE_STORED_IN_GLOBAL
)
373 { fprintf (file
, "%sstored in global", s
); s
= ", "; }
374 if (escape_mask
& ESCAPE_TO_ASM
)
375 { fprintf (file
, "%sgoes through ASM", s
); s
= ", "; }
376 if (escape_mask
& ESCAPE_TO_CALL
)
377 { fprintf (file
, "%spassed to call", s
); s
= ", "; }
378 if (escape_mask
& ESCAPE_BAD_CAST
)
379 { fprintf (file
, "%sbad cast", s
); s
= ", "; }
380 if (escape_mask
& ESCAPE_TO_RETURN
)
381 { fprintf (file
, "%sreturned from func", s
); s
= ", "; }
382 if (escape_mask
& ESCAPE_TO_PURE_CONST
)
383 { fprintf (file
, "%spassed to pure/const", s
); s
= ", "; }
384 if (escape_mask
& ESCAPE_IS_GLOBAL
)
385 { fprintf (file
, "%sis global var", s
); s
= ", "; }
386 if (escape_mask
& ESCAPE_IS_PARM
)
387 { fprintf (file
, "%sis incoming pointer", s
); s
= ", "; }
388 if (escape_mask
& ESCAPE_UNKNOWN
)
389 { fprintf (file
, "%sunknown escape", s
); s
= ", "; }
393 if (ann
->noalias_state
== NO_ALIAS
)
394 fprintf (file
, ", NO_ALIAS (does not alias other NO_ALIAS symbols)");
395 else if (ann
->noalias_state
== NO_ALIAS_GLOBAL
)
396 fprintf (file
, ", NO_ALIAS_GLOBAL (does not alias other NO_ALIAS symbols"
397 " and global vars)");
398 else if (ann
->noalias_state
== NO_ALIAS_ANYTHING
)
399 fprintf (file
, ", NO_ALIAS_ANYTHING (does not alias any other symbols)");
401 if (gimple_default_def (cfun
, var
))
403 fprintf (file
, ", default def: ");
404 print_generic_expr (file
, gimple_default_def (cfun
, var
), dump_flags
);
407 if (MTAG_P (var
) && may_aliases (var
))
409 fprintf (file
, ", may aliases: ");
410 dump_may_aliases_for (file
, var
);
413 if (!is_gimple_reg (var
))
415 if (memory_partition (var
))
417 fprintf (file
, ", belongs to partition: ");
418 print_generic_expr (file
, memory_partition (var
), dump_flags
);
421 if (TREE_CODE (var
) == MEMORY_PARTITION_TAG
)
423 fprintf (file
, ", partition symbols: ");
424 dump_decl_set (file
, MPT_SYMBOLS (var
));
428 fprintf (file
, "\n");
432 /* Dump variable VAR and its may-aliases to stderr. */
435 debug_variable (tree var
)
437 dump_variable (stderr
, var
);
441 /* Dump various DFA statistics to FILE. */
444 dump_dfa_stats (FILE *file
)
446 struct dfa_stats_d dfa_stats
;
448 unsigned long size
, total
= 0;
449 const char * const fmt_str
= "%-30s%-13s%12s\n";
450 const char * const fmt_str_1
= "%-30s%13lu%11lu%c\n";
451 const char * const fmt_str_3
= "%-43s%11lu%c\n";
453 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
455 collect_dfa_stats (&dfa_stats
);
457 fprintf (file
, "\nDFA Statistics for %s\n\n", funcname
);
459 fprintf (file
, "---------------------------------------------------------\n");
460 fprintf (file
, fmt_str
, "", " Number of ", "Memory");
461 fprintf (file
, fmt_str
, "", " instances ", "used ");
462 fprintf (file
, "---------------------------------------------------------\n");
464 size
= num_referenced_vars
* sizeof (tree
);
466 fprintf (file
, fmt_str_1
, "Referenced variables", (unsigned long)num_referenced_vars
,
467 SCALE (size
), LABEL (size
));
469 size
= dfa_stats
.num_stmt_anns
* sizeof (struct stmt_ann_d
);
471 fprintf (file
, fmt_str_1
, "Statements annotated", dfa_stats
.num_stmt_anns
,
472 SCALE (size
), LABEL (size
));
474 size
= dfa_stats
.num_var_anns
* sizeof (struct var_ann_d
);
476 fprintf (file
, fmt_str_1
, "Variables annotated", dfa_stats
.num_var_anns
,
477 SCALE (size
), LABEL (size
));
479 size
= dfa_stats
.num_uses
* sizeof (tree
*);
481 fprintf (file
, fmt_str_1
, "USE operands", dfa_stats
.num_uses
,
482 SCALE (size
), LABEL (size
));
484 size
= dfa_stats
.num_defs
* sizeof (tree
*);
486 fprintf (file
, fmt_str_1
, "DEF operands", dfa_stats
.num_defs
,
487 SCALE (size
), LABEL (size
));
489 size
= dfa_stats
.num_vuses
* sizeof (tree
*);
491 fprintf (file
, fmt_str_1
, "VUSE operands", dfa_stats
.num_vuses
,
492 SCALE (size
), LABEL (size
));
494 size
= dfa_stats
.num_vdefs
* sizeof (tree
*);
496 fprintf (file
, fmt_str_1
, "VDEF operands", dfa_stats
.num_vdefs
,
497 SCALE (size
), LABEL (size
));
499 size
= dfa_stats
.num_phis
* sizeof (struct tree_phi_node
);
501 fprintf (file
, fmt_str_1
, "PHI nodes", dfa_stats
.num_phis
,
502 SCALE (size
), LABEL (size
));
504 size
= dfa_stats
.num_phi_args
* sizeof (struct phi_arg_d
);
506 fprintf (file
, fmt_str_1
, "PHI arguments", dfa_stats
.num_phi_args
,
507 SCALE (size
), LABEL (size
));
509 fprintf (file
, "---------------------------------------------------------\n");
510 fprintf (file
, fmt_str_3
, "Total memory used by DFA/SSA data", SCALE (total
),
512 fprintf (file
, "---------------------------------------------------------\n");
513 fprintf (file
, "\n");
515 if (dfa_stats
.num_phis
)
516 fprintf (file
, "Average number of arguments per PHI node: %.1f (max: %d)\n",
517 (float) dfa_stats
.num_phi_args
/ (float) dfa_stats
.num_phis
,
518 dfa_stats
.max_num_phi_args
);
520 fprintf (file
, "\n");
524 /* Dump DFA statistics on stderr. */
527 debug_dfa_stats (void)
529 dump_dfa_stats (stderr
);
533 /* Collect DFA statistics and store them in the structure pointed to by
537 collect_dfa_stats (struct dfa_stats_d
*dfa_stats_p
)
539 struct pointer_set_t
*pset
;
541 block_stmt_iterator i
;
543 gcc_assert (dfa_stats_p
);
545 memset ((void *)dfa_stats_p
, 0, sizeof (struct dfa_stats_d
));
547 /* Walk all the trees in the function counting references. Start at
548 basic block NUM_FIXED_BLOCKS, but don't stop at block boundaries. */
549 pset
= pointer_set_create ();
551 for (i
= bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS
));
552 !bsi_end_p (i
); bsi_next (&i
))
553 walk_tree (bsi_stmt_ptr (i
), collect_dfa_stats_r
, (void *) dfa_stats_p
,
556 pointer_set_destroy (pset
);
561 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
563 dfa_stats_p
->num_phis
++;
564 dfa_stats_p
->num_phi_args
+= PHI_NUM_ARGS (phi
);
565 if (PHI_NUM_ARGS (phi
) > dfa_stats_p
->max_num_phi_args
)
566 dfa_stats_p
->max_num_phi_args
= PHI_NUM_ARGS (phi
);
572 /* Callback for walk_tree to collect DFA statistics for a tree and its
576 collect_dfa_stats_r (tree
*tp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
580 struct dfa_stats_d
*dfa_stats_p
= (struct dfa_stats_d
*)data
;
584 switch (ann_type (t
->base
.ann
))
588 dfa_stats_p
->num_stmt_anns
++;
589 dfa_stats_p
->num_defs
+= NUM_SSA_OPERANDS (t
, SSA_OP_DEF
);
590 dfa_stats_p
->num_uses
+= NUM_SSA_OPERANDS (t
, SSA_OP_USE
);
591 dfa_stats_p
->num_vdefs
+= NUM_SSA_OPERANDS (t
, SSA_OP_VDEF
);
592 dfa_stats_p
->num_vuses
+= NUM_SSA_OPERANDS (t
, SSA_OP_VUSE
);
597 dfa_stats_p
->num_var_anns
++;
609 /*---------------------------------------------------------------------------
610 Miscellaneous helpers
611 ---------------------------------------------------------------------------*/
612 /* Callback for walk_tree. Used to collect variables referenced in
616 find_vars_r (tree
*tp
, int *walk_subtrees
, void *data ATTRIBUTE_UNUSED
)
618 /* If we are reading the lto info back in, we need to rescan the
620 if (TREE_CODE (*tp
) == SSA_NAME
)
621 add_referenced_var (SSA_NAME_VAR (*tp
));
623 /* If T is a regular variable that the optimizers are interested
624 in, add it to the list of variables. */
625 else if (SSA_VAR_P (*tp
))
626 add_referenced_var (*tp
);
628 /* Type, _DECL and constant nodes have no interesting children.
630 else if (IS_TYPE_OR_DECL_P (*tp
) || CONSTANT_CLASS_P (*tp
))
636 /* Lookup UID in the referenced_vars hashtable and return the associated
640 referenced_var_lookup (unsigned int uid
)
643 struct tree_decl_minimal in
;
645 h
= (tree
) htab_find_with_hash (gimple_referenced_vars (cfun
), &in
, uid
);
646 gcc_assert (h
|| uid
== 0);
650 /* Check if TO is in the referenced_vars hash table and insert it if not.
651 Return true if it required insertion. */
654 referenced_var_check_and_insert (tree to
)
657 struct tree_decl_minimal in
;
658 unsigned int uid
= DECL_UID (to
);
661 h
= (tree
) htab_find_with_hash (gimple_referenced_vars (cfun
), &in
, uid
);
664 /* DECL_UID has already been entered in the table. Verify that it is
665 the same entry as TO. See PR 27793. */
666 gcc_assert (h
== to
);
670 loc
= (tree
*) htab_find_slot_with_hash (gimple_referenced_vars (cfun
),
676 /* Lookup VAR UID in the default_defs hashtable and return the associated
680 gimple_default_def (struct function
*fn
, tree var
)
682 struct tree_decl_minimal ind
;
683 struct tree_ssa_name in
;
684 gcc_assert (SSA_VAR_P (var
));
686 ind
.uid
= DECL_UID (var
);
687 return (tree
) htab_find_with_hash (DEFAULT_DEFS (fn
), &in
, DECL_UID (var
));
690 /* Insert the pair VAR's UID, DEF into the default_defs hashtable. */
693 set_default_def (tree var
, tree def
)
695 struct tree_decl_minimal ind
;
696 struct tree_ssa_name in
;
699 gcc_assert (SSA_VAR_P (var
));
701 ind
.uid
= DECL_UID (var
);
704 loc
= htab_find_slot_with_hash (DEFAULT_DEFS (cfun
), &in
,
705 DECL_UID (var
), INSERT
);
707 htab_remove_elt (DEFAULT_DEFS (cfun
), *loc
);
710 gcc_assert (TREE_CODE (def
) == SSA_NAME
&& SSA_NAME_VAR (def
) == var
);
711 loc
= htab_find_slot_with_hash (DEFAULT_DEFS (cfun
), &in
,
712 DECL_UID (var
), INSERT
);
714 /* Default definition might be changed by tail call optimization. */
716 SSA_NAME_IS_DEFAULT_DEF (*(tree
*) loc
) = false;
719 /* Mark DEF as the default definition for VAR. */
720 SSA_NAME_IS_DEFAULT_DEF (def
) = true;
723 /* Add VAR to the list of referenced variables if it isn't already there. */
726 add_referenced_var (tree var
)
730 v_ann
= get_var_ann (var
);
731 gcc_assert (DECL_P (var
));
733 /* Insert VAR into the referenced_vars has table if it isn't present. */
734 if (referenced_var_check_and_insert (var
))
736 /* This is the first time we found this variable, annotate it with
737 attributes that are intrinsic to the variable. */
739 /* Tag's don't have DECL_INITIAL. */
743 /* Scan DECL_INITIAL for pointer variables as they may contain
744 address arithmetic referencing the address of other
746 Even non-constant intializers need to be walked, because
747 IPA passes might prove that their are invariant later on. */
748 if (DECL_INITIAL (var
)
749 /* Initializers of external variables are not useful to the
751 && !DECL_EXTERNAL (var
))
752 walk_tree (&DECL_INITIAL (var
), find_vars_r
, NULL
, 0);
756 /* Remove VAR from the list. */
759 remove_referenced_var (tree var
)
762 struct tree_decl_minimal in
;
764 unsigned int uid
= DECL_UID (var
);
766 clear_call_clobbered (var
);
767 if ((v_ann
= var_ann (var
)))
769 var
->base
.ann
= NULL
;
770 gcc_assert (DECL_P (var
));
772 loc
= htab_find_slot_with_hash (gimple_referenced_vars (cfun
), &in
, uid
,
774 htab_clear_slot (gimple_referenced_vars (cfun
), loc
);
778 /* Return the virtual variable associated to the non-scalar variable VAR. */
781 get_virtual_var (tree var
)
785 if (TREE_CODE (var
) == SSA_NAME
)
786 var
= SSA_NAME_VAR (var
);
788 while (TREE_CODE (var
) == REALPART_EXPR
|| TREE_CODE (var
) == IMAGPART_EXPR
789 || handled_component_p (var
))
790 var
= TREE_OPERAND (var
, 0);
792 /* Treating GIMPLE registers as virtual variables makes no sense.
793 Also complain if we couldn't extract a _DECL out of the original
795 gcc_assert (SSA_VAR_P (var
));
796 gcc_assert (!is_gimple_reg (var
));
801 /* Mark all the naked symbols in STMT for SSA renaming.
803 NOTE: This function should only be used for brand new statements.
804 If the caller is modifying an existing statement, it should use the
805 combination push_stmt_changes/pop_stmt_changes. */
808 mark_symbols_for_renaming (tree stmt
)
815 /* Mark all the operands for renaming. */
816 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_ALL_OPERANDS
)
818 mark_sym_for_renaming (op
);
822 /* Find all variables within the gimplified statement that were not previously
823 visible to the function and add them to the referenced variables list. */
826 find_new_referenced_vars_1 (tree
*tp
, int *walk_subtrees
,
827 void *data ATTRIBUTE_UNUSED
)
831 if (TREE_CODE (t
) == VAR_DECL
&& !var_ann (t
))
833 add_referenced_var (t
);
834 mark_sym_for_renaming (t
);
837 if (IS_TYPE_OR_DECL_P (t
))
844 find_new_referenced_vars (tree
*stmt_p
)
846 walk_tree (stmt_p
, find_new_referenced_vars_1
, NULL
, NULL
);
850 /* If EXP is a handled component reference for a structure, return the
851 base variable. The access range is delimited by bit positions *POFFSET and
852 *POFFSET + *PMAX_SIZE. The access size is *PSIZE bits. If either
853 *PSIZE or *PMAX_SIZE is -1, they could not be determined. If *PSIZE
854 and *PMAX_SIZE are equal, the access is non-variable. */
857 get_ref_base_and_extent (tree exp
, HOST_WIDE_INT
*poffset
,
858 HOST_WIDE_INT
*psize
,
859 HOST_WIDE_INT
*pmax_size
)
861 HOST_WIDE_INT bitsize
= -1;
862 HOST_WIDE_INT maxsize
= -1;
863 tree size_tree
= NULL_TREE
;
864 HOST_WIDE_INT bit_offset
= 0;
865 bool seen_variable_array_ref
= false;
867 gcc_assert (!SSA_VAR_P (exp
));
869 /* First get the final access size from just the outermost expression. */
870 if (TREE_CODE (exp
) == COMPONENT_REF
)
871 size_tree
= DECL_SIZE (TREE_OPERAND (exp
, 1));
872 else if (TREE_CODE (exp
) == BIT_FIELD_REF
)
873 size_tree
= TREE_OPERAND (exp
, 1);
876 enum machine_mode mode
= TYPE_MODE (TREE_TYPE (exp
));
878 size_tree
= TYPE_SIZE (TREE_TYPE (exp
));
880 bitsize
= GET_MODE_BITSIZE (mode
);
882 if (size_tree
!= NULL_TREE
)
884 if (! host_integerp (size_tree
, 1))
887 bitsize
= TREE_INT_CST_LOW (size_tree
);
890 /* Initially, maxsize is the same as the accessed element size.
891 In the following it will only grow (or become -1). */
894 /* Compute cumulative bit-offset for nested component-refs and array-refs,
895 and find the ultimate containing object. */
898 switch (TREE_CODE (exp
))
901 bit_offset
+= tree_low_cst (TREE_OPERAND (exp
, 2), 0);
906 tree field
= TREE_OPERAND (exp
, 1);
907 tree this_offset
= component_ref_field_offset (exp
);
909 if (this_offset
&& TREE_CODE (this_offset
) == INTEGER_CST
)
911 HOST_WIDE_INT hthis_offset
= tree_low_cst (this_offset
, 0);
913 hthis_offset
*= BITS_PER_UNIT
;
914 bit_offset
+= hthis_offset
;
915 bit_offset
+= tree_low_cst (DECL_FIELD_BIT_OFFSET (field
), 0);
919 tree csize
= TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp
, 0)));
920 /* We need to adjust maxsize to the whole structure bitsize.
921 But we can subtract any constant offset seen sofar,
922 because that would get us out of the structure otherwise. */
923 if (maxsize
!= -1 && csize
&& host_integerp (csize
, 1))
924 maxsize
= TREE_INT_CST_LOW (csize
) - bit_offset
;
932 case ARRAY_RANGE_REF
:
934 tree index
= TREE_OPERAND (exp
, 1);
935 tree low_bound
= array_ref_low_bound (exp
);
936 tree unit_size
= array_ref_element_size (exp
);
938 /* If the resulting bit-offset is constant, track it. */
939 if (host_integerp (index
, 0)
940 && host_integerp (low_bound
, 0)
941 && host_integerp (unit_size
, 1))
943 HOST_WIDE_INT hindex
= tree_low_cst (index
, 0);
945 hindex
-= tree_low_cst (low_bound
, 0);
946 hindex
*= tree_low_cst (unit_size
, 1);
947 hindex
*= BITS_PER_UNIT
;
948 bit_offset
+= hindex
;
950 /* An array ref with a constant index up in the structure
951 hierarchy will constrain the size of any variable array ref
952 lower in the access hierarchy. */
953 seen_variable_array_ref
= false;
957 tree asize
= TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp
, 0)));
958 /* We need to adjust maxsize to the whole array bitsize.
959 But we can subtract any constant offset seen sofar,
960 because that would get us outside of the array otherwise. */
961 if (maxsize
!= -1 && asize
&& host_integerp (asize
, 1))
962 maxsize
= TREE_INT_CST_LOW (asize
) - bit_offset
;
966 /* Remember that we have seen an array ref with a variable
968 seen_variable_array_ref
= true;
977 bit_offset
+= bitsize
;
980 case VIEW_CONVERT_EXPR
:
981 /* ??? We probably should give up here and bail out. */
988 exp
= TREE_OPERAND (exp
, 0);
992 /* We need to deal with variable arrays ending structures such as
993 struct { int length; int a[1]; } x; x.a[d]
994 struct { struct { int a; int b; } a[1]; } x; x.a[d].a
995 struct { struct { int a[1]; } a[1]; } x; x.a[0][d], x.a[d][0]
996 where we do not know maxsize for variable index accesses to
997 the array. The simplest way to conservatively deal with this
998 is to punt in the case that offset + maxsize reaches the
999 base type boundary. */
1000 if (seen_variable_array_ref
1002 && host_integerp (TYPE_SIZE (TREE_TYPE (exp
)), 1)
1003 && bit_offset
+ maxsize
1004 == (signed)TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp
))))
1007 /* ??? Due to negative offsets in ARRAY_REF we can end up with
1008 negative bit_offset here. We might want to store a zero offset
1010 *poffset
= bit_offset
;
1012 *pmax_size
= maxsize
;
1017 /* Returns true if STMT references an SSA_NAME that has
1018 SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false. */
1021 stmt_references_abnormal_ssa_name (tree stmt
)
1024 use_operand_p use_p
;
1026 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, oi
, SSA_OP_USE
)
1028 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p
)))
1035 /* Return true, if the two memory references REF1 and REF2 may alias. */
1038 refs_may_alias_p (tree ref1
, tree ref2
)
1041 HOST_WIDE_INT offset1
= 0, offset2
= 0;
1042 HOST_WIDE_INT size1
= -1, size2
= -1;
1043 HOST_WIDE_INT max_size1
= -1, max_size2
= -1;
1045 gcc_assert ((SSA_VAR_P (ref1
)
1046 || handled_component_p (ref1
)
1047 || INDIRECT_REF_P (ref1
)
1048 || TREE_CODE (ref1
) == TARGET_MEM_REF
)
1049 && (SSA_VAR_P (ref2
)
1050 || handled_component_p (ref2
)
1051 || INDIRECT_REF_P (ref2
)
1052 || TREE_CODE (ref2
) == TARGET_MEM_REF
));
1054 /* Defer to TBAA if possible. */
1055 if (flag_strict_aliasing
1056 && !alias_sets_conflict_p (get_alias_set (ref1
), get_alias_set (ref2
)))
1059 /* Decompose the references into their base objects and the access. */
1061 if (handled_component_p (ref1
))
1062 base1
= get_ref_base_and_extent (ref1
, &offset1
, &size1
, &max_size1
);
1064 if (handled_component_p (ref2
))
1065 base2
= get_ref_base_and_extent (ref2
, &offset2
, &size2
, &max_size2
);
1067 /* If both references are based on different variables, they cannot alias.
1068 If both references are based on the same variable, they cannot alias if
1069 if the accesses do not overlap. */
1070 if (SSA_VAR_P (base1
)
1071 && SSA_VAR_P (base2
)
1072 && (!operand_equal_p (base1
, base2
, 0)
1073 || !ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
)))
1076 /* If both references are through pointers and both pointers are equal
1077 then they do not alias if the accesses do not overlap. */
1078 if (TREE_CODE (base1
) == INDIRECT_REF
1079 && TREE_CODE (base2
) == INDIRECT_REF
1080 && operand_equal_p (TREE_OPERAND (base1
, 0),
1081 TREE_OPERAND (base2
, 0), 0)
1082 && !ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
))
1088 /* Given a stmt STMT that references memory, return the single stmt
1089 that is reached by following the VUSE -> VDEF link. Returns
1090 NULL_TREE, if there is no single stmt that defines all VUSEs of
1092 Note that for a stmt with a single virtual operand this may return
1093 a PHI node as well. Note that if all VUSEs are default definitions
1094 this function will return an empty statement. */
1097 get_single_def_stmt (tree stmt
)
1099 tree def_stmt
= NULL_TREE
;
1103 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
1105 tree tmp
= SSA_NAME_DEF_STMT (use
);
1107 /* ??? This is too simplistic for multiple virtual operands
1108 reaching different PHI nodes of the same basic blocks or for
1109 reaching all default definitions. */
1112 && !(IS_EMPTY_STMT (def_stmt
)
1113 && IS_EMPTY_STMT (tmp
)))
1122 /* Given a PHI node of virtual operands, tries to eliminate cyclic
1123 reached definitions if they do not alias REF and returns the
1124 defining statement of the single virtual operand that flows in
1125 from a non-backedge. Returns NULL_TREE if such statement within
1126 the above conditions cannot be found. */
1129 get_single_def_stmt_from_phi (tree ref
, tree phi
)
1131 tree def_arg
= NULL_TREE
;
1134 /* Find the single PHI argument that is not flowing in from a
1135 back edge and verify that the loop-carried definitions do
1136 not alias the reference we look for. */
1137 for (i
= 0; i
< PHI_NUM_ARGS (phi
); ++i
)
1139 tree arg
= PHI_ARG_DEF (phi
, i
);
1142 if (!(PHI_ARG_EDGE (phi
, i
)->flags
& EDGE_DFS_BACK
))
1144 /* Multiple non-back edges? Do not try to handle this. */
1151 /* Follow the definitions back to the original PHI node. Bail
1152 out once a definition is found that may alias REF. */
1153 def_stmt
= SSA_NAME_DEF_STMT (arg
);
1156 if (TREE_CODE (def_stmt
) != GIMPLE_MODIFY_STMT
1157 || refs_may_alias_p (ref
, GIMPLE_STMT_OPERAND (def_stmt
, 0)))
1159 /* ??? This will only work, reaching the PHI node again if
1160 there is a single virtual operand on def_stmt. */
1161 def_stmt
= get_single_def_stmt (def_stmt
);
1165 while (def_stmt
!= phi
);
1168 return SSA_NAME_DEF_STMT (def_arg
);
1171 /* Return the single reference statement defining all virtual uses
1172 on STMT or NULL_TREE, if there are multiple defining statements.
1173 Take into account only definitions that alias REF if following
1174 back-edges when looking through a loop PHI node. */
1177 get_single_def_stmt_with_phi (tree ref
, tree stmt
)
1179 switch (NUM_SSA_OPERANDS (stmt
, SSA_OP_VIRTUAL_USES
))
1186 tree def_stmt
= SSA_NAME_DEF_STMT (SINGLE_SSA_TREE_OPERAND
1187 (stmt
, SSA_OP_VIRTUAL_USES
));
1188 /* We can handle lookups over PHI nodes only for a single
1190 if (TREE_CODE (def_stmt
) == PHI_NODE
)
1191 return get_single_def_stmt_from_phi (ref
, def_stmt
);
1196 return get_single_def_stmt (stmt
);