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 /* Local functions. */
69 static void collect_dfa_stats (struct dfa_stats_d *);
70 static tree collect_dfa_stats_r (tree *, int *, void *);
71 static tree find_vars_r (tree *, int *, void *);
72 static void add_referenced_var (tree, bool);
75 /* Global declarations. */
77 /* Array of all variables referenced in the function. */
78 htab_t referenced_vars;
81 /*---------------------------------------------------------------------------
82 Dataflow analysis (DFA) routines
83 ---------------------------------------------------------------------------*/
84 /* Find all the variables referenced in the function. This function
85 builds the global arrays REFERENCED_VARS and CALL_CLOBBERED_VARS.
87 Note that this function does not look for statement operands, it simply
88 determines what variables are referenced in the program and detects
89 various attributes for each variable used by alias analysis and the
93 find_referenced_vars (void)
96 block_stmt_iterator si;
99 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
101 tree *stmt_p = bsi_stmt_ptr (si);
102 walk_tree (stmt_p, find_vars_r, NULL, NULL);
107 struct tree_opt_pass pass_referenced_vars =
111 find_referenced_vars, /* execute */
114 0, /* static_pass_number */
115 TV_FIND_REFERENCED_VARS, /* tv_id */
116 PROP_gimple_leh | PROP_cfg, /* properties_required */
117 PROP_referenced_vars, /* properties_provided */
118 0, /* properties_destroyed */
119 0, /* todo_flags_start */
120 0, /* todo_flags_finish */
125 /*---------------------------------------------------------------------------
127 ---------------------------------------------------------------------------*/
128 /* Create a new annotation for a _DECL node T. */
131 create_var_ann (tree t)
136 gcc_assert (DECL_P (t));
137 gcc_assert (!t->common.ann || t->common.ann->common.type == VAR_ANN);
139 ann = ggc_alloc (sizeof (*ann));
140 memset ((void *) ann, 0, sizeof (*ann));
142 ann->common.type = VAR_ANN;
144 t->common.ann = (tree_ann_t) ann;
150 /* Create a new annotation for a statement node T. */
153 create_stmt_ann (tree t)
157 gcc_assert (is_gimple_stmt (t));
158 gcc_assert (!t->common.ann || t->common.ann->common.type == STMT_ANN);
160 ann = ggc_alloc (sizeof (*ann));
161 memset ((void *) ann, 0, sizeof (*ann));
163 ann->common.type = STMT_ANN;
165 /* Since we just created the annotation, mark the statement modified. */
166 ann->modified = true;
168 t->common.ann = (tree_ann_t) ann;
173 /* Create a new annotation for a tree T. */
176 create_tree_ann (tree t)
181 gcc_assert (!t->common.ann || t->common.ann->common.type == TREE_ANN_COMMON);
183 ann = ggc_alloc (sizeof (*ann));
184 memset ((void *) ann, 0, sizeof (*ann));
186 ann->common.type = TREE_ANN_COMMON;
192 /* Build a temporary. Make sure and register it to be renamed. */
195 make_rename_temp (tree type, const char *prefix)
197 tree t = create_tmp_var (type, prefix);
199 if (TREE_CODE (type) == COMPLEX_TYPE)
200 DECL_COMPLEX_GIMPLE_REG_P (t) = 1;
204 add_referenced_tmp_var (t);
205 mark_sym_for_renaming (t);
213 /*---------------------------------------------------------------------------
215 ---------------------------------------------------------------------------*/
216 /* Dump the list of all the referenced variables in the current function to
220 dump_referenced_vars (FILE *file)
223 referenced_var_iterator rvi;
225 fprintf (file, "\nReferenced variables in %s: %u\n\n",
226 get_name (current_function_decl), (unsigned) num_referenced_vars);
228 FOR_EACH_REFERENCED_VAR (var, rvi)
230 fprintf (file, "Variable: ");
231 dump_variable (file, var);
232 fprintf (file, "\n");
237 /* Dump the list of all the referenced variables to stderr. */
240 debug_referenced_vars (void)
242 dump_referenced_vars (stderr);
246 /* Dump sub-variables for VAR to FILE. */
249 dump_subvars_for (FILE *file, tree var)
251 subvar_t sv = get_subvars_for_var (var);
256 fprintf (file, "{ ");
258 for (; sv; sv = sv->next)
260 print_generic_expr (file, sv->var, dump_flags);
268 /* Dumb sub-variables for VAR to stderr. */
271 debug_subvars_for (tree var)
273 dump_subvars_for (stderr, var);
277 /* Dump variable VAR and its may-aliases to FILE. */
280 dump_variable (FILE *file, tree var)
284 if (TREE_CODE (var) == SSA_NAME)
286 if (POINTER_TYPE_P (TREE_TYPE (var)))
287 dump_points_to_info_for (file, var);
288 var = SSA_NAME_VAR (var);
291 if (var == NULL_TREE)
293 fprintf (file, "<nil>");
297 print_generic_expr (file, var, dump_flags);
301 fprintf (file, ", UID %u", (unsigned) DECL_UID (var));
303 fprintf (file, ", ");
304 print_generic_expr (file, TREE_TYPE (var), dump_flags);
306 if (ann && ann->type_mem_tag)
308 fprintf (file, ", type memory tag: ");
309 print_generic_expr (file, ann->type_mem_tag, dump_flags);
312 if (ann && ann->is_alias_tag)
313 fprintf (file, ", is an alias tag");
315 if (TREE_ADDRESSABLE (var))
316 fprintf (file, ", is addressable");
318 if (is_global_var (var))
319 fprintf (file, ", is global");
321 if (TREE_THIS_VOLATILE (var))
322 fprintf (file, ", is volatile");
324 if (is_call_clobbered (var))
325 fprintf (file, ", call clobbered");
327 if (default_def (var))
329 fprintf (file, ", default def: ");
330 print_generic_expr (file, default_def (var), dump_flags);
333 if (may_aliases (var))
335 fprintf (file, ", may aliases: ");
336 dump_may_aliases_for (file, var);
339 if (get_subvars_for_var (var))
341 fprintf (file, ", sub-vars: ");
342 dump_subvars_for (file, var);
345 fprintf (file, "\n");
349 /* Dump variable VAR and its may-aliases to stderr. */
352 debug_variable (tree var)
354 dump_variable (stderr, var);
358 /* Dump various DFA statistics to FILE. */
361 dump_dfa_stats (FILE *file)
363 struct dfa_stats_d dfa_stats;
365 unsigned long size, total = 0;
366 const char * const fmt_str = "%-30s%-13s%12s\n";
367 const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
368 const char * const fmt_str_3 = "%-43s%11lu%c\n";
370 = lang_hooks.decl_printable_name (current_function_decl, 2);
372 collect_dfa_stats (&dfa_stats);
374 fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
376 fprintf (file, "---------------------------------------------------------\n");
377 fprintf (file, fmt_str, "", " Number of ", "Memory");
378 fprintf (file, fmt_str, "", " instances ", "used ");
379 fprintf (file, "---------------------------------------------------------\n");
381 size = num_referenced_vars * sizeof (tree);
383 fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars,
384 SCALE (size), LABEL (size));
386 size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
388 fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns,
389 SCALE (size), LABEL (size));
391 size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
393 fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
394 SCALE (size), LABEL (size));
396 size = dfa_stats.num_uses * sizeof (tree *);
398 fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
399 SCALE (size), LABEL (size));
401 size = dfa_stats.num_defs * sizeof (tree *);
403 fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
404 SCALE (size), LABEL (size));
406 size = dfa_stats.num_vuses * sizeof (tree *);
408 fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
409 SCALE (size), LABEL (size));
411 size = dfa_stats.num_v_may_defs * sizeof (tree *);
413 fprintf (file, fmt_str_1, "V_MAY_DEF operands", dfa_stats.num_v_may_defs,
414 SCALE (size), LABEL (size));
416 size = dfa_stats.num_v_must_defs * sizeof (tree *);
418 fprintf (file, fmt_str_1, "V_MUST_DEF operands", dfa_stats.num_v_must_defs,
419 SCALE (size), LABEL (size));
421 size = dfa_stats.num_phis * sizeof (struct tree_phi_node);
423 fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
424 SCALE (size), LABEL (size));
426 size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
428 fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
429 SCALE (size), LABEL (size));
431 fprintf (file, "---------------------------------------------------------\n");
432 fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
434 fprintf (file, "---------------------------------------------------------\n");
435 fprintf (file, "\n");
437 if (dfa_stats.num_phis)
438 fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n",
439 (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
440 dfa_stats.max_num_phi_args);
442 fprintf (file, "\n");
446 /* Dump DFA statistics on stderr. */
449 debug_dfa_stats (void)
451 dump_dfa_stats (stderr);
455 /* Collect DFA statistics and store them in the structure pointed to by
459 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
461 struct pointer_set_t *pset;
463 block_stmt_iterator i;
465 gcc_assert (dfa_stats_p);
467 memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
469 /* Walk all the trees in the function counting references. Start at
470 basic block 0, but don't stop at block boundaries. */
471 pset = pointer_set_create ();
473 for (i = bsi_start (BASIC_BLOCK (0)); !bsi_end_p (i); bsi_next (&i))
474 walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
477 pointer_set_destroy (pset);
482 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
484 dfa_stats_p->num_phis++;
485 dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
486 if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
487 dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
493 /* Callback for walk_tree to collect DFA statistics for a tree and its
497 collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
501 struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
505 switch (ann_type (t->common.ann))
509 dfa_stats_p->num_stmt_anns++;
510 dfa_stats_p->num_defs += NUM_SSA_OPERANDS (t, SSA_OP_DEF);
511 dfa_stats_p->num_uses += NUM_SSA_OPERANDS (t, SSA_OP_USE);
512 dfa_stats_p->num_v_may_defs += NUM_SSA_OPERANDS (t, SSA_OP_VMAYDEF);
513 dfa_stats_p->num_vuses += NUM_SSA_OPERANDS (t, SSA_OP_VUSE);
514 dfa_stats_p->num_v_must_defs +=
515 NUM_SSA_OPERANDS (t, SSA_OP_VMUSTDEF);
520 dfa_stats_p->num_var_anns++;
532 /*---------------------------------------------------------------------------
533 Miscellaneous helpers
534 ---------------------------------------------------------------------------*/
535 /* Callback for walk_tree. Used to collect variables referenced in
539 find_vars_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
541 /* If T is a regular variable that the optimizers are interested
542 in, add it to the list of variables. */
544 add_referenced_var (*tp, false);
546 /* Type, _DECL and constant nodes have no interesting children.
548 else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
555 /* Lookup UID in the referenced_vars hashtable and return the associated
556 variable or NULL if it is not there. */
559 referenced_var_lookup_if_exists (unsigned int uid)
561 struct int_tree_map *h, in;
563 h = htab_find_with_hash (referenced_vars, &in, uid);
569 /* Lookup UID in the referenced_vars hashtable and return the associated
573 referenced_var_lookup (unsigned int uid)
575 struct int_tree_map *h, in;
577 h = htab_find_with_hash (referenced_vars, &in, uid);
578 gcc_assert (h || uid == 0);
584 /* Insert the pair UID, TO into the referenced_vars hashtable. */
587 referenced_var_insert (unsigned int uid, tree to)
589 struct int_tree_map *h;
592 h = ggc_alloc (sizeof (struct int_tree_map));
595 loc = htab_find_slot_with_hash (referenced_vars, h, uid, INSERT);
596 /* This assert can only trigger if a variable with the same UID has been
598 gcc_assert ((*(struct int_tree_map **)loc) == NULL);
599 *(struct int_tree_map **) loc = h;
602 /* Add VAR to the list of dereferenced variables.
604 WALK_STATE contains a hash table used to avoid adding the same
605 variable more than once. Note that this function assumes that
606 VAR is a valid SSA variable. If WALK_STATE is NULL, no
607 duplicate checking is done. */
610 add_referenced_var (tree var, bool always)
614 v_ann = get_var_ann (var);
615 gcc_assert (DECL_P (var));
617 if (always || referenced_var_lookup_if_exists (DECL_UID (var)) == NULL_TREE)
619 /* This is the first time we find this variable, add it to the
620 REFERENCED_VARS array and annotate it with attributes that are
621 intrinsic to the variable. */
623 referenced_var_insert (DECL_UID (var), var);
625 /* Global variables are always call-clobbered. */
626 if (is_global_var (var))
627 mark_call_clobbered (var);
629 /* Scan DECL_INITIAL for pointer variables as they may contain
630 address arithmetic referencing the address of other
632 if (DECL_INITIAL (var)
633 /* Initializers of external variables are not useful to the
635 && !DECL_EXTERNAL (var)
636 /* It's not necessary to walk the initial value of non-constant
637 variables because it cannot be propagated by the
639 && (TREE_CONSTANT (var) || TREE_READONLY (var)))
640 walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0);
645 /* Return the virtual variable associated to the non-scalar variable VAR. */
648 get_virtual_var (tree var)
652 if (TREE_CODE (var) == SSA_NAME)
653 var = SSA_NAME_VAR (var);
655 while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
656 || handled_component_p (var))
657 var = TREE_OPERAND (var, 0);
659 /* Treating GIMPLE registers as virtual variables makes no sense.
660 Also complain if we couldn't extract a _DECL out of the original
662 gcc_assert (SSA_VAR_P (var));
663 gcc_assert (!is_gimple_reg (var));
668 /* Add a temporary variable to REFERENCED_VARS. This is similar to
669 add_referenced_var, but is used by passes that need to add new temps to
670 the REFERENCED_VARS array after the program has been scanned for
671 variables. The variable will just receive a new UID and be added
672 to the REFERENCED_VARS array without checking for duplicates. */
675 add_referenced_tmp_var (tree var)
677 add_referenced_var (var, true);
681 /* Mark all the non-SSA variables found in STMT's operands to be
682 processed by update_ssa. */
685 mark_new_vars_to_rename (tree stmt)
689 bitmap vars_in_vops_to_rename;
690 bool found_exposed_symbol = false;
691 int v_may_defs_before, v_may_defs_after;
692 int v_must_defs_before, v_must_defs_after;
694 if (TREE_CODE (stmt) == PHI_NODE)
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)