On Fri, May 13, 2016 at 2:43 PM, Kyrill Tkachov
<kyrylo.tkac...@foss.arm.com> wrote:
> Hi Martin,
>
>
> On 13/05/16 13:39, Martin Liška wrote:
>>
>> On 05/13/2016 02:11 PM, H.J. Lu wrote:
>>>
>>> On Fri, May 13, 2016 at 3:44 AM, Martin Liška <mli...@suse.cz> wrote:
>>>>
>>>> On 05/13/2016 11:43 AM, Bin.Cheng wrote:
>>>>>
>>>>> On Thu, May 12, 2016 at 5:41 PM, Martin Liška <mli...@suse.cz> wrote:
>>>>>>
>>>>>> On 05/12/2016 03:51 PM, Bin.Cheng wrote:
>>>>>>>
>>>>>>> On Thu, May 12, 2016 at 1:13 PM, Martin Liška <mli...@suse.cz> wrote:
>>>>>>>>
>>>>>>>> On 05/10/2016 03:16 PM, Bin.Cheng wrote:
>>>>>>>>>
>>>>>>>>> Another way is to remove the use of id for struct iv_inv_expr_ent
>>>>>>>>> once
>>>>>>>>> for all. We can change iv_ca.used_inv_expr and
>>>>>>>>> cost_pair.inv_expr_id
>>>>>>>>> to pointers, and rename iv_inv_expr_ent.id to count and use this to
>>>>>>>>> record reference number in iv_ca. This if-statement on dump_file
>>>>>>>>> can
>>>>>>>>> be saved. Also I think it simplifies current code a bit. For now,
>>>>>>>>> there are id <-> struct maps for different structures in IVOPT
>>>>>>>>> which
>>>>>>>>> make it not straightforward.
>>>>>>>>
>>>>>>>> Hi.
>>>>>>>>
>>>>>>>> I'm sending second version of the patch. I tried to follow your
>>>>>>>> advices, but
>>>>>>>> because of a iv_inv_expr_ent can simultaneously belong to multiply
>>>>>>>> iv_cas,
>>>>>>>> putting counter to iv_inv_expr_ent does not works. Instead of that,
>>>>>>>> I've
>>>>>>>> decided to replace used_inv_expr with a hash_map that contains used
>>>>>>>> inv_exps
>>>>>>>> and where value of the map is # of usages.
>>>>>>>>
>>>>>>>> Further questions:
>>>>>>>> + iv_inv_expr_ent::id can be now removed as it's used just for
>>>>>>>> purpose of dumps
>>>>>>>> Group 0:
>>>>>>>> cand cost scaled freq compl. depends on
>>>>>>>> 5 2 2.00 1.000
>>>>>>>> 6 4 4.00 1.001 inv_expr:0
>>>>>>>> 7 4 4.00 1.001 inv_expr:1
>>>>>>>> 8 4 4.00 1.001 inv_expr:2
>>>>>>>>
>>>>>>>> That can be replaced with print_generic_expr, but I think using ids
>>>>>>>> makes the dump
>>>>>>>> output more clear.
>>>>>>>
>>>>>>> I am okay with keeping id. Could you please dump all inv_exprs in a
>>>>>>> single section like
>>>>>>> <Invariant Exprs>:
>>>>>>> inv_expr 0: print_generic_expr
>>>>>>> inv_expr 1: ...
>>>>>>>
>>>>>>> Then only dump the id afterwards?
>>>>>>>
>>>>>> Sure, it would be definitely better:
>>>>>>
>>>>>> The new dump format looks:
>>>>>>
>>>>>> <Invariant Expressions>:
>>>>>> inv_expr 0: sudoku_351(D) + (sizetype) S.833_774 * 4
>>>>>> inv_expr 1: sudoku_351(D) + ((sizetype) S.833_774 * 4 +
>>>>>> 18446744073709551580)
>>>>>> inv_expr 2: sudoku_351(D) + ((sizetype) S.833_774 + 72) * 4
>>>>>> inv_expr 3: sudoku_351(D) + ((sizetype) S.833_774 + 81) * 4
>>>>>> inv_expr 4: &A.832 + (sizetype) _377 * 4
>>>>>> inv_expr 5: &A.832 + ((sizetype) _377 * 4 + 18446744073709551612)
>>>>>> inv_expr 6: &A.832 + ((sizetype) _377 + 8) * 4
>>>>>> inv_expr 7: &A.832 + ((sizetype) _377 + 9) * 4
>>>>>>
>>>>>> <Group-candidate Costs>:
>>>>>> Group 0:
>>>>>> cand cost scaled freq compl. depends on
>>>>>>
>>>>>> ...
>>>>>>
>>>>>> Improved to:
>>>>>> cost: 27 (complexity 2)
>>>>>> cand_cost: 11
>>>>>> cand_group_cost: 10 (complexity 2)
>>>>>> candidates: 3, 5
>>>>>> group:0 --> iv_cand:5, cost=(2,0)
>>>>>> group:1 --> iv_cand:5, cost=(4,1)
>>>>>> group:2 --> iv_cand:5, cost=(4,1)
>>>>>> group:3 --> iv_cand:3, cost=(0,0)
>>>>>> group:4 --> iv_cand:3, cost=(0,0)
>>>>>> invariants 1, 6
>>>>>> invariant expressions 6, 3
>>>>>>
>>>>>> The only question here is that as used_inv_exprs are stored in a
>>>>>> hash_map,
>>>>>> order of dumped invariants would not be stable. Is it problem?
>>>>>
>>>>> It is okay.
>>>>>
>>>>> Only nitpicking on this version.
>>>>>
>>>>>>>> + As check_GNU_style.sh reported multiple 8 spaces issues in hunks
>>>>>>>> I've touched, I decided
>>>>>>>> to fix all 8 spaces issues. Hope it's fine.
>>>>>>>>
>>>>>>>> I'm going to test the patch.
>>>>>>>> Thoughts?
>>>>>>>
>>>>>>> Some comments on the patch embedded.
>>>>>>>
>>>>>>>> +/* Forward declaration. */
>>>>>>>
>>>>>>> Not necessary.
>>>>>>>>
>>>>>>>> +struct iv_inv_expr_ent;
>>>>>>>> +
>>>>>>
>>>>>> I think it's needed because struct cost_pair uses a pointer to
>>>>>> iv_inv_expr_ent.
>>>>>
>>>>> I mean the comment, clearly the declaration is self-documented.
>>>>
>>>> Hi.
>>>>
>>>> Yeah, removed.
>>>>
>>>>>> @@ -6000,11 +6045,12 @@ iv_ca_set_no_cp (struct ivopts_data *data,
>>>>>> struct iv_ca *ivs,
>>>>>>
>>>>>> iv_ca_set_remove_invariants (ivs, cp->depends_on);
>>>>>>
>>>>>> - if (cp->inv_expr_id != -1)
>>>>>> + if (cp->inv_expr != NULL)
>>>>>> {
>>>>>> - ivs->used_inv_expr[cp->inv_expr_id]--;
>>>>>> - if (ivs->used_inv_expr[cp->inv_expr_id] == 0)
>>>>>> - ivs->num_used_inv_expr--;
>>>>>> + unsigned *slot = ivs->used_inv_exprs->get (cp->inv_expr);
>>>>>> + --(*slot);
>>>>>> + if (*slot == 0)
>>>>>> + ivs->used_inv_exprs->remove (cp->inv_expr);
>>>>>
>>>>> I suppose insertion/removal of hash_map are not expensive? Because
>>>>> the algorithm causes a lot of these operations.
>>>>
>>>> I think it should be ~ a constant operation.
>>>>
>>>>>> @@ -6324,12 +6368,26 @@ iv_ca_dump (struct ivopts_data *data, FILE
>>>>>> *file, struct iv_ca *ivs)
>>>>>> fprintf (file, " group:%d --> ??\n", group->id);
>>>>>> }
>>>>>>
>>>>>> + bool any_invariant = false;
>>>>>> for (i = 1; i <= data->max_inv_id; i++)
>>>>>> if (ivs->n_invariant_uses[i])
>>>>>> {
>>>>>> + const char *pref = any_invariant ? ", " : " invariants ";
>>>>>> + any_invariant = true;
>>>>>> fprintf (file, "%s%d", pref, i);
>>>>>> - pref = ", ";
>>>>>> }
>>>>>> +
>>>>>> + if (any_invariant)
>>>>>> + fprintf (file, "\n");
>>>>>> +
>>>>>
>>>>> To make dump easier to read, we can simply dump invariant
>>>>> variables/expressions unconditionally. Also keep invariant variables
>>>>> and expressions in the same form.
>>>>
>>>> Sure, that's a good idea!
>>>>
>>>> Sample output:
>>>>
>>>>
>>>> Initial set of candidates:
>>>> cost: 17 (complexity 0)
>>>> cand_cost: 11
>>>> cand_group_cost: 2 (complexity 0)
>>>> candidates: 1, 5
>>>> group:0 --> iv_cand:5, cost=(2,0)
>>>> group:1 --> iv_cand:1, cost=(0,0)
>>>> invariant variables: 1, 4
>>>> invariant expressions:
>>>>
>>>> Initial set of candidates:
>>>> cost: 42 (complexity 2)
>>>> cand_cost: 15
>>>> cand_group_cost: 12 (complexity 2)
>>>> candidates: 4, 15, 16
>>>> group:0 --> iv_cand:16, cost=(0,0)
>>>> group:1 --> iv_cand:15, cost=(-1,0)
>>>> group:2 --> iv_cand:4, cost=(0,0)
>>>> group:3 --> iv_cand:15, cost=(9,1)
>>>> group:4 --> iv_cand:15, cost=(4,1)
>>>> invariant variables:
>>>> invariant expressions:
>>>>
>>>>> const char *pref = "";
>>>>> //...
>>>>> fprintf (file, " invariant variables: "
>>>>> for (i = 1; i <= data->max_inv_id; i++)
>>>>> if (ivs->n_invariant_uses[i])
>>>>> {
>>>>> fprintf (file, "%s%d", pref, i);
>>>>> pref = ", ";
>>>>> }
>>>>> fprintf (file, "\n");
>>>>>
>>>>>> + const char *pref = " invariant expressions ";
>>>>>> + for (hash_map<iv_inv_expr_ent *, unsigned>::iterator it
>>>>>> + = ivs->used_inv_exprs->begin (); it !=
>>>>>> ivs->used_inv_exprs->end (); ++it)
>>>>>> + {
>>>>>> + fprintf (file, "%s%d", pref, (*it).first->id);
>>>>>> + pref = ", ";
>>>>>> + }
>>>>>> +
>>>>>> fprintf (file, "\n\n");
>>>>>> }
>>>>>>
>>>>> Okay with the dump change, you may need to update Changelog entry too.
>>>>
>>>> There's no fundamental change, thus not changing the ChangeLog entry.
>>>>
>>>> Thanks for the review, installed as r236200.
>>>>
>>> It failed to build on 32-bit hosts:
>>>
>>> ../../src-trunk/gcc/tree-ssa-loop-ivopts.c: In function \u2018void
>>> create_new_ivs(ivopts_data*, iv_ca*)\u2019:
>>> ../../src-trunk/gcc/tree-ssa-loop-ivopts.c:7050:44: error: format
>>> \u2018%lu\u2019 expects argument of type \u2018long unsigned
>>> int\u2019, but argument 3 has type \u2018long long int\u2019
>>> [-Werror=format=]
>>> avg_loop_niter (data->current_loop));
>>> ^
>>> ../../src-trunk/gcc/tree-ssa-loop-ivopts.c:7052:41: error: format
>>> \u2018%lu\u2019 expects argument of type \u2018long unsigned
>>> int\u2019, but argument 3 has type \u2018size_t {aka unsigned
>>> int}\u2019 [-Werror=format=]
>>> set->used_inv_exprs->elements ());
>>> ^
>>>
>>>
>>>
>> Hi.
>> Thanks for heads up, can you please test the following patch?
>>
>> Thanks,
>> Martin
>
>
> diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
> index 62b8835..abfe73d 100644
> --- a/gcc/tree-ssa-loop-ivopts.c
> +++ b/gcc/tree-ssa-loop-ivopts.c
> @@ -7046,9 +7046,9 @@ create_new_ivs (struct ivopts_data *data, struct iv_ca
> *set)
> if (data->loop_loc != UNKNOWN_LOCATION)
> fprintf (dump_file, " at %s:%d", LOCATION_FILE (data->loop_loc),
> LOCATION_LINE (data->loop_loc));
> - fprintf (dump_file, ", %lu avg niters",
> + fprintf (dump_file, ", %" PRId64 " avg niters",
> avg_loop_niter (data->current_loop));
> - fprintf (dump_file, ", %lu expressions",
> + fprintf (dump_file, ", %" PRIu64 " expressions",
>
>
> I believe hwint.h defines HOST_WIDE_INT_PRINT_DEC and
> HOST_WIDE_INT_PRINT_UNSIGNED
> for the HOST_WIDE_INT print formats, though I don't know how strictly their
> use
> is enforced in the codebase.
Use them for HOST_WIDE_INT printing, for [u]int64_t use the PRI stuff.
Richard.
> Kyrill
