On Thu, Jun 8, 2017 at 3:48 AM, kugan <kugan.vivekanandara...@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
