[3/3] Enhance dumps of IVOPTS

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?

>>
>> + 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.

> 
>>
>>  /* Stores EXPR in DATA->inv_expr_tab, and assigns it an inv_expr_id.  */
>>
>> -static int
>> +static iv_inv_expr_ent *
>>  get_expr_id (struct ivopts_data *data, tree expr)
> We are not returning id any more, maybe rename to record_inv_expr or else.

Done.

> 
>>  {
>>    struct iv_inv_expr_ent ent;
>> @@ -4806,13 +4809,13 @@ get_expr_id (struct ivopts_data *data, tree expr)
>>    ent.hash = iterative_hash_expr (expr, 0);
>>    slot = data->inv_expr_tab->find_slot (&ent, INSERT);
>>    if (*slot)
>> -    return (*slot)->id;
>> +    return *slot;
>>
>>    *slot = XNEW (struct iv_inv_expr_ent);
>>    (*slot)->expr = expr;
>>    (*slot)->hash = ent.hash;
>>    (*slot)->id = data->max_inv_expr_id++;
>> -  return (*slot)->id;
>> +  return *slot;
> This could be changed to
>   if (!*slot)
>     {
>       //new and insert
>     }
>   return *slot;

Also done.

>>  }
>>
>>  /* Returns the pseudo expr id if expression UBASE - RATIO * CBASE
>> @@ -4820,10 +4823,10 @@ get_expr_id (struct ivopts_data *data, tree expr)
>>     ADDRESS_P is a flag indicating if the expression is for address
>>     computation.  */
>>
>> -static int
>> +static iv_inv_expr_ent *
>>  get_loop_invariant_expr_id (struct ivopts_data *data, tree ubase,
>> -                            tree cbase, HOST_WIDE_INT ratio,
>> -                            bool address_p)
>> +                tree cbase, HOST_WIDE_INT ratio,
>> +                bool address_p)
> Rename function name here too.
>>  {
> 

Likewise.

>> @@ -5988,9 +5992,9 @@ determine_group_iv_costs (struct ivopts_data *data)
>>            if (group->cost_map[j].depends_on)
>>          bitmap_print (dump_file,
>>                    group->cost_map[j].depends_on, "","");
>> -          if (group->cost_map[j].inv_expr_id != -1)
>> +        if (group->cost_map[j].inv_expr != NULL)
>>          fprintf (dump_file, " inv_expr:%d",
>> -             group->cost_map[j].inv_expr_id);
>> +             group->cost_map[j].inv_expr->id);
> Dump inv_expr in another column thus it won't appear under depends_on
> in dump.  Also make it preceding depends_on which is a bitmap.

Sure, now the output looks:

<Group-candidate Costs>:
Group 0:
  cand	cost	compl.	inv.ex.	depends on
  0	9	0	0	2
  1	32	0		2
  2	42	0		2
  3	9	1	1	2
  4	42	0		2
  5	9	1	2	2
  6	9	0	0	2
  7	9	1	2	2
  8	9	1	3	2
  9	0	0		2

> 
> While we are on this one before the other two, could you please make
> this independent so it can be committed after rework?

That would be better to start with that. I'm going to trigger regression tests and we
can install the patch.

Martin

> 
> Thanks,
> bin
> 
>>
>> Martin

[3/3] Enhance dumps of IVOPTS

Commit Message

Comments

Patch