[PATCH] Distribute inliner's size_time data across entries with similar predicates

[PATCH] Distribute inliner's size_time data across entries with similar predicates

[Maxim Kuvyrkov]

[-- Attachment #1: Type: text/plain, Size: 1082 bytes --]

Jan,

The following patch started as a one-liner for ipa-inline-analysis.c: account_size_time() to merge predicates when we are adding data to entry[0] (i.e., when space for 32 size_time entries is exhausted):

@@ -537,6 +592,9 @@ account_size_time (struct inline_summary
     }
   else
     {
+      e->predicate = or_predicates (summary->conds, &e->predicate, pred);
       e->size += size;
       e->time += time;
       if (e->time > MAX_TIME * INLINE_TIME_SCALE)

The rationale was that since we are accounting size and time under the entry we also need to make entry's predicate a superset of the predicate we want to account the data under.

Then I thought that mushing all predicates into the single predicate of entry[0] will cause it to become true_predicate() very quickly, so I added logic to distribute incoming size_time information across all 32 entries by searching for entries with similar predicates.

OK for trunk assuming testing on x86_64-linux-gnu shows no regressions?

Thank you,

--
Maxim Kuvyrkov
CodeSourcery / Mentor Graphics



[-- Attachment #2: 0001-Improve-ipa-inline-analysis.c-account_size_time-to-d.patch --]
[-- Type: application/octet-stream, Size: 4460 bytes --]

From d9e253e0cea39634ccb196680ad95e855cba41f0 Mon Sep 17 00:00:00 2001
From: Maxim Kuvyrkov <maxim@codesourcery.com>
Date: Mon, 19 Sep 2011 12:33:33 -0700
Subject: [PATCH] Improve ipa-inline-analysis.c:account_size_time() to distribute data
 	across entries with similar predicates.

	* ipa-inline-analysis.c (predicate_distance,):
	(find_size_time_entry_with_closest_predicate): New functions.
	(account_size_time): Use them instead of mushing data into entry[0].
---
 gcc/ipa-inline-analysis.c |   92 ++++++++++++++++++++++++++++++++++++--------
 1 files changed, 75 insertions(+), 17 deletions(-)

diff --git a/gcc/ipa-inline-analysis.c b/gcc/ipa-inline-analysis.c
index 6bc96c7..b53962d 100644
--- a/gcc/ipa-inline-analysis.c
+++ b/gcc/ipa-inline-analysis.c
@@ -485,14 +485,80 @@ dump_predicate (FILE *f, conditions conds, struct predicate *pred)
 }
 
 
+/* Return number of different clauses between predicates P and P2.  */
+
+static int
+predicate_distance (struct predicate *p, struct predicate *p2)
+{
+  int i;
+  int distance = 0;
+
+  for (i = 0; p->clause[i]; i++)
+    if (p->clause[i] != p2->clause[i])
+      ++distance;
+
+  /* Increase distance by the number of extra clauses in P2.  */
+  for (; p2->clause[i]; i++)
+    ++distance;
+
+  return distance;
+}
+
+
+/* Find size_time_entry in SUMMARY with the closest predicate to PRED.
+   Return the entry and set *EXACT to true if we found an exact match.
+   Return NULL if there is space for a new entry.  */
+
+static size_time_entry *
+find_size_time_entry_with_closest_predicate (struct inline_summary *summary,
+					     struct predicate *pred,
+					     bool *exact)
+{
+  size_time_entry *e;
+  int i;
+
+  /* Try to find the exact match.  */
+  *exact = true;
+  for (i = 0; VEC_iterate (size_time_entry, summary->entry, i, e); i++)
+    if (predicates_equal_p (&e->predicate, pred))
+      return e;
+
+  /* Return NULL to indicate that we still have room for a new new entry.  */
+  if (i < 32)
+    return NULL;
+
+  /* No exact match and don't want to create new entries.
+     Find entry with the closest predicate.  */
+  *exact = false;
+  {
+    int min_distance = MAX_CLAUSES + 1;
+    size_time_entry *best_entry = NULL;
+
+    for (i = 0; VEC_iterate (size_time_entry, summary->entry, i, e); i++)
+      {
+	int distance = predicate_distance (&e->predicate, pred);
+
+	if (distance < min_distance)
+	  {
+	    min_distance = distance;
+	    best_entry = e;
+	  }
+      }
+
+    gcc_assert (0 <= min_distance && min_distance <= MAX_CLAUSES);
+    gcc_assert (best_entry != NULL);
+    return best_entry;
+  }
+}
+
+
 /* Record SIZE and TIME under condition PRED into the inline summary.  */
 
 static void
 account_size_time (struct inline_summary *summary, int size, int time, struct predicate *pred)
 {
   size_time_entry *e;
-  bool found = false;
-  int i;
+  bool exact;
 
   if (false_predicate_p (pred))
     return;
@@ -507,27 +573,16 @@ account_size_time (struct inline_summary *summary, int size, int time, struct pr
     time = MAX_TIME * INLINE_TIME_SCALE;
   gcc_assert (time >= 0);
 
-  for (i = 0; VEC_iterate (size_time_entry, summary->entry, i, e); i++)
-    if (predicates_equal_p (&e->predicate, pred))
-      {
-	found = true;
-        break;
-      }
-  if (i == 32)
-    {
-      i = 0;
-      found = true;
-      e = VEC_index (size_time_entry, summary->entry, 0);
-      gcc_assert (!e->predicate.clause[0]);
-    }
+  e = find_size_time_entry_with_closest_predicate (summary, pred, &exact);
+
   if (dump_file && (dump_flags & TDF_DETAILS) && (time || size))
     {
       fprintf (dump_file, "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
 	       ((double)size) / INLINE_SIZE_SCALE, ((double)time) / INLINE_TIME_SCALE,
-	       found ? "" : "new ");
+	       e != NULL ? "" : "new ");
       dump_predicate (dump_file, summary->conds, pred);
     }
-  if (!found)
+  if (e == NULL)
     {
       struct size_time_entry new_entry;
       new_entry.size = size;
@@ -537,6 +592,9 @@ account_size_time (struct inline_summary *summary, int size, int time, struct pr
     }
   else
     {
+      if (!exact)
+	e->predicate = or_predicates (summary->conds, &e->predicate, pred);
+
       e->size += size;
       e->time += time;
       if (e->time > MAX_TIME * INLINE_TIME_SCALE)
-- 
1.7.4.1

Re: [PATCH] Distribute inliner's size_time data across entries with similar predicates

[Richard Guenther]

On Mon, Sep 19, 2011 at 10:16 PM, Maxim Kuvyrkov <maxim@codesourcery.com> wrote:
> Jan,
>
> The following patch started as a one-liner for ipa-inline-analysis.c: account_size_time() to merge predicates when we are adding data to entry[0] (i.e., when space for 32 size_time entries is exhausted):
>
> @@ -537,6 +592,9 @@ account_size_time (struct inline_summary
>     }
>   else
>     {
> +      e->predicate = or_predicates (summary->conds, &e->predicate, pred);
>       e->size += size;
>       e->time += time;

Shouldn't this be either and_predicates or not accumulating but taking
the minimum (or maximum?)
of the size/time values if using or_predicates?

I wonder why we bother to record so many predicates though.

>       if (e->time > MAX_TIME * INLINE_TIME_SCALE)
>
> The rationale was that since we are accounting size and time under the entry we also need to make entry's predicate a superset of the predicate we want to account the data under.
>
> Then I thought that mushing all predicates into the single predicate of entry[0] will cause it to become true_predicate() very quickly, so I added logic to distribute incoming size_time information across all 32 entries by searching for entries with similar predicates.

That sounds expensive (without looking at the patch).  Shouldn't we
instead look for similar size/time values (maybe sorting the
predicates)?
Thus, when size and time are equal we can simply or the predicates.

Richard.

> OK for trunk assuming testing on x86_64-linux-gnu shows no regressions?
>
> Thank you,
>
> --
> Maxim Kuvyrkov
> CodeSourcery / Mentor Graphics
>
>
>

Re: [PATCH] Distribute inliner's size_time data across entries with similar predicates

[Jan Hubicka]

> 
> Shouldn't this be either and_predicates or not accumulating but taking
> the minimum (or maximum?)

The predicates are always assumed to be conservative estimate (i.e. when they
are false, the code is known to be unreachable. When they are true they may or
may not be.  This is used when detecting optimized out callgraph edges).

> of the size/time values if using or_predicates?

Maximum should work if the predicates are known to be disjoint. Otherwise I guess
sum is the only conservative way.
> 
> I wonder why we bother to record so many predicates though.

Yep, I wonder if it comes from some real testcase?  I didn't see functions that
reach the limit and still be inlinable very often in practice.
> 
> >       if (e->time > MAX_TIME * INLINE_TIME_SCALE)
> >
> > The rationale was that since we are accounting size and time under the entry we also need to make entry's predicate a superset of the predicate we want to account the data under.
> >
> > Then I thought that mushing all predicates into the single predicate of entry[0] will cause it to become true_predicate() very quickly, so I added logic to distribute incoming size_time information across all 32 entries by searching for entries with similar predicates.

Entry[0] is always true predicate BTW.  This is why you don't need or predicate there.
This is arranged in:

  /* When we run into maximal number of entries, we assign everything to the
     constant truth case.  Be sure to have it in list. */
  bb_predicate = true_predicate ();
  account_size_time (info, 0, 0, &bb_predicate);

It is there precisely to make the predicates overflow to work.  It is quite
stupid way to handle too many predicates, but I tought I don't need to worry at
least in the initial implementation.

I will take at the patch later today.
> 
> That sounds expensive (without looking at the patch).  Shouldn't we
> instead look for similar size/time values (maybe sorting the
> predicates)?
> Thus, when size and time are equal we can simply or the predicates.

Again the predicates must be mutually disjoint for that.  I.e. when we have

if (op0 > 10)
  some code
if (op1 > 10)
  the same code

You will account same size and time at predicate (op0 > 10) and (op1 > 10) and they
are additive when values of op0 and op1 are not disjoint.

Honza
> 
> Richard.
> 
> > OK for trunk assuming testing on x86_64-linux-gnu shows no regressions?
> >
> > Thank you,
> >
> > --
> > Maxim Kuvyrkov
> > CodeSourcery / Mentor Graphics
> >
> >
> >

Re: [PATCH] Distribute inliner's size_time data across entries with similar predicates

[Richard Guenther]

2011/9/25 Jan Hubicka <hubicka@ucw.cz>:
>>
>> Shouldn't this be either and_predicates or not accumulating but taking
>> the minimum (or maximum?)
>
> The predicates are always assumed to be conservative estimate (i.e. when they
> are false, the code is known to be unreachable. When they are true they may or
> may not be.  This is used when detecting optimized out callgraph edges).
>
>> of the size/time values if using or_predicates?
>
> Maximum should work if the predicates are known to be disjoint. Otherwise I guess
> sum is the only conservative way.
>>
>> I wonder why we bother to record so many predicates though.
>
> Yep, I wonder if it comes from some real testcase?  I didn't see functions that
> reach the limit and still be inlinable very often in practice.
>>
>> >       if (e->time > MAX_TIME * INLINE_TIME_SCALE)
>> >
>> > The rationale was that since we are accounting size and time under the entry we also need to make entry's predicate a superset of the predicate we want to account the data under.
>> >
>> > Then I thought that mushing all predicates into the single predicate of entry[0] will cause it to become true_predicate() very quickly, so I added logic to distribute incoming size_time information across all 32 entries by searching for entries with similar predicates.
>
> Entry[0] is always true predicate BTW.  This is why you don't need or predicate there.
> This is arranged in:
>
>  /* When we run into maximal number of entries, we assign everything to the
>     constant truth case.  Be sure to have it in list. */
>  bb_predicate = true_predicate ();
>  account_size_time (info, 0, 0, &bb_predicate);
>
> It is there precisely to make the predicates overflow to work.  It is quite
> stupid way to handle too many predicates, but I tought I don't need to worry at
> least in the initial implementation.
>
> I will take at the patch later today.
>>
>> That sounds expensive (without looking at the patch).  Shouldn't we
>> instead look for similar size/time values (maybe sorting the
>> predicates)?
>> Thus, when size and time are equal we can simply or the predicates.
>
> Again the predicates must be mutually disjoint for that.  I.e. when we have
>
> if (op0 > 10)
>  some code
> if (op1 > 10)
>  the same code
>
> You will account same size and time at predicate (op0 > 10) and (op1 > 10) and they
> are additive when values of op0 and op1 are not disjoint.

Hm, what do we do for

 if (op0 > 10)
   if (op1 > 10)
     some code

?  Do we make sure to only register one predicate with op0 > 10 && op1 > 10?

> Honza
>>
>> Richard.
>>
>> > OK for trunk assuming testing on x86_64-linux-gnu shows no regressions?
>> >
>> > Thank you,
>> >
>> > --
>> > Maxim Kuvyrkov
>> > CodeSourcery / Mentor Graphics
>> >
>> >
>> >
>

Re: [PATCH] Distribute inliner's size_time data across entries with similar predicates

[Jan Hubicka]

> 
> Hm, what do we do for
> 
>  if (op0 > 10)
>    if (op1 > 10)
>      some code
> 
> ?  Do we make sure to only register one predicate with op0 > 10 && op1 > 10?

Yes, we end up with predicate (op0 > 10) && (op1 > 10). That is until we hit of
maximum limit of clauses in a single predicate. Then we just give up and start
dropping more of && clauses.

Honza

Re: [PATCH] Distribute inliner's size_time data across entries with similar predicates

[Maxim Kuvyrkov]

On 25/09/2011, at 11:21 PM, Jan Hubicka wrote:

>> 
>> I wonder why we bother to record so many predicates though.
> 
> Yep, I wonder if it comes from some real testcase?  I didn't see functions that
> reach the limit and still be inlinable very often in practice.

This patch wasn't inspired by a real testcase.  I was studying your new context-sensitive inliner analysis and thought that we can deal with predicate overflow a bit better.

>> 
>>>       if (e->time > MAX_TIME * INLINE_TIME_SCALE)
>>> 
>>> The rationale was that since we are accounting size and time under the entry we also need to make entry's predicate a superset of the predicate we want to account the data under.
>>> 
>>> Then I thought that mushing all predicates into the single predicate of entry[0] will cause it to become true_predicate() very quickly, so I added logic to distribute incoming size_time information across all 32 entries by searching for entries with similar predicates.
> 
> Entry[0] is always true predicate BTW.  This is why you don't need or predicate there.

Yeap, I learned this several hours after I posted the patch.

> 
> I will take at the patch later today.

Thanks,

--
Maxim Kuvyrkov
CodeSourcery / Mentor Graphics

Re: [PATCH] Distribute inliner's size_time data across entries with similar predicates

[Jan Hubicka]

Hi,
> Jan,
> 
> The following patch started as a one-liner for ipa-inline-analysis.c: account_size_time() to merge predicates when we are adding data to entry[0] (i.e., when space for 32 size_time entries is exhausted):
> 
> @@ -537,6 +592,9 @@ account_size_time (struct inline_summary
>      }
>    else
>      {
> +      e->predicate = or_predicates (summary->conds, &e->predicate, pred);
>        e->size += size;
>        e->time += time;
>        if (e->time > MAX_TIME * INLINE_TIME_SCALE)

As we discussed, this is not needed in current form because we arrange first predicate to be always
true and thus we could always place there all the costs that did not fit elwhere.

The patch has a problem with fact that the predicates must be always conservative i.e. when
they are proved to be false the code must be unreachable after inlining.

We could either go with your patch with the distance fuction modified to accept
only predicates such that the new predicate is implied by them.  If you are
willing to play with this, I have no problem with going for this.

The accounting is run just at most N statements of time, so the overall time should not be too bad.

We could also stay with current logic until we hit real world testcases that demonstrate need
for something like this and drop comment in the code above explaning why or is not needed
to avoid confussion.

Honza

Re: [PATCH] Distribute inliner's size_time data across entries with similar predicates

[Maxim Kuvyrkov]

On 20/10/2011, at 10:32 PM, Jan Hubicka wrote:

> Hi,
>> Jan,
>> 
>> The following patch started as a one-liner for ipa-inline-analysis.c: account_size_time() to merge predicates when we are adding data to entry[0] (i.e., when space for 32 size_time entries is exhausted):
>> 
>> @@ -537,6 +592,9 @@ account_size_time (struct inline_summary
>>     }
>>   else
>>     {
>> +      e->predicate = or_predicates (summary->conds, &e->predicate, pred);
>>       e->size += size;
>>       e->time += time;
>>       if (e->time > MAX_TIME * INLINE_TIME_SCALE)
> 
> As we discussed, this is not needed in current form because we arrange first predicate to be always
> true and thus we could always place there all the costs that did not fit elwhere.
> 
> The patch has a problem with fact that the predicates must be always conservative i.e. when
> they are proved to be false the code must be unreachable after inlining.

I don't understand your point.  The OR-ing of the predicates allows us to merge size_time_entries and keep the total number of them under a desired limit.  Currently all merging goes into entry[0], and the patch makes the extra information to get distributed across more entries.  Because we OR the predicates, we keep the information conservative; now in order to say that certain code will be unreachable the inliner has to prove to be false the OR-ed predicate.

Now, one can argue whether it is actually a benefit to distribute the information more evenly and, consequently, making more predicates harder to disprove.  In current scheme we have the surplus of size_time information under one impossible-to-disprove predicate and many entries with easier-to-disprove-predicates.  My patch changes the situation to having most of the size_time information in entries with harder-but-possible-to-disprove predicates.

Am I missing something?

> 
> We could either go with your patch with the distance fuction modified to accept
> only predicates such that the new predicate is implied by them.  If you are
> willing to play with this, I have no problem with going for this.

Yes, favoring predicates that already imply the new one is a good suggestion.


Thank you,

--
Maxim Kuvyrkov
CodeSourcery / Mentor Graphics

Re: [PATCH] Distribute inliner's size_time data across entries with similar predicates

[Maxim Kuvyrkov]

On 28/10/2011, at 7:24 PM, Maxim Kuvyrkov wrote:

> On 20/10/2011, at 10:32 PM, Jan Hubicka wrote:
> 
>> Hi,
>>> Jan,
>>> 
>>> The following patch started as a one-liner for ipa-inline-analysis.c: account_size_time() to merge predicates when we are adding data to entry[0] (i.e., when space for 32 size_time entries is exhausted):
>>> 
>>> @@ -537,6 +592,9 @@ account_size_time (struct inline_summary
>>>    }
>>>  else
>>>    {
>>> +      e->predicate = or_predicates (summary->conds, &e->predicate, pred);
>>>      e->size += size;
>>>      e->time += time;
>>>      if (e->time > MAX_TIME * INLINE_TIME_SCALE)
>> 
>> As we discussed, this is not needed in current form because we arrange first predicate to be always
>> true and thus we could always place there all the costs that did not fit elwhere.
>> 
>> The patch has a problem with fact that the predicates must be always conservative i.e. when
>> they are proved to be false the code must be unreachable after inlining.
> 
> I don't understand your point.  The OR-ing of the predicates allows us to merge size_time_entries and keep the total number of them under a desired limit.  Currently all merging goes into entry[0], and the patch makes the extra information to get distributed across more entries.  Because we OR the predicates, we keep the information conservative; now in order to say that certain code will be unreachable the inliner has to prove to be false the OR-ed predicate.
> 
> Now, one can argue whether it is actually a benefit to distribute the information more evenly and, consequently, making more predicates harder to disprove.  In current scheme we have the surplus of size_time information under one impossible-to-disprove predicate and many entries with easier-to-disprove-predicates.  My patch changes the situation to having most of the size_time information in entries with harder-but-possible-to-disprove predicates.
> 
> Am I missing something?

Ping.

Though this patch is not motivated by a real testcase, I want to confirm (or correct) my understanding of the IPA context-tracking infrastructure.

Jan, does the above sound reasonable as to why predicates would still be conservative after the patch?

Thank you,

--
Maxim Kuvyrkov
CodeSourcery / Mentor Graphics