[PATCH] One possible fix for the compute_bb_predicate oscillation (PR ipa/60013)

[Jakub Jelinek <jakub at redhat dot com>]

Hi!

Here is one possible fix for the PR60013 compute_bb_predicates oscillation,
the PR contains long analysis, but to sum it up, the problem is that
we only allow 8 conjuction operands for the predicates and when we reach 8
and want to add some further one, we just throw some of the disjunctions
on the floor, which makes the dataflow computation not guaranteed to
terminate.

The following patch fixes that by just turning all predicates that would
need more than 8 CNF toplevel operands into always true predicates (meaning
that we conservatively consider the particular basic block to be potentially
always executed independently on the function arguments).

I've bootstrapped/regtested this patch on x86_64-linux and i686-linux,
the (i2 == MAX_CLAUSES) condition was true in 2447 cases while inside
of compute_bb_predicates (on average compute_bb_predicates call that
triggered at least one such conservative bail out would see 3.14 of those)
and 482 times outside of compute_bb_predicate, on 159 unique source files
something triggered.  But, the fact that it triggered doesn't mean at all
the function would be even considered for inlining and even if it would, it
often would not change the inlining decisions.

As I said in the PR, the other possibility I see is just in letting
compute_bb_predicates do the dataflow until it set's the predicates on all
basic blocks, and then perhaps have some counter for each bb how many times
it has changed in the following iterations and if it changes too many times,
just use true_predicate for it or something similar.

Or the following patch could be combined with some MAX_CLAUSES growth (say
from 8 to 16) to make it punt less often.

2014-02-05  Jakub Jelinek  <jakub@redhat.com>

	PR ipa/60013
	* ipa-inline-analysis.c (add_clause): Fix comment typos.  If
	clause couldn't be added because there are already MAX_CLAUSES
	clauses, turn p into a true predicate.
	(and_predicates, or_predicates): If add_clause turned the
	result into a true_predicate_p, break out of the loop nest.

	* gcc.dg/pr60013.c: New test.

--- gcc/ipa-inline-analysis.c.jj	2014-02-03 08:53:12.000000000 +0100
+++ gcc/ipa-inline-analysis.c	2014-02-05 08:01:57.093878954 +0100
@@ -310,7 +310,7 @@ add_clause (conditions conditions, struc
   if (false_predicate_p (p))
     return;
 
-  /* No one should be sily enough to add false into nontrivial clauses.  */
+  /* No one should be silly enough to add false into nontrivial clauses.  */
   gcc_checking_assert (!(clause & (1 << predicate_false_condition)));
 
   /* Look where to insert the clause.  At the same time prune out
@@ -372,9 +372,13 @@ add_clause (conditions conditions, struc
     }
 
 
-  /* We run out of variants.  Be conservative in positive direction.  */
+  /* We run out of variants.  Conservatively turn clause into true
+     predicate.  */
   if (i2 == MAX_CLAUSES)
-    return;
+    {
+      p->clause[0] = 0;
+      return;
+    }
   /* Keep clauses in decreasing order. This makes equivalence testing easy.  */
   p->clause[i2 + 1] = 0;
   if (insert_here >= 0)
@@ -412,6 +416,8 @@ and_predicates (conditions conditions,
     {
       gcc_checking_assert (i < MAX_CLAUSES);
       add_clause (conditions, &out, p2->clause[i]);
+      if (true_predicate_p (&out))
+	break;
     }
   return out;
 }
@@ -459,6 +465,8 @@ or_predicates (conditions conditions,
       {
 	gcc_checking_assert (i < MAX_CLAUSES && j < MAX_CLAUSES);
 	add_clause (conditions, &out, p->clause[i] | p2->clause[j]);
+	if (true_predicate_p (&out))
+	  return out;
       }
   return out;
 }
@@ -1035,7 +1043,7 @@ inline_node_removal_hook (struct cgraph_
   memset (info, 0, sizeof (inline_summary_t));
 }
 
-/* Remap predicate P of former function to be predicate of duplicated functoin.
+/* Remap predicate P of former function to be predicate of duplicated function.
    POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
    INFO is inline summary of the duplicated node.  */
 
--- gcc/testsuite/gcc.dg/pr60013.c.jj	2014-02-05 09:49:51.632142747 +0100
+++ gcc/testsuite/gcc.dg/pr60013.c	2014-02-05 09:49:14.000000000 +0100
@@ -0,0 +1,47 @@
+/* PR ipa/60013 */
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+typedef long int jmp_buf[64];
+extern int _setjmp (jmp_buf) __attribute__ ((__nothrow__));
+struct S { int a, b, c; };
+extern struct S *baz (struct S *);
+static jmp_buf j;
+
+static inline int
+bar (int b, int d)
+{
+  return (b & d) < 0;
+}
+
+struct S *
+foo (int a, struct S *b, struct S *c, struct S *d)
+{
+  if (b->a == 0)
+    {
+      switch (a)
+	{
+	case 8:
+	  return baz (b);
+	case 7:
+	  bar (b->c, c->b);
+	  return 0;
+	case 6:
+	case 5:
+	case 4:
+	  return baz (c);
+	case 3:
+	case 2:
+	  return baz (d);
+	}
+      return 0;
+    }
+  if (b->a == 1)
+    {
+      if (baz (c))
+	return c;
+      else if (_setjmp (j))
+	baz (b);
+    }
+  return 0;
+}

	Jakub