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
prev parent 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).