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 (default_def (var))
340 fprintf (file, ", default def: ");
341 print_generic_expr (file, default_def (var), 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
569 variable or NULL if it is not there. */
572 referenced_var_lookup_if_exists (unsigned int uid)
574 struct int_tree_map *h, in;
576 h = htab_find_with_hash (referenced_vars, &in, uid);
582 /* Lookup UID in the referenced_vars hashtable and return the associated
586 referenced_var_lookup (unsigned int uid)
588 struct int_tree_map *h, in;
590 h = htab_find_with_hash (referenced_vars, &in, uid);
591 gcc_assert (h || uid == 0);
597 /* Insert the pair UID, TO into the referenced_vars hashtable. */
600 referenced_var_insert (unsigned int uid, tree to)
602 struct int_tree_map *h;
605 h = ggc_alloc (sizeof (struct int_tree_map));
608 loc = htab_find_slot_with_hash (referenced_vars, h, uid, INSERT);
609 *(struct int_tree_map **) loc = h;
612 /* Add VAR to the list of dereferenced variables.
614 WALK_STATE contains a hash table used to avoid adding the same
615 variable more than once. Note that this function assumes that
616 VAR is a valid SSA variable. If WALK_STATE is NULL, no
617 duplicate checking is done. */
620 add_referenced_var (tree var, struct walk_state *walk_state)
625 v_ann = get_var_ann (var);
628 slot = htab_find_slot (walk_state->vars_found, (void *) var, INSERT);
632 if (slot == NULL || *slot == NULL)
634 /* This is the first time we find this variable, add it to the
635 REFERENCED_VARS array and annotate it with attributes that are
636 intrinsic to the variable. */
638 *slot = (void *) var;
640 referenced_var_insert (DECL_UID (var), var);
642 /* Global variables are always call-clobbered. */
643 if (is_global_var (var))
644 mark_call_clobbered (var);
646 /* Scan DECL_INITIAL for pointer variables as they may contain
647 address arithmetic referencing the address of other
649 if (DECL_INITIAL (var)
650 /* Initializers of external variables are not useful to the
652 && !DECL_EXTERNAL (var)
653 /* It's not necessary to walk the initial value of non-constant
654 public variables because it cannot be propagated by the
656 && (!TREE_PUBLIC (var) || !TREE_CONSTANT (var)))
657 walk_tree (&DECL_INITIAL (var), find_vars_r, walk_state, 0);
662 /* Return the virtual variable associated to the non-scalar variable VAR. */
665 get_virtual_var (tree var)
669 if (TREE_CODE (var) == SSA_NAME)
670 var = SSA_NAME_VAR (var);
672 while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
673 || handled_component_p (var))
674 var = TREE_OPERAND (var, 0);
676 /* Treating GIMPLE registers as virtual variables makes no sense.
677 Also complain if we couldn't extract a _DECL out of the original
679 gcc_assert (SSA_VAR_P (var));
680 gcc_assert (!is_gimple_reg (var));
685 /* Add a temporary variable to REFERENCED_VARS. This is similar to
686 add_referenced_var, but is used by passes that need to add new temps to
687 the REFERENCED_VARS array after the program has been scanned for
688 variables. The variable will just receive a new UID and be added
689 to the REFERENCED_VARS array without checking for duplicates. */
692 add_referenced_tmp_var (tree var)
694 add_referenced_var (var, NULL);
698 /* Mark all the non-SSA variables found in STMT's operands to be
699 processed by update_ssa. */
702 mark_new_vars_to_rename (tree stmt)
706 bitmap vars_in_vops_to_rename;
707 bool found_exposed_symbol = false;
708 int v_may_defs_before, v_may_defs_after;
709 int v_must_defs_before, v_must_defs_after;
711 vars_in_vops_to_rename = BITMAP_ALLOC (NULL);
713 /* Before re-scanning the statement for operands, mark the existing
714 virtual operands to be renamed again. We do this because when new
715 symbols are exposed, the virtual operands that were here before due to
716 aliasing will probably be removed by the call to get_stmt_operand.
717 Therefore, we need to flag them to be renamed beforehand.
719 We flag them in a separate bitmap because we don't really want to
720 rename them if there are not any newly exposed symbols in the
721 statement operands. */
722 v_may_defs_before = NUM_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF);
723 v_must_defs_before = NUM_SSA_OPERANDS (stmt, SSA_OP_VMUSTDEF);
725 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter,
726 SSA_OP_VMAYDEF | SSA_OP_VUSE | SSA_OP_VMUSTDEF)
729 val = SSA_NAME_VAR (val);
730 bitmap_set_bit (vars_in_vops_to_rename, DECL_UID (val));
733 /* Now force an operand re-scan on the statement and mark any newly
734 exposed variables. */
737 v_may_defs_after = NUM_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF);
738 v_must_defs_after = NUM_SSA_OPERANDS (stmt, SSA_OP_VMUSTDEF);
740 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_ALL_OPERANDS)
743 found_exposed_symbol = true;
744 mark_sym_for_renaming (val);
747 /* If we found any newly exposed symbols, or if there are fewer VDEF
748 operands in the statement, add the variables we had set in
749 VARS_IN_VOPS_TO_RENAME to VARS_TO_RENAME. We need to check for
750 vanishing VDEFs because in those cases, the names that were formerly
751 generated by this statement are not going to be available anymore. */
752 if (found_exposed_symbol
753 || v_may_defs_before > v_may_defs_after
754 || v_must_defs_before > v_must_defs_after)
755 mark_set_for_renaming (vars_in_vops_to_rename);
757 BITMAP_FREE (vars_in_vops_to_rename);
760 /* Find all variables within the gimplified statement that were not previously
761 visible to the function and add them to the referenced variables list. */
764 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
765 void *data ATTRIBUTE_UNUSED)
769 if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
771 add_referenced_tmp_var (t);
772 mark_sym_for_renaming (t);
775 if (IS_TYPE_OR_DECL_P (t))
782 find_new_referenced_vars (tree *stmt_p)
784 walk_tree (stmt_p, find_new_referenced_vars_1, NULL, NULL);
788 /* If REF is a COMPONENT_REF for a structure that can have sub-variables, and
789 we know where REF is accessing, return the variable in REF that has the
790 sub-variables. If the return value is not NULL, POFFSET will be the
791 offset, in bits, of REF inside the return value, and PSIZE will be the
792 size, in bits, of REF inside the return value. */
795 okay_component_ref_for_subvars (tree ref, unsigned HOST_WIDE_INT *poffset,
796 unsigned HOST_WIDE_INT *psize)
799 HOST_WIDE_INT bitsize;
800 HOST_WIDE_INT bitpos;
802 enum machine_mode mode;
806 gcc_assert (!SSA_VAR_P (ref));
808 *psize = (unsigned int) -1;
810 if (ref_contains_array_ref (ref))
812 ref = get_inner_reference (ref, &bitsize, &bitpos, &offset, &mode,
813 &unsignedp, &volatilep, false);
814 if (TREE_CODE (ref) == INDIRECT_REF)
816 else if (offset == NULL && bitsize != -1 && SSA_VAR_P (ref))
820 if (get_subvars_for_var (ref) != NULL)
823 else if (SSA_VAR_P (ref))
825 if (get_subvars_for_var (ref) != NULL)