1 /* Data flow functions for trees.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005 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 2, 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 COPYING. If not, write to
19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20 Boston, MA 02110-1301, USA. */
24 #include "coretypes.h"
27 #include "pointer-set.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
37 #include "langhooks.h"
40 #include "diagnostic.h"
41 #include "tree-dump.h"
42 #include "tree-gimple.h"
43 #include "tree-flow.h"
44 #include "tree-inline.h"
45 #include "tree-pass.h"
50 /* Build and maintain data flow information for trees. */
52 /* Counters used to display DFA and SSA statistics. */
68 /* State information for find_vars_r. */
71 /* Hash table used to avoid adding the same variable more than once. */
76 /* Local functions. */
77 static void collect_dfa_stats (struct dfa_stats_d
*);
78 static tree
collect_dfa_stats_r (tree
*, int *, void *);
79 static tree
find_vars_r (tree
*, int *, void *);
80 static void add_referenced_var (tree
, struct walk_state
*);
83 /* Global declarations. */
85 /* Array of all variables referenced in the function. */
86 htab_t referenced_vars
;
89 /*---------------------------------------------------------------------------
90 Dataflow analysis (DFA) routines
91 ---------------------------------------------------------------------------*/
92 /* Find all the variables referenced in the function. This function
93 builds the global arrays REFERENCED_VARS and CALL_CLOBBERED_VARS.
95 Note that this function does not look for statement operands, it simply
96 determines what variables are referenced in the program and detects
97 various attributes for each variable used by alias analysis and the
101 find_referenced_vars (void)
105 block_stmt_iterator si
;
106 struct walk_state walk_state
;
108 vars_found
= htab_create (50, htab_hash_pointer
, htab_eq_pointer
, NULL
);
109 memset (&walk_state
, 0, sizeof (walk_state
));
110 walk_state
.vars_found
= vars_found
;
113 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
115 tree
*stmt_p
= bsi_stmt_ptr (si
);
116 walk_tree (stmt_p
, find_vars_r
, &walk_state
, NULL
);
119 htab_delete (vars_found
);
122 struct tree_opt_pass pass_referenced_vars
=
126 find_referenced_vars
, /* execute */
129 0, /* static_pass_number */
130 TV_FIND_REFERENCED_VARS
, /* tv_id */
131 PROP_gimple_leh
| PROP_cfg
, /* properties_required */
132 PROP_referenced_vars
, /* properties_provided */
133 0, /* properties_destroyed */
134 0, /* todo_flags_start */
135 0, /* todo_flags_finish */
140 /*---------------------------------------------------------------------------
142 ---------------------------------------------------------------------------*/
143 /* Create a new annotation for a _DECL node T. */
146 create_var_ann (tree t
)
151 gcc_assert (DECL_P (t
));
152 gcc_assert (!t
->common
.ann
|| t
->common
.ann
->common
.type
== VAR_ANN
);
154 ann
= ggc_alloc (sizeof (*ann
));
155 memset ((void *) ann
, 0, sizeof (*ann
));
157 ann
->common
.type
= VAR_ANN
;
159 t
->common
.ann
= (tree_ann_t
) ann
;
165 /* Create a new annotation for a statement node T. */
168 create_stmt_ann (tree t
)
172 gcc_assert (is_gimple_stmt (t
));
173 gcc_assert (!t
->common
.ann
|| t
->common
.ann
->common
.type
== STMT_ANN
);
175 ann
= ggc_alloc (sizeof (*ann
));
176 memset ((void *) ann
, 0, sizeof (*ann
));
178 ann
->common
.type
= STMT_ANN
;
180 /* Since we just created the annotation, mark the statement modified. */
181 ann
->modified
= true;
183 t
->common
.ann
= (tree_ann_t
) ann
;
188 /* Create a new annotation for a tree T. */
191 create_tree_ann (tree t
)
196 gcc_assert (!t
->common
.ann
|| t
->common
.ann
->common
.type
== TREE_ANN_COMMON
);
198 ann
= ggc_alloc (sizeof (*ann
));
199 memset ((void *) ann
, 0, sizeof (*ann
));
201 ann
->common
.type
= TREE_ANN_COMMON
;
207 /* Build a temporary. Make sure and register it to be renamed. */
210 make_rename_temp (tree type
, const char *prefix
)
212 tree t
= create_tmp_var (type
, prefix
);
215 add_referenced_tmp_var (t
);
216 mark_sym_for_renaming (t
);
224 /*---------------------------------------------------------------------------
226 ---------------------------------------------------------------------------*/
227 /* Dump the list of all the referenced variables in the current function to
231 dump_referenced_vars (FILE *file
)
234 referenced_var_iterator rvi
;
236 fprintf (file
, "\nReferenced variables in %s: %u\n\n",
237 get_name (current_function_decl
), (unsigned) num_referenced_vars
);
239 FOR_EACH_REFERENCED_VAR (var
, rvi
)
241 fprintf (file
, "Variable: ");
242 dump_variable (file
, var
);
243 fprintf (file
, "\n");
248 /* Dump the list of all the referenced variables to stderr. */
251 debug_referenced_vars (void)
253 dump_referenced_vars (stderr
);
257 /* Dump sub-variables for VAR to FILE. */
260 dump_subvars_for (FILE *file
, tree var
)
262 subvar_t sv
= get_subvars_for_var (var
);
267 fprintf (file
, "{ ");
269 for (; sv
; sv
= sv
->next
)
271 print_generic_expr (file
, sv
->var
, dump_flags
);
279 /* Dumb sub-variables for VAR to stderr. */
282 debug_subvars_for (tree var
)
284 dump_subvars_for (stderr
, var
);
288 /* Dump variable VAR and its may-aliases to FILE. */
291 dump_variable (FILE *file
, tree var
)
295 if (TREE_CODE (var
) == SSA_NAME
)
297 if (POINTER_TYPE_P (TREE_TYPE (var
)))
298 dump_points_to_info_for (file
, var
);
299 var
= SSA_NAME_VAR (var
);
302 if (var
== NULL_TREE
)
304 fprintf (file
, "<nil>");
308 print_generic_expr (file
, var
, dump_flags
);
312 fprintf (file
, ", UID %u", (unsigned) DECL_UID (var
));
314 fprintf (file
, ", ");
315 print_generic_expr (file
, TREE_TYPE (var
), dump_flags
);
317 if (ann
->type_mem_tag
)
319 fprintf (file
, ", type memory tag: ");
320 print_generic_expr (file
, ann
->type_mem_tag
, dump_flags
);
323 if (ann
->is_alias_tag
)
324 fprintf (file
, ", is an alias tag");
326 if (TREE_ADDRESSABLE (var
))
327 fprintf (file
, ", is addressable");
329 if (is_global_var (var
))
330 fprintf (file
, ", is global");
332 if (TREE_THIS_VOLATILE (var
))
333 fprintf (file
, ", is volatile");
335 if (is_call_clobbered (var
))
336 fprintf (file
, ", call clobbered");
338 if (ann
->default_def
)
340 fprintf (file
, ", default def: ");
341 print_generic_expr (file
, ann
->default_def
, dump_flags
);
344 if (ann
->may_aliases
)
346 fprintf (file
, ", may aliases: ");
347 dump_may_aliases_for (file
, var
);
350 if (get_subvars_for_var (var
))
352 fprintf (file
, ", sub-vars: ");
353 dump_subvars_for (file
, var
);
356 fprintf (file
, "\n");
360 /* Dump variable VAR and its may-aliases to stderr. */
363 debug_variable (tree var
)
365 dump_variable (stderr
, var
);
369 /* Dump various DFA statistics to FILE. */
372 dump_dfa_stats (FILE *file
)
374 struct dfa_stats_d dfa_stats
;
376 unsigned long size
, total
= 0;
377 const char * const fmt_str
= "%-30s%-13s%12s\n";
378 const char * const fmt_str_1
= "%-30s%13lu%11lu%c\n";
379 const char * const fmt_str_3
= "%-43s%11lu%c\n";
381 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
383 collect_dfa_stats (&dfa_stats
);
385 fprintf (file
, "\nDFA Statistics for %s\n\n", funcname
);
387 fprintf (file
, "---------------------------------------------------------\n");
388 fprintf (file
, fmt_str
, "", " Number of ", "Memory");
389 fprintf (file
, fmt_str
, "", " instances ", "used ");
390 fprintf (file
, "---------------------------------------------------------\n");
392 size
= num_referenced_vars
* sizeof (tree
);
394 fprintf (file
, fmt_str_1
, "Referenced variables", (unsigned long)num_referenced_vars
,
395 SCALE (size
), LABEL (size
));
397 size
= dfa_stats
.num_stmt_anns
* sizeof (struct stmt_ann_d
);
399 fprintf (file
, fmt_str_1
, "Statements annotated", dfa_stats
.num_stmt_anns
,
400 SCALE (size
), LABEL (size
));
402 size
= dfa_stats
.num_var_anns
* sizeof (struct var_ann_d
);
404 fprintf (file
, fmt_str_1
, "Variables annotated", dfa_stats
.num_var_anns
,
405 SCALE (size
), LABEL (size
));
407 size
= dfa_stats
.num_uses
* sizeof (tree
*);
409 fprintf (file
, fmt_str_1
, "USE operands", dfa_stats
.num_uses
,
410 SCALE (size
), LABEL (size
));
412 size
= dfa_stats
.num_defs
* sizeof (tree
*);
414 fprintf (file
, fmt_str_1
, "DEF operands", dfa_stats
.num_defs
,
415 SCALE (size
), LABEL (size
));
417 size
= dfa_stats
.num_vuses
* sizeof (tree
*);
419 fprintf (file
, fmt_str_1
, "VUSE operands", dfa_stats
.num_vuses
,
420 SCALE (size
), LABEL (size
));
422 size
= dfa_stats
.num_v_may_defs
* sizeof (tree
*);
424 fprintf (file
, fmt_str_1
, "V_MAY_DEF operands", dfa_stats
.num_v_may_defs
,
425 SCALE (size
), LABEL (size
));
427 size
= dfa_stats
.num_v_must_defs
* sizeof (tree
*);
429 fprintf (file
, fmt_str_1
, "V_MUST_DEF operands", dfa_stats
.num_v_must_defs
,
430 SCALE (size
), LABEL (size
));
432 size
= dfa_stats
.num_phis
* sizeof (struct tree_phi_node
);
434 fprintf (file
, fmt_str_1
, "PHI nodes", dfa_stats
.num_phis
,
435 SCALE (size
), LABEL (size
));
437 size
= dfa_stats
.num_phi_args
* sizeof (struct phi_arg_d
);
439 fprintf (file
, fmt_str_1
, "PHI arguments", dfa_stats
.num_phi_args
,
440 SCALE (size
), LABEL (size
));
442 fprintf (file
, "---------------------------------------------------------\n");
443 fprintf (file
, fmt_str_3
, "Total memory used by DFA/SSA data", SCALE (total
),
445 fprintf (file
, "---------------------------------------------------------\n");
446 fprintf (file
, "\n");
448 if (dfa_stats
.num_phis
)
449 fprintf (file
, "Average number of arguments per PHI node: %.1f (max: %d)\n",
450 (float) dfa_stats
.num_phi_args
/ (float) dfa_stats
.num_phis
,
451 dfa_stats
.max_num_phi_args
);
453 fprintf (file
, "\n");
457 /* Dump DFA statistics on stderr. */
460 debug_dfa_stats (void)
462 dump_dfa_stats (stderr
);
466 /* Collect DFA statistics and store them in the structure pointed by
470 collect_dfa_stats (struct dfa_stats_d
*dfa_stats_p
)
472 struct pointer_set_t
*pset
;
474 block_stmt_iterator i
;
476 gcc_assert (dfa_stats_p
);
478 memset ((void *)dfa_stats_p
, 0, sizeof (struct dfa_stats_d
));
480 /* Walk all the trees in the function counting references. Start at
481 basic block 0, but don't stop at block boundaries. */
482 pset
= pointer_set_create ();
484 for (i
= bsi_start (BASIC_BLOCK (0)); !bsi_end_p (i
); bsi_next (&i
))
485 walk_tree (bsi_stmt_ptr (i
), collect_dfa_stats_r
, (void *) dfa_stats_p
,
488 pointer_set_destroy (pset
);
493 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
495 dfa_stats_p
->num_phis
++;
496 dfa_stats_p
->num_phi_args
+= PHI_NUM_ARGS (phi
);
497 if (PHI_NUM_ARGS (phi
) > dfa_stats_p
->max_num_phi_args
)
498 dfa_stats_p
->max_num_phi_args
= PHI_NUM_ARGS (phi
);
504 /* Callback for walk_tree to collect DFA statistics for a tree and its
508 collect_dfa_stats_r (tree
*tp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
512 struct dfa_stats_d
*dfa_stats_p
= (struct dfa_stats_d
*)data
;
516 switch (ann_type (t
->common
.ann
))
520 dfa_stats_p
->num_stmt_anns
++;
521 dfa_stats_p
->num_defs
+= NUM_SSA_OPERANDS (t
, SSA_OP_DEF
);
522 dfa_stats_p
->num_uses
+= NUM_SSA_OPERANDS (t
, SSA_OP_USE
);
523 dfa_stats_p
->num_v_may_defs
+= NUM_SSA_OPERANDS (t
, SSA_OP_VMAYDEF
);
524 dfa_stats_p
->num_vuses
+= NUM_SSA_OPERANDS (t
, SSA_OP_VUSE
);
525 dfa_stats_p
->num_v_must_defs
+=
526 NUM_SSA_OPERANDS (t
, SSA_OP_VMUSTDEF
);
531 dfa_stats_p
->num_var_anns
++;
543 /*---------------------------------------------------------------------------
544 Miscellaneous helpers
545 ---------------------------------------------------------------------------*/
546 /* Callback for walk_tree. Used to collect variables referenced in
550 find_vars_r (tree
*tp
, int *walk_subtrees
, void *data
)
552 struct walk_state
*walk_state
= (struct walk_state
*) data
;
554 /* If T is a regular variable that the optimizers are interested
555 in, add it to the list of variables. */
557 add_referenced_var (*tp
, walk_state
);
559 /* Type, _DECL and constant nodes have no interesting children.
561 else if (IS_TYPE_OR_DECL_P (*tp
) || CONSTANT_CLASS_P (*tp
))
568 /* Lookup UID in the referenced_vars hashtable and return the associated
572 referenced_var_lookup (unsigned int uid
)
574 struct int_tree_map
*h
, in
;
576 h
= htab_find_with_hash (referenced_vars
, &in
, uid
);
577 gcc_assert (h
|| uid
== 0);
583 /* Insert the pair UID, TO into the referenced_vars hashtable. */
586 referenced_var_insert (unsigned int uid
, tree to
)
588 struct int_tree_map
*h
;
591 h
= ggc_alloc (sizeof (struct int_tree_map
));
594 loc
= htab_find_slot_with_hash (referenced_vars
, h
, uid
, INSERT
);
595 *(struct int_tree_map
**) loc
= h
;
598 /* Add VAR to the list of dereferenced variables.
600 WALK_STATE contains a hash table used to avoid adding the same
601 variable more than once. Note that this function assumes that
602 VAR is a valid SSA variable. If WALK_STATE is NULL, no
603 duplicate checking is done. */
606 add_referenced_var (tree var
, struct walk_state
*walk_state
)
611 v_ann
= get_var_ann (var
);
614 slot
= htab_find_slot (walk_state
->vars_found
, (void *) var
, INSERT
);
618 if (slot
== NULL
|| *slot
== NULL
)
620 /* This is the first time we find this variable, add it to the
621 REFERENCED_VARS array and annotate it with attributes that are
622 intrinsic to the variable. */
624 *slot
= (void *) var
;
626 referenced_var_insert (DECL_UID (var
), var
);
628 /* Global variables are always call-clobbered. */
629 if (is_global_var (var
))
630 mark_call_clobbered (var
);
632 /* Scan DECL_INITIAL for pointer variables as they may contain
633 address arithmetic referencing the address of other
635 if (DECL_INITIAL (var
)
636 /* Initializers of external variables are not useful to the
638 && !DECL_EXTERNAL (var
)
639 /* It's not necessary to walk the initial value of non-constant
640 public variables because it cannot be propagated by the
642 && (!TREE_PUBLIC (var
) || !TREE_CONSTANT (var
)))
643 walk_tree (&DECL_INITIAL (var
), find_vars_r
, walk_state
, 0);
648 /* Return the virtual variable associated to the non-scalar variable VAR. */
651 get_virtual_var (tree var
)
655 if (TREE_CODE (var
) == SSA_NAME
)
656 var
= SSA_NAME_VAR (var
);
658 while (TREE_CODE (var
) == REALPART_EXPR
|| TREE_CODE (var
) == IMAGPART_EXPR
659 || handled_component_p (var
))
660 var
= TREE_OPERAND (var
, 0);
662 /* Treating GIMPLE registers as virtual variables makes no sense.
663 Also complain if we couldn't extract a _DECL out of the original
665 gcc_assert (SSA_VAR_P (var
));
666 gcc_assert (!is_gimple_reg (var
));
671 /* Add a temporary variable to REFERENCED_VARS. This is similar to
672 add_referenced_var, but is used by passes that need to add new temps to
673 the REFERENCED_VARS array after the program has been scanned for
674 variables. The variable will just receive a new UID and be added
675 to the REFERENCED_VARS array without checking for duplicates. */
678 add_referenced_tmp_var (tree var
)
680 add_referenced_var (var
, NULL
);
684 /* Mark all the non-SSA variables found in STMT's operands to be
685 processed by update_ssa. */
688 mark_new_vars_to_rename (tree stmt
)
692 bitmap vars_in_vops_to_rename
;
693 bool found_exposed_symbol
= false;
694 int v_may_defs_before
, v_may_defs_after
;
695 int v_must_defs_before
, v_must_defs_after
;
697 vars_in_vops_to_rename
= BITMAP_ALLOC (NULL
);
699 /* Before re-scanning the statement for operands, mark the existing
700 virtual operands to be renamed again. We do this because when new
701 symbols are exposed, the virtual operands that were here before due to
702 aliasing will probably be removed by the call to get_stmt_operand.
703 Therefore, we need to flag them to be renamed beforehand.
705 We flag them in a separate bitmap because we don't really want to
706 rename them if there are not any newly exposed symbols in the
707 statement operands. */
708 v_may_defs_before
= NUM_SSA_OPERANDS (stmt
, SSA_OP_VMAYDEF
);
709 v_must_defs_before
= NUM_SSA_OPERANDS (stmt
, SSA_OP_VMUSTDEF
);
711 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
,
712 SSA_OP_VMAYDEF
| SSA_OP_VUSE
| SSA_OP_VMUSTDEF
)
715 val
= SSA_NAME_VAR (val
);
716 bitmap_set_bit (vars_in_vops_to_rename
, DECL_UID (val
));
719 /* Now force an operand re-scan on the statement and mark any newly
720 exposed variables. */
723 v_may_defs_after
= NUM_SSA_OPERANDS (stmt
, SSA_OP_VMAYDEF
);
724 v_must_defs_after
= NUM_SSA_OPERANDS (stmt
, SSA_OP_VMUSTDEF
);
726 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_ALL_OPERANDS
)
729 found_exposed_symbol
= true;
730 mark_sym_for_renaming (val
);
733 /* If we found any newly exposed symbols, or if there are fewer VDEF
734 operands in the statement, add the variables we had set in
735 VARS_IN_VOPS_TO_RENAME to VARS_TO_RENAME. We need to check for
736 vanishing VDEFs because in those cases, the names that were formerly
737 generated by this statement are not going to be available anymore. */
738 if (found_exposed_symbol
739 || v_may_defs_before
> v_may_defs_after
740 || v_must_defs_before
> v_must_defs_after
)
741 mark_set_for_renaming (vars_in_vops_to_rename
);
743 BITMAP_FREE (vars_in_vops_to_rename
);
746 /* Find all variables within the gimplified statement that were not previously
747 visible to the function and add them to the referenced variables list. */
750 find_new_referenced_vars_1 (tree
*tp
, int *walk_subtrees
,
751 void *data ATTRIBUTE_UNUSED
)
755 if (TREE_CODE (t
) == VAR_DECL
&& !var_ann (t
))
757 add_referenced_tmp_var (t
);
758 mark_sym_for_renaming (t
);
761 if (IS_TYPE_OR_DECL_P (t
))
768 find_new_referenced_vars (tree
*stmt_p
)
770 walk_tree (stmt_p
, find_new_referenced_vars_1
, NULL
, NULL
);
774 /* If REF is a COMPONENT_REF for a structure that can have sub-variables, and
775 we know where REF is accessing, return the variable in REF that has the
776 sub-variables. If the return value is not NULL, POFFSET will be the
777 offset, in bits, of REF inside the return value, and PSIZE will be the
778 size, in bits, of REF inside the return value. */
781 okay_component_ref_for_subvars (tree ref
, unsigned HOST_WIDE_INT
*poffset
,
782 unsigned HOST_WIDE_INT
*psize
)
785 HOST_WIDE_INT bitsize
;
786 HOST_WIDE_INT bitpos
;
788 enum machine_mode mode
;
792 gcc_assert (!SSA_VAR_P (ref
));
794 *psize
= (unsigned int) -1;
796 if (ref_contains_array_ref (ref
))
798 ref
= get_inner_reference (ref
, &bitsize
, &bitpos
, &offset
, &mode
,
799 &unsignedp
, &volatilep
, false);
800 if (TREE_CODE (ref
) == INDIRECT_REF
)
802 else if (offset
== NULL
&& bitsize
!= -1 && SSA_VAR_P (ref
))
806 if (get_subvars_for_var (ref
) != NULL
)
809 else if (SSA_VAR_P (ref
))
811 if (get_subvars_for_var (ref
) != NULL
)