Re: [PATCH 3/3] Enhance dumps of IVOPTS

[Richard Biener <richard.guenther@gmail.com>]

On Fri, May 13, 2016 at 2:43 PM, Kyrill Tkachov
<kyrylo.tkachov@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 <mliska@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 <mliska@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 <mliska@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