On Mon, Jul 24, 2017 at 4:27 PM, Bin.Cheng <amker.ch...@gmail.com> wrote:
> Ping^1.

Ok.

Thanks and sorry for the delay.
Richard.

> Thanks,
> bin
>
> On Mon, Jul 10, 2017 at 9:23 AM, Bin.Cheng <amker.ch...@gmail.com> wrote:
>> On Tue, Jul 4, 2017 at 1:29 PM, Richard Biener
>> <richard.guent...@gmail.com> wrote:
>>> On Tue, Jul 4, 2017 at 2:06 PM, Bin.Cheng <amker.ch...@gmail.com> wrote:
>>>> On Tue, Jul 4, 2017 at 12:19 PM, Richard Biener
>>>> <richard.guent...@gmail.com> wrote:
>>>>> On Mon, Jul 3, 2017 at 4:17 PM, Bin.Cheng <amker.ch...@gmail.com> wrote:
>>>>>> On Mon, Jul 3, 2017 at 10:38 AM, Richard Biener
>>>>>> <richard.guent...@gmail.com> wrote:
>>>>>>> On Tue, Jun 27, 2017 at 12:49 PM, Bin Cheng <bin.ch...@arm.com> wrote:
>>>>>>>> Hi,
>>>>>>>> For the moment, tree-predcom.c only supports 
>>>>>>>> invariant/load-loads/store-loads chains.
>>>>>>>> This patch generalizes dead store elimination (or store motion) across 
>>>>>>>> loop iterations in
>>>>>>>> predictive commoning pass by supporting store-store chain.  As comment 
>>>>>>>> in the patch:
>>>>>>>>
>>>>>>>>    Apart from predictive commoning on Load-Load and Store-Load chains, 
>>>>>>>> we
>>>>>>>>    also support Store-Store chains -- stores killed by other store can 
>>>>>>>> be
>>>>>>>>    eliminated.  Given below example:
>>>>>>>>
>>>>>>>>      for (i = 0; i < n; i++)
>>>>>>>>        {
>>>>>>>>          a[i] = 1;
>>>>>>>>          a[i+2] = 2;
>>>>>>>>        }
>>>>>>>>
>>>>>>>>    It can be replaced with:
>>>>>>>>
>>>>>>>>      t0 = a[0];
>>>>>>>>      t1 = a[1];
>>>>>>>>      for (i = 0; i < n; i++)
>>>>>>>>        {
>>>>>>>>          a[i] = 1;
>>>>>>>>          t2 = 2;
>>>>>>>>          t0 = t1;
>>>>>>>>          t1 = t2;
>>>>>>>>        }
>>>>>>>>      a[n] = t0;
>>>>>>>>      a[n+1] = t1;
>>>>>>>>
>>>>>>>>    If the loop runs more than 1 iterations, it can be further 
>>>>>>>> simplified into:
>>>>>>>>
>>>>>>>>      for (i = 0; i < n; i++)
>>>>>>>>        {
>>>>>>>>          a[i] = 1;
>>>>>>>>        }
>>>>>>>>      a[n] = 2;
>>>>>>>>      a[n+1] = 2;
>>>>>>>>
>>>>>>>>    The interesting part is this can be viewed either as general store 
>>>>>>>> motion
>>>>>>>>    or general dead store elimination in either intra/inter-iterations 
>>>>>>>> way.
>>>>>>>>
>>>>>>>> There are number of interesting facts about this enhancement:
>>>>>>>> a) This patch supports dead store elimination for both 
>>>>>>>> across-iteration case and single-iteration
>>>>>>>>      case.  For the latter, it is dead store elimination.
>>>>>>>> b) There are advantages supporting dead store elimination in predcom, 
>>>>>>>> for example, it has
>>>>>>>>      complete information about memory address.  On the contrary, DSE 
>>>>>>>> pass can only handle
>>>>>>>>      memory references with exact the same memory address expression.
>>>>>>>> c) It's cheap to support store-stores chain in predcom based on 
>>>>>>>> existing code.
>>>>>>>> d) As commented, the enhancement can be viewed as either generalized 
>>>>>>>> dead store elimination
>>>>>>>>      or generalized store motion.  I prefer DSE here.
>>>>>>>>
>>>>>>>> Bootstrap(O2/O3) in patch series on x86_64 and AArch64.  Is it OK?
>>>>>>>
>>>>>>> Looks mostly ok.  I have a few questions though.
>>>>>>>
>>>>>>> +  /* Don't do store elimination if loop has multiple exit edges.  */
>>>>>>> +  bool eliminate_store_p = single_exit (loop) != NULL;
>>>>>>>
>>>>>>> handling this would be an enhancement?  IIRC LIM store-motion handles 
>>>>>>> this
>>>>>>> just fine by emitting code on all exits.
>>>>>> It is an enhancement with a little bit more complication.  We would
>>>>>> need to setup/record finalizer memory references for different exit
>>>>>> edges.  I added TODO description for this (and following one).  Is it
>>>>>> okay to pick up this in the future?
>>>>>
>>>>> Yes.
>>>>>
>>>>>>>
>>>>>>> @@ -1773,6 +2003,9 @@ determine_unroll_factor (vec<chain_p> chains)
>>>>>>>      {
>>>>>>>        if (chain->type == CT_INVARIANT)
>>>>>>>         continue;
>>>>>>> +      /* Don't unroll when eliminating stores.  */
>>>>>>> +      else if (chain->type == CT_STORE_STORE)
>>>>>>> +       return 1;
>>>>>>>
>>>>>>> this is a hard exit value so we do not handle the case where another 
>>>>>>> chain
>>>>>>> in the loop would want to unroll? (enhancement?)  I'd have expected to 
>>>>>>> do
>>>>>>> the same as for CT_INVARIANT here.
>>>>>> I didn't check what change is needed in case of unrolling.  I am not
>>>>>> very sure if we should prefer unroll for *load chains or prefer not
>>>>>> unroll for store-store chains, because unroll in general increases
>>>>>> loop-carried register pressure for store-store chains rather than
>>>>>> decreases register pressure for *load chains.
>>>>>> I was also thinking if it's possible to restrict unrolling somehow in
>>>>>> order to enable predcom at O2.  BTW, this is not common, it only
>>>>>> happens once in spec2k6 with factor forced to 1.  So okay if as it is
>>>>>> now?
>>>>>
>>>>> I think it is ok for now with a TODO added.  Please change the comment
>>>>> to "we can't handle unrolling when eliminating stores" (it's not clear if 
>>>>> we
>>>>> can -- did you try?  maybe add a testcase that would ICE)
>>>>>
>>>>>>
>>>>>>>
>>>>>>> +      tree init = ref_at_iteration (dr, (int) 0 - i, &stmts);
>>>>>>> +      if (!chain->all_always_accessed && tree_could_trap_p (init))
>>>>>>> +       {
>>>>>>> +         gimple_seq_discard (stmts);
>>>>>>> +         return false;
>>>>>>>
>>>>>>> so this is the only place that remotely cares for not always performed 
>>>>>>> stores.
>>>>>>> But as-is the patch doesn't seem to avoid speculating stores and thus
>>>>>>> violates the C++ memory model, aka, introduces store-data-races?  The 
>>>>>>> LIM
>>>>>>> store-motion code was fixed to avoid this by keeping track of whether a 
>>>>>>> BB
>>>>>>> has executed to guard the stores done in the compensation code on the 
>>>>>>> loop
>>>>>>> exit.
>>>>>>>
>>>>>>> That said, to "fix" this all && tree_could_trap_p cases would need to 
>>>>>>> be removed
>>>>>>> (or similarly flag vars be introduced).  Speculating loads that do not
>>>>>>> trap is ok
>>>>>>> (might only introduce false uninit use reports by tools like valgrind).
>>>>>> Hmm, not sure IIUC.  Patch updated, is it correct (though conservative)?
>>>>>
>>>>> +static bool
>>>>> +prepare_initializers_chain_store_elim (struct loop *, chain_p chain)
>>>>> +{
>>>>> ...
>>>>> +      tree init = ref_at_iteration (dr, (int) 0 - i, &stmts);
>>>>> +      if (!chain->all_always_accessed && tree_could_trap_p (init))
>>>>> +       {
>>>>>
>>>>> remove && tree_could_trap_p and hoist the other check.
>>>>>
>>>>> Same in prepare_finalizers_chain.  I think you should check
>>>>>
>>>>>    if (! chain->all_always_accessed
>>>>>       && ! PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES))
>>>>>      return false;
>>>>>
>>>>> at the beginning of both functions and retain
>>>>>
>>>>>     if (! chain->all_always_accessed && tree_could_trap_p ())
>>>>>
>>>>> in the loops.
>>>>>
>>>>> Ok with that change and a testcase that would exercise failure/ICE of
>>>>> store chains w/ unrolling.
>>>> Hmm, now I remember maybe these
>>>> all_always_accessed/trap/data_store_race checks can be simplified.  In
>>>> function suitable_component_p, we call just_once_each_iteration_p for
>>>> all references.  So we shouldn't not end up with
>>>> chain->all_always_accessed == false cases, right?  why means we don't
>>>> really need to check at all?
>>>
>>> Not sure.  We have this check in the existing code already.  Please come
>>> up with a testcase that we might not DSE-pcom because of store speculation.
>> So just_once_each_iteration_p function call skips all if-condition
>> cases, while chain->all_always_accessed skips multi-exit cases.  As
>> for store-elimination, given we already requires single-exit loops, we
>> can assume chain->all_always_accessed is true in
>> prepare_initializers_chain_store_elim and prepare_finalizers_chain.
>> To make code clearer, this updated patch explicitly checks
>> chain->all_always_accessed at the beginning of both functions.  The
>> fact is, we can't eliminate conditional stores (at least with current
>> code) because both the condition and niters need to be compilation
>> time constants to propagate the value for storing.  It's complicated
>> and may not worth the effort if they are constants.
>> I also added two new tests, one for conditional store elimination, the
>> other for unrolling/store-elimination.
>> Bootstrap and test on x86_64 and AArch64.  Is it OK?
>>
>> Thanks,
>> bin
>> 2017-07-04  Bin Cheng  <bin.ch...@arm.com>
>>
>>     * tree-predcom.c: Revise general description of pass.
>>     (enum chain_type): New enum type for store elimination.
>>     (struct chain): New field supporting store elimination.
>>     (dump_chain): Dump store-stores chain.
>>     (release_chain): Release resources.
>>     (split_data_refs_to_components): Compute and create component
>>     contains only stores for elimination.
>>     (get_chain_last_ref_at): New function.
>>     (make_invariant_chain): Initialization.
>>     (make_rooted_chain): Specify chain type in parameter.
>>     (add_looparound_copies): Skip for store-stores chain.
>>     (determine_roots_comp): Compute type of chain and pass it to
>>     make_rooted_chain.
>>     (initialize_root_vars_store_elim_2): New function.
>>     (finalize_eliminated_stores): New function.
>>     (remove_stmt): Handle store for elimination.
>>     (execute_pred_commoning_chain): Execute predictive commoning on
>>     store-store chains.
>>     (determine_unroll_factor): Skip unroll for store-stores chain.
>>     (prepare_initializers_chain_store_elim): New function.
>>     (prepare_initializers_chain): Hanlde store-store chain.
>>     (prepare_finalizers_chain, prepare_finalizers): New function.
>>     (tree_predictive_commoning_loop): Return integer value indicating
>>     if loop is unrolled or lcssa form is corrupted.
>>     (tree_predictive_commoning): Rewrite for lcssa form if necessary.
>>
>> gcc/testsuite/ChangeLog
>> 2017-07-04  Bin Cheng  <bin.ch...@arm.com>
>>
>>     * gcc.dg/tree-ssa/predcom-dse-1.c: New test.
>>     * gcc.dg/tree-ssa/predcom-dse-2.c: New test.
>>     * gcc.dg/tree-ssa/predcom-dse-3.c: New test.
>>     * gcc.dg/tree-ssa/predcom-dse-4.c: New test.
>>     * gcc.dg/tree-ssa/predcom-dse-5.c: New test.
>>     * gcc.dg/tree-ssa/predcom-dse-6.c: New test.
>>     * gcc.dg/tree-ssa/predcom-dse-7.c: New test.
>>     * gcc.dg/tree-ssa/predcom-dse-8.c: New test.
>>     * gcc.dg/tree-ssa/predcom-dse-9.c: New test.
>>     * gcc.dg/tree-ssa/predcom-dse-10.c: New test.
>>     * gcc.dg/tree-ssa/predcom-dse-11.c: New test.

Reply via email to