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.