Re: [PATCH GCC][4/5]Improve loop distribution to handle hmmer

["Bin.Cheng" <amker dot cheng at gmail dot com>]

On Thu, Jun 8, 2017 at 3:48 AM, kugan <kugan.vivekanandarajah@linaro.org> wrote:
> Hi Bin,
>
>> +
>> +/* In reduced dependence graph RDG for loop distribution, return true if
>> +   dependence between references DR1 and DR2 may create dependence cycle
>> +   and such dependence cycle can't be resolved by runtime alias check.
>> */
>> +
>> +static bool
>> +possible_data_dep_cycle_p (struct graph *rdg,
>> +                          hash_table<ddr_entry_hasher> *ddr_table,
>> +                          data_reference_p dr1, data_reference_p dr2)
>
>
> This name seems to be misleading a bit. It is basically dependence test ? Of
> course this can lead to a cycle but looks like possible_data_dep_p would be
> better.
This tests dependence between statements in one partition.  It
indicates a must dependence cycle if the function returns true,  I
suppose data_dep_in_cycle_p should be better.
>
>> +{
>> +  struct data_dependence_relation *ddr;
>> +
>> +  /* Re-shuffle data-refs to be in topological order.  */
>> +  if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1))
>> +      > rdg_vertex_for_stmt (rdg, DR_STMT (dr2)))
>> +    std::swap (dr1, dr2);
>> +
>> +  ddr = get_ddr (rdg, ddr_table, dr1, dr2);
>> +
>> +  /* In case something goes wrong in data dependence analysis.  */
>> +  if (ddr == NULL)
>> +    return true;
>> +  /* In case of no data dependence.  */
>> +  else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
>> +    return false;
>> +  /* Or the data dependence can be resolved by compilation time alias
>> +     check.  */
>> +  else if (!alias_sets_conflict_p (get_alias_set (DR_REF (dr1)),
>> +                                  get_alias_set (DR_REF (dr2))))
>> +    return false;
>> +  /* For unknown data dependence or known data dependence which can't be
>> +     expressed in classic distance vector, we check if it can be resolved
>> +     by runtime alias check.  If yes, we still consider data dependence
>> +     as won't introduce data dependence cycle.  */
>> +  else if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
>> +          || DDR_NUM_DIST_VECTS (ddr) == 0)
>
>
> You have already handled chrec_known above. Can you still have known data
> dependence which can't be expressed in classic distance vector ?
I don't know the very details in data dependence analyzer, only I tend
to believe it's possible by code.  Reading build_classic_dist_vector
gives:
  if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
    return false;

  //...

  dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
  if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
                    dist_v, &init_b, &index_carry))
    return false;

Looks like we can have DDR_ARE_DEPENDENT (ddr) == NULL_TREE without
classic distance vector.  Or the code could be simplified vice versa.
>
>> (dr1)
>> +               || !DR_BASE_ADDRESS (dr2) || !DR_OFFSET (dr2) || !DR_INIT
>> (dr2)
>> +               || !DR_STEP (dr1) || !tree_fits_uhwi_p (DR_STEP (dr1))
>> +               || !DR_STEP (dr2) || !tree_fits_uhwi_p (DR_STEP (dr2))
>> +               || res == 0)
>> +             this_dir = 2;
>> +           /* If it's possible to do runtime alias check, simply record
>> the
>> +              ddr.  */
>> +           else if (alias_ddrs != NULL)
>> +             alias_ddrs->safe_push (ddr);
>
>
> If alias_ddrs is not passed (i.e. NULL), shouldn't this_ddr = 2. May be add
> an assert for alias_ddrs ?
No, it's intended to ignore the dependence when alias_ddrs == NULL,  I
will add more comment for this.

>
>> +/* Build and return partition dependence graph for PARTITIONS.  RDG is
>> +   reduced dependence graph for the loop to be distributed.  DDR_TABLE
>> +   is hash table contains all data dependence relations.  ALIAS_DDRS is
>> +   a data dependence relations vector for temporary use.  If ALIAS_DDRS
>> +   is NULL, dependence which can be resolved by runtime alias check will
>> +   not be considered, vice versa.  */
>> +
>> +static struct graph *
>> +build_partition_graph (struct graph *rdg,
>> +                      hash_table<ddr_entry_hasher> *ddr_table,
>> +                      vec<struct partition *> *partitions,
>> +                      vec<ddr_p> *alias_ddrs)
>
>
> Why do you pass alias_ddrs to this. alias_ddrs does not pass any data or
> return any. It can be defined in the function and used there. If you are
> using this to indicate runtime alias check should be considered, you can
> define a different bool for that ?
I need to pass vector at two end of function calling stack, so I tried
to use vector pointer parameter for all related functions.  Apparently
this causes confusion for you, I will try the other way by using bool
parameter in next version patch.

>
>> +{
>> +
>> +static void
>> +break_alias_scc_partitions (struct graph *rdg,
>> +                           hash_table<ddr_entry_hasher> *ddr_table,
>> +                           vec<struct partition *> *partitions,
>> +                           vec<ddr_p> *alias_ddrs)
>
>
> I am not sure I understand this. When you are in pg_add_dependence_edges,
> when you record alias_ddrs for runtime checking you set this_dur io 1. That
> means you have broken the dpendency there itself. Were you planning to keep
No, it's not.  And thanks for catching this, it's in actuality a
mistake to set this_dir to 1 here.  I will explicitly set this_dir to
0 for alias case.  Setting it to 1 changes "alias" dependence into
"true" dependence, which could corrupt distribution opportunities.
> this_dir = 2 and break the dependency here ?
The dependence is to be broken in this function.
Thanks for reviewing, I am splitting patch into small ones and will
address above comments.

BTW, please remove long un-commented code piece when reviewing, I
scrolled a lot to find where the comment is.

Thanks,
bin