From 9cdcebf971e71e69a773d729b97cfb55652cca31 Mon Sep 17 00:00:00 2001 From: Bin Cheng Date: Mon, 20 Nov 2017 14:20:08 +0000 Subject: [PATCH] tree-predcom.c: Add general comment on Store-Store chains. * 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 * gcc.dg/tree-ssa/predcom-dse-12.c: New test. From-SVN: r254956 --- gcc/ChangeLog | 18 +++ gcc/testsuite/ChangeLog | 4 + .../gcc.dg/tree-ssa/predcom-dse-12.c | 67 +++++++++++ gcc/tree-predcom.c | 111 ++++++++++++++---- 4 files changed, 177 insertions(+), 23 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/predcom-dse-12.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 900fa2e6583..adba8872261 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,21 @@ +2017-11-20 Bin Cheng + + * 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. + 2017-11-20 Bin Cheng * tree-predcom.c (add_ref_to_chain): Remove check on distance. diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 35fd8dfe0a9..85e4c71e8b5 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2017-11-20 Bin Cheng + + * gcc.dg/tree-ssa/predcom-dse-12.c: New test. + 2017-11-20 Marc Glisse PR testsuite/82951 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 00000000000..510c600f574 --- /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 499cedbf2c2..dde903794fd 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++) @@ -1039,19 +1041,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 ()); - return (i > 0) ? chain->refs[i - 1] : NULL; + unsigned distance = chain->refs[load_idx]->distance; + + 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. */ @@ -1075,6 +1094,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 @@ -1347,9 +1370,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)) { @@ -1361,11 +1404,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; @@ -1676,7 +1719,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; @@ -1720,7 +1763,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; @@ -1783,10 +1826,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; } @@ -2054,7 +2100,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; @@ -2091,10 +2137,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 { -- 2.30.2