X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-dfa.c;h=088c45ab33552b5b3bd18b5369ddb8ef0cca33d0;hb=6e8435a1039a5266c33343f12606821de0c68c54;hp=9fc48d5cbe8c8fdb77941a46917763acb7aaf55f;hpb=f7741cb166d978ce30a573a0905f7aad4eac9ccd;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-dfa.c b/gcc/tree-dfa.c index 9fc48d5cbe8..088c45ab335 100644 --- a/gcc/tree-dfa.c +++ b/gcc/tree-dfa.c @@ -65,19 +65,10 @@ struct dfa_stats_d }; -/* 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. */ @@ -85,6 +76,12 @@ static void add_referenced_var (tree, struct walk_state *); /* 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; + /*--------------------------------------------------------------------------- Dataflow analysis (DFA) routines @@ -97,26 +94,20 @@ htab_t referenced_vars; 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; 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); + walk_tree (stmt_p, find_vars_r, NULL, NULL); } - htab_delete (vars_found); + return 0; } struct tree_opt_pass pass_referenced_vars = @@ -151,8 +142,7 @@ create_var_ann (tree t) gcc_assert (DECL_P (t)); gcc_assert (!t->common.ann || t->common.ann->common.type == VAR_ANN); - ann = ggc_alloc (sizeof (*ann)); - memset ((void *) ann, 0, sizeof (*ann)); + ann = GGC_CNEW (struct var_ann_d); ann->common.type = VAR_ANN; @@ -161,6 +151,26 @@ create_var_ann (tree t) return ann; } +/* Create a new annotation for a FUNCTION_DECL node T. */ + +function_ann_t +create_function_ann (tree t) +{ + function_ann_t ann; + + gcc_assert (t); + gcc_assert (TREE_CODE (t) == FUNCTION_DECL); + gcc_assert (!t->common.ann || t->common.ann->common.type == FUNCTION_ANN); + + ann = ggc_alloc (sizeof (*ann)); + memset ((void *) ann, 0, sizeof (*ann)); + + ann->common.type = FUNCTION_ANN; + + t->common.ann = (tree_ann_t) ann; + + return ann; +} /* Create a new annotation for a statement node T. */ @@ -172,8 +182,7 @@ create_stmt_ann (tree t) gcc_assert (is_gimple_stmt (t)); gcc_assert (!t->common.ann || t->common.ann->common.type == STMT_ANN); - ann = ggc_alloc (sizeof (*ann)); - memset ((void *) ann, 0, sizeof (*ann)); + ann = GGC_CNEW (struct stmt_ann_d); ann->common.type = STMT_ANN; @@ -187,19 +196,18 @@ create_stmt_ann (tree t) /* 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); - ann = ggc_alloc (sizeof (*ann)); - 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; + t->common.ann = (tree_ann_t) ann; return ann; } @@ -210,9 +218,13 @@ tree make_rename_temp (tree type, const char *prefix) { tree t = create_tmp_var (type, prefix); + + if (TREE_CODE (type) == COMPLEX_TYPE) + DECL_COMPLEX_GIMPLE_REG_P (t) = 1; + if (referenced_vars) { - add_referenced_tmp_var (t); + add_referenced_var (t); mark_sym_for_renaming (t); } @@ -314,14 +326,14 @@ dump_variable (FILE *file, tree 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 (ann && ann->is_aliased) + fprintf (file, ", is aliased"); if (TREE_ADDRESSABLE (var)) fprintf (file, ", is addressable"); @@ -333,7 +345,35 @@ dump_variable (FILE *file, tree var) fprintf (file, ", is volatile"); if (is_call_clobbered (var)) - fprintf (file, ", call clobbered"); + { + fprintf (file, ", call clobbered"); + if (dump_flags & TDF_DETAILS) + { + var_ann_t va = var_ann (var); + unsigned int escape_mask = va->escape_mask; + + fprintf (file, " ("); + if (escape_mask & ESCAPE_STORED_IN_GLOBAL) + fprintf (file, ", stored in global"); + if (escape_mask & ESCAPE_TO_ASM) + fprintf (file, ", goes through ASM"); + if (escape_mask & ESCAPE_TO_CALL) + fprintf (file, ", passed to call"); + if (escape_mask & ESCAPE_BAD_CAST) + fprintf (file, ", bad cast"); + if (escape_mask & ESCAPE_TO_RETURN) + fprintf (file, ", returned from func"); + if (escape_mask & ESCAPE_TO_PURE_CONST) + fprintf (file, ", passed to pure/const"); + if (escape_mask & ESCAPE_IS_GLOBAL) + fprintf (file, ", is global var"); + if (escape_mask & ESCAPE_IS_PARM) + fprintf (file, ", is incoming pointer"); + if (escape_mask & ESCAPE_UNKNOWN) + fprintf (file, ", unknown escape"); + fprintf (file, " )"); + } + } if (default_def (var)) { @@ -478,10 +518,11 @@ collect_dfa_stats (struct dfa_stats_d *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 0, but don't stop at block boundaries. */ + basic block NUM_FIXED_BLOCKS, but don't stop at block boundaries. */ pset = pointer_set_create (); - for (i = bsi_start (BASIC_BLOCK (0)); !bsi_end_p (i); bsi_next (&i)) + 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); @@ -547,14 +588,12 @@ 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 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); + add_referenced_var (*tp); /* Type, _DECL and constant nodes have no interesting children. Ignore them. */ @@ -564,84 +603,120 @@ 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. */ + variable. */ tree -referenced_var_lookup_if_exists (unsigned int uid) +referenced_var_lookup (unsigned int uid) { struct int_tree_map *h, in; in.uid = uid; - h = htab_find_with_hash (referenced_vars, &in, uid); + h = (struct int_tree_map *) htab_find_with_hash (referenced_vars, &in, uid); + gcc_assert (h || uid == 0); if (h) return h->to; return NULL_TREE; } -/* Lookup UID in the referenced_vars hashtable and return the associated +/* Check if TO is in the referenced_vars hash table and insert it if not. + Return true if it required insertion. */ + +static bool +referenced_var_check_and_insert (tree to) +{ + struct int_tree_map *h, in; + void **loc; + unsigned int uid = DECL_UID (to); + + in.uid = uid; + in.to = to; + h = (struct int_tree_map *) htab_find_with_hash (referenced_vars, &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 == to); + return false; + } + + 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; + return true; +} + +/* Lookup VAR UID in the default_defs hashtable and return the associated variable. */ tree -referenced_var_lookup (unsigned int uid) +default_def (tree var) { struct int_tree_map *h, in; - in.uid = uid; - h = htab_find_with_hash (referenced_vars, &in, uid); - gcc_assert (h || uid == 0); + 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; } -/* Insert the pair UID, TO into the referenced_vars hashtable. */ +/* Insert the pair VAR's UID, DEF into the default_defs hashtable. */ -static void -referenced_var_insert (unsigned int uid, tree to) +void +set_default_def (tree var, tree def) { + struct int_tree_map in; struct int_tree_map *h; void **loc; - h = ggc_alloc (sizeof (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; + gcc_assert (SSA_VAR_P (var)); + in.uid = DECL_UID (var); + if (!def && default_def (var)) + { + loc = htab_find_slot_with_hash (default_defs, &in, DECL_UID (var), INSERT); + htab_remove_elt (default_defs, *loc); + return; + } + gcc_assert (TREE_CODE (def) == SSA_NAME); + loc = htab_find_slot_with_hash (default_defs, &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; + } } -/* Add VAR to the list of dereferenced variables. - - 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 @@ -654,7 +729,7 @@ add_referenced_var (tree var, struct walk_state *walk_state) 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); + walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0); } } @@ -682,19 +757,6 @@ 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. */ @@ -711,6 +773,7 @@ mark_new_vars_to_rename (tree stmt) if (TREE_CODE (stmt) == PHI_NODE) return; + get_stmt_ann (stmt); vars_in_vops_to_rename = BITMAP_ALLOC (NULL); /* Before re-scanning the statement for operands, mark the existing @@ -771,7 +834,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); } @@ -788,45 +851,182 @@ find_new_referenced_vars (tree *stmt_p) } -/* If REF is a COMPONENT_REF for a structure that can have sub-variables, and - we know where REF is accessing, return the variable in REF that has the - sub-variables. If the return value is not NULL, POFFSET will be the - offset, in bits, of REF inside the return value, and PSIZE will be the - size, in bits, of REF inside the return value. */ +/* If REF 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 + and *PMAX_SIZE are equal, the access is non-variable. */ tree -okay_component_ref_for_subvars (tree ref, unsigned HOST_WIDE_INT *poffset, - unsigned HOST_WIDE_INT *psize) +get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset, + HOST_WIDE_INT *psize, + HOST_WIDE_INT *pmax_size) { - tree result = NULL; - HOST_WIDE_INT bitsize; - HOST_WIDE_INT bitpos; - tree offset; - enum machine_mode mode; - int unsignedp; - int volatilep; - - gcc_assert (!SSA_VAR_P (ref)); - *poffset = 0; - *psize = (unsigned int) -1; - - if (ref_contains_array_ref (ref)) - return result; - ref = get_inner_reference (ref, &bitsize, &bitpos, &offset, &mode, - &unsignedp, &volatilep, false); - if (TREE_CODE (ref) == INDIRECT_REF) - return result; - else if (offset == NULL && bitsize != -1 && SSA_VAR_P (ref)) + HOST_WIDE_INT bitsize = -1; + HOST_WIDE_INT maxsize = -1; + tree size_tree = NULL_TREE; + tree bit_offset = bitsize_zero_node; + bool seen_variable_array_ref = false; + + gcc_assert (!SSA_VAR_P (exp)); + + /* First get the final access size from just the outermost expression. */ + if (TREE_CODE (exp) == COMPONENT_REF) + size_tree = DECL_SIZE (TREE_OPERAND (exp, 1)); + else if (TREE_CODE (exp) == BIT_FIELD_REF) + size_tree = TREE_OPERAND (exp, 1); + else { - *poffset = bitpos; - *psize = bitsize; - if (get_subvars_for_var (ref) != NULL) - return ref; + enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp)); + if (mode == BLKmode) + size_tree = TYPE_SIZE (TREE_TYPE (exp)); + else + bitsize = GET_MODE_BITSIZE (mode); } - else if (SSA_VAR_P (ref)) + if (size_tree != NULL_TREE) { - if (get_subvars_for_var (ref) != NULL) - return ref; + if (! host_integerp (size_tree, 1)) + bitsize = -1; + else + bitsize = TREE_INT_CST_LOW (size_tree); } - return NULL_TREE; + + /* Initially, maxsize is the same as the accessed element size. + In the following it will only grow (or become -1). */ + maxsize = bitsize; + + /* Compute cumulative bit-offset for nested component-refs and array-refs, + and find the ultimate containing object. */ + while (1) + { + switch (TREE_CODE (exp)) + { + case BIT_FIELD_REF: + bit_offset = size_binop (PLUS_EXPR, bit_offset, + TREE_OPERAND (exp, 2)); + break; + + case COMPONENT_REF: + { + tree field = TREE_OPERAND (exp, 1); + tree this_offset = component_ref_field_offset (exp); + + 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)); + } + 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, + 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)); + } + else + maxsize = -1; + } + } + break; + + case ARRAY_REF: + case ARRAY_RANGE_REF: + { + tree index = TREE_OPERAND (exp, 1); + 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) + { + index = size_binop (MULT_EXPR, + fold_convert (bitsizetype, index), + bitsize_unit_node); + bit_offset = size_binop (PLUS_EXPR, bit_offset, index); + + /* 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, + 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)); + } + else + maxsize = -1; + + /* Remember that we have seen an array ref with a variable + index. */ + seen_variable_array_ref = true; + } + } + break; + + case REALPART_EXPR: + break; + + case IMAGPART_EXPR: + bit_offset = size_binop (PLUS_EXPR, bit_offset, + bitsize_int (bitsize)); + break; + + case VIEW_CONVERT_EXPR: + /* ??? We probably should give up here and bail out. */ + break; + + default: + goto done; + } + + exp = TREE_OPERAND (exp, 0); + } + 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) + && TREE_INT_CST_LOW (bit_offset) + maxsize + == 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); + *psize = bitsize; + *pmax_size = maxsize; + + return exp; }