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 variable VAR and its may-aliases to FILE. */
260 dump_variable (FILE *file
, tree var
)
264 if (TREE_CODE (var
) == SSA_NAME
)
266 if (POINTER_TYPE_P (TREE_TYPE (var
)))
267 dump_points_to_info_for (file
, var
);
268 var
= SSA_NAME_VAR (var
);
271 if (var
== NULL_TREE
)
273 fprintf (file
, "<nil>");
277 print_generic_expr (file
, var
, dump_flags
);
281 fprintf (file
, ", UID %u", (unsigned) DECL_UID (var
));
283 fprintf (file
, ", ");
284 print_generic_expr (file
, TREE_TYPE (var
), dump_flags
);
286 if (ann
->type_mem_tag
)
288 fprintf (file
, ", type memory tag: ");
289 print_generic_expr (file
, ann
->type_mem_tag
, dump_flags
);
292 if (ann
->is_alias_tag
)
293 fprintf (file
, ", is an alias tag");
295 if (TREE_ADDRESSABLE (var
))
296 fprintf (file
, ", is addressable");
298 if (is_global_var (var
))
299 fprintf (file
, ", is global");
301 if (TREE_THIS_VOLATILE (var
))
302 fprintf (file
, ", is volatile");
304 if (is_call_clobbered (var
))
305 fprintf (file
, ", call clobbered");
307 if (ann
->default_def
)
309 fprintf (file
, ", default def: ");
310 print_generic_expr (file
, ann
->default_def
, dump_flags
);
313 if (ann
->may_aliases
)
315 fprintf (file
, ", may aliases: ");
316 dump_may_aliases_for (file
, var
);
319 fprintf (file
, "\n");
323 /* Dump variable VAR and its may-aliases to stderr. */
326 debug_variable (tree var
)
328 dump_variable (stderr
, var
);
332 /* Dump various DFA statistics to FILE. */
335 dump_dfa_stats (FILE *file
)
337 struct dfa_stats_d dfa_stats
;
339 unsigned long size
, total
= 0;
340 const char * const fmt_str
= "%-30s%-13s%12s\n";
341 const char * const fmt_str_1
= "%-30s%13lu%11lu%c\n";
342 const char * const fmt_str_3
= "%-43s%11lu%c\n";
344 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
346 collect_dfa_stats (&dfa_stats
);
348 fprintf (file
, "\nDFA Statistics for %s\n\n", funcname
);
350 fprintf (file
, "---------------------------------------------------------\n");
351 fprintf (file
, fmt_str
, "", " Number of ", "Memory");
352 fprintf (file
, fmt_str
, "", " instances ", "used ");
353 fprintf (file
, "---------------------------------------------------------\n");
355 size
= num_referenced_vars
* sizeof (tree
);
357 fprintf (file
, fmt_str_1
, "Referenced variables", (unsigned long)num_referenced_vars
,
358 SCALE (size
), LABEL (size
));
360 size
= dfa_stats
.num_stmt_anns
* sizeof (struct stmt_ann_d
);
362 fprintf (file
, fmt_str_1
, "Statements annotated", dfa_stats
.num_stmt_anns
,
363 SCALE (size
), LABEL (size
));
365 size
= dfa_stats
.num_var_anns
* sizeof (struct var_ann_d
);
367 fprintf (file
, fmt_str_1
, "Variables annotated", dfa_stats
.num_var_anns
,
368 SCALE (size
), LABEL (size
));
370 size
= dfa_stats
.num_uses
* sizeof (tree
*);
372 fprintf (file
, fmt_str_1
, "USE operands", dfa_stats
.num_uses
,
373 SCALE (size
), LABEL (size
));
375 size
= dfa_stats
.num_defs
* sizeof (tree
*);
377 fprintf (file
, fmt_str_1
, "DEF operands", dfa_stats
.num_defs
,
378 SCALE (size
), LABEL (size
));
380 size
= dfa_stats
.num_vuses
* sizeof (tree
*);
382 fprintf (file
, fmt_str_1
, "VUSE operands", dfa_stats
.num_vuses
,
383 SCALE (size
), LABEL (size
));
385 size
= dfa_stats
.num_v_may_defs
* sizeof (tree
*);
387 fprintf (file
, fmt_str_1
, "V_MAY_DEF operands", dfa_stats
.num_v_may_defs
,
388 SCALE (size
), LABEL (size
));
390 size
= dfa_stats
.num_v_must_defs
* sizeof (tree
*);
392 fprintf (file
, fmt_str_1
, "V_MUST_DEF operands", dfa_stats
.num_v_must_defs
,
393 SCALE (size
), LABEL (size
));
395 size
= dfa_stats
.num_phis
* sizeof (struct tree_phi_node
);
397 fprintf (file
, fmt_str_1
, "PHI nodes", dfa_stats
.num_phis
,
398 SCALE (size
), LABEL (size
));
400 size
= dfa_stats
.num_phi_args
* sizeof (struct phi_arg_d
);
402 fprintf (file
, fmt_str_1
, "PHI arguments", dfa_stats
.num_phi_args
,
403 SCALE (size
), LABEL (size
));
405 fprintf (file
, "---------------------------------------------------------\n");
406 fprintf (file
, fmt_str_3
, "Total memory used by DFA/SSA data", SCALE (total
),
408 fprintf (file
, "---------------------------------------------------------\n");
409 fprintf (file
, "\n");
411 if (dfa_stats
.num_phis
)
412 fprintf (file
, "Average number of arguments per PHI node: %.1f (max: %d)\n",
413 (float) dfa_stats
.num_phi_args
/ (float) dfa_stats
.num_phis
,
414 dfa_stats
.max_num_phi_args
);
416 fprintf (file
, "\n");
420 /* Dump DFA statistics on stderr. */
423 debug_dfa_stats (void)
425 dump_dfa_stats (stderr
);
429 /* Collect DFA statistics and store them in the structure pointed by
433 collect_dfa_stats (struct dfa_stats_d
*dfa_stats_p
)
435 struct pointer_set_t
*pset
;
437 block_stmt_iterator i
;
439 gcc_assert (dfa_stats_p
);
441 memset ((void *)dfa_stats_p
, 0, sizeof (struct dfa_stats_d
));
443 /* Walk all the trees in the function counting references. Start at
444 basic block 0, but don't stop at block boundaries. */
445 pset
= pointer_set_create ();
447 for (i
= bsi_start (BASIC_BLOCK (0)); !bsi_end_p (i
); bsi_next (&i
))
448 walk_tree (bsi_stmt_ptr (i
), collect_dfa_stats_r
, (void *) dfa_stats_p
,
451 pointer_set_destroy (pset
);
456 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
458 dfa_stats_p
->num_phis
++;
459 dfa_stats_p
->num_phi_args
+= PHI_NUM_ARGS (phi
);
460 if (PHI_NUM_ARGS (phi
) > dfa_stats_p
->max_num_phi_args
)
461 dfa_stats_p
->max_num_phi_args
= PHI_NUM_ARGS (phi
);
467 /* Callback for walk_tree to collect DFA statistics for a tree and its
471 collect_dfa_stats_r (tree
*tp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
475 struct dfa_stats_d
*dfa_stats_p
= (struct dfa_stats_d
*)data
;
479 switch (ann_type (t
->common
.ann
))
483 dfa_stats_p
->num_stmt_anns
++;
484 dfa_stats_p
->num_defs
+= NUM_SSA_OPERANDS (t
, SSA_OP_DEF
);
485 dfa_stats_p
->num_uses
+= NUM_SSA_OPERANDS (t
, SSA_OP_USE
);
486 dfa_stats_p
->num_v_may_defs
+= NUM_SSA_OPERANDS (t
, SSA_OP_VMAYDEF
);
487 dfa_stats_p
->num_vuses
+= NUM_SSA_OPERANDS (t
, SSA_OP_VUSE
);
488 dfa_stats_p
->num_v_must_defs
+=
489 NUM_SSA_OPERANDS (t
, SSA_OP_VMUSTDEF
);
494 dfa_stats_p
->num_var_anns
++;
506 /*---------------------------------------------------------------------------
507 Miscellaneous helpers
508 ---------------------------------------------------------------------------*/
509 /* Callback for walk_tree. Used to collect variables referenced in
513 find_vars_r (tree
*tp
, int *walk_subtrees
, void *data
)
515 struct walk_state
*walk_state
= (struct walk_state
*) data
;
517 /* If T is a regular variable that the optimizers are interested
518 in, add it to the list of variables. */
520 add_referenced_var (*tp
, walk_state
);
522 /* Type, _DECL and constant nodes have no interesting children.
524 else if (IS_TYPE_OR_DECL_P (*tp
) || CONSTANT_CLASS_P (*tp
))
531 /* Lookup UID in the referenced_vars hashtable and return the associated
535 referenced_var_lookup (unsigned int uid
)
537 struct int_tree_map
*h
, in
;
539 h
= htab_find_with_hash (referenced_vars
, &in
, uid
);
540 gcc_assert (h
|| uid
== 0);
546 /* Insert the pair UID, TO into the referenced_vars hashtable. */
549 referenced_var_insert (unsigned int uid
, tree to
)
551 struct int_tree_map
*h
;
554 h
= ggc_alloc (sizeof (struct int_tree_map
));
557 loc
= htab_find_slot_with_hash (referenced_vars
, h
, uid
, INSERT
);
558 *(struct int_tree_map
**) loc
= h
;
561 /* Add VAR to the list of dereferenced variables.
563 WALK_STATE contains a hash table used to avoid adding the same
564 variable more than once. Note that this function assumes that
565 VAR is a valid SSA variable. If WALK_STATE is NULL, no
566 duplicate checking is done. */
569 add_referenced_var (tree var
, struct walk_state
*walk_state
)
574 v_ann
= get_var_ann (var
);
577 slot
= htab_find_slot (walk_state
->vars_found
, (void *) var
, INSERT
);
581 if (slot
== NULL
|| *slot
== NULL
)
583 /* This is the first time we find this variable, add it to the
584 REFERENCED_VARS array and annotate it with attributes that are
585 intrinsic to the variable. */
587 *slot
= (void *) var
;
589 referenced_var_insert (DECL_UID (var
), var
);
591 /* Global variables are always call-clobbered. */
592 if (is_global_var (var
))
593 mark_call_clobbered (var
);
595 /* Scan DECL_INITIAL for pointer variables as they may contain
596 address arithmetic referencing the address of other
598 if (DECL_INITIAL (var
)
599 /* Initializers of external variables are not useful to the
601 && !DECL_EXTERNAL (var
)
602 /* It's not necessary to walk the initial value of non-constant
603 public variables because it cannot be propagated by the
605 && (!TREE_PUBLIC (var
) || !TREE_CONSTANT (var
)))
606 walk_tree (&DECL_INITIAL (var
), find_vars_r
, walk_state
, 0);
611 /* Return the virtual variable associated to the non-scalar variable VAR. */
614 get_virtual_var (tree var
)
618 if (TREE_CODE (var
) == SSA_NAME
)
619 var
= SSA_NAME_VAR (var
);
621 while (TREE_CODE (var
) == REALPART_EXPR
|| TREE_CODE (var
) == IMAGPART_EXPR
622 || handled_component_p (var
))
623 var
= TREE_OPERAND (var
, 0);
625 /* Treating GIMPLE registers as virtual variables makes no sense.
626 Also complain if we couldn't extract a _DECL out of the original
628 gcc_assert (SSA_VAR_P (var
));
629 gcc_assert (!is_gimple_reg (var
));
634 /* Add a temporary variable to REFERENCED_VARS. This is similar to
635 add_referenced_var, but is used by passes that need to add new temps to
636 the REFERENCED_VARS array after the program has been scanned for
637 variables. The variable will just receive a new UID and be added
638 to the REFERENCED_VARS array without checking for duplicates. */
641 add_referenced_tmp_var (tree var
)
643 add_referenced_var (var
, NULL
);
647 /* Mark all the non-SSA variables found in STMT's operands to be
648 processed by update_ssa. */
651 mark_new_vars_to_rename (tree stmt
)
655 bitmap vars_in_vops_to_rename
;
656 bool found_exposed_symbol
= false;
657 int v_may_defs_before
, v_may_defs_after
;
658 int v_must_defs_before
, v_must_defs_after
;
660 vars_in_vops_to_rename
= BITMAP_ALLOC (NULL
);
662 /* Before re-scanning the statement for operands, mark the existing
663 virtual operands to be renamed again. We do this because when new
664 symbols are exposed, the virtual operands that were here before due to
665 aliasing will probably be removed by the call to get_stmt_operand.
666 Therefore, we need to flag them to be renamed beforehand.
668 We flag them in a separate bitmap because we don't really want to
669 rename them if there are not any newly exposed symbols in the
670 statement operands. */
671 v_may_defs_before
= NUM_SSA_OPERANDS (stmt
, SSA_OP_VMAYDEF
);
672 v_must_defs_before
= NUM_SSA_OPERANDS (stmt
, SSA_OP_VMUSTDEF
);
674 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
,
675 SSA_OP_VMAYDEF
| SSA_OP_VUSE
| SSA_OP_VMUSTDEF
)
678 val
= SSA_NAME_VAR (val
);
679 bitmap_set_bit (vars_in_vops_to_rename
, DECL_UID (val
));
682 /* Now force an operand re-scan on the statement and mark any newly
683 exposed variables. */
686 v_may_defs_after
= NUM_SSA_OPERANDS (stmt
, SSA_OP_VMAYDEF
);
687 v_must_defs_after
= NUM_SSA_OPERANDS (stmt
, SSA_OP_VMUSTDEF
);
689 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_ALL_OPERANDS
)
692 found_exposed_symbol
= true;
693 mark_sym_for_renaming (val
);
696 /* If we found any newly exposed symbols, or if there are fewer VDEF
697 operands in the statement, add the variables we had set in
698 VARS_IN_VOPS_TO_RENAME to VARS_TO_RENAME. We need to check for
699 vanishing VDEFs because in those cases, the names that were formerly
700 generated by this statement are not going to be available anymore. */
701 if (found_exposed_symbol
702 || v_may_defs_before
> v_may_defs_after
703 || v_must_defs_before
> v_must_defs_after
)
704 mark_set_for_renaming (vars_in_vops_to_rename
);
706 BITMAP_FREE (vars_in_vops_to_rename
);
709 /* Find all variables within the gimplified statement that were not previously
710 visible to the function and add them to the referenced variables list. */
713 find_new_referenced_vars_1 (tree
*tp
, int *walk_subtrees
,
714 void *data ATTRIBUTE_UNUSED
)
718 if (TREE_CODE (t
) == VAR_DECL
&& !var_ann (t
))
720 add_referenced_tmp_var (t
);
721 mark_sym_for_renaming (t
);
724 if (IS_TYPE_OR_DECL_P (t
))
731 find_new_referenced_vars (tree
*stmt_p
)
733 walk_tree (stmt_p
, find_new_referenced_vars_1
, NULL
, NULL
);
737 /* If REF is a COMPONENT_REF for a structure that can have sub-variables, and
738 we know where REF is accessing, return the variable in REF that has the
739 sub-variables. If the return value is not NULL, POFFSET will be the
740 offset, in bits, of REF inside the return value, and PSIZE will be the
741 size, in bits, of REF inside the return value. */
744 okay_component_ref_for_subvars (tree ref
, HOST_WIDE_INT
*poffset
,
745 HOST_WIDE_INT
*psize
)
748 HOST_WIDE_INT bitsize
;
749 HOST_WIDE_INT bitpos
;
751 enum machine_mode mode
;
755 gcc_assert (!SSA_VAR_P (ref
));
757 *psize
= (unsigned int) -1;
759 if (ref_contains_array_ref (ref
))
761 ref
= get_inner_reference (ref
, &bitsize
, &bitpos
, &offset
, &mode
,
762 &unsignedp
, &volatilep
, false);
763 if (TREE_CODE (ref
) == INDIRECT_REF
)
765 else if (offset
== NULL
&& bitsize
!= -1 && SSA_VAR_P (ref
))
769 if (get_subvars_for_var (ref
) != NULL
)
772 else if (SSA_VAR_P (ref
))
774 if (get_subvars_for_var (ref
) != NULL
)