X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-data-ref.c;h=3de3234c22b093baa5d7ceaeac378017b3296b88;hb=95cdaa86ed9bb149a93d8603c6f6497872a80262;hp=e1d2dfcadca5d6c2acf9288c001522cba94d62d4;hpb=9ff256032c64eeed5baff9dfe5e0bf42dfbc3229;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index e1d2dfcadca..3de3234c22b 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -77,16 +77,8 @@ along with GCC; see the file COPYING3. If not see #include "config.h" #include "system.h" #include "coretypes.h" -#include "tm.h" -#include "ggc.h" -#include "flags.h" -#include "tree.h" -#include "basic-block.h" -#include "tree-pretty-print.h" #include "gimple-pretty-print.h" #include "tree-flow.h" -#include "tree-dump.h" -#include "timevar.h" #include "cfgloop.h" #include "tree-data-ref.h" #include "tree-scalar-evolution.h" @@ -1233,154 +1225,20 @@ object_address_invariant_in_loop_p (const struct loop *loop, const_tree obj) loop->num); } -/* Returns true if A and B are accesses to different objects, or to different - fields of the same object. */ - -static bool -disjoint_objects_p (tree a, tree b) -{ - tree base_a, base_b; - VEC (tree, heap) *comp_a = NULL, *comp_b = NULL; - bool ret; - - base_a = get_base_address (a); - base_b = get_base_address (b); - - if (DECL_P (base_a) - && DECL_P (base_b) - && base_a != base_b) - return true; - - if (!operand_equal_p (base_a, base_b, 0)) - return false; - - /* Compare the component references of A and B. We must start from the inner - ones, so record them to the vector first. */ - while (handled_component_p (a)) - { - VEC_safe_push (tree, heap, comp_a, a); - a = TREE_OPERAND (a, 0); - } - while (handled_component_p (b)) - { - VEC_safe_push (tree, heap, comp_b, b); - b = TREE_OPERAND (b, 0); - } - - ret = false; - while (1) - { - if (VEC_length (tree, comp_a) == 0 - || VEC_length (tree, comp_b) == 0) - break; - - a = VEC_pop (tree, comp_a); - b = VEC_pop (tree, comp_b); - - /* Real and imaginary part of a variable do not alias. */ - if ((TREE_CODE (a) == REALPART_EXPR - && TREE_CODE (b) == IMAGPART_EXPR) - || (TREE_CODE (a) == IMAGPART_EXPR - && TREE_CODE (b) == REALPART_EXPR)) - { - ret = true; - break; - } - - if (TREE_CODE (a) != TREE_CODE (b)) - break; - - /* Nothing to do for ARRAY_REFs, as the indices of array_refs in - DR_BASE_OBJECT are always zero. */ - if (TREE_CODE (a) == ARRAY_REF) - continue; - else if (TREE_CODE (a) == COMPONENT_REF) - { - if (operand_equal_p (TREE_OPERAND (a, 1), TREE_OPERAND (b, 1), 0)) - continue; - - /* Different fields of unions may overlap. */ - base_a = TREE_OPERAND (a, 0); - if (TREE_CODE (TREE_TYPE (base_a)) == UNION_TYPE) - break; - - /* Different fields of structures cannot. */ - ret = true; - break; - } - else - break; - } - - VEC_free (tree, heap, comp_a); - VEC_free (tree, heap, comp_b); - - return ret; -} - /* Returns false if we can prove that data references A and B do not alias, true otherwise. */ bool dr_may_alias_p (const struct data_reference *a, const struct data_reference *b) { - const_tree addr_a = DR_BASE_ADDRESS (a); - const_tree addr_b = DR_BASE_ADDRESS (b); - const_tree type_a, type_b; - const_tree decl_a = NULL_TREE, decl_b = NULL_TREE; + tree addr_a = DR_BASE_OBJECT (a); + tree addr_b = DR_BASE_OBJECT (b); - /* If the accessed objects are disjoint, the memory references do not - alias. */ - if (disjoint_objects_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b))) - return false; - - /* Query the alias oracle. */ if (DR_IS_WRITE (a) && DR_IS_WRITE (b)) - { - if (!refs_output_dependent_p (DR_REF (a), DR_REF (b))) - return false; - } + return refs_output_dependent_p (addr_a, addr_b); else if (DR_IS_READ (a) && DR_IS_WRITE (b)) - { - if (!refs_anti_dependent_p (DR_REF (a), DR_REF (b))) - return false; - } - else if (!refs_may_alias_p (DR_REF (a), DR_REF (b))) - return false; - - if (!addr_a || !addr_b) - return true; - - /* If the references are based on different static objects, they cannot - alias (PTA should be able to disambiguate such accesses, but often - it fails to). */ - if (TREE_CODE (addr_a) == ADDR_EXPR - && TREE_CODE (addr_b) == ADDR_EXPR) - return TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0); - - /* An instruction writing through a restricted pointer is "independent" of any - instruction reading or writing through a different restricted pointer, - in the same block/scope. */ - - type_a = TREE_TYPE (addr_a); - type_b = TREE_TYPE (addr_b); - gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b)); - - if (TREE_CODE (addr_a) == SSA_NAME) - decl_a = SSA_NAME_VAR (addr_a); - if (TREE_CODE (addr_b) == SSA_NAME) - decl_b = SSA_NAME_VAR (addr_b); - - if (TYPE_RESTRICT (type_a) && TYPE_RESTRICT (type_b) - && (DR_IS_WRITE (a) || DR_IS_WRITE (b)) - && decl_a && DECL_P (decl_a) - && decl_b && DECL_P (decl_b) - && decl_a != decl_b - && TREE_CODE (DECL_CONTEXT (decl_a)) == FUNCTION_DECL - && DECL_CONTEXT (decl_a) == DECL_CONTEXT (decl_b)) - return false; - - return true; + return refs_anti_dependent_p (addr_a, addr_b); + return refs_may_alias_p (addr_a, addr_b); } static void compute_self_dependence (struct data_dependence_relation *); @@ -2787,7 +2645,8 @@ analyze_overlapping_iterations (tree chrec_a, /* If they are the same chrec, and are affine, they overlap on every iteration. */ else if (eq_evolutions_p (chrec_a, chrec_b) - && evolution_function_is_affine_multivariate_p (chrec_a, lnn)) + && (evolution_function_is_affine_multivariate_p (chrec_a, lnn) + || operand_equal_p (chrec_a, chrec_b, 0))) { dependence_stats.num_same_subscript_function++; *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node)); @@ -2796,7 +2655,7 @@ analyze_overlapping_iterations (tree chrec_a, } /* If they aren't the same, and aren't affine, we can't do anything - yet. */ + yet. */ else if ((chrec_contains_symbols (chrec_a) || chrec_contains_symbols (chrec_b)) && (!evolution_function_is_affine_multivariate_p (chrec_a, lnn) @@ -3616,6 +3475,7 @@ omega_setup_subscript (tree access_fun_a, tree access_fun_b, tree fun_a = chrec_convert (type, access_fun_a, NULL); tree fun_b = chrec_convert (type, access_fun_b, NULL); tree difference = chrec_fold_minus (type, fun_a, fun_b); + tree minus_one; /* When the fun_a - fun_b is not constant, the dependence is not captured by the classic distance vector representation. */ @@ -3630,7 +3490,8 @@ omega_setup_subscript (tree access_fun_a, tree access_fun_b, return true; } - fun_b = chrec_fold_multiply (type, fun_b, integer_minus_one_node); + minus_one = build_int_cst (type, -1); + fun_b = chrec_fold_multiply (type, fun_b, minus_one); eq = omega_add_zero_eq (pb, omega_black); if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr) @@ -4378,11 +4239,11 @@ find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest) bool compute_data_dependences_for_loop (struct loop *loop, bool compute_self_and_read_read_dependences, + VEC (loop_p, heap) **loop_nest, VEC (data_reference_p, heap) **datarefs, VEC (ddr_p, heap) **dependence_relations) { bool res = true; - VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3); memset (&dependence_stats, 0, sizeof (dependence_stats)); @@ -4390,19 +4251,19 @@ compute_data_dependences_for_loop (struct loop *loop, is not computable, give up without spending time to compute other dependences. */ if (!loop - || !find_loop_nest (loop, &vloops) + || !find_loop_nest (loop, loop_nest) || find_data_references_in_loop (loop, datarefs) == chrec_dont_know) { struct data_dependence_relation *ddr; /* Insert a single relation into dependence_relations: chrec_dont_know. */ - ddr = initialize_data_dependence_relation (NULL, NULL, vloops); + ddr = initialize_data_dependence_relation (NULL, NULL, *loop_nest); VEC_safe_push (ddr_p, heap, *dependence_relations, ddr); res = false; } else - compute_all_dependences (*datarefs, dependence_relations, vloops, + compute_all_dependences (*datarefs, dependence_relations, *loop_nest, compute_self_and_read_read_dependences); if (dump_file && (dump_flags & TDF_STATS)) @@ -4506,9 +4367,10 @@ analyze_all_data_dependences (struct loop *loop) VEC_alloc (data_reference_p, heap, nb_data_refs); VEC (ddr_p, heap) *dependence_relations = VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs); + VEC (loop_p, heap) *loop_nest = VEC_alloc (loop_p, heap, 3); /* Compute DDs on the whole function. */ - compute_data_dependences_for_loop (loop, false, &datarefs, + compute_data_dependences_for_loop (loop, false, &loop_nest, &datarefs, &dependence_relations); if (dump_file) @@ -4542,6 +4404,7 @@ analyze_all_data_dependences (struct loop *loop) } } + VEC_free (loop_p, heap, loop_nest); free_dependence_relations (dependence_relations); free_data_refs (datarefs); } @@ -4585,22 +4448,11 @@ free_dependence_relations (VEC (ddr_p, heap) *dependence_relations) { unsigned int i; struct data_dependence_relation *ddr; - VEC (loop_p, heap) *loop_nest = NULL; FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr) - { - if (ddr == NULL) - continue; - if (loop_nest == NULL) - loop_nest = DDR_LOOP_NEST (ddr); - else - gcc_assert (DDR_LOOP_NEST (ddr) == NULL - || DDR_LOOP_NEST (ddr) == loop_nest); + if (ddr) free_dependence_relation (ddr); - } - if (loop_nest) - VEC_free (loop_p, heap, loop_nest); VEC_free (ddr_p, heap, dependence_relations); } @@ -4641,7 +4493,7 @@ dump_rdg_vertex (FILE *file, struct graph *rdg, int i) for (e = v->succ; e; e = e->succ_next) fprintf (file, " %d", e->dest); - fprintf (file, ") \n"); + fprintf (file, ")\n"); print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS); fprintf (file, ")\n"); } @@ -4709,6 +4561,76 @@ debug_rdg (struct graph *rdg) dump_rdg (stderr, rdg); } +static void +dot_rdg_1 (FILE *file, struct graph *rdg) +{ + int i; + + fprintf (file, "digraph RDG {\n"); + + for (i = 0; i < rdg->n_vertices; i++) + { + struct vertex *v = &(rdg->vertices[i]); + struct graph_edge *e; + + /* Highlight reads from memory. */ + if (RDG_MEM_READS_STMT (rdg, i)) + fprintf (file, "%d [style=filled, fillcolor=green]\n", i); + + /* Highlight stores to memory. */ + if (RDG_MEM_WRITE_STMT (rdg, i)) + fprintf (file, "%d [style=filled, fillcolor=red]\n", i); + + if (v->succ) + for (e = v->succ; e; e = e->succ_next) + switch (RDGE_TYPE (e)) + { + case input_dd: + fprintf (file, "%d -> %d [label=input] \n", i, e->dest); + break; + + case output_dd: + fprintf (file, "%d -> %d [label=output] \n", i, e->dest); + break; + + case flow_dd: + /* These are the most common dependences: don't print these. */ + fprintf (file, "%d -> %d \n", i, e->dest); + break; + + case anti_dd: + fprintf (file, "%d -> %d [label=anti] \n", i, e->dest); + break; + + default: + gcc_unreachable (); + } + } + + fprintf (file, "}\n\n"); +} + +/* Display the Reduced Dependence Graph using dotty. */ +extern void dot_rdg (struct graph *); + +DEBUG_FUNCTION void +dot_rdg (struct graph *rdg) +{ + /* When debugging, enable the following code. This cannot be used + in production compilers because it calls "system". */ +#if 0 + FILE *file = fopen ("/tmp/rdg.dot", "w"); + gcc_assert (file != NULL); + + dot_rdg_1 (file, rdg); + fclose (file); + + system ("dotty /tmp/rdg.dot &"); +#else + dot_rdg_1 (stderr, rdg); +#endif +} + /* This structure is used for recording the mapping statement index in the RDG. */ @@ -4966,37 +4888,24 @@ build_empty_rdg (int n_stmts) scalar dependence. */ struct graph * -build_rdg (struct loop *loop) +build_rdg (struct loop *loop, + VEC (loop_p, heap) **loop_nest, + VEC (ddr_p, heap) **dependence_relations, + VEC (data_reference_p, heap) **datarefs) { - int nb_data_refs = 10; struct graph *rdg = NULL; - VEC (ddr_p, heap) *dependence_relations; - VEC (data_reference_p, heap) *datarefs; - VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, nb_data_refs); - - dependence_relations = VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs) ; - datarefs = VEC_alloc (data_reference_p, heap, nb_data_refs); - compute_data_dependences_for_loop (loop, - false, - &datarefs, - &dependence_relations); - - if (!known_dependences_p (dependence_relations)) - { - free_dependence_relations (dependence_relations); - free_data_refs (datarefs); - VEC_free (gimple, heap, stmts); - - return rdg; - } + VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, 10); - stmts_from_loop (loop, &stmts); - rdg = build_empty_rdg (VEC_length (gimple, stmts)); + compute_data_dependences_for_loop (loop, false, loop_nest, datarefs, + dependence_relations); - rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info, - eq_stmt_vertex_info, hash_stmt_vertex_del); - create_rdg_vertices (rdg, stmts); - create_rdg_edges (rdg, dependence_relations); + if (known_dependences_p (*dependence_relations)) + { + stmts_from_loop (loop, &stmts); + rdg = build_empty_rdg (VEC_length (gimple, stmts)); + create_rdg_vertices (rdg, stmts); + create_rdg_edges (rdg, *dependence_relations); + } VEC_free (gimple, heap, stmts); return rdg; @@ -5010,7 +4919,17 @@ free_rdg (struct graph *rdg) int i; for (i = 0; i < rdg->n_vertices; i++) - free (rdg->vertices[i].data); + { + struct vertex *v = &(rdg->vertices[i]); + struct graph_edge *e; + + for (e = v->succ; e; e = e->succ_next) + if (e->data) + free (e->data); + + if (v->data) + free (v->data); + } htab_delete (rdg->indices); free_graph (rdg); @@ -5038,6 +4957,38 @@ stores_from_loop (struct loop *loop, VEC (gimple, heap) **stmts) free (bbs); } +/* Returns true when the statement at STMT is of the form "A[i] = 0" + that contains a data reference on its LHS with a stride of the same + size as its unit type. */ + +bool +stmt_with_adjacent_zero_store_dr_p (gimple stmt) +{ + tree op0, op1; + bool res; + struct data_reference *dr; + + if (!stmt + || !gimple_vdef (stmt) + || !is_gimple_assign (stmt) + || !gimple_assign_single_p (stmt) + || !(op1 = gimple_assign_rhs1 (stmt)) + || !(integer_zerop (op1) || real_zerop (op1))) + return false; + + dr = XCNEW (struct data_reference); + op0 = gimple_assign_lhs (stmt); + + DR_STMT (dr) = stmt; + DR_REF (dr) = op0; + + res = dr_analyze_innermost (dr) + && stride_of_unit_type_p (DR_STEP (dr), TREE_TYPE (op0)); + + free_data_ref (dr); + return res; +} + /* Initialize STMTS with all the statements of LOOP that contain a store to memory of the form "A[i] = 0". */ @@ -5048,17 +4999,12 @@ stores_zero_from_loop (struct loop *loop, VEC (gimple, heap) **stmts) basic_block bb; gimple_stmt_iterator si; gimple stmt; - tree op; basic_block *bbs = get_loop_body_in_dom_order (loop); for (i = 0; i < loop->num_nodes; i++) for (bb = bbs[i], si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) if ((stmt = gsi_stmt (si)) - && gimple_vdef (stmt) - && is_gimple_assign (stmt) - && gimple_assign_rhs_code (stmt) == INTEGER_CST - && (op = gimple_assign_rhs1 (stmt)) - && (integer_zerop (op) || real_zerop (op))) + && stmt_with_adjacent_zero_store_dr_p (stmt)) VEC_safe_push (gimple, heap, *stmts, gsi_stmt (si)); free (bbs);