public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
From: "Bin.Cheng" <amker.cheng@gmail.com>
To: kugan <kugan.vivekanandarajah@linaro.org>
Cc: "gcc-patches@gcc.gnu.org" <gcc-patches@gcc.gnu.org>
Subject: Re: [PATCH GCC][4/5]Improve loop distribution to handle hmmer
Date: Thu, 08 Jun 2017 17:35:00 -0000	[thread overview]
Message-ID: <CAHFci2_nptZAqXJ3Fv6=oc1bR8emw1EDkOpZuG2Nfa9Es2NO=Q@mail.gmail.com> (raw)
In-Reply-To: <2df529ae-803d-f955-cc6e-494a13ab7d6a@linaro.org>

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

      reply	other threads:[~2017-06-08 17:35 UTC|newest]

Thread overview: 7+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-06-02 11:51 Bin Cheng
2017-06-05  4:21 ` Kugan Vivekanandarajah
2017-06-05  9:01   ` Bin.Cheng
2017-06-07 10:03 ` Richard Biener
2017-06-07 10:19   ` Bin.Cheng
2017-06-08  2:48 ` kugan
2017-06-08 17:35   ` Bin.Cheng [this message]

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CAHFci2_nptZAqXJ3Fv6=oc1bR8emw1EDkOpZuG2Nfa9Es2NO=Q@mail.gmail.com' \
    --to=amker.cheng@gmail.com \
    --cc=gcc-patches@gcc.gnu.org \
    --cc=kugan.vivekanandarajah@linaro.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).