Re: [PATCH GCC][V2]A simple implementation of loop interchange

[Richard Biener <richard dot guenther at gmail dot com>]

On Thu, Nov 30, 2017 at 4:09 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Thu, Nov 30, 2017 at 3:13 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>> On Thu, Nov 30, 2017 at 1:01 PM, Richard Biener
>> <richard.guenther@gmail.com> wrote:
>>> On Tue, Nov 28, 2017 at 4:26 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>>>> Hi,
>>>> This is updated patch with review comments resolved.  Some explanation embedded below.
>>>>
>>>>> +
>>>>> +  iloop->nb_iterations = nb_iterations;
>>>>>
>>>>> use std::swap?  Also I think if you can keep nb_iterations you
>>>>> can certainly keep the upper bounds.  You're probably
>>>>> afraid of the ->stmt references in the nb_iter_bound entries?
>>>>>
>>>>> Anyway, either scrap everything or try to keep everything.
>>>> Yeah, not only the stmts, but also the control_iv information because the SCEV
>>>> information may be corrupted during code transformation.
>>>> Now I discarded all the information.
>>>
>>> Note that given you interchange the loops but not the CFG or the loop structures
>>> you might want to swap loop->num and flags like ->force_vectorize.  That is,
>>> essentially change the ->header/latch association (and other CFG related stuff
>>> like recorded exits).
>>>
>>> It might also be we want to / need to disable interchange for, say,
>>> ->force_vectorize
>>> inner loops or ->unroll != 0?  Or we need to clear them, maybe
>>> optionally diagnosing
>>> that fact.
>>>
>>> At least we need to think about what it means to preserve loop
>>> structure (semantically,
>>> loop->num should maintain association to the same source-level loop
>>> throughout the
>>> compilation) for transforms like interchange.
>>>
>>>>>
>>>>> +  for (i = 0; oloop.reductions.iterate (i, &re); ++i)
>>>>> +    {
>>>>> +      if (re->type != DOUBLE_RTYPE)
>>>>> +       gcc_unreachable ();
>>>>> +
>>>>> +      use_operand_p use_p;
>>>>> +      imm_use_iterator iterator;
>>>>> +      FOR_EACH_IMM_USE_FAST (use_p, iterator, re->var)
>>>>> +       mark_or_remove_dbg_stmt (USE_STMT (use_p), re->var);
>>>>> +      FOR_EACH_IMM_USE_FAST (use_p, iterator, re->next)
>>>>> +       mark_or_remove_dbg_stmt (USE_STMT (use_p), re->next);
>>>>> +      if (TREE_CODE (re->init) == SSA_NAME)
>>>>> +       {
>>>>> +         FOR_EACH_IMM_USE_FAST (use_p, iterator, re->init)
>>>>> +           mark_or_remove_dbg_stmt (USE_STMT (use_p), re->init);
>>>>> +       }
>>>>>
>>>>> can you add a comment what you are doing here?
>>>>>
>>>>> Note that other loop opts simply scrap all debug stmts ...
>>>> As mentioned above, updated patch doesn't try hard to maintain debug use info any more.
>>>>
>>>>>
>>>>> +static void
>>>>> +compute_access_stride (struct loop *loop_nest, struct loop *loop,
>>>>> +                      data_reference_p dr)
>>>>> +{
>>>>> ...
>>>>> +  tree ref = DR_REF (dr);
>>>>> +  tree scev_base = build_fold_addr_expr (ref);
>>>>> +  tree access_size = TYPE_SIZE_UNIT (TREE_TYPE (ref));
>>>>> +  tree niters = build_int_cst (sizetype, AVG_LOOP_NITER);
>>>>> +  access_size = fold_build2 (MULT_EXPR, sizetype, niters, access_size);
>>>>> +
>>>>> +  do {
>>>>> +    tree scev_fn = analyze_scalar_evolution (loop, scev_base);
>>>>> +    if (chrec_contains_undetermined (scev_fn)
>>>>> +       || chrec_contains_symbols_defined_in_loop (scev_fn, loop->num))
>>>>> +      break;
>>>>> ...
>>>>> +    strides->safe_push (scev_step);
>>>>> +  } while (loop != loop_nest && (loop = loop_outer (loop)) != NULL);
>>>>> +
>>>>>
>>>>> I _think_ you want to do
>>>>>
>>>>>    scev_fn = analyze_scalar_evolution (loop, scev_base); // assuming
>>>>> DR_STMT (dr) is in loop
>>>>>    scev_fn = instantiate_parameters (nest, scev_fn);
>>>>>    if (chrec_contains_undetermined (scev_fn))
>>>>>      return; // false?
>>>>>
>>>>> and analyze the result which should be of the form
>>>>>
>>>>>   { { { init, +, step1 }_1, +, step2 }_2, + , step3 }_3 ...
>>>>>
>>>>> if canonical.  I think estimate_val_by_simplify_replace isn't needed
>>>>> if you do that
>>>>> (it also looks odd to replace all vairables in step by niter...).
>>>> I replied on this in previous message, instantiate_parameters doesn't always
>>>> give canonical form result as expected.  The loop here could be seen as a
>>>> local instantiate process, right?
>>>
>>> Kind of.  I'll see if I can reproduce the difference with any of your
>>> intercahnge
>>> testcases - any hint which one to look at?
>> For added tests, I think there will be no difference between the two.
>> I noticed the difference for
>> pointer cases like:
>> for (i...)
>>   for (j...)
>>     for (k...)
>>        p[i*n*n + j*n+ k] =...
>>
>>>
>>>> Also estimate_val_by_simplify_replace is needed for pointers, where strides
>>>> are computed from niters of loops which could be non compilation time constant.
>>>> But yes, it's an odd fixup after I failed to do anything better.
>>>
>>> But you are for example computing _1 - _2 to zero, right?  Because both _1
>>> and _2 are not constant and thus you replace it with the same (symbolical)
>>> constant 'niter'.
>>>
>>> I think that asks for garbage-in-garbage-out ...
>>>
>>> Which testcase is this important for so I can have a look?
>> So far this is only for the above pointer case.  Actually I don't
>> think it's that important, and thought about skip it.
>> So we don't have to do estimate_val_by_simplify_replace.
>
> Ok, I'd like to "dumb" the pass down to the level we can solve the
> bwave case (which I realize is already one of the more complicated ones).
>
> Just because it's already late for GCC 8.

For reference I'll commit the following tomorrow, will play with adding
a testcase for bwaves and doing the multiple_of_p thing we talked about.

Richard.

> Richard.
>
>> Thanks,
>> bin
>>>
>>>>>
>>>>> I think keeping the chrec in the above form is also more suitable for what
>>>>> the caller does so the outermost loop is simply
>>>>>
>>>>>   loop = loop_nest;
>>>>>   loop-over-all-dr-chrecs
>>>>>     if (flow_loop_nested_p (loop, CHREC_LOOP (chrec)))
>>>>>       loop = CHREC_LOOP (chrec);
>>>>>
>>>>> given the outermost loop is the outer evolution.  If you sort the
>>>>> stride vecs from inner
>>>>> to outer you don't need prune_access_strides_not_in_loop.
>>>> Hmm, So stripping outer loops prefer inner to outer sort of strides, but cost computation
>>>> during interchange prefers outer to inner sort because loop_nest in tree-data-ref is sorted
>>>> in this way.  Seems a single prune_* function is better than fiddling with cost computation.
>>>
>>> Not sure how to interpret your answer...  I'll see to have a more
>>> detailed suggestion
>>> after playing with the code a bit.
>>>
>>>>>
>>>>> +/* Count and return the number of loops in LOOP_NEST.  */
>>>>> +
>>>>> +unsigned int
>>>>> +num_loops_in_loop_nest (struct loop *loop_nest)
>>>>> +{
>>>>> +  unsigned num_loops;
>>>>> +  for (num_loops = 0; loop_nest; num_loops++, loop_nest = loop_nest->inner)
>>>>> +    ;
>>>>> +  return num_loops;
>>>>>
>>>>> loop_depth (innermost) - loop_depth (nest)?
>>>> Done.
>>>>
>>>>>
>>>>> +static bool
>>>>> +should_interchange_loops (unsigned i_idx, unsigned o_idx,
>>>>> +                         vec<data_reference_p> datarefs,
>>>>> +                         bool innermost_loops_p, bool dump_info_p = true)
>>>>> +{
>>>>>
>>>>> isn't all we need associating the above CHREC to sort after the CHREC_RIGHTs
>>>>> and figure a permutation sequence to arrive there?  That is for the local
>>>>> decision you compute here it is CHREC_RIGHT [i_idx] > CHREC_RIGHT [o_idx]
>>>>> when we should interchange?
>>>>>
>>>>> That subloop_stride_p and tracking invariant DRs looks a bit odd.  For loops
>>>>> where a DR is invariant you simply do not have an evolution in that loop.
>>>>> You seem to simply add strides in the inner and outer loops for each DR,
>>>>> can you explain how that works?  Also I guess strides bigger than the
>>>>> various cache-line size parameters should be treated 'equal'?  That is,
>>>>> if we don't get any DR to a step that results in L1 cache hits because
>>>>> two DRs share a cache line the interchange is pointless?
>>>> So given below loop:
>>>>
>>>>   for (int i = 0; i < M; i++)
>>>>     for (int j = 0; j < M; j++)
>>>>       for (int k = 0; k < M; k++)
>>>>         a[k][0][i] = b[k][0][i]
>>>>
>>>> We check if memory reference is invariant wrto a loop only if it has zero strides within
>>>> current loop nest.  In this example, there is no invariant given address changes in the
>>>> innermost loop.
>>>
>>> But they simply wouldn't take part in the sorting?  That is, invariant
>>> refs in a loop
>>> shouldn't prevent it becoming more inner or more outer, no?
>>>
>>>> For strides bigger than cache-line size, it's also possible the interchange is wanted, as
>>>> in below example:
>>>>
>>>>   for (int i = 0; i < M; i++)          //loop 1
>>>>     for (int j = 0; j < M; j++)        //loop 2
>>>>       for (int k = 0; k < M; k++)    //loop 3
>>>>         a[j][i][k] = b[j][i][k]
>>>>
>>>> Strides for loop 1/2 are very like to be big, but after interchange, we will have stream
>>>> access of both arrays.
>>>>
>>>> More advanced heuristics may be possible, but so far the estimation is quite good by
>>>> checking all interchanges I looked into.
>>>>
>>>>>
>>>>> +/* Prune DATAREFS by removing any data reference not inside of LOOP.  */
>>>>> +
>>>>> +static inline void
>>>>> +prune_datarefs_not_in_loop (struct loop *loop, vec<data_reference_p> datarefs)
>>>>> +{
>>>>> +  struct data_reference *dr;
>>>>> +
>>>>> +  for (unsigned i = 0; datarefs.iterate (i, &dr);)
>>>>> +    if (flow_bb_inside_loop_p (loop, gimple_bb (DR_STMT (dr))))
>>>>> +      i++;
>>>>> +    else
>>>>> +      {
>>>>> +       datarefs.ordered_remove (i);
>>>>>
>>>>> that's expensive.  It's better to keep moving DRs we want to keep
>>>>> when walking the array.  That is, add a j you increment only when
>>>>> we keep a DR, moving *i to *j.
>>>> Done.
>>>>
>>>>>
>>>>> +       if (dr->aux)
>>>>> +         {
>>>>> +           DR_ACCESS_STRIDE (dr)->release ();
>>>>> +           free (dr->aux);
>>>>> +         }
>>>>> +       free_data_ref (dr);
>>>>> +      }
>>>>> +}
>>>>>
>>>>> +
>>>>> +  start_loop = prune_non_rectangle_loop_nest (innermost_loop, start_loop);
>>>>> +
>>>>>
>>>>> Hmm.  If you instantiate the SCEV for the niters for each loop in the nest
>>>>> wrt the nest you can figure if it has any evolution in sth else than the
>>>>> loop (evolution_function_is_univariate_p).   That is, this is not a problem
>>>>> until you arrive at analyzing DR strides, right?  At which point you
>>>>> can check for the appropriate form?
>>>> Hmm, not really.  The niter relation may not appear in SCEV of reference addr.
>>>> For example, below loop:
>>>>
>>>>   for (int i = 0; i < M; i++)          //loop 1
>>>>     for (int j = 0; j < M; j++)        //loop 2
>>>>       for (int k = 0; k < i; k++)    //loop 3
>>>>         a[k][0][i] = b[k][0][i]
>>>>
>>>> There is no information in data reference about i/j loops.
>>>> Anyway, I refactored the code and put this check in proper_loop_form_for_interchange.
>>>> Simpler I think.
>>>>
>>>>>
>>>>> +  if (find_data_references_in_loop (start_loop, datarefs) == chrec_dont_know
>>>>> +      /* Check if there is no data reference.  */
>>>>> +      || datarefs->length () == 0
>>>>> +      /* Check if there are too many of data references.  */
>>>>> +      || ((int) datarefs->length ()
>>>>> +         > PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS))
>>>>> +      /* Check if there is any data reference in loop latch.  We can't handle
>>>>> +        loops which loop header and data references have different execution
>>>>> +        times.  */
>>>>> +      || dataref_niters_diff_to_loop_header (*datarefs)
>>>>>
>>>>> this suggests to do your own find_data_references_in_loop so you can early
>>>>> out.
>>>> I refactored the code a bit.  Now this check is in proper_loop_form_for_interchange,
>>>> but I do customized my own data references finder.  It's needed to strip outer loops
>>>> once a difficult reference is found.
>>>>
>>>>>
>>>>> Overall the flow through the pass is a bit hard to follow given there are
>>>>> IMHO too many functions.
>>>> Yeah, I removed quite number of small functions and refactor the code a lot.  Hope this
>>>> version is more straightforward.
>>>>>
>>>>> +unsigned int
>>>>> +pass_linterchange::execute (function *fun)
>>>>> +{
>>>>> +  if (number_of_loops (fun) <= 2)
>>>>> +    return 0;
>>>>> +
>>>>> +  bool changed_p = false;;
>>>>> +  struct loop *loop;
>>>>> +  vec<loop_p> loop_nest;
>>>>> +  vec<data_reference_p> datarefs;
>>>>> +  vec<ddr_p> ddrs;
>>>>> +
>>>>> +  FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST)
>>>>> +    if (prepare_perfect_loop_nest (loop, &loop_nest, &datarefs, &ddrs))
>>>>> +      {
>>>>> +       tree_loop_interchange loop_interchange (loop_nest, datarefs, ddrs);
>>>>> +       changed_p |= loop_interchange.interchange ();
>>>>> +      }
>>>>>
>>>>> you leak datarefs/ddrs?
>>>> It was release in destructor, but I refactored it anyway.  I will push the code to branch
>>>> gcc.gnu.org/svn/gcc/branches/gimple-linterchange.
>>>>
>>>> Thanks again for the comment of you two.
>>>
>>> Digging into the code now...
>>>
>>> Richard.
>>>
>>>> Thanks,
>>>> bin
>>>> 2017-11-27  Bin Cheng  <bin.cheng@arm.com>
>>>>
>>>>         * Makefile.in (gimple-loop-interchange.o): New object file.
>>>>         * common.opt (floop-interchange): Reuse the option from graphite.
>>>>         * doc/invoke.texi (-floop-interchange): Ditto.  New document.
>>>>         * gimple-loop-interchange.cc: New file.
>>>>         * params.def (PARAM_LOOP_INTERCHANGE_MAX_NUM_STMTS): New parameter.
>>>>         (PARAM_LOOP_INTERCHANGE_STRIDE_RATIO): New parameter.
>>>>         * passes.def (pass_linterchange): New pass.
>>>>         * timevar.def (TV_LINTERCHANGE): New time var.
>>>>         * tree-pass.h (make_pass_linterchange): New declaration.
>>>>         * tree-ssa-loop-ivcanon.c (create_canonical_iv): Change to external
>>>>         interchange.  Record IV before/after increment in new parameters.
>>>>         * tree-ssa-loop-ivopts.h (create_canonical_iv): New declaration.
>>>>
>>>> gcc/testsuite
>>>> 2017-11-27  Bin Cheng  <bin.cheng@arm.com>
>>>>
>>>>         * gcc.dg/tree-ssa/loop-interchange-1.c: New test.
>>>>         * gcc.dg/tree-ssa/loop-interchange-2.c: New test.
>>>>         * gcc.dg/tree-ssa/loop-interchange-3.c: New test.
>>>>         * gcc.dg/tree-ssa/loop-interchange-4.c: New test.
>>>>         * gcc.dg/tree-ssa/loop-interchange-5.c: New test.
>>>>         * gcc.dg/tree-ssa/loop-interchange-6.c: New test.
>>>>         * gcc.dg/tree-ssa/loop-interchange-7.c: New test.
>>>>         * gcc.dg/tree-ssa/loop-interchange-8.c: New test.
>>>>         * gcc.dg/tree-ssa/loop-interchange-9.c: New test.
>>>>         * gcc.dg/tree-ssa/loop-interchange-10.c: New test.
>>>>         * gcc.dg/tree-ssa/loop-interchange-11.c: New test.

Attachment: interchange
Description: Binary data