Hi,
I previously introduced CT_STORE_STORE chains in predcom. This patch further
supports load
reference in CT_STORE_STORE chain if the load is dominated by a store reference
in the same
loop iteration. So example as in added test case:
for (i = 0; i < len; i++)
{
a[i] = t1;
a[i + 3] = t2;
a[i + 1] = -1;
sum = sum + a[i] + a[i + 3];
}
can be transformed into:
for (i = 0; i < len; i++)
{
a[i] = t1;
a[i + 3] = t2;
a[i + 1] = -1;
sum = sum + t1 + t2;
}
Before this patch, we can't eliminate load because no load reference is allowed
in CT_STORE_STORE
chain.
This patch only supports it if the load is dominated by a store reference in
the same loop
iteration. If we generalize this to load/store in arbitrary loop iterations,
it basically
generalizes CT_STORE_LOAD/CT_STORE_STORE chains into arbitrary mixed chain.
That would
need fundamental rewrite of the pass and not sure how useful it would be.
Bootstrap and test on x86_64 and AArch64. Is it OK?
Thanks,
bin
2017-11-15 Bin Cheng <bin.ch...@arm.com>
* tree-predcom.c: Add general comment on Store-Store chains.
(split_data_refs_to_components): Postpone clearing eliminate_store_p
flag in component.
(get_chain_last_ref_at): Rename into...
(get_chain_last_write_at): ...this.
(get_chain_last_write_before_load): New function.
(add_ref_to_chain): Promote type of chain from CT_STORE_LOAD to
CT_STORE_STORE when write reference is added.
(determine_roots_comp): Support load ref in CT_STORE_STORE chains.
(is_inv_store_elimination_chain): Update get_chain_last_write_at call.
(initialize_root_vars_store_elim_1): Ditto.
(initialize_root_vars_store_elim_2): Ditto. Replace rhs once default
definition is created.
(execute_pred_commoning_chain): Support load ref in CT_STORE_STORE
chain by replacing it with dominant stored value.
gcc/testsuite/ChangeLog
2017-11-15 Bin Cheng <bin.ch...@arm.com>
* gcc.dg/tree-ssa/predcom-dse-12.c: New test.diff --git a/gcc/testsuite/gcc.dg/tree-ssa/predcom-dse-12.c
b/gcc/testsuite/gcc.dg/tree-ssa/predcom-dse-12.c
new file mode 100644
index 0000000..510c600
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/predcom-dse-12.c
@@ -0,0 +1,67 @@
+/* { dg-do run } */
+/* { dg-options "-O2 -fno-inline -fpredictive-commoning
-fdump-tree-pcom-details" } */
+
+int arr[105] = {2, 3, 5, 7, 11};
+int result0[10] = {2, 3, 5, 7, 11};
+int result1[10] = {0, -1, 5, -2, 11, 0};
+int result2[10] = {0, 0, -1, -2, -2, 0};
+int result3[10] = {0, 0, 0, -1, -2, -2, 0};
+int result4[10] = {0, 0, 0, 0, -1, -2, -2, 0};
+int result100[105] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -2, -2, 0};
+
+extern void abort (void);
+int sum;
+
+void __attribute__((noinline)) foo (int * restrict a, int len, int t1, int t2)
+{
+ int i;
+ for (i = 0; i < len; i++)
+ {
+ a[i] = t1;
+ a[i + 3] = t2;
+ a[i + 1] = -1;
+ sum = sum + a[i] + a[i + 3];
+ }
+}
+
+void check (int *a, int *res, int len, int sval)
+{
+ int i;
+
+ if (sum != sval)
+ abort ();
+
+ for (i = 0; i < len; i++)
+ if (a[i] != res[i])
+ abort ();
+}
+
+int main (void)
+{
+ foo (arr, 0, 0, -2);
+ check (arr, result0, 10, 0);
+
+ foo (arr, 1, 0, -2);
+ check (arr, result1, 10, -2);
+
+ foo (arr, 2, 0, -2);
+ check (arr, result2, 10, -6);
+
+ foo (arr, 3, 0, -2);
+ check (arr, result3, 10, -12);
+
+ foo (arr, 4, 0, -2);
+ check (arr, result4, 10, -20);
+
+ foo (arr, 100, 0, -2);
+ check (arr, result100, 105, -220);
+
+ return 0;
+}
+/* { dg-final { scan-tree-dump "Store-stores chain" "pcom"} } */
diff --git a/gcc/tree-predcom.c b/gcc/tree-predcom.c
index d078b96..7725941 100644
--- a/gcc/tree-predcom.c
+++ b/gcc/tree-predcom.c
@@ -192,6 +192,10 @@ along with GCC; see the file COPYING3. If not see
The interesting part is this can be viewed either as general store motion
or general dead store elimination in either intra/inter-iterations way.
+ With trivial effort, we also support load inside Store-Store chains if the
+ load is dominated by a store statement in the same iteration of loop. You
+ can see this as a restricted Store-Mixed-Load-Store chain.
+
TODO: For now, we don't support store-store chains in multi-exit loops. We
force to not unroll in case of store-store chain even if other chains might
ask for unroll.
@@ -902,8 +906,6 @@ split_data_refs_to_components (struct loop *loop,
gimple_bb (dataref->stmt));
dataref->pos = comp->refs.length ();
comp->refs.quick_push (dataref);
- if (DR_IS_READ (dr))
- comp->eliminate_store_p = false;
}
for (i = 0; i < n; i++)
@@ -1028,19 +1030,36 @@ get_chain_root (chain_p chain)
return chain->refs[0];
}
-/* Given CHAIN, returns the last ref at DISTANCE, or NULL if it doesn't
+/* Given CHAIN, returns the last write ref at DISTANCE, or NULL if it doesn't
exist. */
static inline dref
-get_chain_last_ref_at (chain_p chain, unsigned distance)
+get_chain_last_write_at (chain_p chain, unsigned distance)
{
- unsigned i;
+ for (unsigned i = chain->refs.length (); i > 0; i--)
+ if (DR_IS_WRITE (chain->refs[i - 1]->ref)
+ && distance == chain->refs[i - 1]->distance)
+ return chain->refs[i - 1];
- for (i = chain->refs.length (); i > 0; i--)
- if (distance == chain->refs[i - 1]->distance)
- break;
+ return NULL;
+}
+
+/* Given CHAIN, returns the last write ref with the same distance before load
+ at index LOAD_IDX, or NULL if it doesn't exist. */
+
+static inline dref
+get_chain_last_write_before_load (chain_p chain, unsigned load_idx)
+{
+ gcc_assert (load_idx < chain->refs.length ());
+
+ unsigned distance = chain->refs[load_idx]->distance;
- return (i > 0) ? chain->refs[i - 1] : NULL;
+ for (unsigned i = load_idx; i > 0; i--)
+ if (DR_IS_WRITE (chain->refs[i - 1]->ref)
+ && distance == chain->refs[i - 1]->distance)
+ return chain->refs[i - 1];
+
+ return NULL;
}
/* Adds REF to the chain CHAIN. */
@@ -1069,6 +1083,10 @@ add_ref_to_chain (chain_p chain, dref ref)
chain->has_max_use_after = false;
}
+ /* Promote this chain to CT_STORE_STORE if it has multiple stores. */
+ if (DR_IS_WRITE (ref->ref))
+ chain->type = CT_STORE_STORE;
+
/* Don't set the flag for store-store chain since there is no use. */
if (chain->type != CT_STORE_STORE
&& ref->distance == chain->length
@@ -1341,9 +1359,29 @@ determine_roots_comp (struct loop *loop,
}
comp->refs.qsort (order_drefs);
+
+ /* For Store-Store chain, we only support load if it is dominated by a
+ store statement in the same iteration of loop. */
+ if (comp->eliminate_store_p)
+ for (a = NULL, i = 0; i < comp->refs.length (); i++)
+ {
+ if (DR_IS_WRITE (comp->refs[i]->ref))
+ a = comp->refs[i];
+ else if (a == NULL || a->offset != comp->refs[i]->offset)
+ {
+ /* If there is load that is not dominated by a store in the
+ same iteration of loop, clear the flag so no Store-Store
+ chain is generated for this component. */
+ comp->eliminate_store_p = false;
+ break;
+ }
+ }
+
+ /* Determine roots and create chains for components. */
FOR_EACH_VEC_ELT (comp->refs, i, a)
{
if (!chain
+ || (chain->type == CT_LOAD && DR_IS_WRITE (a->ref))
|| (!comp->eliminate_store_p && DR_IS_WRITE (a->ref))
|| wi::leu_p (MAX_DISTANCE, a->offset - last_ofs))
{
@@ -1355,11 +1393,11 @@ determine_roots_comp (struct loop *loop,
else
release_chain (chain);
- if (DR_IS_READ (a->ref))
- type = CT_LOAD;
- else
- type = comp->eliminate_store_p ? CT_STORE_STORE : CT_STORE_LOAD;
-
+ /* Determine type of the chain. If the root reference is a load,
+ this can only be a CT_LOAD chain; other chains are intialized
+ to CT_STORE_LOAD and might be promoted to CT_STORE_STORE when
+ new reference is added. */
+ type = DR_IS_READ (a->ref) ? CT_LOAD : CT_STORE_LOAD;
chain = make_rooted_chain (a, type);
last_ofs = a->offset;
continue;
@@ -1670,7 +1708,7 @@ is_inv_store_elimination_chain (struct loop *loop,
chain_p chain)
values. */
for (unsigned i = 0; i < chain->length; i++)
{
- dref a = get_chain_last_ref_at (chain, i);
+ dref a = get_chain_last_write_at (chain, i);
if (a == NULL)
continue;
@@ -1714,7 +1752,7 @@ initialize_root_vars_store_elim_1 (chain_p chain)
/* Initialize root value for eliminated stores at each distance. */
for (i = 0; i < n; i++)
{
- dref a = get_chain_last_ref_at (chain, i);
+ dref a = get_chain_last_write_at (chain, i);
if (a == NULL)
continue;
@@ -1777,10 +1815,13 @@ initialize_root_vars_store_elim_2 (struct loop *loop,
{
/* Root value is rhs operand of the store to be eliminated if
it isn't loaded from memory before loop. */
- dref a = get_chain_last_ref_at (chain, i);
+ dref a = get_chain_last_write_at (chain, i);
val = gimple_assign_rhs1 (a->stmt);
if (TREE_CLOBBER_P (val))
- val = get_or_create_ssa_default_def (cfun, SSA_NAME_VAR (var));
+ {
+ val = get_or_create_ssa_default_def (cfun, SSA_NAME_VAR (var));
+ gimple_assign_set_rhs1 (a->stmt, val);
+ }
vtemps[n - i - 1] = val;
}
@@ -2048,7 +2089,7 @@ static void
execute_pred_commoning_chain (struct loop *loop, chain_p chain,
bitmap tmp_vars)
{
- unsigned i, n;
+ unsigned i;
dref a;
tree var;
bool in_lhs;
@@ -2085,10 +2126,29 @@ execute_pred_commoning_chain (struct loop *loop,
chain_p chain,
finalize_eliminated_stores (loop, chain);
}
- /* Eliminate the stores killed by following store. */
- n = chain->refs.length ();
- for (i = 0; i < n - 1; i++)
- remove_stmt (chain->refs[i]->stmt);
+ bool last_store_p = true;
+ for (i = chain->refs.length (); i > 0; i--)
+ {
+ a = chain->refs[i - 1];
+ /* Preserve the last store of the chain. Eliminate other stores
+ which are killed by the last one. */
+ if (DR_IS_WRITE (a->ref))
+ {
+ if (last_store_p)
+ last_store_p = false;
+ else
+ remove_stmt (a->stmt);
+
+ continue;
+ }
+
+ /* Any load in Store-Store chain must be dominated by a previous
+ store, we replace the load reference with rhs of the store. */
+ dref b = get_chain_last_write_before_load (chain, i - 1);
+ gcc_assert (b != NULL);
+ var = gimple_assign_rhs1 (b->stmt);
+ replace_ref_with (a->stmt, var, false, false);
+ }
}
else
{
