This is the mail archive of the
`gcc-patches@gcc.gnu.org`
mailing list for the GCC project.

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |

Other format: | [Raw text] |

*From*: Diego Novillo <dnovillo at redhat dot com>*To*: Daniel Berlin <dberlin at dberlin dot org>*Cc*: gcc-patches at gcc dot gnu dot org*Date*: Tue, 7 Jun 2005 16:17:55 -0400*Subject*: Re: [PATCH]: Structure aliasing, take 2*References*: <1117577413.19295.38.camel@linux.site>

On Tue, May 31, 2005 at 06:10:12PM -0400, Daniel Berlin wrote: > Okay for mainline? > Yes. I found it easier to edit tree-ssa-structalias.c to give you feedback. The changes are minor, as your implementation is pretty clean (thanks). Mostly clarifying comments and some spacing. Grep for 'FIXME'. Unless you are working on it now, I will start removing the old analyzer. That'll help identify bugs in the new analyzer. Diego. --- tree-ssa-structalias.c 2005-06-07 16:13:05.809369862 -0400 +++ tree-ssa-structalias.c.new 2005-06-07 16:11:53.308181560 -0400 @@ -110,8 +110,8 @@ Foundation, Inc., 59 Temple Place, Suite bar -> id 3, size 32, offset 0, fullsize 32, next NULL -In order to solve the system of set constraints, the following is -done: + In order to solve the system of set constraints, the following is + done: 1. Each constraint variable x has a solution set associated with it, Sol(x). @@ -143,23 +143,22 @@ done: 8. The process of walking the graph is iterated until no solution sets change. + Prior to walking the graph in steps 6 and 7, We perform static + cycle elimination on the constraint graph, as well + as off-line variable substitution. + + TODO: Adding offsets to pointer-to-structures can be handled (IE not punted + on and turned into anything), but isn't. You can just see what offset + inside the pointed-to struct it's going to access. + + TODO: Constant bounded arrays can be handled as if they were structs of the + same number of elements. - Prior to walking the graph in steps 6 and 7, We perform static - cycle elimination on the constraint graph, as well - as off-line variable substitution. - - TODO: Adding offsets to pointer-to-structures can be handled (IE not punted - on and turned into anything), but isn't. You can just see what offset - inside the pointed-to struct it's going to access. - - TODO: Constant bounded arrays can be handled as if they were structs of the - same number of elements. - - TODO: Modeling heap and incoming pointers becomes much better if we - add fields to them as we discover them, which we could do. + TODO: Modeling heap and incoming pointers becomes much better if we + add fields to them as we discover them, which we could do. - TODO: We could handle unions, but to be honest, it's probably not - worth the pain or slowdown. */ + TODO: We could handle unions, but to be honest, it's probably not + worth the pain or slowdown. */ static bool use_field_sensitive = true; static unsigned int create_variable_info_for (tree, const char *); @@ -243,6 +242,7 @@ DEF_VEC_P(varinfo_t); DEF_VEC_ALLOC_P(varinfo_t, gc); +/* FIXME. Description? */ static VEC(varinfo_t,gc) *varmap; #define get_varinfo(n) VEC_index(varinfo_t, varmap, n) @@ -270,6 +270,7 @@ static unsigned int integer_id; /* Return a new variable info structure consisting for a variable named NAME, ending at id END, and using constraint graph node + ^^^^^^^^^^^^^^^^ FIXME: Hmm? NODE. */ static varinfo_t @@ -988,6 +989,7 @@ static sbitmap changed; DEF_VEC_I(uint); DEF_VEC_ALLOC_I(uint,heap); + /* Strongly Connected Component visitation info. */ struct scc_info @@ -1002,6 +1004,7 @@ struct scc_info /* Recursive routine to find strongly connected components in GRAPH. + FIXME: Document SI and N. This is Tarjan's strongly connected component finding algorithm, as modified by Nuutila to keep only non-root nodes on the stack. @@ -1035,9 +1038,7 @@ scc_visit (constraint_graph_t graph, str unsigned int t = get_varinfo (w)->node; unsigned int nnode = get_varinfo (n)->node; if (si->visited_index[t] < si->visited_index[nnode]) - { - get_varinfo (n)->node = t; - } + get_varinfo (n)->node = t; } } } @@ -1061,6 +1062,7 @@ scc_visit (constraint_graph_t graph, str VEC_safe_push (uint, heap, si->scc_stack, n); } + /* Collapse two variables into one variable. */ static void @@ -1090,7 +1092,8 @@ collapse_nodes (constraint_graph_t graph } -/* Unify nodes that we have found to be part of a cycle. */ +/* Unify nodes in GRAPH that we have found to be part of a cycle. + FIXME: Document SI and UPDATE_CHANGED. */ static void process_unification_queue (constraint_graph_t graph, struct scc_info *si, @@ -1122,9 +1125,7 @@ process_unification_queue (constraint_gr Merge tmp into solution for rep, marking rep changed if this changed rep's solution. - Delete any 0 weighted self-edges we now have for rep. - */ - + Delete any 0 weighted self-edges we now have for rep. */ while (i != VEC_length (uint, si->unification_queue)) { unsigned int tounify = VEC_index (uint, si->unification_queue, i); @@ -1190,6 +1191,7 @@ process_unification_queue (constraint_gr BITMAP_FREE (tmp); } + /* Information needed to compute the topological ordering of a graph. */ struct topo_info @@ -1201,6 +1203,7 @@ struct topo_info VEC(uint,heap) *topo_order; }; + /* Initialize and return a topological info structure. */ static struct topo_info * @@ -1214,6 +1217,7 @@ init_topo_info (void) return ti; } + /* Free the topological sort info pointed to by TI. */ static void @@ -1555,6 +1559,7 @@ perform_var_substitution (constraint_gra break; } w = get_varinfo (ce->dest)->node; + /* We can't eliminate the node if one of the predecessors is part of a different strongly connected component. */ if (!okay_to_elim) @@ -1567,6 +1572,7 @@ perform_var_substitution (constraint_gra okay_to_elim = false; break; } + /* Theorem 4 in Rountev and Chandra: If i is a direct node, then Solution(i) is a subset of Solution (w), where w is a predecessor in the graph. @@ -1584,6 +1590,7 @@ perform_var_substitution (constraint_gra } BITMAP_FREE (tmp); } + /* See if the root is different than the original node. If so, we've found an equivalence. */ if (root != get_varinfo (i)->node && okay_to_elim) @@ -1598,10 +1605,13 @@ perform_var_substitution (constraint_gra stats.collapsed_vars++; } } + free_topo_info (ti); } -/* Solve the constraint graph GRAPH using our worklist solver. */ + +/* Solve the constraint graph GRAPH using our worklist solver. + FIXME: Add some high-level description. */ static void solve_graph (constraint_graph_t graph) @@ -1629,14 +1639,17 @@ solve_graph (constraint_graph_t graph) if (edge_added) { - /* We already did cycle elimination once, when we did variable - substitution, so we don't need it again for the first iteration. */ + /* We already did cycle elimination once, when we did + variable substitution, so we don't need it again for the + first iteration. */ if (stats.iterations > 1) find_and_collapse_graph_cycles (graph, true); edge_added = false; } + compute_topo_order (graph, ti); + while (VEC_length (uint, ti->topo_order) != 0) { i = VEC_pop (uint, ti->topo_order); @@ -1690,6 +1703,7 @@ solve_graph (constraint_graph_t graph) free_topo_info (ti); bitmap_obstack_release (&iteration_obstack); } + sbitmap_free (changed); } @@ -1742,7 +1756,7 @@ insert_id_for_tree (tree t, int id) *slot = (void *)new_pair; } -/* Find the variable id for tree T in the hashtable. If T does not +/* Find the variable id for tree T in ID_FOR_TREE. If T does not exist in the hash table, return false, otherwise, return true and set *ID to the id we found. */ @@ -1907,10 +1921,11 @@ static unsigned HOST_WIDE_INT bitpos_of_field (const tree fdecl) { return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8) - + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1); + + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1); } -/* Given a COMPONENT_REF, return the constraint_expr for it. */ + +/* Given a COMPONENT_REF T, return the constraint_expr for it. */ static struct constraint_expr get_constraint_for_component_ref (tree t) @@ -1930,7 +1945,6 @@ get_constraint_for_component_ref (tree t /* Some people like to do cute things like take the address of &0->a.b */ - forzero = t; while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero)) forzero = TREE_OPERAND (forzero, 0); @@ -1976,12 +1990,14 @@ get_constraint_for_component_ref (tree t else if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "Access to past the end of variable, ignoring\n"); + result.offset = 0; } return result; } + /* Dereference the constraint expression CONS, and return the result. DEREF (ADDRESSOF) = SCALAR DEREF (SCALAR) = DEREF @@ -2012,22 +2028,22 @@ do_deref (struct constraint_expr cons) gcc_unreachable (); } -/* Given a TREE, return the constraint expression for it. */ + +/* Given a tree T, return the constraint expression for it. */ static struct constraint_expr get_constraint_for (tree t) { struct constraint_expr temp; - /* x = integer is all glommed to a single variable, which doesn't point to - anything by itself. - That is, of course, unless it is an integer constant being treated as a - pointer, in which case, we will return that this is really the addressof - anything. This happens below, since it will fall into the default case. - - The only case we know something about an integer treated like a pointer - is when it is the NULL pointer, and then we just say it points to NULL. - */ + /* x = integer is all glommed to a single variable, which doesn't + point to anything by itself. That is, of course, unless it is an + integer constant being treated as a pointer, in which case, we + will return that this is really the addressof anything. This + happens below, since it will fall into the default case. The only + case we know something about an integer treated like a pointer is + when it is the NULL pointer, and then we just say it points to + NULL. */ if (TREE_CODE (t) == INTEGER_CST && !POINTER_TYPE_P (TREE_TYPE (t))) { @@ -2065,9 +2081,7 @@ get_constraint_for (tree t) /* XXX: In interprocedural mode, if we didn't have the body, we would need to do *each pointer argument = - &ANYTHING added. - */ - + &ANYTHING added. */ if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)) { tree heapvar = create_tmp_var_raw (ptr_type_node, "HEAP"); @@ -2241,10 +2255,10 @@ do_rhs_deref_structure_copy (const struc } } -/* Handle the structure copy case where we have a structure copy between a - aggregate on the RHS and a dereference of a pointer on the LHS - that is of SIZE (in bits) - +/* Handle the structure copy case where we have a structure copy + between a aggregate on the RHS and a dereference of a pointer on + the LHS that is of SIZE (in bits) + For each field of the rhs variable (rhsfield) lhs.offset = rhsfield->offset add the constraint lhs = rhsfield @@ -2280,6 +2294,7 @@ do_lhs_deref_structure_copy (const struc } } + /* Handle aggregate copies by expanding into copies of the respective fields of the structures. */ @@ -2321,7 +2336,6 @@ do_structure_copy (tree lhsop, tree rhso } else { - if (rhs.type == SCALAR && lhs.type == SCALAR) do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)); else if (lhs.type != DEREF && rhs.type == DEREF) @@ -2345,6 +2359,7 @@ do_structure_copy (tree lhsop, tree rhso } } + /* Return true if REF, a COMPONENT_REF, has an INDIRECT_REF somewhere in it. */ @@ -2360,6 +2375,7 @@ ref_contains_indirect_ref (tree ref) return false; } + /* Tree walker that is the heart of the aliasing infrastructure. TP is a pointer to the current tree. WALK_SUBTREES specifies whether to continue traversing subtrees or @@ -2379,6 +2395,7 @@ find_func_aliases (tree t) case PHI_NODE: { int i; + /* Only care about pointers and structures containing pointers. */ if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t))) @@ -2393,11 +2410,13 @@ find_func_aliases (tree t) } } break; + case MODIFY_EXPR: { tree lhsop = TREE_OPERAND (t, 0); tree rhsop = TREE_OPERAND (t, 1); int i; + if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop)) && AGGREGATE_TYPE_P (TREE_TYPE (rhsop))) { @@ -2405,14 +2424,14 @@ find_func_aliases (tree t) } else { - /* Only care about operations with pointers, structures containing - pointers, dereferences, and call expressions*/ + /* Only care about operations with pointers, structures + containing pointers, dereferences, and call + expressions. */ if (POINTER_TYPE_P (TREE_TYPE (lhsop)) || AGGREGATE_TYPE_P (TREE_TYPE (lhsop)) || ref_contains_indirect_ref (lhsop) || TREE_CODE (rhsop) == CALL_EXPR) { - lhs = get_constraint_for (lhsop); switch (TREE_CODE_CLASS (TREE_CODE (rhsop))) { @@ -2430,7 +2449,8 @@ find_func_aliases (tree t) process_constraint (new_constraint (lhs, rhs)); } break; - /* other classes, we walk each operator */ + + /* Otherwise, walk each operand. */ default: for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++) { @@ -2443,11 +2463,13 @@ find_func_aliases (tree t) } } break; + default: break; } } + /* Find the first varinfo in the same variable as START that overlaps with OFFSET. Effectively, walk the chain of fields for the variable START to find the @@ -2468,9 +2490,11 @@ first_vi_for_offset (varinfo_t start, un return curr; curr = curr->next; } + gcc_unreachable (); } + /* Insert the varinfo FIELD into the field list for BASE, ordered by offset. */ @@ -2499,6 +2523,7 @@ insert_into_field_list (varinfo_t base, } } + /* This structure is simply used during pushing fields onto the fieldstack to track the offset of the field, since bitpos_of_field gives it relative to its immediate containing type, and we want it relative to the ultimate @@ -2513,6 +2538,7 @@ typedef struct fieldoff DEF_VEC_O (fieldoff_s); DEF_VEC_ALLOC_O(fieldoff_s,heap); + /* qsort comparison function for two fieldoff's PA and PB */ static int @@ -2539,6 +2565,8 @@ fieldoff_compare (const void *pa, const HAS_UNION is set to true if we find a union type as a field of TYPE. */ +/* FIXME: Dup of tree-ssa-alias.c:push_fields_onto_fieldstack. */ + static int push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack, HOST_WIDE_INT offset, bool *has_union) @@ -2577,6 +2605,7 @@ push_fields_onto_fieldstack (tree type, count++; } } + return count; } @@ -2596,8 +2625,9 @@ make_constraint_to_anything (varinfo_t v } -/* Create a varinfo structure for NAME and DECL, and add it to the varmap. - This will also create any variable infos necessary for fields of DECL. */ +/* Create a varinfo structure for NAME and DECL, and add it to VARMAP. + This will also create any varinfo structures necessary for fields + of DECL. */ static unsigned int create_variable_info_for (tree decl, const char *name) @@ -2642,7 +2672,9 @@ create_variable_info_for (tree decl, con char *tempname; const char *newname; - asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC "."HOST_WIDE_INT_PRINT_DEC, alias_get_name (decl), sv->offset, sv->size); + asprintf (&tempname, + "%s." HOST_WIDE_INT_PRINT_DEC "." HOST_WIDE_INT_PRINT_DEC, + alias_get_name (decl), sv->offset, sv->size); newname = ggc_strdup (tempname); free (tempname); vi = new_var_info (sv->var, index, newname, index); @@ -2794,6 +2826,7 @@ debug_solution_for_var (unsigned int var dump_solution_for_var (stdout, var); } + /* Create varinfo structures for all of the variables in the function for intraprocedural mode. */ @@ -2801,10 +2834,9 @@ static void intra_create_variable_infos (void) { tree t; + /* For each incoming argument arg, ARG = &ANYTHING */ - for (t = DECL_ARGUMENTS (current_function_decl); - t; - t = TREE_CHAIN (t)) + for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t)) { struct constraint_expr lhs; struct constraint_expr rhs; @@ -2938,6 +2970,7 @@ static void init_base_vars (void) { struct constraint_expr lhs, rhs; + /* Create the NULL variable, used to represent that a variable points to NULL. */ nothing_tree = create_tmp_var_raw (void_type_node, "NULL"); @@ -2962,9 +2995,8 @@ init_base_vars (void) var_anything->fullsize = ~0; anything_id = 1; - /* anything points to anything. This makes deref constraints just - work. */ - + /* Anything points to anything. This makes deref constraints just + work. FIXME: "just work"? Some elaboration would help here. */ VEC_safe_push (varinfo_t, gc, varmap, var_anything); lhs.type = SCALAR; lhs.var = anything_id; @@ -2989,7 +3021,8 @@ init_base_vars (void) readonly_id = 2; VEC_safe_push (varinfo_t, gc, varmap, var_readonly); - /* readonly memory points to anything, in order to make deref easier. */ + /* readonly memory points to anything, in order to make deref + easier. FIXME: Refer to previous deref explanation. */ lhs.type = SCALAR; lhs.var = readonly_id; lhs.offset = 0; @@ -3014,7 +3047,9 @@ init_base_vars (void) VEC_safe_push (varinfo_t, gc, varmap, var_integer); } -/* Create points-to sets for the current function. */ + +/* Create points-to sets for the current function. See the comments + at the start of the file for an algorithmic overview. */ static void create_alias_vars (void) @@ -3039,30 +3074,38 @@ create_alias_vars (void) init_base_vars (); intra_create_variable_infos (); + /* Now walk all statements and derive aliases. */ FOR_EACH_BB (bb) { block_stmt_iterator bsi; tree phi; + for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) if (is_gimple_reg (PHI_RESULT (phi))) find_func_aliases (phi); + for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) find_func_aliases (bsi_stmt (bsi)); } build_constraint_graph (); + if (dump_file) { fprintf (dump_file, "Constraints:\n"); dump_constraints (dump_file); } + if (dump_file) fprintf (dump_file, "Collapsing static cycles and doing variable substitution:\n"); + find_and_collapse_graph_cycles (graph, false); perform_var_substitution (graph); + if (dump_file) fprintf (dump_file, "Solving graph:\n"); + solve_graph (graph); if (dump_file) @@ -3118,6 +3161,3 @@ struct tree_opt_pass pass_del_pta = 0, /* todo_flags_finish */ 0 /* letter */ }; - - -

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |