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
;
90 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
92 tree
*stmt_p
= bsi_stmt_ptr (si
);
93 walk_tree (stmt_p
, find_vars_r
, NULL
, NULL
);
99 struct gimple_opt_pass pass_referenced_vars
=
105 find_referenced_vars
, /* execute */
108 0, /* static_pass_number */
109 TV_FIND_REFERENCED_VARS
, /* tv_id */
110 PROP_gimple_leh
| PROP_cfg
, /* properties_required */
111 PROP_referenced_vars
, /* properties_provided */
112 0, /* properties_destroyed */
113 0, /* todo_flags_start */
114 0 /* todo_flags_finish */
119 /*---------------------------------------------------------------------------
121 ---------------------------------------------------------------------------*/
122 /* Create a new annotation for a _DECL node T. */
125 create_var_ann (tree t
)
128 struct static_var_ann_d
*sann
= NULL
;
131 gcc_assert (DECL_P (t
));
132 gcc_assert (!t
->base
.ann
|| t
->base
.ann
->common
.type
== VAR_ANN
);
134 if (!MTAG_P (t
) && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
136 sann
= GGC_CNEW (struct static_var_ann_d
);
140 ann
= GGC_CNEW (struct var_ann_d
);
142 ann
->common
.type
= VAR_ANN
;
144 if (!MTAG_P (t
) && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
147 sann
->uid
= DECL_UID (t
);
148 slot
= htab_find_slot_with_hash (gimple_var_anns (cfun
),
149 t
, DECL_UID (t
), INSERT
);
154 t
->base
.ann
= (tree_ann_t
) ann
;
159 /* Create a new annotation for a FUNCTION_DECL node T. */
162 create_function_ann (tree t
)
167 gcc_assert (TREE_CODE (t
) == FUNCTION_DECL
);
168 gcc_assert (!t
->base
.ann
|| t
->base
.ann
->common
.type
== FUNCTION_ANN
);
170 ann
= ggc_alloc (sizeof (*ann
));
171 memset ((void *) ann
, 0, sizeof (*ann
));
173 ann
->common
.type
= FUNCTION_ANN
;
175 t
->base
.ann
= (tree_ann_t
) ann
;
180 /* Create a new annotation for a statement node T. */
183 create_stmt_ann (tree t
)
187 gcc_assert (is_gimple_stmt (t
));
188 gcc_assert (!t
->base
.ann
|| t
->base
.ann
->common
.type
== STMT_ANN
);
190 ann
= GGC_CNEW (struct stmt_ann_d
);
192 ann
->common
.type
= STMT_ANN
;
194 /* Since we just created the annotation, mark the statement modified. */
195 ann
->modified
= true;
197 t
->base
.ann
= (tree_ann_t
) ann
;
202 /* Create a new annotation for a tree T. */
205 create_tree_common_ann (tree t
)
207 tree_ann_common_t ann
;
210 gcc_assert (!t
->base
.ann
|| t
->base
.ann
->common
.type
== TREE_ANN_COMMON
);
212 ann
= GGC_CNEW (struct tree_ann_common_d
);
214 ann
->type
= TREE_ANN_COMMON
;
215 t
->base
.ann
= (tree_ann_t
) ann
;
220 /* Build a temporary. Make sure and register it to be renamed. */
223 make_rename_temp (tree type
, const char *prefix
)
225 tree t
= create_tmp_var (type
, prefix
);
227 if (TREE_CODE (TREE_TYPE (t
)) == COMPLEX_TYPE
228 || TREE_CODE (TREE_TYPE (t
)) == VECTOR_TYPE
)
229 DECL_GIMPLE_REG_P (t
) = 1;
231 if (gimple_referenced_vars (cfun
))
233 add_referenced_var (t
);
234 mark_sym_for_renaming (t
);
242 /*---------------------------------------------------------------------------
244 ---------------------------------------------------------------------------*/
245 /* Dump the list of all the referenced variables in the current function to
249 dump_referenced_vars (FILE *file
)
252 referenced_var_iterator rvi
;
254 fprintf (file
, "\nReferenced variables in %s: %u\n\n",
255 get_name (current_function_decl
), (unsigned) num_referenced_vars
);
257 FOR_EACH_REFERENCED_VAR (var
, rvi
)
259 fprintf (file
, "Variable: ");
260 dump_variable (file
, var
);
261 fprintf (file
, "\n");
266 /* Dump the list of all the referenced variables to stderr. */
269 debug_referenced_vars (void)
271 dump_referenced_vars (stderr
);
275 /* Dump variable VAR and its may-aliases to FILE. */
278 dump_variable (FILE *file
, tree var
)
282 if (TREE_CODE (var
) == SSA_NAME
)
284 if (POINTER_TYPE_P (TREE_TYPE (var
)))
285 dump_points_to_info_for (file
, var
);
286 var
= SSA_NAME_VAR (var
);
289 if (var
== NULL_TREE
)
291 fprintf (file
, "<nil>");
295 print_generic_expr (file
, var
, dump_flags
);
299 fprintf (file
, ", UID D.%u", (unsigned) DECL_UID (var
));
301 fprintf (file
, ", ");
302 print_generic_expr (file
, TREE_TYPE (var
), dump_flags
);
304 if (ann
&& ann
->symbol_mem_tag
)
306 fprintf (file
, ", symbol memory tag: ");
307 print_generic_expr (file
, ann
->symbol_mem_tag
, dump_flags
);
310 if (TREE_ADDRESSABLE (var
))
311 fprintf (file
, ", is addressable");
313 if (is_global_var (var
))
314 fprintf (file
, ", is global");
316 if (TREE_THIS_VOLATILE (var
))
317 fprintf (file
, ", is volatile");
319 dump_mem_sym_stats_for_var (file
, var
);
321 if (is_call_clobbered (var
))
324 var_ann_t va
= var_ann (var
);
325 unsigned int escape_mask
= va
->escape_mask
;
327 fprintf (file
, ", call clobbered");
328 fprintf (file
, " (");
329 if (escape_mask
& ESCAPE_STORED_IN_GLOBAL
)
330 { fprintf (file
, "%sstored in global", s
); s
= ", "; }
331 if (escape_mask
& ESCAPE_TO_ASM
)
332 { fprintf (file
, "%sgoes through ASM", s
); s
= ", "; }
333 if (escape_mask
& ESCAPE_TO_CALL
)
334 { fprintf (file
, "%spassed to call", s
); s
= ", "; }
335 if (escape_mask
& ESCAPE_BAD_CAST
)
336 { fprintf (file
, "%sbad cast", s
); s
= ", "; }
337 if (escape_mask
& ESCAPE_TO_RETURN
)
338 { fprintf (file
, "%sreturned from func", s
); s
= ", "; }
339 if (escape_mask
& ESCAPE_TO_PURE_CONST
)
340 { fprintf (file
, "%spassed to pure/const", s
); s
= ", "; }
341 if (escape_mask
& ESCAPE_IS_GLOBAL
)
342 { fprintf (file
, "%sis global var", s
); s
= ", "; }
343 if (escape_mask
& ESCAPE_IS_PARM
)
344 { fprintf (file
, "%sis incoming pointer", s
); s
= ", "; }
345 if (escape_mask
& ESCAPE_UNKNOWN
)
346 { fprintf (file
, "%sunknown escape", s
); s
= ", "; }
350 if (ann
->noalias_state
== NO_ALIAS
)
351 fprintf (file
, ", NO_ALIAS (does not alias other NO_ALIAS symbols)");
352 else if (ann
->noalias_state
== NO_ALIAS_GLOBAL
)
353 fprintf (file
, ", NO_ALIAS_GLOBAL (does not alias other NO_ALIAS symbols"
354 " and global vars)");
355 else if (ann
->noalias_state
== NO_ALIAS_ANYTHING
)
356 fprintf (file
, ", NO_ALIAS_ANYTHING (does not alias any other symbols)");
358 if (gimple_default_def (cfun
, var
))
360 fprintf (file
, ", default def: ");
361 print_generic_expr (file
, gimple_default_def (cfun
, var
), dump_flags
);
364 if (MTAG_P (var
) && may_aliases (var
))
366 fprintf (file
, ", may aliases: ");
367 dump_may_aliases_for (file
, var
);
370 if (!is_gimple_reg (var
))
372 if (memory_partition (var
))
374 fprintf (file
, ", belongs to partition: ");
375 print_generic_expr (file
, memory_partition (var
), dump_flags
);
378 if (TREE_CODE (var
) == MEMORY_PARTITION_TAG
)
380 fprintf (file
, ", partition symbols: ");
381 dump_decl_set (file
, MPT_SYMBOLS (var
));
385 fprintf (file
, "\n");
389 /* Dump variable VAR and its may-aliases to stderr. */
392 debug_variable (tree var
)
394 dump_variable (stderr
, var
);
398 /* Dump various DFA statistics to FILE. */
401 dump_dfa_stats (FILE *file
)
403 struct dfa_stats_d dfa_stats
;
405 unsigned long size
, total
= 0;
406 const char * const fmt_str
= "%-30s%-13s%12s\n";
407 const char * const fmt_str_1
= "%-30s%13lu%11lu%c\n";
408 const char * const fmt_str_3
= "%-43s%11lu%c\n";
410 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
412 collect_dfa_stats (&dfa_stats
);
414 fprintf (file
, "\nDFA Statistics for %s\n\n", funcname
);
416 fprintf (file
, "---------------------------------------------------------\n");
417 fprintf (file
, fmt_str
, "", " Number of ", "Memory");
418 fprintf (file
, fmt_str
, "", " instances ", "used ");
419 fprintf (file
, "---------------------------------------------------------\n");
421 size
= num_referenced_vars
* sizeof (tree
);
423 fprintf (file
, fmt_str_1
, "Referenced variables", (unsigned long)num_referenced_vars
,
424 SCALE (size
), LABEL (size
));
426 size
= dfa_stats
.num_stmt_anns
* sizeof (struct stmt_ann_d
);
428 fprintf (file
, fmt_str_1
, "Statements annotated", dfa_stats
.num_stmt_anns
,
429 SCALE (size
), LABEL (size
));
431 size
= dfa_stats
.num_var_anns
* sizeof (struct var_ann_d
);
433 fprintf (file
, fmt_str_1
, "Variables annotated", dfa_stats
.num_var_anns
,
434 SCALE (size
), LABEL (size
));
436 size
= dfa_stats
.num_uses
* sizeof (tree
*);
438 fprintf (file
, fmt_str_1
, "USE operands", dfa_stats
.num_uses
,
439 SCALE (size
), LABEL (size
));
441 size
= dfa_stats
.num_defs
* sizeof (tree
*);
443 fprintf (file
, fmt_str_1
, "DEF operands", dfa_stats
.num_defs
,
444 SCALE (size
), LABEL (size
));
446 size
= dfa_stats
.num_vuses
* sizeof (tree
*);
448 fprintf (file
, fmt_str_1
, "VUSE operands", dfa_stats
.num_vuses
,
449 SCALE (size
), LABEL (size
));
451 size
= dfa_stats
.num_vdefs
* sizeof (tree
*);
453 fprintf (file
, fmt_str_1
, "VDEF operands", dfa_stats
.num_vdefs
,
454 SCALE (size
), LABEL (size
));
456 size
= dfa_stats
.num_phis
* sizeof (struct tree_phi_node
);
458 fprintf (file
, fmt_str_1
, "PHI nodes", dfa_stats
.num_phis
,
459 SCALE (size
), LABEL (size
));
461 size
= dfa_stats
.num_phi_args
* sizeof (struct phi_arg_d
);
463 fprintf (file
, fmt_str_1
, "PHI arguments", dfa_stats
.num_phi_args
,
464 SCALE (size
), LABEL (size
));
466 fprintf (file
, "---------------------------------------------------------\n");
467 fprintf (file
, fmt_str_3
, "Total memory used by DFA/SSA data", SCALE (total
),
469 fprintf (file
, "---------------------------------------------------------\n");
470 fprintf (file
, "\n");
472 if (dfa_stats
.num_phis
)
473 fprintf (file
, "Average number of arguments per PHI node: %.1f (max: %d)\n",
474 (float) dfa_stats
.num_phi_args
/ (float) dfa_stats
.num_phis
,
475 dfa_stats
.max_num_phi_args
);
477 fprintf (file
, "\n");
481 /* Dump DFA statistics on stderr. */
484 debug_dfa_stats (void)
486 dump_dfa_stats (stderr
);
490 /* Collect DFA statistics and store them in the structure pointed to by
494 collect_dfa_stats (struct dfa_stats_d
*dfa_stats_p
)
496 struct pointer_set_t
*pset
;
498 block_stmt_iterator i
;
500 gcc_assert (dfa_stats_p
);
502 memset ((void *)dfa_stats_p
, 0, sizeof (struct dfa_stats_d
));
504 /* Walk all the trees in the function counting references. Start at
505 basic block NUM_FIXED_BLOCKS, but don't stop at block boundaries. */
506 pset
= pointer_set_create ();
508 for (i
= bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS
));
509 !bsi_end_p (i
); bsi_next (&i
))
510 walk_tree (bsi_stmt_ptr (i
), collect_dfa_stats_r
, (void *) dfa_stats_p
,
513 pointer_set_destroy (pset
);
518 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
520 dfa_stats_p
->num_phis
++;
521 dfa_stats_p
->num_phi_args
+= PHI_NUM_ARGS (phi
);
522 if (PHI_NUM_ARGS (phi
) > dfa_stats_p
->max_num_phi_args
)
523 dfa_stats_p
->max_num_phi_args
= PHI_NUM_ARGS (phi
);
529 /* Callback for walk_tree to collect DFA statistics for a tree and its
533 collect_dfa_stats_r (tree
*tp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
537 struct dfa_stats_d
*dfa_stats_p
= (struct dfa_stats_d
*)data
;
541 switch (ann_type (t
->base
.ann
))
545 dfa_stats_p
->num_stmt_anns
++;
546 dfa_stats_p
->num_defs
+= NUM_SSA_OPERANDS (t
, SSA_OP_DEF
);
547 dfa_stats_p
->num_uses
+= NUM_SSA_OPERANDS (t
, SSA_OP_USE
);
548 dfa_stats_p
->num_vdefs
+= NUM_SSA_OPERANDS (t
, SSA_OP_VDEF
);
549 dfa_stats_p
->num_vuses
+= NUM_SSA_OPERANDS (t
, SSA_OP_VUSE
);
554 dfa_stats_p
->num_var_anns
++;
566 /*---------------------------------------------------------------------------
567 Miscellaneous helpers
568 ---------------------------------------------------------------------------*/
569 /* Callback for walk_tree. Used to collect variables referenced in
573 find_vars_r (tree
*tp
, int *walk_subtrees
, void *data ATTRIBUTE_UNUSED
)
575 /* If T is a regular variable that the optimizers are interested
576 in, add it to the list of variables. */
578 add_referenced_var (*tp
);
580 /* Type, _DECL and constant nodes have no interesting children.
582 else if (IS_TYPE_OR_DECL_P (*tp
) || CONSTANT_CLASS_P (*tp
))
588 /* Lookup UID in the referenced_vars hashtable and return the associated
592 referenced_var_lookup (unsigned int uid
)
595 struct tree_decl_minimal in
;
597 h
= (tree
) htab_find_with_hash (gimple_referenced_vars (cfun
), &in
, uid
);
598 gcc_assert (h
|| uid
== 0);
602 /* Check if TO is in the referenced_vars hash table and insert it if not.
603 Return true if it required insertion. */
606 referenced_var_check_and_insert (tree to
)
609 struct tree_decl_minimal in
;
610 unsigned int uid
= DECL_UID (to
);
613 h
= (tree
) htab_find_with_hash (gimple_referenced_vars (cfun
), &in
, uid
);
616 /* DECL_UID has already been entered in the table. Verify that it is
617 the same entry as TO. See PR 27793. */
618 gcc_assert (h
== to
);
622 loc
= (tree
*) htab_find_slot_with_hash (gimple_referenced_vars (cfun
),
628 /* Lookup VAR UID in the default_defs hashtable and return the associated
632 gimple_default_def (struct function
*fn
, tree var
)
634 struct tree_decl_minimal ind
;
635 struct tree_ssa_name in
;
636 gcc_assert (SSA_VAR_P (var
));
638 ind
.uid
= DECL_UID (var
);
639 return (tree
) htab_find_with_hash (DEFAULT_DEFS (fn
), &in
, DECL_UID (var
));
642 /* Insert the pair VAR's UID, DEF into the default_defs hashtable. */
645 set_default_def (tree var
, tree def
)
647 struct tree_decl_minimal ind
;
648 struct tree_ssa_name in
;
651 gcc_assert (SSA_VAR_P (var
));
653 ind
.uid
= DECL_UID (var
);
656 loc
= htab_find_slot_with_hash (DEFAULT_DEFS (cfun
), &in
,
657 DECL_UID (var
), INSERT
);
659 htab_remove_elt (DEFAULT_DEFS (cfun
), *loc
);
662 gcc_assert (TREE_CODE (def
) == SSA_NAME
&& SSA_NAME_VAR (def
) == var
);
663 loc
= htab_find_slot_with_hash (DEFAULT_DEFS (cfun
), &in
,
664 DECL_UID (var
), INSERT
);
666 /* Default definition might be changed by tail call optimization. */
668 SSA_NAME_IS_DEFAULT_DEF (*(tree
*) loc
) = false;
671 /* Mark DEF as the default definition for VAR. */
672 SSA_NAME_IS_DEFAULT_DEF (def
) = true;
675 /* Add VAR to the list of referenced variables if it isn't already there. */
678 add_referenced_var (tree var
)
682 v_ann
= get_var_ann (var
);
683 gcc_assert (DECL_P (var
));
685 /* Insert VAR into the referenced_vars has table if it isn't present. */
686 if (referenced_var_check_and_insert (var
))
688 /* This is the first time we found this variable, annotate it with
689 attributes that are intrinsic to the variable. */
691 /* Tag's don't have DECL_INITIAL. */
695 /* Scan DECL_INITIAL for pointer variables as they may contain
696 address arithmetic referencing the address of other
698 Even non-constant intializers need to be walked, because
699 IPA passes might prove that their are invariant later on. */
700 if (DECL_INITIAL (var
)
701 /* Initializers of external variables are not useful to the
703 && !DECL_EXTERNAL (var
))
704 walk_tree (&DECL_INITIAL (var
), find_vars_r
, NULL
, 0);
708 /* Remove VAR from the list. */
711 remove_referenced_var (tree var
)
714 struct tree_decl_minimal in
;
716 unsigned int uid
= DECL_UID (var
);
718 clear_call_clobbered (var
);
719 if ((v_ann
= var_ann (var
)))
721 var
->base
.ann
= NULL
;
722 gcc_assert (DECL_P (var
));
724 loc
= htab_find_slot_with_hash (gimple_referenced_vars (cfun
), &in
, uid
,
726 htab_clear_slot (gimple_referenced_vars (cfun
), loc
);
730 /* Return the virtual variable associated to the non-scalar variable VAR. */
733 get_virtual_var (tree var
)
737 if (TREE_CODE (var
) == SSA_NAME
)
738 var
= SSA_NAME_VAR (var
);
740 while (TREE_CODE (var
) == REALPART_EXPR
|| TREE_CODE (var
) == IMAGPART_EXPR
741 || handled_component_p (var
))
742 var
= TREE_OPERAND (var
, 0);
744 /* Treating GIMPLE registers as virtual variables makes no sense.
745 Also complain if we couldn't extract a _DECL out of the original
747 gcc_assert (SSA_VAR_P (var
));
748 gcc_assert (!is_gimple_reg (var
));
753 /* Mark all the naked symbols in STMT for SSA renaming.
755 NOTE: This function should only be used for brand new statements.
756 If the caller is modifying an existing statement, it should use the
757 combination push_stmt_changes/pop_stmt_changes. */
760 mark_symbols_for_renaming (tree stmt
)
767 /* Mark all the operands for renaming. */
768 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_ALL_OPERANDS
)
770 mark_sym_for_renaming (op
);
774 /* Find all variables within the gimplified statement that were not previously
775 visible to the function and add them to the referenced variables list. */
778 find_new_referenced_vars_1 (tree
*tp
, int *walk_subtrees
,
779 void *data ATTRIBUTE_UNUSED
)
783 if (TREE_CODE (t
) == VAR_DECL
&& !var_ann (t
))
785 add_referenced_var (t
);
786 mark_sym_for_renaming (t
);
789 if (IS_TYPE_OR_DECL_P (t
))
796 find_new_referenced_vars (tree
*stmt_p
)
798 walk_tree (stmt_p
, find_new_referenced_vars_1
, NULL
, NULL
);
802 /* If EXP is a handled component reference for a structure, return the
803 base variable. The access range is delimited by bit positions *POFFSET and
804 *POFFSET + *PMAX_SIZE. The access size is *PSIZE bits. If either
805 *PSIZE or *PMAX_SIZE is -1, they could not be determined. If *PSIZE
806 and *PMAX_SIZE are equal, the access is non-variable. */
809 get_ref_base_and_extent (tree exp
, HOST_WIDE_INT
*poffset
,
810 HOST_WIDE_INT
*psize
,
811 HOST_WIDE_INT
*pmax_size
)
813 HOST_WIDE_INT bitsize
= -1;
814 HOST_WIDE_INT maxsize
= -1;
815 tree size_tree
= NULL_TREE
;
816 HOST_WIDE_INT bit_offset
= 0;
817 bool seen_variable_array_ref
= false;
819 gcc_assert (!SSA_VAR_P (exp
));
821 /* First get the final access size from just the outermost expression. */
822 if (TREE_CODE (exp
) == COMPONENT_REF
)
823 size_tree
= DECL_SIZE (TREE_OPERAND (exp
, 1));
824 else if (TREE_CODE (exp
) == BIT_FIELD_REF
)
825 size_tree
= TREE_OPERAND (exp
, 1);
828 enum machine_mode mode
= TYPE_MODE (TREE_TYPE (exp
));
830 size_tree
= TYPE_SIZE (TREE_TYPE (exp
));
832 bitsize
= GET_MODE_BITSIZE (mode
);
834 if (size_tree
!= NULL_TREE
)
836 if (! host_integerp (size_tree
, 1))
839 bitsize
= TREE_INT_CST_LOW (size_tree
);
842 /* Initially, maxsize is the same as the accessed element size.
843 In the following it will only grow (or become -1). */
846 /* Compute cumulative bit-offset for nested component-refs and array-refs,
847 and find the ultimate containing object. */
850 switch (TREE_CODE (exp
))
853 bit_offset
+= tree_low_cst (TREE_OPERAND (exp
, 2), 0);
858 tree field
= TREE_OPERAND (exp
, 1);
859 tree this_offset
= component_ref_field_offset (exp
);
861 if (this_offset
&& TREE_CODE (this_offset
) == INTEGER_CST
)
863 HOST_WIDE_INT hthis_offset
= tree_low_cst (this_offset
, 0);
865 hthis_offset
*= BITS_PER_UNIT
;
866 bit_offset
+= hthis_offset
;
867 bit_offset
+= tree_low_cst (DECL_FIELD_BIT_OFFSET (field
), 0);
871 tree csize
= TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp
, 0)));
872 /* We need to adjust maxsize to the whole structure bitsize.
873 But we can subtract any constant offset seen sofar,
874 because that would get us out of the structure otherwise. */
875 if (maxsize
!= -1 && csize
&& host_integerp (csize
, 1))
876 maxsize
= TREE_INT_CST_LOW (csize
) - bit_offset
;
884 case ARRAY_RANGE_REF
:
886 tree index
= TREE_OPERAND (exp
, 1);
887 tree low_bound
= array_ref_low_bound (exp
);
888 tree unit_size
= array_ref_element_size (exp
);
890 /* If the resulting bit-offset is constant, track it. */
891 if (host_integerp (index
, 0)
892 && host_integerp (low_bound
, 0)
893 && host_integerp (unit_size
, 1))
895 HOST_WIDE_INT hindex
= tree_low_cst (index
, 0);
897 hindex
-= tree_low_cst (low_bound
, 0);
898 hindex
*= tree_low_cst (unit_size
, 1);
899 hindex
*= BITS_PER_UNIT
;
900 bit_offset
+= hindex
;
902 /* An array ref with a constant index up in the structure
903 hierarchy will constrain the size of any variable array ref
904 lower in the access hierarchy. */
905 seen_variable_array_ref
= false;
909 tree asize
= TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp
, 0)));
910 /* We need to adjust maxsize to the whole array bitsize.
911 But we can subtract any constant offset seen sofar,
912 because that would get us outside of the array otherwise. */
913 if (maxsize
!= -1 && asize
&& host_integerp (asize
, 1))
914 maxsize
= TREE_INT_CST_LOW (asize
) - bit_offset
;
918 /* Remember that we have seen an array ref with a variable
920 seen_variable_array_ref
= true;
929 bit_offset
+= bitsize
;
932 case VIEW_CONVERT_EXPR
:
933 /* ??? We probably should give up here and bail out. */
940 exp
= TREE_OPERAND (exp
, 0);
944 /* We need to deal with variable arrays ending structures such as
945 struct { int length; int a[1]; } x; x.a[d]
946 struct { struct { int a; int b; } a[1]; } x; x.a[d].a
947 struct { struct { int a[1]; } a[1]; } x; x.a[0][d], x.a[d][0]
948 where we do not know maxsize for variable index accesses to
949 the array. The simplest way to conservatively deal with this
950 is to punt in the case that offset + maxsize reaches the
951 base type boundary. */
952 if (seen_variable_array_ref
954 && host_integerp (TYPE_SIZE (TREE_TYPE (exp
)), 1)
955 && bit_offset
+ maxsize
956 == (signed)TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp
))))
959 /* ??? Due to negative offsets in ARRAY_REF we can end up with
960 negative bit_offset here. We might want to store a zero offset
962 *poffset
= bit_offset
;
964 *pmax_size
= maxsize
;
969 /* Returns true if STMT references an SSA_NAME that has
970 SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false. */
973 stmt_references_abnormal_ssa_name (tree stmt
)
978 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, oi
, SSA_OP_USE
)
980 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p
)))
987 /* Return true, if the two memory references REF1 and REF2 may alias. */
990 refs_may_alias_p (tree ref1
, tree ref2
)
993 HOST_WIDE_INT offset1
= 0, offset2
= 0;
994 HOST_WIDE_INT size1
= -1, size2
= -1;
995 HOST_WIDE_INT max_size1
= -1, max_size2
= -1;
997 gcc_assert ((SSA_VAR_P (ref1
)
998 || handled_component_p (ref1
)
999 || INDIRECT_REF_P (ref1
)
1000 || TREE_CODE (ref1
) == TARGET_MEM_REF
)
1001 && (SSA_VAR_P (ref2
)
1002 || handled_component_p (ref2
)
1003 || INDIRECT_REF_P (ref2
)
1004 || TREE_CODE (ref2
) == TARGET_MEM_REF
));
1006 /* Defer to TBAA if possible. */
1007 if (flag_strict_aliasing
1008 && !alias_sets_conflict_p (get_alias_set (ref1
), get_alias_set (ref2
)))
1011 /* Decompose the references into their base objects and the access. */
1013 if (handled_component_p (ref1
))
1014 base1
= get_ref_base_and_extent (ref1
, &offset1
, &size1
, &max_size1
);
1016 if (handled_component_p (ref2
))
1017 base2
= get_ref_base_and_extent (ref2
, &offset2
, &size2
, &max_size2
);
1019 /* If both references are based on different variables, they cannot alias.
1020 If both references are based on the same variable, they cannot alias if
1021 if the accesses do not overlap. */
1022 if (SSA_VAR_P (base1
)
1023 && SSA_VAR_P (base2
)
1024 && (!operand_equal_p (base1
, base2
, 0)
1025 || !ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
)))
1028 /* If both references are through pointers and both pointers are equal
1029 then they do not alias if the accesses do not overlap. */
1030 if (TREE_CODE (base1
) == INDIRECT_REF
1031 && TREE_CODE (base2
) == INDIRECT_REF
1032 && operand_equal_p (TREE_OPERAND (base1
, 0),
1033 TREE_OPERAND (base2
, 0), 0)
1034 && !ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
))
1040 /* Given a stmt STMT that references memory, return the single stmt
1041 that is reached by following the VUSE -> VDEF link. Returns
1042 NULL_TREE, if there is no single stmt that defines all VUSEs of
1044 Note that for a stmt with a single virtual operand this may return
1045 a PHI node as well. Note that if all VUSEs are default definitions
1046 this function will return an empty statement. */
1049 get_single_def_stmt (tree stmt
)
1051 tree def_stmt
= NULL_TREE
;
1055 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
1057 tree tmp
= SSA_NAME_DEF_STMT (use
);
1059 /* ??? This is too simplistic for multiple virtual operands
1060 reaching different PHI nodes of the same basic blocks or for
1061 reaching all default definitions. */
1064 && !(IS_EMPTY_STMT (def_stmt
)
1065 && IS_EMPTY_STMT (tmp
)))
1074 /* Given a PHI node of virtual operands, tries to eliminate cyclic
1075 reached definitions if they do not alias REF and returns the
1076 defining statement of the single virtual operand that flows in
1077 from a non-backedge. Returns NULL_TREE if such statement within
1078 the above conditions cannot be found. */
1081 get_single_def_stmt_from_phi (tree ref
, tree phi
)
1083 tree def_arg
= NULL_TREE
;
1086 /* Find the single PHI argument that is not flowing in from a
1087 back edge and verify that the loop-carried definitions do
1088 not alias the reference we look for. */
1089 for (i
= 0; i
< PHI_NUM_ARGS (phi
); ++i
)
1091 tree arg
= PHI_ARG_DEF (phi
, i
);
1094 if (!(PHI_ARG_EDGE (phi
, i
)->flags
& EDGE_DFS_BACK
))
1096 /* Multiple non-back edges? Do not try to handle this. */
1103 /* Follow the definitions back to the original PHI node. Bail
1104 out once a definition is found that may alias REF. */
1105 def_stmt
= SSA_NAME_DEF_STMT (arg
);
1108 if (TREE_CODE (def_stmt
) != GIMPLE_MODIFY_STMT
1109 || refs_may_alias_p (ref
, GIMPLE_STMT_OPERAND (def_stmt
, 0)))
1111 /* ??? This will only work, reaching the PHI node again if
1112 there is a single virtual operand on def_stmt. */
1113 def_stmt
= get_single_def_stmt (def_stmt
);
1117 while (def_stmt
!= phi
);
1120 return SSA_NAME_DEF_STMT (def_arg
);
1123 /* Return the single reference statement defining all virtual uses
1124 on STMT or NULL_TREE, if there are multiple defining statements.
1125 Take into account only definitions that alias REF if following
1126 back-edges when looking through a loop PHI node. */
1129 get_single_def_stmt_with_phi (tree ref
, tree stmt
)
1131 switch (NUM_SSA_OPERANDS (stmt
, SSA_OP_VIRTUAL_USES
))
1138 tree def_stmt
= SSA_NAME_DEF_STMT (SINGLE_SSA_TREE_OPERAND
1139 (stmt
, SSA_OP_VIRTUAL_USES
));
1140 /* We can handle lookups over PHI nodes only for a single
1142 if (TREE_CODE (def_stmt
) == PHI_NODE
)
1143 return get_single_def_stmt_from_phi (ref
, def_stmt
);
1148 return get_single_def_stmt (stmt
);