From 358f3a0662b79de06420e7aa96864b6e43a063d3 Mon Sep 17 00:00:00 2001 From: rsandifo Date: Mon, 3 Jul 2017 07:26:21 +0000 Subject: Tweak BB analysis for dr_analyze_innermost dr_analyze_innermost had a "struct loop *nest" parameter that acted like a boolean. This was added in r179161, with the idea that a null nest selected BB-level analysis rather than loop analysis. The handling seemed strange though. If the DR was part of a loop, we still tried to express the base and offset values as IVs, potentially giving a nonzero step. If that failed for any reason, we'd revert to using the original base and offset, just as we would if we hadn't asked for an IV in the first place. It seems more natural to use the !in_loop handling whenever nest is null and always set the step to zero. This actually enables one more SLP opportunity in bb-slp-pr65935.c. I checked out r179161 and tried the patch there. The test case added in that revision still passes, so I don't think there was any particular need to check simple_iv. 2017-06-28 Richard Sandiford gcc/ * tree-data-ref.c (dr_analyze_innermost): Replace the "nest" parameter with a "loop" parameter and use it instead of the loop containing DR_STMT. Don't check simple_iv when doing BB analysis. Describe the two analysis modes in the comment. gcc/testsuite/ * gcc.dg/vect/bb-slp-pr65935.c: Expect SLP to be used in main as well. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@249896 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-data-ref.c | 66 +++++++++++++++++++++++------------------------------ 1 file changed, 29 insertions(+), 37 deletions(-) (limited to 'gcc/tree-data-ref.c') diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index ba473021534..0fcefdc43b1 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -749,15 +749,29 @@ 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 or - basic block that contains it. Returns true if analysis succeed or false - otherwise. */ +/* Analyze the behavior of memory reference DR. There are two modes: + + - BB analysis. In this case we simply split the address into base, + init and offset components, without reference to any containing loop. + The resulting base and offset are general expressions and they can + vary arbitrarily from one iteration of the containing loop to the next. + The step is always zero. + + - loop analysis. In this case we analyze the reference both wrt LOOP + and on the basis that the reference occurs (is "used") in LOOP; + see the comment above analyze_scalar_evolution_in_loop for more + information about this distinction. The base, init, offset and + step fields are all invariant in LOOP. + + Perform BB analysis if LOOP is null, or if LOOP is the function's + dummy outermost loop. In other cases perform loop analysis. + + Return true if the analysis succeeded and store the results in DR if so. + BB analysis can only fail for bitfield or reversed-storage accesses. */ bool -dr_analyze_innermost (struct data_reference *dr, struct loop *nest) +dr_analyze_innermost (struct data_reference *dr, struct loop *loop) { - gimple *stmt = DR_STMT (dr); - struct loop *loop = loop_containing_stmt (stmt); tree ref = DR_REF (dr); HOST_WIDE_INT pbitsize, pbitpos; tree base, poffset; @@ -806,22 +820,11 @@ dr_analyze_innermost (struct data_reference *dr, struct loop *nest) if (in_loop) { - if (!simple_iv (loop, loop_containing_stmt (stmt), base, &base_iv, - nest ? true : false)) + if (!simple_iv (loop, loop, base, &base_iv, true)) { - if (nest) - { - 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 (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "failed: evolution of base is not affine.\n"); + return false; } } else @@ -843,22 +846,11 @@ dr_analyze_innermost (struct data_reference *dr, struct loop *nest) offset_iv.base = poffset; offset_iv.step = ssize_int (0); } - else if (!simple_iv (loop, loop_containing_stmt (stmt), - poffset, &offset_iv, - nest ? true : false)) + else if (!simple_iv (loop, loop, poffset, &offset_iv, true)) { - if (nest) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "failed: evolution of offset is not" - " affine.\n"); - return false; - } - else - { - offset_iv.base = poffset; - offset_iv.step = ssize_int (0); - } + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "failed: evolution of offset is not affine.\n"); + return false; } } @@ -1077,7 +1069,7 @@ create_data_ref (loop_p nest, loop_p loop, tree memref, gimple *stmt, DR_REF (dr) = memref; DR_IS_READ (dr) = is_read; - dr_analyze_innermost (dr, nest); + dr_analyze_innermost (dr, nest != NULL ? loop : NULL); dr_analyze_indices (dr, nest, loop); dr_analyze_alias (dr); -- cgit v1.2.1 From 004a30422775d45c42d6156c06f4cf00a6594bf6 Mon Sep 17 00:00:00 2001 From: rsandifo Date: Mon, 3 Jul 2017 13:36:26 +0000 Subject: Make dr_analyze_innermost operate on innermost_loop_behavior This means that callers to dr_analyze_innermost don't need a full data_reference and don't need to fill in any fields beforehand. 2017-07-03 Richard Sandiford gcc/ * tree-data-ref.h (dr_analyze_innermost): Replace the dr argument with a "innermost_loop_behavior *" and refeence tree. * tree-data-ref.c (dr_analyze_innermost): Likewise. (create_data_ref): Update call accordingly. * tree-predcom.c (find_looparound_phi): Likewise. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@249913 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-data-ref.c | 22 +++++++++++----------- 1 file changed, 11 insertions(+), 11 deletions(-) (limited to 'gcc/tree-data-ref.c') diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 0fcefdc43b1..1545fdb9076 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -749,7 +749,7 @@ canonicalize_base_object_address (tree addr) return build_fold_addr_expr (TREE_OPERAND (addr, 0)); } -/* Analyze the behavior of memory reference DR. There are two modes: +/* Analyze the behavior of memory reference REF. There are two modes: - BB analysis. In this case we simply split the address into base, init and offset components, without reference to any containing loop. @@ -766,13 +766,13 @@ canonicalize_base_object_address (tree addr) Perform BB analysis if LOOP is null, or if LOOP is the function's dummy outermost loop. In other cases perform loop analysis. - Return true if the analysis succeeded and store the results in DR if so. + Return true if the analysis succeeded and store the results in DRB if so. BB analysis can only fail for bitfield or reversed-storage accesses. */ bool -dr_analyze_innermost (struct data_reference *dr, struct loop *loop) +dr_analyze_innermost (innermost_loop_behavior *drb, tree ref, + struct loop *loop) { - tree ref = DR_REF (dr); HOST_WIDE_INT pbitsize, pbitpos; tree base, poffset; machine_mode pmode; @@ -864,13 +864,12 @@ dr_analyze_innermost (struct data_reference *dr, struct loop *loop) fold_convert (ssizetype, base_iv.step), fold_convert (ssizetype, offset_iv.step)); - DR_BASE_ADDRESS (dr) = canonicalize_base_object_address (base_iv.base); - - DR_OFFSET (dr) = fold_convert (ssizetype, offset_iv.base); - DR_INIT (dr) = init; - DR_STEP (dr) = step; + drb->base_address = canonicalize_base_object_address (base_iv.base); - DR_ALIGNED_TO (dr) = size_int (highest_pow2_factor (offset_iv.base)); + drb->offset = fold_convert (ssizetype, offset_iv.base); + drb->init = init; + drb->step = step; + drb->aligned_to = size_int (highest_pow2_factor (offset_iv.base)); if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "success.\n"); @@ -1069,7 +1068,8 @@ create_data_ref (loop_p nest, loop_p loop, tree memref, gimple *stmt, DR_REF (dr) = memref; DR_IS_READ (dr) = is_read; - dr_analyze_innermost (dr, nest != NULL ? loop : NULL); + dr_analyze_innermost (&DR_INNERMOST (dr), memref, + nest != NULL ? loop : NULL); dr_analyze_indices (dr, nest, loop); dr_analyze_alias (dr); -- cgit v1.2.1 From a7e05ef215098046508869309183d6a1b83362c9 Mon Sep 17 00:00:00 2001 From: rsandifo Date: Mon, 3 Jul 2017 13:36:36 +0000 Subject: Rename DR_ALIGNED_TO to DR_OFFSET_ALIGNMENT This patch renames DR_ALIGNED_TO to DR_OFFSET_ALIGNMENT, to avoid confusion with the upcoming DR_BASE_ALIGNMENT. Nothing needed the value as a tree, and the value is clipped to BIGGEST_ALIGNMENT (maybe it should be MAX_OFILE_ALIGNMENT?) so we might as well use an unsigned int instead. 2017-07-03 Richard Sandiford gcc/ * tree-data-ref.h (innermost_loop_behavior): Replace aligned_to with offset_alignment. (DR_ALIGNED_TO): Delete. (DR_OFFSET_ALIGNMENT): New macro. * tree-vectorizer.h (STMT_VINFO_DR_ALIGNED_TO): Delete. (STMT_VINFO_DR_OFFSET_ALIGNMENT): New macro. * tree-data-ref.c (dr_analyze_innermost): Update after above changes. (create_data_ref): Likewise. * tree-vect-data-refs.c (vect_compute_data_ref_alignment): Likewise. (vect_analyze_data_refs): Likewise. * tree-if-conv.c (if_convertible_loop_p_1): Use memset before creating dummy innermost behavior. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@249914 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-data-ref.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'gcc/tree-data-ref.c') diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 1545fdb9076..c5cf0acabae 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -869,7 +869,7 @@ dr_analyze_innermost (innermost_loop_behavior *drb, tree ref, drb->offset = fold_convert (ssizetype, offset_iv.base); drb->init = init; drb->step = step; - drb->aligned_to = size_int (highest_pow2_factor (offset_iv.base)); + drb->offset_alignment = highest_pow2_factor (offset_iv.base); if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "success.\n"); @@ -1084,8 +1084,8 @@ create_data_ref (loop_p nest, loop_p loop, tree memref, gimple *stmt, print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM); fprintf (dump_file, "\n\tstep: "); print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM); - fprintf (dump_file, "\n\taligned to: "); - print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM); + fprintf (dump_file, "\n\toffset alignment: %d", + DR_OFFSET_ALIGNMENT (dr)); fprintf (dump_file, "\n\tbase_object: "); print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM); fprintf (dump_file, "\n"); -- cgit v1.2.1 From 668dd7dcb468a4e7114c3c4a301748b491b541c5 Mon Sep 17 00:00:00 2001 From: rsandifo Date: Mon, 3 Jul 2017 13:36:45 +0000 Subject: Add DR_STEP_ALIGNMENT A later patch adds base alignment information to innermost_loop_behavior. After that, the only remaining piece of alignment information that wasn't immediately obvious was the step alignment. Adding that allows a minor simplification to vect_compute_data_ref_alignment, and also potentially improves the handling of variable strides for outer loop vectorisation. A later patch will also use it to give the alignment of the DR as a whole. 2017-07-03 Richard Sandiford gcc/ * tree-data-ref.h (innermost_loop_behavior): Add a step_alignment field. (DR_STEP_ALIGNMENT): New macro. * tree-vectorizer.h (STMT_VINFO_DR_STEP_ALIGNMENT): Likewise. * tree-data-ref.c (dr_analyze_innermost): Initalize step_alignment. (create_data_ref): Print it. * tree-vect-stmts.c (vectorizable_load): Use the step alignment to tell whether the step preserves vector (mis)alignment. * tree-vect-data-refs.c (vect_compute_data_ref_alignment): Likewise. Move the check for an integer step and generalise to all INTEGER_CST. (vect_analyze_data_refs): Set DR_STEP_ALIGNMENT when setting DR_STEP. Print the outer step alignment. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@249915 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-data-ref.c | 2 ++ 1 file changed, 2 insertions(+) (limited to 'gcc/tree-data-ref.c') diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index c5cf0acabae..03dfb204685 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -870,6 +870,7 @@ dr_analyze_innermost (innermost_loop_behavior *drb, tree ref, drb->init = init; drb->step = step; drb->offset_alignment = highest_pow2_factor (offset_iv.base); + drb->step_alignment = highest_pow2_factor (step); if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "success.\n"); @@ -1086,6 +1087,7 @@ create_data_ref (loop_p nest, loop_p loop, tree memref, gimple *stmt, print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM); fprintf (dump_file, "\n\toffset alignment: %d", DR_OFFSET_ALIGNMENT (dr)); + fprintf (dump_file, "\n\tstep alignment: %d", DR_STEP_ALIGNMENT (dr)); fprintf (dump_file, "\n\tbase_object: "); print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM); fprintf (dump_file, "\n"); -- cgit v1.2.1 From a5456a6d2e5b85ae2ba6e351ddadf41bacbd6a72 Mon Sep 17 00:00:00 2001 From: rsandifo Date: Mon, 3 Jul 2017 13:36:55 +0000 Subject: Add DR_BASE_ALIGNMENT and DR_BASE_MISALIGNMENT This patch records the base alignment and misalignment in innermost_loop_behavior, to avoid the second-guessing that was previously done in vect_compute_data_ref_alignment. It also makes vect_analyze_data_refs use dr_analyze_innermost, instead of having an almost-copy of the same code. I wasn't sure whether the alignments should be measured in bits (for consistency with most other interfaces) or in bytes (for consistency with DR_ALIGNED_TO, now DR_OFFSET_ALIGNMENT, and with *_ptr_info_alignment). I went for bytes because: - I think in practice most consumers are going to want bytes. E.g. using bytes avoids having to mix TYPE_ALIGN and TYPE_ALIGN_UNIT in vect_compute_data_ref_alignment. - It means that any bit-level paranoia is dealt with when building the innermost_loop_behavior and doesn't get pushed down to consumers. 2017-07-03 Richard Sandiford gcc/ * tree-data-ref.h (innermost_loop_behavior): Add base_alignment and base_misalignment fields. (DR_BASE_ALIGNMENT, DR_BASE_MISALIGNMENT): New macros. * tree-data-ref.c: Include builtins.h. (dr_analyze_innermost): Set up the new innmost_loop_behavior fields. * tree-vectorizer.h (STMT_VINFO_DR_BASE_ALIGNMENT): New macro. (STMT_VINFO_DR_BASE_MISALIGNMENT): Likewise. * tree-vect-data-refs.c: Include tree-cfg.h. (vect_compute_data_ref_alignment): Use the new innermost_loop_behavior fields instead of calculating an alignment here. (vect_analyze_data_refs): Use dr_analyze_innermost. Dump the new innermost_loop_behavior fields. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@249916 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-data-ref.c | 51 ++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 48 insertions(+), 3 deletions(-) (limited to 'gcc/tree-data-ref.c') diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 03dfb204685..ab768535bf8 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -94,6 +94,7 @@ along with GCC; see the file COPYING3. If not see #include "dumpfile.h" #include "tree-affine.h" #include "params.h" +#include "builtins.h" static struct datadep_stats { @@ -802,11 +803,26 @@ dr_analyze_innermost (innermost_loop_behavior *drb, tree ref, return false; } + /* Calculate the alignment and misalignment for the inner reference. */ + unsigned int HOST_WIDE_INT base_misalignment; + unsigned int base_alignment; + get_object_alignment_1 (base, &base_alignment, &base_misalignment); + + /* There are no bitfield references remaining in BASE, so the values + we got back must be whole bytes. */ + gcc_assert (base_alignment % BITS_PER_UNIT == 0 + && base_misalignment % BITS_PER_UNIT == 0); + base_alignment /= BITS_PER_UNIT; + base_misalignment /= BITS_PER_UNIT; + if (TREE_CODE (base) == MEM_REF) { if (!integer_zerop (TREE_OPERAND (base, 1))) { + /* Subtract MOFF from the base and add it to POFFSET instead. + Adjust the misalignment to reflect the amount we subtracted. */ offset_int moff = mem_ref_offset (base); + base_misalignment -= moff.to_short_addr (); tree mofft = wide_int_to_tree (sizetype, moff); if (!poffset) poffset = mofft; @@ -855,20 +871,46 @@ dr_analyze_innermost (innermost_loop_behavior *drb, tree ref, } init = ssize_int (pbitpos / BITS_PER_UNIT); + + /* Subtract any constant component from the base and add it to INIT instead. + Adjust the misalignment to reflect the amount we subtracted. */ split_constant_offset (base_iv.base, &base_iv.base, &dinit); - init = size_binop (PLUS_EXPR, init, dinit); + init = size_binop (PLUS_EXPR, init, dinit); + base_misalignment -= TREE_INT_CST_LOW (dinit); + split_constant_offset (offset_iv.base, &offset_iv.base, &dinit); - init = size_binop (PLUS_EXPR, init, dinit); + init = size_binop (PLUS_EXPR, init, dinit); step = size_binop (PLUS_EXPR, fold_convert (ssizetype, base_iv.step), fold_convert (ssizetype, offset_iv.step)); - drb->base_address = canonicalize_base_object_address (base_iv.base); + base = canonicalize_base_object_address (base_iv.base); + + /* See if get_pointer_alignment can guarantee a higher alignment than + the one we calculated above. */ + unsigned int HOST_WIDE_INT alt_misalignment; + unsigned int alt_alignment; + get_pointer_alignment_1 (base, &alt_alignment, &alt_misalignment); + + /* As above, these values must be whole bytes. */ + gcc_assert (alt_alignment % BITS_PER_UNIT == 0 + && alt_misalignment % BITS_PER_UNIT == 0); + alt_alignment /= BITS_PER_UNIT; + alt_misalignment /= BITS_PER_UNIT; + + if (base_alignment < alt_alignment) + { + base_alignment = alt_alignment; + base_misalignment = alt_misalignment; + } + drb->base_address = base; drb->offset = fold_convert (ssizetype, offset_iv.base); drb->init = init; drb->step = step; + drb->base_alignment = base_alignment; + drb->base_misalignment = base_misalignment & (base_alignment - 1); drb->offset_alignment = highest_pow2_factor (offset_iv.base); drb->step_alignment = highest_pow2_factor (step); @@ -1085,6 +1127,9 @@ create_data_ref (loop_p nest, loop_p loop, tree memref, gimple *stmt, print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM); fprintf (dump_file, "\n\tstep: "); print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM); + fprintf (dump_file, "\n\tbase alignment: %d", DR_BASE_ALIGNMENT (dr)); + fprintf (dump_file, "\n\tbase misalignment: %d", + DR_BASE_MISALIGNMENT (dr)); fprintf (dump_file, "\n\toffset alignment: %d", DR_OFFSET_ALIGNMENT (dr)); fprintf (dump_file, "\n\tstep alignment: %d", DR_STEP_ALIGNMENT (dr)); -- cgit v1.2.1 From 5528b2de4ea96414487dec9b1d8bd76f8729325d Mon Sep 17 00:00:00 2001 From: rsandifo Date: Mon, 3 Jul 2017 13:37:07 +0000 Subject: Add a helper for getting the overall alignment of a DR This combines the information from previous patches to give a guaranteed alignment for the DR as a whole. This should be a bit safer than using base_element_aligned, since that only really took the base into account (not the init or offset). 2017-07-03 Richard Sandiford gcc/ * tree-data-ref.h (dr_alignment): Declare. * tree-data-ref.c (dr_alignment): New function. * tree-vectorizer.h (dataref_aux): Remove base_element_aligned. * tree-vect-data-refs.c (vect_compute_data_ref_alignment): Don't set it. * tree-vect-stmts.c (vectorizable_store): Use dr_alignment. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@249917 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-data-ref.c | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) (limited to 'gcc/tree-data-ref.c') diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index ab768535bf8..b7f9a570abb 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -4770,6 +4770,30 @@ find_data_references_in_loop (struct loop *loop, return NULL_TREE; } +/* Return the alignment in bytes that DRB is guaranteed to have at all + times. */ + +unsigned int +dr_alignment (innermost_loop_behavior *drb) +{ + /* Get the alignment of BASE_ADDRESS + INIT. */ + unsigned int alignment = drb->base_alignment; + unsigned int misalignment = (drb->base_misalignment + + TREE_INT_CST_LOW (drb->init)); + if (misalignment != 0) + alignment = MIN (alignment, misalignment & -misalignment); + + /* Cap it to the alignment of OFFSET. */ + if (!integer_zerop (drb->offset)) + alignment = MIN (alignment, drb->offset_alignment); + + /* Cap it to the alignment of STEP. */ + if (!integer_zerop (drb->step)) + alignment = MIN (alignment, drb->step_alignment); + + return alignment; +} + /* Recursive helper function. */ static bool -- cgit v1.2.1