X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-dfa.c;h=df0be2df134a54b11af9672de482a5be1f485ca8;hb=83204f13a20e4a7e55d5b2763892298b711836f2;hp=5af9753d5c683b2bc582098f69d74f1133204a7c;hpb=20168cf29dbef684cb40d4b196bc3df39d8e34ee;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-dfa.c b/gcc/tree-dfa.c index 5af9753d5c6..df0be2df134 100644 --- a/gcc/tree-dfa.c +++ b/gcc/tree-dfa.c @@ -1,12 +1,13 @@ /* Data flow functions for trees. - Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. + Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008 Free Software + Foundation, Inc. Contributed by Diego Novillo This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2, or (at your option) +the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, @@ -15,9 +16,8 @@ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING. If not, write to -the Free Software Foundation, 51 Franklin Street, Fifth Floor, -Boston, MA 02110-1301, USA. */ +along with GCC; see the file COPYING3. If not see +. */ #include "config.h" #include "system.h" @@ -39,7 +39,7 @@ Boston, MA 02110-1301, USA. */ #include "function.h" #include "diagnostic.h" #include "tree-dump.h" -#include "tree-gimple.h" +#include "gimple.h" #include "tree-flow.h" #include "tree-inline.h" #include "tree-pass.h" @@ -52,44 +52,20 @@ Boston, MA 02110-1301, USA. */ /* Counters used to display DFA and SSA statistics. */ struct dfa_stats_d { - long num_stmt_anns; long num_var_anns; long num_defs; long num_uses; long num_phis; long num_phi_args; - int max_num_phi_args; - long num_v_may_defs; + size_t max_num_phi_args; + long num_vdefs; long num_vuses; - long num_v_must_defs; -}; - - -/* State information for find_vars_r. */ -struct walk_state -{ - /* Hash table used to avoid adding the same variable more than once. */ - htab_t vars_found; }; /* Local functions. */ static void collect_dfa_stats (struct dfa_stats_d *); -static tree collect_dfa_stats_r (tree *, int *, void *); static tree find_vars_r (tree *, int *, void *); -static void add_referenced_var (tree, struct walk_state *); - - -/* Global declarations. */ - -/* Array of all variables referenced in the function. */ -htab_t referenced_vars; - -/* Default definition for this symbols. If set for symbol, it - means that the first reference to this variable in the function is a - USE or a VUSE. In those cases, the SSA renamer creates an SSA name - for this variable with an empty defining statement. */ -htab_t default_defs; /*--------------------------------------------------------------------------- @@ -103,30 +79,44 @@ htab_t default_defs; various attributes for each variable used by alias analysis and the optimizer. */ -static void +static unsigned int find_referenced_vars (void) { - htab_t vars_found; basic_block bb; - block_stmt_iterator si; - struct walk_state walk_state; - - vars_found = htab_create (50, htab_hash_pointer, htab_eq_pointer, NULL); - memset (&walk_state, 0, sizeof (walk_state)); - walk_state.vars_found = vars_found; + gimple_stmt_iterator si; FOR_EACH_BB (bb) - for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) - { - tree *stmt_p = bsi_stmt_ptr (si); - walk_tree (stmt_p, find_vars_r, &walk_state, NULL); - } + { + for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) + { + size_t i; + gimple stmt = gsi_stmt (si); + for (i = 0; i < gimple_num_ops (stmt); i++) + walk_tree (gimple_op_ptr (stmt, i), find_vars_r, NULL, NULL); + } - htab_delete (vars_found); + for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) + { + gimple phi = gsi_stmt (si); + size_t i, len = gimple_phi_num_args (phi); + + walk_tree (gimple_phi_result_ptr (phi), find_vars_r, NULL, NULL); + + for (i = 0; i < len; i++) + { + tree arg = gimple_phi_arg_def (phi, i); + walk_tree (&arg, find_vars_r, NULL, NULL); + } + } + } + + return 0; } -struct tree_opt_pass pass_referenced_vars = +struct gimple_opt_pass pass_referenced_vars = { + { + GIMPLE_PASS, NULL, /* name */ NULL, /* gate */ find_referenced_vars, /* execute */ @@ -137,9 +127,9 @@ struct tree_opt_pass pass_referenced_vars = PROP_gimple_leh | PROP_cfg, /* properties_required */ PROP_referenced_vars, /* properties_provided */ 0, /* properties_destroyed */ - 0, /* todo_flags_start */ - 0, /* todo_flags_finish */ - 0 /* letter */ + TODO_dump_func, /* todo_flags_start */ + TODO_dump_func /* todo_flags_finish */ + } }; @@ -155,14 +145,11 @@ create_var_ann (tree t) gcc_assert (t); gcc_assert (DECL_P (t)); - gcc_assert (!t->common.ann || t->common.ann->common.type == VAR_ANN); - - ann = GGC_NEW (struct var_ann_d); - memset ((void *) ann, 0, sizeof (*ann)); + gcc_assert (!t->base.ann || t->base.ann->common.type == VAR_ANN); + ann = GGC_CNEW (struct var_ann_d); ann->common.type = VAR_ANN; - - t->common.ann = (tree_ann_t) ann; + t->base.ann = (tree_ann_t) ann; return ann; } @@ -176,56 +163,52 @@ create_function_ann (tree t) gcc_assert (t); gcc_assert (TREE_CODE (t) == FUNCTION_DECL); - gcc_assert (!t->common.ann || t->common.ann->common.type == FUNCTION_ANN); + gcc_assert (!t->base.ann || t->base.ann->common.type == FUNCTION_ANN); - ann = ggc_alloc (sizeof (*ann)); + ann = (function_ann_t) ggc_alloc (sizeof (*ann)); memset ((void *) ann, 0, sizeof (*ann)); ann->common.type = FUNCTION_ANN; - t->common.ann = (tree_ann_t) ann; + t->base.ann = (tree_ann_t) ann; return ann; } -/* Create a new annotation for a statement node T. */ +/* Renumber all of the gimple stmt uids. */ -stmt_ann_t -create_stmt_ann (tree t) +void +renumber_gimple_stmt_uids (void) { - stmt_ann_t ann; - - gcc_assert (is_gimple_stmt (t)); - gcc_assert (!t->common.ann || t->common.ann->common.type == STMT_ANN); - - ann = GGC_NEW (struct stmt_ann_d); - memset ((void *) ann, 0, sizeof (*ann)); - - ann->common.type = STMT_ANN; - - /* Since we just created the annotation, mark the statement modified. */ - ann->modified = true; - - t->common.ann = (tree_ann_t) ann; + basic_block bb; - return ann; + set_gimple_stmt_max_uid (cfun, 0); + FOR_ALL_BB (bb) + { + gimple_stmt_iterator bsi; + for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) + { + gimple stmt = gsi_stmt (bsi); + gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun)); + } + } } /* Create a new annotation for a tree T. */ -tree_ann_t -create_tree_ann (tree t) +tree_ann_common_t +create_tree_common_ann (tree t) { - tree_ann_t ann; + tree_ann_common_t ann; gcc_assert (t); - gcc_assert (!t->common.ann || t->common.ann->common.type == TREE_ANN_COMMON); + gcc_assert (!t->base.ann || t->base.ann->common.type == TREE_ANN_COMMON); - ann = GGC_NEW (union tree_ann_d); - memset ((void *) ann, 0, sizeof (*ann)); + ann = GGC_CNEW (struct tree_ann_common_d); - ann->common.type = TREE_ANN_COMMON; - t->common.ann = ann; + ann->type = TREE_ANN_COMMON; + ann->rn = -1; + t->base.ann = (tree_ann_t) ann; return ann; } @@ -236,9 +219,14 @@ tree make_rename_temp (tree type, const char *prefix) { tree t = create_tmp_var (type, prefix); - if (referenced_vars) + + if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE + || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE) + DECL_GIMPLE_REG_P (t) = 1; + + if (gimple_referenced_vars (cfun)) { - add_referenced_tmp_var (t); + add_referenced_var (t); mark_sym_for_renaming (t); } @@ -280,37 +268,6 @@ debug_referenced_vars (void) } -/* Dump sub-variables for VAR to FILE. */ - -void -dump_subvars_for (FILE *file, tree var) -{ - subvar_t sv = get_subvars_for_var (var); - - if (!sv) - return; - - fprintf (file, "{ "); - - for (; sv; sv = sv->next) - { - print_generic_expr (file, sv->var, dump_flags); - fprintf (file, " "); - } - - fprintf (file, "}"); -} - - -/* Dumb sub-variables for VAR to stderr. */ - -void -debug_subvars_for (tree var) -{ - dump_subvars_for (stderr, var); -} - - /* Dump variable VAR and its may-aliases to FILE. */ void @@ -335,20 +292,17 @@ dump_variable (FILE *file, tree var) ann = var_ann (var); - fprintf (file, ", UID %u", (unsigned) DECL_UID (var)); + fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var)); fprintf (file, ", "); print_generic_expr (file, TREE_TYPE (var), dump_flags); - if (ann && ann->type_mem_tag) + if (ann && ann->symbol_mem_tag) { - fprintf (file, ", type memory tag: "); - print_generic_expr (file, ann->type_mem_tag, dump_flags); + fprintf (file, ", symbol memory tag: "); + print_generic_expr (file, ann->symbol_mem_tag, dump_flags); } - if (ann && ann->is_alias_tag) - fprintf (file, ", is an alias tag"); - if (TREE_ADDRESSABLE (var)) fprintf (file, ", is addressable"); @@ -358,25 +312,70 @@ dump_variable (FILE *file, tree var) if (TREE_THIS_VOLATILE (var)) fprintf (file, ", is volatile"); + dump_mem_sym_stats_for_var (file, var); + if (is_call_clobbered (var)) - fprintf (file, ", call clobbered"); + { + const char *s = ""; + var_ann_t va = var_ann (var); + unsigned int escape_mask = va->escape_mask; + + fprintf (file, ", call clobbered"); + fprintf (file, " ("); + if (escape_mask & ESCAPE_STORED_IN_GLOBAL) + { fprintf (file, "%sstored in global", s); s = ", "; } + if (escape_mask & ESCAPE_TO_ASM) + { fprintf (file, "%sgoes through ASM", s); s = ", "; } + if (escape_mask & ESCAPE_TO_CALL) + { fprintf (file, "%spassed to call", s); s = ", "; } + if (escape_mask & ESCAPE_BAD_CAST) + { fprintf (file, "%sbad cast", s); s = ", "; } + if (escape_mask & ESCAPE_TO_RETURN) + { fprintf (file, "%sreturned from func", s); s = ", "; } + if (escape_mask & ESCAPE_TO_PURE_CONST) + { fprintf (file, "%spassed to pure/const", s); s = ", "; } + if (escape_mask & ESCAPE_IS_GLOBAL) + { fprintf (file, "%sis global var", s); s = ", "; } + if (escape_mask & ESCAPE_IS_PARM) + { fprintf (file, "%sis incoming pointer", s); s = ", "; } + if (escape_mask & ESCAPE_UNKNOWN) + { fprintf (file, "%sunknown escape", s); s = ", "; } + fprintf (file, ")"); + } - if (default_def (var)) + if (ann->noalias_state == NO_ALIAS) + fprintf (file, ", NO_ALIAS (does not alias other NO_ALIAS symbols)"); + else if (ann->noalias_state == NO_ALIAS_GLOBAL) + fprintf (file, ", NO_ALIAS_GLOBAL (does not alias other NO_ALIAS symbols" + " and global vars)"); + else if (ann->noalias_state == NO_ALIAS_ANYTHING) + fprintf (file, ", NO_ALIAS_ANYTHING (does not alias any other symbols)"); + + if (gimple_default_def (cfun, var)) { fprintf (file, ", default def: "); - print_generic_expr (file, default_def (var), dump_flags); + print_generic_expr (file, gimple_default_def (cfun, var), dump_flags); } - if (may_aliases (var)) + if (MTAG_P (var) && may_aliases (var)) { fprintf (file, ", may aliases: "); dump_may_aliases_for (file, var); } - if (get_subvars_for_var (var)) + if (!is_gimple_reg (var)) { - fprintf (file, ", sub-vars: "); - dump_subvars_for (file, var); + if (memory_partition (var)) + { + fprintf (file, ", belongs to partition: "); + print_generic_expr (file, memory_partition (var), dump_flags); + } + + if (TREE_CODE (var) == MEMORY_PARTITION_TAG) + { + fprintf (file, ", partition symbols: "); + dump_decl_set (file, MPT_SYMBOLS (var)); + } } fprintf (file, "\n"); @@ -420,11 +419,6 @@ dump_dfa_stats (FILE *file) fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars, SCALE (size), LABEL (size)); - size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d); - total += size; - fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns, - SCALE (size), LABEL (size)); - size = dfa_stats.num_var_anns * sizeof (struct var_ann_d); total += size; fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns, @@ -445,17 +439,12 @@ dump_dfa_stats (FILE *file) fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses, SCALE (size), LABEL (size)); - size = dfa_stats.num_v_may_defs * sizeof (tree *); - total += size; - fprintf (file, fmt_str_1, "V_MAY_DEF operands", dfa_stats.num_v_may_defs, - SCALE (size), LABEL (size)); - - size = dfa_stats.num_v_must_defs * sizeof (tree *); + size = dfa_stats.num_vdefs * sizeof (tree *); total += size; - fprintf (file, fmt_str_1, "V_MUST_DEF operands", dfa_stats.num_v_must_defs, + fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs, SCALE (size), LABEL (size)); - size = dfa_stats.num_phis * sizeof (struct tree_phi_node); + size = dfa_stats.num_phis * sizeof (struct gimple_statement_phi); total += size; fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis, SCALE (size), LABEL (size)); @@ -472,9 +461,9 @@ dump_dfa_stats (FILE *file) fprintf (file, "\n"); if (dfa_stats.num_phis) - fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n", + fprintf (file, "Average number of arguments per PHI node: %.1f (max: %ld)\n", (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis, - dfa_stats.max_num_phi_args); + (long) dfa_stats.max_num_phi_args); fprintf (file, "\n"); } @@ -493,77 +482,44 @@ debug_dfa_stats (void) DFA_STATS_P. */ static void -collect_dfa_stats (struct dfa_stats_d *dfa_stats_p) +collect_dfa_stats (struct dfa_stats_d *dfa_stats_p ATTRIBUTE_UNUSED) { - struct pointer_set_t *pset; basic_block bb; - block_stmt_iterator i; + referenced_var_iterator vi; + tree var; gcc_assert (dfa_stats_p); memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d)); - /* Walk all the trees in the function counting references. Start at - basic block NUM_FIXED_BLOCKS, but don't stop at block boundaries. */ - pset = pointer_set_create (); - - for (i = bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS)); - !bsi_end_p (i); bsi_next (&i)) - walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p, - pset); - - pointer_set_destroy (pset); + /* Count all the variable annotations. */ + FOR_EACH_REFERENCED_VAR (var, vi) + if (var_ann (var)) + dfa_stats_p->num_var_anns++; + /* Walk all the statements in the function counting references. */ FOR_EACH_BB (bb) { - tree phi; - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + gimple_stmt_iterator si; + + for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) { + gimple phi = gsi_stmt (si); dfa_stats_p->num_phis++; - dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi); - if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args) - dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi); + dfa_stats_p->num_phi_args += gimple_phi_num_args (phi); + if (gimple_phi_num_args (phi) > dfa_stats_p->max_num_phi_args) + dfa_stats_p->max_num_phi_args = gimple_phi_num_args (phi); } - } -} - - -/* Callback for walk_tree to collect DFA statistics for a tree and its - children. */ - -static tree -collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, - void *data) -{ - tree t = *tp; - struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data; - if (t->common.ann) - { - switch (ann_type (t->common.ann)) + for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) { - case STMT_ANN: - { - dfa_stats_p->num_stmt_anns++; - dfa_stats_p->num_defs += NUM_SSA_OPERANDS (t, SSA_OP_DEF); - dfa_stats_p->num_uses += NUM_SSA_OPERANDS (t, SSA_OP_USE); - dfa_stats_p->num_v_may_defs += NUM_SSA_OPERANDS (t, SSA_OP_VMAYDEF); - dfa_stats_p->num_vuses += NUM_SSA_OPERANDS (t, SSA_OP_VUSE); - dfa_stats_p->num_v_must_defs += - NUM_SSA_OPERANDS (t, SSA_OP_VMUSTDEF); - break; - } - - case VAR_ANN: - dfa_stats_p->num_var_anns++; - break; - - default: - break; + gimple stmt = gsi_stmt (si); + dfa_stats_p->num_defs += NUM_SSA_OPERANDS (stmt, SSA_OP_DEF); + dfa_stats_p->num_uses += NUM_SSA_OPERANDS (stmt, SSA_OP_USE); + dfa_stats_p->num_vdefs += NUM_SSA_OPERANDS (stmt, SSA_OP_VDEF); + dfa_stats_p->num_vuses += NUM_SSA_OPERANDS (stmt, SSA_OP_VUSE); } } - - return NULL; } @@ -574,14 +530,17 @@ collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, the function. */ static tree -find_vars_r (tree *tp, int *walk_subtrees, void *data) +find_vars_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED) { - struct walk_state *walk_state = (struct walk_state *) data; + /* If we are reading the lto info back in, we need to rescan the + referenced vars. */ + if (TREE_CODE (*tp) == SSA_NAME) + add_referenced_var (SSA_NAME_VAR (*tp)); /* If T is a regular variable that the optimizers are interested in, add it to the list of variables. */ - if (SSA_VAR_P (*tp)) - add_referenced_var (*tp, walk_state); + else if (SSA_VAR_P (*tp)) + add_referenced_var (*tp); /* Type, _DECL and constant nodes have no interesting children. Ignore them. */ @@ -591,65 +550,58 @@ find_vars_r (tree *tp, int *walk_subtrees, void *data) return NULL_TREE; } - -/* Lookup UID in the referenced_vars hashtable and return the associated - variable or NULL if it is not there. */ - -tree -referenced_var_lookup_if_exists (unsigned int uid) -{ - struct int_tree_map *h, in; - in.uid = uid; - h = (struct int_tree_map *) htab_find_with_hash (referenced_vars, &in, uid); - if (h) - return h->to; - return NULL_TREE; -} - /* Lookup UID in the referenced_vars hashtable and return the associated variable. */ tree referenced_var_lookup (unsigned int uid) { - struct int_tree_map *h, in; + tree h; + struct tree_decl_minimal in; in.uid = uid; - h = (struct int_tree_map *) htab_find_with_hash (referenced_vars, &in, uid); + h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid); gcc_assert (h || uid == 0); - if (h) - return h->to; - return NULL_TREE; + return h; } -/* Insert the pair UID, TO into the referenced_vars hashtable. */ +/* Check if TO is in the referenced_vars hash table and insert it if not. + Return true if it required insertion. */ -static void -referenced_var_insert (unsigned int uid, tree to) +bool +referenced_var_check_and_insert (tree to) { - struct int_tree_map *h; - void **loc; + tree h, *loc; + struct tree_decl_minimal in; + unsigned int uid = DECL_UID (to); - h = GGC_NEW (struct int_tree_map); - h->uid = uid; - h->to = to; - loc = htab_find_slot_with_hash (referenced_vars, h, uid, INSERT); - *(struct int_tree_map **) loc = h; + in.uid = uid; + h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid); + if (h) + { + /* DECL_UID has already been entered in the table. Verify that it is + the same entry as TO. See PR 27793. */ + gcc_assert (h == to); + return false; + } + + loc = (tree *) htab_find_slot_with_hash (gimple_referenced_vars (cfun), + &in, uid, INSERT); + *loc = to; + return true; } /* Lookup VAR UID in the default_defs hashtable and return the associated variable. */ tree -default_def (tree var) +gimple_default_def (struct function *fn, tree var) { - struct int_tree_map *h, in; + struct tree_decl_minimal ind; + struct tree_ssa_name in; gcc_assert (SSA_VAR_P (var)); - in.uid = DECL_UID (var); - h = (struct int_tree_map *) htab_find_with_hash (default_defs, &in, - DECL_UID (var)); - if (h) - return h->to; - return NULL_TREE; + in.var = (tree)&ind; + ind.uid = DECL_UID (var); + return (tree) htab_find_with_hash (DEFAULT_DEFS (fn), &in, DECL_UID (var)); } /* Insert the pair VAR's UID, DEF into the default_defs hashtable. */ @@ -657,86 +609,99 @@ default_def (tree var) void set_default_def (tree var, tree def) { - struct int_tree_map in; - struct int_tree_map *h; + struct tree_decl_minimal ind; + struct tree_ssa_name in; void **loc; gcc_assert (SSA_VAR_P (var)); - in.uid = DECL_UID (var); - if (!def && default_def (var)) + in.var = (tree)&ind; + ind.uid = DECL_UID (var); + if (!def) { - loc = htab_find_slot_with_hash (default_defs, &in, DECL_UID (var), INSERT); - htab_remove_elt (default_defs, *loc); + loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in, + DECL_UID (var), INSERT); + gcc_assert (*loc); + htab_remove_elt (DEFAULT_DEFS (cfun), *loc); return; } - gcc_assert (TREE_CODE (def) == SSA_NAME); - loc = htab_find_slot_with_hash (default_defs, &in, DECL_UID (var), INSERT); + gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var); + loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in, + DECL_UID (var), INSERT); + /* Default definition might be changed by tail call optimization. */ - if (!*loc) - { - h = GGC_NEW (struct int_tree_map); - h->uid = DECL_UID (var); - h->to = def; - *(struct int_tree_map **) loc = h; - } - else - { - h = (struct int_tree_map *) *loc; - h->to = def; - } -} + if (*loc) + SSA_NAME_IS_DEFAULT_DEF (*(tree *) loc) = false; + *(tree *) loc = def; -/* Add VAR to the list of dereferenced variables. + /* Mark DEF as the default definition for VAR. */ + SSA_NAME_IS_DEFAULT_DEF (def) = true; +} - WALK_STATE contains a hash table used to avoid adding the same - variable more than once. Note that this function assumes that - VAR is a valid SSA variable. If WALK_STATE is NULL, no - duplicate checking is done. */ +/* Add VAR to the list of referenced variables if it isn't already there. */ -static void -add_referenced_var (tree var, struct walk_state *walk_state) +void +add_referenced_var (tree var) { - void **slot; var_ann_t v_ann; v_ann = get_var_ann (var); - - if (walk_state) - slot = htab_find_slot (walk_state->vars_found, (void *) var, INSERT); - else - slot = NULL; - - if (slot == NULL || *slot == NULL) + gcc_assert (DECL_P (var)); + + /* Insert VAR into the referenced_vars has table if it isn't present. */ + if (referenced_var_check_and_insert (var)) { - /* This is the first time we find this variable, add it to the - REFERENCED_VARS array and annotate it with attributes that are - intrinsic to the variable. */ - if (slot) - *slot = (void *) var; + /* This is the first time we found this variable, annotate it with + attributes that are intrinsic to the variable. */ - referenced_var_insert (DECL_UID (var), var); - - /* Global variables are always call-clobbered. */ - if (is_global_var (var)) - mark_call_clobbered (var); - /* Tag's don't have DECL_INITIAL. */ if (MTAG_P (var)) return; - + /* Scan DECL_INITIAL for pointer variables as they may contain address arithmetic referencing the address of other - variables. */ + variables. + Even non-constant initializers need to be walked, because + IPA passes might prove that their are invariant later on. */ if (DECL_INITIAL (var) /* Initializers of external variables are not useful to the optimizers. */ - && !DECL_EXTERNAL (var) - /* It's not necessary to walk the initial value of non-constant - variables because it cannot be propagated by the - optimizers. */ - && (TREE_CONSTANT (var) || TREE_READONLY (var))) - walk_tree (&DECL_INITIAL (var), find_vars_r, walk_state, 0); + && !DECL_EXTERNAL (var)) + walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0); + } +} + +/* Remove VAR from the list. */ + +void +remove_referenced_var (tree var) +{ + var_ann_t v_ann; + struct tree_decl_minimal in; + void **loc; + unsigned int uid = DECL_UID (var); + + clear_call_clobbered (var); + bitmap_clear_bit (gimple_call_used_vars (cfun), uid); + if ((v_ann = var_ann (var))) + { + /* Preserve var_anns of globals, but clear their alias info. */ + if (MTAG_P (var) + || (!TREE_STATIC (var) && !DECL_EXTERNAL (var))) + { + ggc_free (v_ann); + var->base.ann = NULL; + } + else + { + v_ann->mpt = NULL_TREE; + v_ann->symbol_mem_tag = NULL_TREE; + } } + gcc_assert (DECL_P (var)); + in.uid = uid; + loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid, + NO_INSERT); + htab_clear_slot (gimple_referenced_vars (cfun), loc); } @@ -763,86 +728,30 @@ get_virtual_var (tree var) return var; } -/* Add a temporary variable to REFERENCED_VARS. This is similar to - add_referenced_var, but is used by passes that need to add new temps to - the REFERENCED_VARS array after the program has been scanned for - variables. The variable will just receive a new UID and be added - to the REFERENCED_VARS array without checking for duplicates. */ - -void -add_referenced_tmp_var (tree var) -{ - add_referenced_var (var, NULL); -} - - -/* Mark all the non-SSA variables found in STMT's operands to be - processed by update_ssa. */ +/* Mark all the naked symbols in STMT for SSA renaming. + + NOTE: This function should only be used for brand new statements. + If the caller is modifying an existing statement, it should use the + combination push_stmt_changes/pop_stmt_changes. */ void -mark_new_vars_to_rename (tree stmt) +mark_symbols_for_renaming (gimple stmt) { + tree op; ssa_op_iter iter; - tree val; - bitmap vars_in_vops_to_rename; - bool found_exposed_symbol = false; - int v_may_defs_before, v_may_defs_after; - int v_must_defs_before, v_must_defs_after; - - if (TREE_CODE (stmt) == PHI_NODE) - return; - - vars_in_vops_to_rename = BITMAP_ALLOC (NULL); - - /* Before re-scanning the statement for operands, mark the existing - virtual operands to be renamed again. We do this because when new - symbols are exposed, the virtual operands that were here before due to - aliasing will probably be removed by the call to get_stmt_operand. - Therefore, we need to flag them to be renamed beforehand. - - We flag them in a separate bitmap because we don't really want to - rename them if there are not any newly exposed symbols in the - statement operands. */ - v_may_defs_before = NUM_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF); - v_must_defs_before = NUM_SSA_OPERANDS (stmt, SSA_OP_VMUSTDEF); - - FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, - SSA_OP_VMAYDEF | SSA_OP_VUSE | SSA_OP_VMUSTDEF) - { - if (!DECL_P (val)) - val = SSA_NAME_VAR (val); - bitmap_set_bit (vars_in_vops_to_rename, DECL_UID (val)); - } - /* Now force an operand re-scan on the statement and mark any newly - exposed variables. */ update_stmt (stmt); - v_may_defs_after = NUM_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF); - v_must_defs_after = NUM_SSA_OPERANDS (stmt, SSA_OP_VMUSTDEF); - - FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_ALL_OPERANDS) - if (DECL_P (val)) - { - found_exposed_symbol = true; - mark_sym_for_renaming (val); - } - - /* If we found any newly exposed symbols, or if there are fewer VDEF - operands in the statement, add the variables we had set in - VARS_IN_VOPS_TO_RENAME to VARS_TO_RENAME. We need to check for - vanishing VDEFs because in those cases, the names that were formerly - generated by this statement are not going to be available anymore. */ - if (found_exposed_symbol - || v_may_defs_before > v_may_defs_after - || v_must_defs_before > v_must_defs_after) - mark_set_for_renaming (vars_in_vops_to_rename); - - BITMAP_FREE (vars_in_vops_to_rename); + /* Mark all the operands for renaming. */ + FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS) + if (DECL_P (op)) + mark_sym_for_renaming (op); } -/* Find all variables within the gimplified statement that were not previously - visible to the function and add them to the referenced variables list. */ + +/* Find all variables within the gimplified statement that were not + previously visible to the function and add them to the referenced + variables list. */ static tree find_new_referenced_vars_1 (tree *tp, int *walk_subtrees, @@ -852,7 +761,7 @@ find_new_referenced_vars_1 (tree *tp, int *walk_subtrees, if (TREE_CODE (t) == VAR_DECL && !var_ann (t)) { - add_referenced_tmp_var (t); + add_referenced_var (t); mark_sym_for_renaming (t); } @@ -862,14 +771,17 @@ find_new_referenced_vars_1 (tree *tp, int *walk_subtrees, return NULL; } + +/* Find any new referenced variables in STMT. */ + void -find_new_referenced_vars (tree *stmt_p) +find_new_referenced_vars (gimple stmt) { - walk_tree (stmt_p, find_new_referenced_vars_1, NULL, NULL); + walk_gimple_op (stmt, find_new_referenced_vars_1, NULL); } -/* If REF is a handled component reference for a structure, return the +/* If EXP is a handled component reference for a structure, return the base variable. The access range is delimited by bit positions *POFFSET and *POFFSET + *PMAX_SIZE. The access size is *PSIZE bits. If either *PSIZE or *PMAX_SIZE is -1, they could not be determined. If *PSIZE @@ -883,7 +795,8 @@ get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset, HOST_WIDE_INT bitsize = -1; HOST_WIDE_INT maxsize = -1; tree size_tree = NULL_TREE; - tree bit_offset = bitsize_zero_node; + HOST_WIDE_INT bit_offset = 0; + bool seen_variable_array_ref = false; gcc_assert (!SSA_VAR_P (exp)); @@ -919,8 +832,7 @@ get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset, switch (TREE_CODE (exp)) { case BIT_FIELD_REF: - bit_offset = size_binop (PLUS_EXPR, bit_offset, - TREE_OPERAND (exp, 2)); + bit_offset += tree_low_cst (TREE_OPERAND (exp, 2), 0); break; case COMPONENT_REF: @@ -930,27 +842,20 @@ get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset, if (this_offset && TREE_CODE (this_offset) == INTEGER_CST) { - this_offset = size_binop (MULT_EXPR, - fold_convert (bitsizetype, - this_offset), - bitsize_unit_node); - bit_offset = size_binop (PLUS_EXPR, - bit_offset, this_offset); - bit_offset = size_binop (PLUS_EXPR, bit_offset, - DECL_FIELD_BIT_OFFSET (field)); + HOST_WIDE_INT hthis_offset = tree_low_cst (this_offset, 0); + + hthis_offset *= BITS_PER_UNIT; + bit_offset += hthis_offset; + bit_offset += tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 0); } else { tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0))); /* We need to adjust maxsize to the whole structure bitsize. - But we can subtract any constant offset seen sofar, + But we can subtract any constant offset seen so far, because that would get us out of the structure otherwise. */ - if (maxsize != -1 - && csize && host_integerp (csize, 1)) - { - maxsize = (TREE_INT_CST_LOW (csize) - - TREE_INT_CST_LOW (bit_offset)); - } + if (maxsize != -1 && csize && host_integerp (csize, 1)) + maxsize = TREE_INT_CST_LOW (csize) - bit_offset; else maxsize = -1; } @@ -964,32 +869,37 @@ get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset, tree low_bound = array_ref_low_bound (exp); tree unit_size = array_ref_element_size (exp); - if (! integer_zerop (low_bound)) - index = fold_build2 (MINUS_EXPR, TREE_TYPE (index), - index, low_bound); - index = size_binop (MULT_EXPR, - fold_convert (sizetype, index), unit_size); - if (TREE_CODE (index) == INTEGER_CST) + /* If the resulting bit-offset is constant, track it. */ + if (host_integerp (index, 0) + && host_integerp (low_bound, 0) + && host_integerp (unit_size, 1)) { - index = size_binop (MULT_EXPR, - fold_convert (bitsizetype, index), - bitsize_unit_node); - bit_offset = size_binop (PLUS_EXPR, bit_offset, index); + HOST_WIDE_INT hindex = tree_low_cst (index, 0); + + hindex -= tree_low_cst (low_bound, 0); + hindex *= tree_low_cst (unit_size, 1); + hindex *= BITS_PER_UNIT; + bit_offset += hindex; + + /* An array ref with a constant index up in the structure + hierarchy will constrain the size of any variable array ref + lower in the access hierarchy. */ + seen_variable_array_ref = false; } else { tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0))); /* We need to adjust maxsize to the whole array bitsize. - But we can subtract any constant offset seen sofar, + But we can subtract any constant offset seen so far, because that would get us outside of the array otherwise. */ - if (maxsize != -1 - && asize && host_integerp (asize, 1)) - { - maxsize = (TREE_INT_CST_LOW (asize) - - TREE_INT_CST_LOW (bit_offset)); - } + if (maxsize != -1 && asize && host_integerp (asize, 1)) + maxsize = TREE_INT_CST_LOW (asize) - bit_offset; else maxsize = -1; + + /* Remember that we have seen an array ref with a variable + index. */ + seen_variable_array_ref = true; } } break; @@ -998,8 +908,7 @@ get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset, break; case IMAGPART_EXPR: - bit_offset = size_binop (PLUS_EXPR, bit_offset, - bitsize_int (bitsize)); + bit_offset += bitsize; break; case VIEW_CONVERT_EXPR: @@ -1014,12 +923,285 @@ get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset, } done: + /* We need to deal with variable arrays ending structures such as + struct { int length; int a[1]; } x; x.a[d] + struct { struct { int a; int b; } a[1]; } x; x.a[d].a + struct { struct { int a[1]; } a[1]; } x; x.a[0][d], x.a[d][0] + where we do not know maxsize for variable index accesses to + the array. The simplest way to conservatively deal with this + is to punt in the case that offset + maxsize reaches the + base type boundary. */ + if (seen_variable_array_ref + && maxsize != -1 + && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1) + && bit_offset + maxsize + == (signed)TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp)))) + maxsize = -1; + /* ??? Due to negative offsets in ARRAY_REF we can end up with negative bit_offset here. We might want to store a zero offset in this case. */ - *poffset = TREE_INT_CST_LOW (bit_offset); + *poffset = bit_offset; *psize = bitsize; *pmax_size = maxsize; return exp; } + +/* Returns true if STMT references an SSA_NAME that has + SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false. */ + +bool +stmt_references_abnormal_ssa_name (gimple stmt) +{ + ssa_op_iter oi; + use_operand_p use_p; + + FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE) + { + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p))) + return true; + } + + return false; +} + +/* Return true, if the two memory references REF1 and REF2 may alias. */ + +bool +refs_may_alias_p (tree ref1, tree ref2) +{ + tree base1, base2; + HOST_WIDE_INT offset1 = 0, offset2 = 0; + HOST_WIDE_INT size1 = -1, size2 = -1; + HOST_WIDE_INT max_size1 = -1, max_size2 = -1; + bool strict_aliasing_applies; + + gcc_assert ((SSA_VAR_P (ref1) + || handled_component_p (ref1) + || INDIRECT_REF_P (ref1) + || TREE_CODE (ref1) == TARGET_MEM_REF) + && (SSA_VAR_P (ref2) + || handled_component_p (ref2) + || INDIRECT_REF_P (ref2) + || TREE_CODE (ref2) == TARGET_MEM_REF)); + + /* Defer to TBAA if possible. */ + if (flag_strict_aliasing + && !alias_sets_conflict_p (get_alias_set (ref1), get_alias_set (ref2))) + return false; + + /* Decompose the references into their base objects and the access. */ + base1 = ref1; + if (handled_component_p (ref1)) + base1 = get_ref_base_and_extent (ref1, &offset1, &size1, &max_size1); + base2 = ref2; + if (handled_component_p (ref2)) + base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &max_size2); + + /* If both references are based on different variables, they cannot alias. + If both references are based on the same variable, they cannot alias if + the accesses do not overlap. */ + if (SSA_VAR_P (base1) + && SSA_VAR_P (base2)) + { + if (!operand_equal_p (base1, base2, 0)) + return false; + return ranges_overlap_p (offset1, max_size1, offset2, max_size2); + } + + /* If one base is a ref-all pointer weird things are allowed. */ + strict_aliasing_applies = (flag_strict_aliasing + && (!INDIRECT_REF_P (base1) + || get_alias_set (base1) != 0) + && (!INDIRECT_REF_P (base2) + || get_alias_set (base2) != 0)); + + /* If strict aliasing applies the only way to access a scalar variable + is through a pointer dereference or through a union (gcc extension). */ + if (strict_aliasing_applies + && ((SSA_VAR_P (ref2) + && !AGGREGATE_TYPE_P (TREE_TYPE (ref2)) + && !INDIRECT_REF_P (ref1) + && TREE_CODE (TREE_TYPE (base1)) != UNION_TYPE) + || (SSA_VAR_P (ref1) + && !AGGREGATE_TYPE_P (TREE_TYPE (ref1)) + && !INDIRECT_REF_P (ref2) + && TREE_CODE (TREE_TYPE (base2)) != UNION_TYPE))) + return false; + + /* If both references are through the same type, or if strict aliasing + doesn't apply they are through two same pointers, they do not alias + if the accesses do not overlap. */ + if ((strict_aliasing_applies + && (TYPE_MAIN_VARIANT (TREE_TYPE (base1)) + == TYPE_MAIN_VARIANT (TREE_TYPE (base2)))) + || (TREE_CODE (base1) == INDIRECT_REF + && TREE_CODE (base2) == INDIRECT_REF + && operand_equal_p (TREE_OPERAND (base1, 0), + TREE_OPERAND (base2, 0), 0))) + return ranges_overlap_p (offset1, max_size1, offset2, max_size2); + + /* If both are component references through pointers try to find a + common base and apply offset based disambiguation. This handles + for example + struct A { int i; int j; } *q; + struct B { struct A a; int k; } *p; + disambiguating q->i and p->a.j. */ + if (strict_aliasing_applies + && (TREE_CODE (base1) == INDIRECT_REF + || TREE_CODE (base2) == INDIRECT_REF) + && handled_component_p (ref1) + && handled_component_p (ref2)) + { + tree *refp; + /* Now search for the type of base1 in the access path of ref2. This + would be a common base for doing offset based disambiguation on. */ + refp = &ref2; + while (handled_component_p (*refp) + /* Note that the following is only conservative if there are + never copies of types appearing as sub-structures. */ + && (TYPE_MAIN_VARIANT (TREE_TYPE (*refp)) + != TYPE_MAIN_VARIANT (TREE_TYPE (base1)))) + refp = &TREE_OPERAND (*refp, 0); + if (TYPE_MAIN_VARIANT (TREE_TYPE (*refp)) + == TYPE_MAIN_VARIANT (TREE_TYPE (base1))) + { + HOST_WIDE_INT offadj, sztmp, msztmp; + get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp); + offset2 -= offadj; + return ranges_overlap_p (offset1, max_size1, offset2, max_size2); + } + /* The other way around. */ + refp = &ref1; + while (handled_component_p (*refp) + && (TYPE_MAIN_VARIANT (TREE_TYPE (*refp)) + != TYPE_MAIN_VARIANT (TREE_TYPE (base2)))) + refp = &TREE_OPERAND (*refp, 0); + if (TYPE_MAIN_VARIANT (TREE_TYPE (*refp)) + == TYPE_MAIN_VARIANT (TREE_TYPE (base2))) + { + HOST_WIDE_INT offadj, sztmp, msztmp; + get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp); + offset1 -= offadj; + return ranges_overlap_p (offset1, max_size1, offset2, max_size2); + } + /* If we can be sure to catch all equivalent types in the search + for the common base then we could return false here. In that + case we would be able to disambiguate q->i and p->k. */ + } + + return true; +} + +/* Given a stmt STMT that references memory, return the single stmt + that is reached by following the VUSE -> VDEF link. Returns + NULL_TREE, if there is no single stmt that defines all VUSEs of + STMT. + Note that for a stmt with a single virtual operand this may return + a PHI node as well. Note that if all VUSEs are default definitions + this function will return an empty statement. */ + +gimple +get_single_def_stmt (gimple stmt) +{ + gimple def_stmt = NULL; + tree use; + ssa_op_iter iter; + + FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_VIRTUAL_USES) + { + gimple tmp = SSA_NAME_DEF_STMT (use); + + /* ??? This is too simplistic for multiple virtual operands + reaching different PHI nodes of the same basic blocks or for + reaching all default definitions. */ + if (def_stmt + && def_stmt != tmp + && !(gimple_nop_p (def_stmt) + && gimple_nop_p (tmp))) + return NULL; + + def_stmt = tmp; + } + + return def_stmt; +} + +/* Given a PHI node of virtual operands, tries to eliminate cyclic + reached definitions if they do not alias REF and returns the + defining statement of the single virtual operand that flows in + from a non-backedge. Returns NULL_TREE if such statement within + the above conditions cannot be found. */ + +gimple +get_single_def_stmt_from_phi (tree ref, gimple phi) +{ + tree def_arg = NULL_TREE; + unsigned i; + + /* Find the single PHI argument that is not flowing in from a + back edge and verify that the loop-carried definitions do + not alias the reference we look for. */ + for (i = 0; i < gimple_phi_num_args (phi); ++i) + { + tree arg = PHI_ARG_DEF (phi, i); + gimple def_stmt; + + if (!(gimple_phi_arg_edge (phi, i)->flags & EDGE_DFS_BACK)) + { + /* Multiple non-back edges? Do not try to handle this. */ + if (def_arg) + return NULL; + def_arg = arg; + continue; + } + + /* Follow the definitions back to the original PHI node. Bail + out once a definition is found that may alias REF. */ + def_stmt = SSA_NAME_DEF_STMT (arg); + do + { + if (!is_gimple_assign (def_stmt) + || refs_may_alias_p (ref, gimple_assign_lhs (def_stmt))) + return NULL; + /* ??? This will only work, reaching the PHI node again if + there is a single virtual operand on def_stmt. */ + def_stmt = get_single_def_stmt (def_stmt); + if (!def_stmt) + return NULL; + } + while (def_stmt != phi); + } + + return SSA_NAME_DEF_STMT (def_arg); +} + +/* Return the single reference statement defining all virtual uses + on STMT or NULL_TREE, if there are multiple defining statements. + Take into account only definitions that alias REF if following + back-edges when looking through a loop PHI node. */ + +gimple +get_single_def_stmt_with_phi (tree ref, gimple stmt) +{ + switch (NUM_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES)) + { + case 0: + gcc_unreachable (); + + case 1: + { + gimple def_stmt = SSA_NAME_DEF_STMT (SINGLE_SSA_TREE_OPERAND + (stmt, SSA_OP_VIRTUAL_USES)); + /* We can handle lookups over PHI nodes only for a single + virtual operand. */ + if (gimple_code (def_stmt) == GIMPLE_PHI) + return get_single_def_stmt_from_phi (ref, def_stmt); + return def_stmt; + } + + default: + return get_single_def_stmt (stmt); + } +}