X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-data-ref.c;h=ae0a06814792407228567727570dca391bf2da59;hb=f96d34f19f87467b4ca672d423857405c2913bc6;hp=2be0ad1b401a92d60cd95c86b307b82f0250f0cb;hpb=089aa66803c604b8b49c6a0b9c42aeefe1d67169;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 2be0ad1b401..ae0a0681479 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -1,5 +1,6 @@ /* Data references and dependences detectors. - Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc. + Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 + Free Software Foundation, Inc. Contributed by Sebastian Pop This file is part of GCC. @@ -156,6 +157,14 @@ dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs) dump_data_reference (file, dr); } +/* Dump into STDERR all the data references from DATAREFS. */ + +void +debug_data_references (VEC (data_reference_p, heap) *datarefs) +{ + dump_data_references (stderr, datarefs); +} + /* Dump to STDERR all the dependence relations from DDRS. */ void @@ -177,6 +186,14 @@ dump_data_dependence_relations (FILE *file, dump_data_dependence_relation (file, ddr); } +/* Print to STDERR the data_reference DR. */ + +void +debug_data_reference (struct data_reference *dr) +{ + dump_data_reference (stderr, dr); +} + /* Dump function for a DATA_REFERENCE structure. */ void @@ -283,7 +300,8 @@ print_direction_vector (FILE *outf, for (eq = 0; eq < length; eq++) { - enum data_dependence_direction dir = dirv[eq]; + enum data_dependence_direction dir = ((enum data_dependence_direction) + dirv[eq]); switch (dir) { @@ -551,6 +569,7 @@ split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1, enum machine_mode pmode; int punsignedp, pvolatilep; + op0 = TREE_OPERAND (op0, 0); if (!handled_component_p (op0)) return false; @@ -665,10 +684,11 @@ canonicalize_base_object_address (tree addr) return build_fold_addr_expr (TREE_OPERAND (addr, 0)); } -/* Analyzes the behavior of the memory reference DR in the innermost loop that - contains it. */ +/* Analyzes the behavior of the memory reference DR in the innermost loop or + basic block that contains it. Returns true if analysis succeed or false + otherwise. */ -void +bool dr_analyze_innermost (struct data_reference *dr) { gimple stmt = DR_STMT (dr); @@ -680,6 +700,7 @@ dr_analyze_innermost (struct data_reference *dr) int punsignedp, pvolatilep; affine_iv base_iv, offset_iv; tree init, dinit, step; + bool in_loop = (loop && loop->num); if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "analyze_innermost: "); @@ -692,26 +713,47 @@ dr_analyze_innermost (struct data_reference *dr) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "failed: bit offset alignment.\n"); - return; + return false; } base = build_fold_addr_expr (base); - if (!simple_iv (loop, stmt, base, &base_iv, false)) + if (in_loop) { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "failed: evolution of base is not affine.\n"); - return; + if (!simple_iv (loop, loop_containing_stmt (stmt), base, &base_iv, + false)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "failed: evolution of base is not affine.\n"); + return false; + } } + else + { + base_iv.base = base; + base_iv.step = ssize_int (0); + base_iv.no_overflow = true; + } + if (!poffset) { offset_iv.base = ssize_int (0); offset_iv.step = ssize_int (0); } - else if (!simple_iv (loop, stmt, poffset, &offset_iv, false)) + else { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "failed: evolution of offset is not affine.\n"); - return; + if (!in_loop) + { + offset_iv.base = poffset; + offset_iv.step = ssize_int (0); + } + else if (!simple_iv (loop, loop_containing_stmt (stmt), + poffset, &offset_iv, false)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "failed: evolution of offset is not" + " affine.\n"); + return false; + } } init = ssize_int (pbitpos / BITS_PER_UNIT); @@ -734,6 +776,8 @@ dr_analyze_innermost (struct data_reference *dr) if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "success.\n"); + + return true; } /* Determines the base object and the list of indices of memory reference @@ -746,17 +790,23 @@ dr_analyze_indices (struct data_reference *dr, struct loop *nest) struct loop *loop = loop_containing_stmt (stmt); VEC (tree, heap) *access_fns = NULL; tree ref = unshare_expr (DR_REF (dr)), aref = ref, op; - tree base, off, access_fn; - basic_block before_loop = block_before_loop (nest); - + tree base, off, access_fn = NULL_TREE; + basic_block before_loop = NULL; + + if (nest) + before_loop = block_before_loop (nest); + while (handled_component_p (aref)) { if (TREE_CODE (aref) == ARRAY_REF) { op = TREE_OPERAND (aref, 1); - access_fn = analyze_scalar_evolution (loop, op); - access_fn = instantiate_scev (before_loop, loop, access_fn); - VEC_safe_push (tree, heap, access_fns, access_fn); + if (nest) + { + access_fn = analyze_scalar_evolution (loop, op); + access_fn = instantiate_scev (before_loop, loop, access_fn); + VEC_safe_push (tree, heap, access_fns, access_fn); + } TREE_OPERAND (aref, 1) = build_int_cst (TREE_TYPE (op), 0); } @@ -764,7 +814,7 @@ dr_analyze_indices (struct data_reference *dr, struct loop *nest) aref = TREE_OPERAND (aref, 0); } - if (INDIRECT_REF_P (aref)) + if (nest && INDIRECT_REF_P (aref)) { op = TREE_OPERAND (aref, 0); access_fn = analyze_scalar_evolution (loop, op); @@ -787,34 +837,15 @@ dr_analyze_indices (struct data_reference *dr, struct loop *nest) static void dr_analyze_alias (struct data_reference *dr) { - gimple stmt = DR_STMT (dr); tree ref = DR_REF (dr); - tree base = get_base_address (ref), addr, smt = NULL_TREE; - ssa_op_iter it; - tree op; - bitmap vops; + tree base = get_base_address (ref), addr; - if (DECL_P (base)) - smt = base; - else if (INDIRECT_REF_P (base)) + if (INDIRECT_REF_P (base)) { addr = TREE_OPERAND (base, 0); if (TREE_CODE (addr) == SSA_NAME) - { - smt = symbol_mem_tag (SSA_NAME_VAR (addr)); - DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr); - } - } - - DR_SYMBOL_TAG (dr) = smt; - - vops = BITMAP_ALLOC (NULL); - FOR_EACH_SSA_TREE_OPERAND (op, stmt, it, SSA_OP_VIRTUAL_USES) - { - bitmap_set_bit (vops, DECL_UID (SSA_NAME_VAR (op))); + DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr); } - - DR_VOPS (dr) = vops; } /* Returns true if the address of DR is invariant. */ @@ -837,7 +868,6 @@ dr_address_invariant_p (struct data_reference *dr) void free_data_ref (data_reference_p dr) { - BITMAP_FREE (DR_VOPS (dr)); VEC_free (tree, heap, DR_ACCESS_FNS (dr)); free (dr); } @@ -882,8 +912,6 @@ create_data_ref (struct loop *nest, tree memref, gimple stmt, bool is_read) print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM); fprintf (dump_file, "\n\tbase_object: "); print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM); - fprintf (dump_file, "\n\tsymbol tag: "); - print_generic_expr (dump_file, DR_SYMBOL_TAG (dr), TDF_SLIM); fprintf (dump_file, "\n"); } @@ -1233,23 +1261,31 @@ dr_may_alias_p (const struct data_reference *a, const struct data_reference *b) const_tree type_a, type_b; const_tree decl_a = NULL_TREE, decl_b = NULL_TREE; - /* If the sets of virtual operands are disjoint, the memory references do not - alias. */ - if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b))) - return false; - /* 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_READ (a) && !DR_IS_READ (b)) + { + if (!refs_output_dependent_p (DR_REF (a), DR_REF (b))) + return false; + } + else if (DR_IS_READ (a) && !DR_IS_READ (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, - since currently we cannot distinguish between pointer and offset in pointer - arithmetics). */ + /* 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); @@ -1340,8 +1376,9 @@ initialize_data_dependence_relation (struct data_reference *a, /* If the base of the object is not invariant in the loop nest, we cannot analyze it. TODO -- in fact, it would suffice to record that there may be arbitrary dependences in the loops where the base object varies. */ - if (!object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0), - DR_BASE_OBJECT (a))) + if (loop_nest + && !object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0), + DR_BASE_OBJECT (a))) { DDR_ARE_DEPENDENT (res) = chrec_dont_know; return res; @@ -1398,6 +1435,7 @@ free_subscripts (VEC (subscript_p, heap) *subscripts) { free_conflict_function (s->conflicting_iterations_in_a); free_conflict_function (s->conflicting_iterations_in_b); + free (s); } VEC_free (subscript_p, heap, subscripts); } @@ -1892,6 +1930,14 @@ initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult) return chrec_convert (chrec_type (chrec), op, NULL); } + case BIT_NOT_EXPR: + { + /* Handle ~X as -1 - X. */ + tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult); + return chrec_fold_op (MINUS_EXPR, chrec_type (chrec), + build_int_cst (TREE_TYPE (chrec), -1), op); + } + case INTEGER_CST: return chrec; @@ -2288,7 +2334,7 @@ analyze_subscript_affine_affine (tree chrec_a, /* If the overlap occurs outside of the bounds of the loop, there is no dependence. */ - if (x1 > niter || y1 > niter) + if (x1 >= niter || y1 >= niter) { *overlaps_a = conflict_fn_no_dependence (); *overlaps_b = conflict_fn_no_dependence (); @@ -3304,21 +3350,6 @@ access_functions_are_affine_or_constant_p (const struct data_reference *a, return true; } -/* Return true if we can create an affine data-ref for OP in STMT. */ - -bool -stmt_simple_memref_p (struct loop *loop, gimple stmt, tree op) -{ - data_reference_p dr; - - dr = create_data_ref (loop, op, stmt, true); - if (!access_functions_are_affine_or_constant_p (dr, loop)) - return false; - - free_data_ref (dr); - return true; -} - /* Initializes an equation for an OMEGA problem using the information contained in the ACCESS_FUN. Returns true when the operation succeeded. @@ -4001,7 +4032,8 @@ compute_all_dependences (VEC (data_reference_p, heap) *datarefs, { ddr = initialize_data_dependence_relation (a, b, loop_nest); VEC_safe_push (ddr_p, heap, *dependence_relations, ddr); - compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0)); + if (loop_nest) + compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0)); } if (compute_self_and_rr) @@ -4035,7 +4067,7 @@ get_references_in_stmt (gimple stmt, VEC (data_ref_loc, heap) **references) && gimple_asm_volatile_p (stmt))) clobbers_memory = true; - if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) + if (!gimple_vuse (stmt)) return clobbers_memory; if (stmt_code == GIMPLE_ASSIGN) @@ -4108,9 +4140,10 @@ find_data_references_in_stmt (struct loop *nest, gimple stmt, dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read); gcc_assert (dr != NULL); - /* FIXME -- data dependence analysis does not work correctly for objects with - invariant addresses. Let us fail here until the problem is fixed. */ - if (dr_address_invariant_p (dr)) + /* FIXME -- data dependence analysis does not work correctly for objects + with invariant addresses in loop nests. Let us fail here until the + problem is fixed. */ + if (dr_address_invariant_p (dr) && nest) { free_data_ref (dr); if (dump_file && (dump_flags & TDF_DETAILS)) @@ -4125,6 +4158,64 @@ find_data_references_in_stmt (struct loop *nest, gimple stmt, return ret; } +/* Stores the data references in STMT to DATAREFS. If there is an unanalyzable + reference, returns false, otherwise returns true. NEST is the outermost + loop of the loop nest in which the references should be analyzed. */ + +bool +graphite_find_data_references_in_stmt (struct loop *nest, gimple stmt, + VEC (data_reference_p, heap) **datarefs) +{ + unsigned i; + VEC (data_ref_loc, heap) *references; + data_ref_loc *ref; + bool ret = true; + data_reference_p dr; + + if (get_references_in_stmt (stmt, &references)) + { + VEC_free (data_ref_loc, heap, references); + return false; + } + + for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++) + { + dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read); + gcc_assert (dr != NULL); + VEC_safe_push (data_reference_p, heap, *datarefs, dr); + } + + VEC_free (data_ref_loc, heap, references); + return ret; +} + +/* Search the data references in LOOP, and record the information into + DATAREFS. Returns chrec_dont_know when failing to analyze a + difficult case, returns NULL_TREE otherwise. */ + +static tree +find_data_references_in_bb (struct loop *loop, basic_block bb, + VEC (data_reference_p, heap) **datarefs) +{ + gimple_stmt_iterator bsi; + + for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) + { + gimple stmt = gsi_stmt (bsi); + + if (!find_data_references_in_stmt (loop, stmt, datarefs)) + { + struct data_reference *res; + res = XCNEW (struct data_reference); + VEC_safe_push (data_reference_p, heap, *datarefs, res); + + return chrec_dont_know; + } + } + + return NULL_TREE; +} + /* Search the data references in LOOP, and record the information into DATAREFS. Returns chrec_dont_know when failing to analyze a difficult case, returns NULL_TREE otherwise. @@ -4138,7 +4229,6 @@ find_data_references_in_loop (struct loop *loop, { basic_block bb, *bbs; unsigned int i; - gimple_stmt_iterator bsi; bbs = get_loop_body_in_dom_order (loop); @@ -4146,20 +4236,11 @@ find_data_references_in_loop (struct loop *loop, { bb = bbs[i]; - for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) - { - gimple stmt = gsi_stmt (bsi); - - if (!find_data_references_in_stmt (loop, stmt, datarefs)) - { - struct data_reference *res; - res = XCNEW (struct data_reference); - VEC_safe_push (data_reference_p, heap, *datarefs, res); - - free (bbs); - return chrec_dont_know; - } - } + if (find_data_references_in_bb (loop, bb, datarefs) == chrec_dont_know) + { + free (bbs); + return chrec_dont_know; + } } free (bbs); @@ -4296,6 +4377,26 @@ compute_data_dependences_for_loop (struct loop *loop, return res; } +/* Returns true when the data dependences for the basic block BB have been + computed, false otherwise. + DATAREFS is initialized to all the array elements contained in this basic + block, DEPENDENCE_RELATIONS contains the relations between the data + references. Compute read-read and self relations if + COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */ +bool +compute_data_dependences_for_bb (basic_block bb, + bool compute_self_and_read_read_dependences, + VEC (data_reference_p, heap) **datarefs, + VEC (ddr_p, heap) **dependence_relations) +{ + if (find_data_references_in_bb (NULL, bb, datarefs) == chrec_dont_know) + return false; + + compute_all_dependences (*datarefs, dependence_relations, NULL, + compute_self_and_read_read_dependences); + return true; +} + /* Entry point (for testing only). Analyze all the data references and the dependence relations in LOOP. @@ -4343,7 +4444,6 @@ analyze_all_data_dependences (struct loop *loop) { unsigned nb_top_relations = 0; unsigned nb_bot_relations = 0; - unsigned nb_basename_differ = 0; unsigned nb_chrec_relations = 0; struct data_dependence_relation *ddr; @@ -4353,15 +4453,7 @@ analyze_all_data_dependences (struct loop *loop) nb_top_relations++; else if (DDR_ARE_DEPENDENT (ddr) == chrec_known) - { - struct data_reference *a = DDR_A (ddr); - struct data_reference *b = DDR_B (ddr); - - if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b))) - nb_basename_differ++; - else - nb_bot_relations++; - } + nb_bot_relations++; else nb_chrec_relations++; @@ -4605,7 +4697,7 @@ dot_rdg (struct graph *rdg) /* This structure is used for recording the mapping statement index in the RDG. */ -struct rdg_vertex_info GTY(()) +struct GTY(()) rdg_vertex_info { gimple stmt; int index; @@ -4924,7 +5016,7 @@ stores_from_loop (struct loop *loop, VEC (gimple, heap) **stmts) gimple_stmt_iterator bsi; for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) - if (!ZERO_SSA_OPERANDS (gsi_stmt (bsi), SSA_OP_VDEF)) + if (gimple_vdef (gsi_stmt (bsi))) VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi)); }