I haven't seen any followups to this discussion of Bin's patch to
PR68303 and PR69710, the patch submission:
http://gcc.gnu.org/ml/gcc-patches/2016-05/msg02000.html
Discussion:
http://gcc.gnu.org/ml/gcc-patches/2016-07/msg00761.html
http://gcc.gnu.org/ml/gcc-patches/2016-06/msg01551.html
http://gcc.gnu.org/ml/gcc-patches/2016-06/msg00372.html
http://gcc.gnu.org/ml/gcc-patches/2016-06/msg01550.html
http://gcc.gnu.org/ml/gcc-patches/2016-05/msg02162.html
http://gcc.gnu.org/ml/gcc-patches/2016-05/msg02155.html
http://gcc.gnu.org/ml/gcc-patches/2016-05/msg02154.html
so I did some investigation to get a better understanding of the
issues involved.
On 07/13/2016 01:59 PM, Jeff Law wrote:
> On 05/25/2016 05:22 AM, Bin Cheng wrote:
>> Hi, As analyzed in PR68303 and PR69710, vectorizer generates
>> duplicated computations in loop's pre-header basic block when
>> creating base address for vector reference to the same memory object.
> Not a huge surprise. Loop optimizations generally have a tendency
> to create and/or expose CSE opportunities. Unrolling is a common
> culprit, there's certainly the possibility for header duplication,
> code motions and IV rewriting to also expose/create redundant code.
>
> ...
>
> But, 1) It
>> doesn't fix all the problem on x86_64. Root cause is computation for
>> base address of the first reference is somehow moved outside of
>> loop's pre-header, local CSE can't help in this case.
> That's a bid odd -- have you investigated why this is outside the loop header?
> ...
I didn't look at this issue per se, but I did try running DOM between
autovectorization and IVS. Just running DOM had little effect, what
was crucial was adding the change Bin mentioned in his original
message:
Besides CSE issue, this patch also re-associates address
expressions in vect_create_addr_base_for_vector_ref, specifically,
it splits constant offset and adds it back near the expression
root in IR. This is necessary because GCC only handles
re-association for commutative operators in CSE.
I attached a patch for these changes only. These are the important
modifications that address the some of the IVS related issues exposed
by PR68303. I found that adding the CSE change (or calling DOM between
autovectorization and IVOPTS) is not needed, and from what I have
seen, actually makes the code worse.
Applying only the modifications to
vect_create_addr_base_for_vector_ref, additional simplifications will
be done when induction variables are found (function
find_induction_variables). These simplications are indicated by the
appearance of lines:
Applying pattern match.pd:1056, generic-match.c:11865
in the IVOPS dump file. Now IVOPTs transforms the code so that
constants now appear in the computation of the effective addresses for
the memory OPs. However the code generated by IVOPTS still uses a
separate base register for each memory reference. Later DOM3
transforms the code to use just one base register, which is the form
the code needs to be in for the preliminary phase of IVOPTs where
"IV uses" associated with memory OPs are placed into groups. At the
time of this grouping, checks are done to ensure that for each member
of a group the constant offsets don't overflow the immediate fields in
actual machine instructions (more in this see * below).
Currently it appears that an IV is generated for each memory
reference. Instead of generating a new IV for each memory reference,
we could try to detect that value of the new IV is just a constant
offset of an existing IV and just generate a new temp reflecting that.
I haven't worked through what needs to be done to implement that, but
for the issue in PR69710 (saxpy example where the same IV should be
used for a load and store) is straightforward to implement so since
work has already been done in during data dependence analysis to
detect this situation. I attached a patch for PR69710 that was
bootstrapped and tested on X86_64 without errors. It does appear that
it needs more testing, since I did notice SPEC 2006 h264ref produces
different results with the patch applied, which I still need to
investigate.
Doug
* Note that when IV uses are grouped, only positive constant offsets
constraints are considered. That negative offsets can be used are
reflected in the costs of using a different IV than the IV associated
with a particular group. Thus once the optimal IV set is found, a
different IV may chosen, which causes negative constant offsets to be
used.
>From 3ea70edb3bf68057c955d2b22204f17bb670f65a Mon Sep 17 00:00:00 2001
From: Doug Gilmore <doug.gilm...@imgtec.com>
Date: Fri, 4 Nov 2016 18:49:58 -0700
Subject: [PATCH] [PR68030/PR69710] vect_create_addr_base_for_vector_ref
changes only fix.
This patch include changes noted in Bin's first patch message:
https://gcc.gnu.org/ml/gcc-patches/2016-05/msg02000.html
Besides CSE issue, this patch also re-associates address expressions
in vect_create_addr_base_for_vector_ref, specifically, it splits
constant offset and adds it back near the expression root in IR. This
is necessary because GCC only handles re-association for commutative
operators in CSE.
With these changes only one IV and one base register is used for
vectorized memory references in the example for PR68030.
Unfortunately memory OP IV uses cannot be grouped per the comment in
tree-ssa-loop-ivopts.c:
1) The interesting uses of induction variables are found. This includes
-- uses of induction variables in non-linear expressions
-- addresses of arrays
-- comparisons of induction variables
Note the interesting uses are categorized and handled in group.
Generally, address type uses are grouped together if their iv bases
are different in constant offset.
AFAICS checks to select IVs so that offsets do not overflow the fields
in the machine instructions will not be done unless IV uses are
grouped together.
---
gcc/tree-vect-data-refs.c | 24 ++++++++++++++++--------
1 file changed, 16 insertions(+), 8 deletions(-)
diff --git a/gcc/tree-vect-data-refs.c b/gcc/tree-vect-data-refs.c
index 5a30314..4cbe7ae 100644
--- a/gcc/tree-vect-data-refs.c
+++ b/gcc/tree-vect-data-refs.c
@@ -4239,23 +4239,27 @@ vect_create_addr_base_for_vector_ref (gimple *stmt,
base_name = get_name (DR_REF (dr));
}
- /* Create base_offset */
- base_offset = size_binop (PLUS_EXPR,
- fold_convert (sizetype, base_offset),
- fold_convert (sizetype, init));
+ base_offset = fold_convert (sizetype, base_offset);
+ init = fold_convert (sizetype, init);
if (offset)
{
offset = fold_build2 (MULT_EXPR, sizetype,
fold_convert (sizetype, offset), step);
- base_offset = fold_build2 (PLUS_EXPR, sizetype,
- base_offset, offset);
+ if (TREE_CODE (offset) == INTEGER_CST)
+ init = fold_build2 (PLUS_EXPR, sizetype, init, offset);
+ else
+ base_offset = fold_build2 (PLUS_EXPR, sizetype,
+ base_offset, offset);
}
if (byte_offset)
{
byte_offset = fold_convert (sizetype, byte_offset);
- base_offset = fold_build2 (PLUS_EXPR, sizetype,
- base_offset, byte_offset);
+ if (TREE_CODE (byte_offset) == INTEGER_CST)
+ init = fold_build2 (PLUS_EXPR, sizetype, init, byte_offset);
+ else
+ base_offset = fold_build2 (PLUS_EXPR, sizetype,
+ base_offset, byte_offset);
}
/* base + base_offset */
@@ -4269,6 +4273,10 @@ vect_create_addr_base_for_vector_ref (gimple *stmt,
}
vect_ptr_type = build_pointer_type (STMT_VINFO_VECTYPE (stmt_info));
+ addr_base = force_gimple_operand (addr_base, &seq, true, NULL);
+ gimple_seq_add_seq (new_stmt_list, seq);
+ /* Add constant offset at last. */
+ addr_base = fold_build_pointer_plus (addr_base, init);
dest = vect_get_new_vect_var (vect_ptr_type, vect_pointer_var, base_name);
addr_base = force_gimple_operand (addr_base, &seq, true, dest);
gimple_seq_add_seq (new_stmt_list, seq);
--
1.9.1
>From 68d783d5b8e3a6238a7e7b25d76fc6e457bfc484 Mon Sep 17 00:00:00 2001
From: Doug Gilmore <doug.gilm...@imgtec.com>
Date: Fri, 18 Nov 2016 13:29:47 -0800
Subject: [PATCH] Another prototype fix to PR69710.
Would need to be extended to handle PR68030.
Tested on r240609 several weeks ago: bootstrapped and no make check
regressions on x86_64-unknown-linux-gnu, though a run-time error on
SPEC 2006 h264ref at -O3 with --size=test was observed.
---
gcc/tree-data-ref.c | 1 +
gcc/tree-data-ref.h | 4 ++++
gcc/tree-vect-data-refs.c | 50 ++++++++++++++++++++++++++++++++++++++++++++---
gcc/tree-vect-loop.c | 2 ++
gcc/tree-vectorizer.h | 5 +++++
5 files changed, 59 insertions(+), 3 deletions(-)
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index 8152da3..7a4850c 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -1492,6 +1492,7 @@ initialize_data_dependence_relation (struct data_reference *a,
DDR_SUBSCRIPTS (res).create (0);
DDR_DIR_VECTS (res).create (0);
DDR_DIST_VECTS (res).create (0);
+ DDR_PREHEADER_IV (res) = NULL_TREE;
if (a == NULL || b == NULL)
{
diff --git a/gcc/tree-data-ref.h b/gcc/tree-data-ref.h
index 856dd58..ca67d93 100644
--- a/gcc/tree-data-ref.h
+++ b/gcc/tree-data-ref.h
@@ -264,6 +264,9 @@ struct data_dependence_relation
/* Set to true when the dependence relation is on the same data
access. */
bool self_reference_p;
+
+ /* For zero distance dependencies, use the same IV in the preheader. */
+ tree preheader_iv;
};
typedef struct data_dependence_relation *ddr_p;
@@ -294,6 +297,7 @@ typedef struct data_dependence_relation *ddr_p;
#define DDR_DIST_VECT(DDR, I) \
DDR_DIST_VECTS (DDR)[I]
#define DDR_REVERSED_P(DDR) DDR->reversed_p
+#define DDR_PREHEADER_IV(DDR) DDR->preheader_iv
bool dr_analyze_innermost (struct data_reference *, struct loop *);
diff --git a/gcc/tree-vect-data-refs.c b/gcc/tree-vect-data-refs.c
index 5a30314..12cfbec 100644
--- a/gcc/tree-vect-data-refs.c
+++ b/gcc/tree-vect-data-refs.c
@@ -394,6 +394,7 @@ vect_analyze_data_ref_dependence (struct data_dependence_relation *ddr,
}
}
+ LOOP_VINFO_ZERO_DIST_DEPS (loop_vinfo).safe_push (ddr);
continue;
}
@@ -4492,10 +4493,53 @@ vect_create_data_ref_ptr (gimple *stmt, tree aggr_type, struct loop *at_loop,
/* (2) Calculate the initial address of the aggregate-pointer, and set
the aggregate-pointer to point to it before the loop. */
- /* Create: (&(base[init_val+offset]+byte_offset) in the loop preheader. */
+ /* Create: (&(base[init_val+offset]+byte_offset) in the loop preheader,
+ taking care to use reuse IVs. */
- new_temp = vect_create_addr_base_for_vector_ref (stmt, &new_stmt_list,
- offset, loop, byte_offset);
+ bool need_new_temp = true;
+ ddr_p zd_ddr = (ddr_p) NULL;
+ if (loop_vinfo)
+ {
+ int i;
+ ddr_p ddr;
+
+
+ FOR_EACH_VEC_ELT (LOOP_VINFO_ZERO_DIST_DEPS (loop_vinfo), i, ddr)
+ {
+ if (DDR_A(ddr) == dr || DDR_B(ddr) == dr)
+ {
+ zd_ddr = ddr;
+ break;
+ }
+ }
+
+ if (zd_ddr && DDR_PREHEADER_IV (zd_ddr))
+ {
+ new_temp = DDR_PREHEADER_IV (zd_ddr);
+ need_new_temp = false;
+ if (dump_enabled_p ())
+ {
+ dump_printf_loc (MSG_NOTE, vect_location, "reuse ");
+ dump_generic_expr (MSG_NOTE, TDF_SLIM, new_temp);
+ dump_printf (MSG_NOTE, "\n");
+ }
+ }
+ }
+
+ if (need_new_temp)
+ new_temp = vect_create_addr_base_for_vector_ref (stmt, &new_stmt_list,
+ offset, loop, byte_offset);
+ if (zd_ddr)
+ {
+ DDR_PREHEADER_IV (zd_ddr) = new_temp;
+ if (dump_enabled_p ())
+ {
+ dump_printf_loc (MSG_NOTE, vect_location, "save ");
+ dump_generic_expr (MSG_NOTE, TDF_SLIM, new_temp);
+ dump_printf (MSG_NOTE, "\n");
+ }
+ }
+
if (new_stmt_list)
{
if (pe)
diff --git a/gcc/tree-vect-loop.c b/gcc/tree-vect-loop.c
index 4150b0d..0bf67e9 100644
--- a/gcc/tree-vect-loop.c
+++ b/gcc/tree-vect-loop.c
@@ -1173,6 +1173,7 @@ new_loop_vec_info (struct loop *loop)
LOOP_VINFO_PEELING_FOR_NITER (res) = false;
LOOP_VINFO_OPERANDS_SWAPPED (res) = false;
LOOP_VINFO_ORIG_LOOP_INFO (res) = NULL;
+ LOOP_VINFO_ZERO_DIST_DEPS (res) = vNULL;
return res;
}
@@ -1271,6 +1272,7 @@ destroy_loop_vec_info (loop_vec_info loop_vinfo, bool clean_stmts)
LOOP_VINFO_GROUPED_STORES (loop_vinfo).release ();
LOOP_VINFO_REDUCTIONS (loop_vinfo).release ();
LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo).release ();
+ LOOP_VINFO_ZERO_DIST_DEPS (loop_vinfo).release ();
destroy_cost_data (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo));
loop_vinfo->scalar_cost_vec.release ();
diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index 2a7fa0a..7fcc824 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -339,6 +339,10 @@ typedef struct _loop_vec_info : public vec_info {
this points to the original vectorized loop. Otherwise NULL. */
_loop_vec_info *orig_loop_info;
+ /* Dependency relations that have zero distance, thus the associated
+ memory references can share the same IV. */
+ vec<ddr_p> zero_dist_deps;
+
} *loop_vec_info;
/* Access Functions. */
@@ -379,6 +383,7 @@ typedef struct _loop_vec_info : public vec_info {
#define LOOP_VINFO_SCALAR_ITERATION_COST(L) (L)->scalar_cost_vec
#define LOOP_VINFO_SINGLE_SCALAR_ITERATION_COST(L) (L)->single_scalar_iteration_cost
#define LOOP_VINFO_ORIG_LOOP_INFO(L) (L)->orig_loop_info
+#define LOOP_VINFO_ZERO_DIST_DEPS(L) (L)->zero_dist_deps
#define LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT(L) \
((L)->may_misalign_stmts.length () > 0)
--
1.9.1
