Propagate BB predicates in ipa-inline-analysis

Propagate BB predicates in ipa-inline-analysis

[Jan Hubicka]

Hi,
this more or less complettes the infrastructure for predicates by adding
logic propagating predicates across CFG.  I also added switch statement
handling and __builtin_constant_p construct, so we "understand" functions
using those as one in the new testcase.

It also turned out that the predicate handling code should be more aggressive
on simplification and canonicalization so the propagation converges quickly.

Bootstrapped/regtested x86_64-linux, will commit it shortly.

Honza

	* gcc.dg/tree-ssa/inline-10.c: New testcase.
	* gcc.dg/tree-ssa/inline-9.c: Disable partial inlining.
	* ipa-inline.h (clause_t): Turn into unsigned int.
	* ipa-inline-analysis.c (add_clause): Do more simplification.
	(and_predicates): Shortcut more cases.
	(predicates_equal_p): Move forward; check that clauses are properly
	ordered.
	(or_predicates): Shortcut more cases.
	(edge_execution_predicate): Rewrite as...
	(set_cond_stmt_execution_predicate): ... this function; handle
	__builtin_constant_p.
	(set_switch_stmt_execution_predicate): New .
	(compute_bb_predicates): New.
	(will_be_nonconstant_predicate): Update TODO.
	(estimate_function_body_sizes): Use compute_bb_predicates
	and free them later, always try to estimate if stmt is constant.
	(estimate_time_after_inlining, estimate_size_after_inlining):
	Gracefully handle optimized out edges.
	(read_predicate): Fix off by one error.
Index: testsuite/gcc.dg/tree-ssa/inline-9.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/inline-9.c	(revision 173181)
--- testsuite/gcc.dg/tree-ssa/inline-9.c	(working copy)
***************
*** 1,5 ****
  /* { dg-do compile } */
! /* { dg-options "-Os -fdump-tree-optimized" } */
  
  /* When optimizing for size, t should be inlined when it expands to one call only.  */
  extern int q(int);
--- 1,5 ----
  /* { dg-do compile } */
! /* { dg-options "-Os -fdump-tree-optimized -fno-partial-inlining" } */ 
  \f/* When optimizing for size, t should be inlined when it expands to one call only.  */
  extern int q(int);
Index: testsuite/gcc.dg/tree-ssa/inline-10.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/inline-10.c	(revision 0)
--- testsuite/gcc.dg/tree-ssa/inline-10.c	(revision 0)
***************
*** 0 ****
--- 1,38 ----
+ /* { dg-do compile } */
+ /* { dg-options "-Os -fdump-tree-optimized -fno-partial-inlining" } */
+ void do_something1(void);
+ void do_something2(void);
+ void do_something3(void);
+ void do_something4(void);
+ void do_something5(void);
+ void do_something_big(int);
+ 
+ int do_something (int size)
+ {
+   if (__builtin_constant_p (size))
+     switch (size)
+       {
+ 	case 1:do_something1 (); break;
+ 	case 2:do_something2 (); break;
+ 	case 5:do_something1 ();  do_something1 ();
+ 	case 3:do_something3 (); break;
+ 	case 4:do_something4 (); break;
+       }
+   else
+     do_something_big (size);
+ }
+ extern int n;
+ main()
+ {
+   do_something (2);
+   do_something (3);
+   do_something (5);
+   do_something (70);
+ }
+ /* All calls should be inlined, except for do_something (5).  */
+ /* { dg-final { scan-tree-dump-not "do_something1" "optimized" } } */
+ /* { dg-final { scan-tree-dump-times "do_something2" 1 "optimized" } } */
+ /* { dg-final { scan-tree-dump-times "do_something3" 1 "optimized" } } */
+ /* { dg-final { scan-tree-dump-times "do_something \\(5\\)" 1 "optimized" } } */
+ /* { dg-final { scan-tree-dump-not "do_something \\(70\\)" "optimized" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */
Index: ipa-inline.h
===================================================================
*** ipa-inline.h	(revision 173181)
--- ipa-inline.h	(working copy)
*************** typedef VEC(condition,gc) *conditions;
*** 48,54 ****
     must be true in order for clause to be true.  */
  
  #define MAX_CLAUSES 8
! typedef int clause_t;
  struct GTY(()) predicate
  {
    clause_t clause[MAX_CLAUSES + 1];
--- 48,54 ----
     must be true in order for clause to be true.  */
  
  #define MAX_CLAUSES 8
! typedef unsigned int clause_t;
  struct GTY(()) predicate
  {
    clause_t clause[MAX_CLAUSES + 1];
Index: ipa-inline-analysis.c
===================================================================
*** ipa-inline-analysis.c	(revision 173181)
--- ipa-inline-analysis.c	(working copy)
*************** add_condition (struct inline_summary *su
*** 227,245 ****
  }
  
  
! /* Add clause CLAUSE into the predicate.  */
  
  static inline void
  add_clause (struct predicate *p, clause_t clause)
  {
    int i;
    int insert_here = -1;
  
    /* True clause.  */
    if (!clause)
      return;
  
!   /* Flase clause makes the whole predicate false.  Kill the other variants.  */
    if (clause == (1 << predicate_false_condition))
      {
        p->clause[0] = (1 << predicate_false_condition);
--- 227,246 ----
  }
  
  
! /* Add clause CLAUSE into the predicate P.  */
  
  static inline void
  add_clause (struct predicate *p, clause_t clause)
  {
    int i;
+   int i2;
    int insert_here = -1;
  
    /* True clause.  */
    if (!clause)
      return;
  
!   /* False clause makes the whole predicate false.  Kill the other variants.  */
    if (clause == (1 << predicate_false_condition))
      {
        p->clause[0] = (1 << predicate_false_condition);
*************** add_clause (struct predicate *p, clause_
*** 248,273 ****
      }
    if (false_predicate_p (p))
      return;
!   gcc_assert (!(clause & (1 << predicate_false_condition)));
!   for (i = 0; i < MAX_CLAUSES - 1; i++)
      {
!       if (p->clause[i] == clause)
!         return;
        if (!p->clause[i])
  	break;
!       if (p->clause[i] < clause && !insert_here)
! 	insert_here = i;
      }
!   /* We run out of variants.  Be conservative in positive direciton.  */
!   if (i == MAX_CLAUSES)
      return;
!   /* Keep clauses ordered by index, so equivalence testing is easy.  */
!   p->clause[i + 1] = 0;
    if (insert_here >= 0)
!     for (;i > insert_here; i--)
!       p->clause[i] = p->clause[i - 1];
    else
!     insert_here = i;
    p->clause[insert_here] = clause;
  }
  
--- 249,294 ----
      }
    if (false_predicate_p (p))
      return;
! 
!   /* No one should be sily 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
!      clauses of P that are implied by the new clause and thus
!      redundant.  */
!   for (i = 0, i2 = 0; i <= MAX_CLAUSES; i++)
      {
!       p->clause[i2] = p->clause[i];
! 
        if (!p->clause[i])
  	break;
! 
!       /* If p->clause[i] implies clause, there is nothing to add.  */
!       if ((p->clause[i] & clause) == p->clause[i])
! 	{
! 	  /* We had nothing to add, none of clauses should've become redundant.  */
! 	  gcc_checking_assert (i == i2);
! 	  return;
! 	}
! 
!       if (p->clause[i] < clause && insert_here < 0)
! 	insert_here = i2;
! 
!       /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
! 	 Otherwise the p->clause[i] has to stay.  */
!       if ((p->clause[i] & clause) != clause)
! 	i2++;
      }
!   /* We run out of variants.  Be conservative in positive direction.  */
!   if (i2 == MAX_CLAUSES)
      return;
!   /* Keep clauses in decreasing order. This makes equivalence testing easy.  */
!   p->clause[i2 + 1] = 0;
    if (insert_here >= 0)
!     for (;i2 > insert_here; i2--)
!       p->clause[i2] = p->clause[i2 - 1];
    else
!     insert_here = i2;
    p->clause[insert_here] = clause;
  }
  
*************** and_predicates (struct predicate *p, str
*** 280,286 ****
    struct predicate out = *p;
    int i;
  
!   for (i = 0; p2->clause[i]; i++)
      {
        gcc_checking_assert (i < MAX_CLAUSES);
        add_clause (&out, p2->clause[i]);
--- 301,320 ----
    struct predicate out = *p;
    int i;
  
!   /* Avoid busy work.  */
!   if (false_predicate_p (p2) || true_predicate_p (p))
!     return *p2;
!   if (false_predicate_p (p) || true_predicate_p (p2))
!     return *p;
! 
!   /* See how far predicates match.  */
!   for (i = 0; p->clause[i] && p->clause[i] == p2->clause[i]; i++)
!     {
!       gcc_checking_assert (i < MAX_CLAUSES);
!     }
!     
!   /* Combine the predicates rest.  */
!   for (; p2->clause[i]; i++)
      {
        gcc_checking_assert (i < MAX_CLAUSES);
        add_clause (&out, p2->clause[i]);
*************** and_predicates (struct predicate *p, str
*** 289,294 ****
--- 323,346 ----
  }
  
  
+ /* Return true if predicates are obviously equal.  */
+ 
+ static inline bool
+ predicates_equal_p (struct predicate *p, struct predicate *p2)
+ {
+   int i;
+   for (i = 0; p->clause[i]; i++)
+     {
+       gcc_checking_assert (i < MAX_CLAUSES);
+       gcc_checking_assert (p->clause [i] > p->clause[i + 1]);
+       gcc_checking_assert (!p2->clause[i] || p2->clause [i] > p2->clause[i + 1]);
+       if (p->clause[i] != p2->clause[i])
+         return false;
+     }
+   return !p2->clause[i];
+ }
+ 
+ 
  /* Return P | P2.  */
  
  static struct predicate
*************** or_predicates (struct predicate *p, stru
*** 297,307 ****
    struct predicate out = true_predicate ();
    int i,j;
  
!   /* If one of conditions is false, return the other.  */
!   if (false_predicate_p (p2))
      return *p;
!   if (false_predicate_p (p))
      return *p2;
    for (i = 0; p->clause[i]; i++)
      for (j = 0; p2->clause[j]; j++)
        {
--- 349,363 ----
    struct predicate out = true_predicate ();
    int i,j;
  
!   /* Avoid busy work.  */
!   if (false_predicate_p (p2) || true_predicate_p (p))
      return *p;
!   if (false_predicate_p (p) || true_predicate_p (p2))
      return *p2;
+   if (predicates_equal_p (p, p2))
+     return *p;
+ 
+   /* OK, combine the predicates.  */
    for (i = 0; p->clause[i]; i++)
      for (j = 0; p2->clause[j]; j++)
        {
*************** or_predicates (struct predicate *p, stru
*** 312,333 ****
  }
  
  
- /* Return true if predicates are obviously equal.  */
- 
- static inline bool
- predicates_equal_p (struct predicate *p, struct predicate *p2)
- {
-   int i;
-   for (i = 0; p->clause[i]; i++)
-     {
-       gcc_checking_assert (i < MAX_CLAUSES);
-       if (p->clause[i] != p2->clause[i])
-         return false;
-     }
-   return !p2->clause[i];
- }
- 
- 
  /* Having partial truth assignment in POSSIBLE_TRUTHS, return false if predicate P
     to be false.  */
  
--- 368,373 ----
*************** eliminated_by_inlining_prob (gimple stmt
*** 885,934 ****
  }
  
  
! /* Return predicate that must be true when is E executable.  */
  
! static struct predicate
! edge_execution_predicate (struct ipa_node_params *info,
! 			  struct inline_summary *summary,
! 			  edge e)
  {
-   struct predicate p = true_predicate ();
    gimple last;
    tree op;
    int index;
!   enum tree_code code;
  
!   if (e->src == ENTRY_BLOCK_PTR)
!     return p;
! 
!   last = last_stmt (e->src);
!   /* TODO: handle switch.  */
    if (!last
        || gimple_code (last) != GIMPLE_COND)
!     return p;
    if (!is_gimple_ip_invariant (gimple_cond_rhs (last)))
!     return p;
    op = gimple_cond_lhs (last);
    /* TODO: handle conditionals like
       var = op0 < 4;
!      if (var != 0)
!      and __bulitin_constant_p.  */
    if (TREE_CODE (op) != SSA_NAME
        || !SSA_NAME_IS_DEFAULT_DEF (op))
!     return p;
    index = ipa_get_param_decl_index (info, SSA_NAME_VAR (op));
    if (index == -1)
!     return p;
!   code = gimple_cond_code (last);
  
!   if (EDGE_TRUE_VALUE)
!     code = invert_tree_comparison (code,
! 				   HONOR_NANS (TYPE_MODE (TREE_TYPE (op))));
! 
!   return add_condition (summary,
! 			index,
! 			gimple_cond_code (last),
! 			gimple_cond_rhs (last));
  }
  
  
--- 925,1150 ----
  }
  
  
! /* If BB ends by a conditional we can turn into predicates, attach corresponding
!    predicates to the CFG edges.   */
  
! static void
! set_cond_stmt_execution_predicate (struct ipa_node_params *info,
! 			           struct inline_summary *summary,
! 			           basic_block bb)
  {
    gimple last;
    tree op;
    int index;
!   enum tree_code code, inverted_code;
!   edge e;
!   edge_iterator ei;
!   gimple set_stmt;
!   tree op2;
  
!   last = last_stmt (bb);
    if (!last
        || gimple_code (last) != GIMPLE_COND)
!     return;
    if (!is_gimple_ip_invariant (gimple_cond_rhs (last)))
!     return;
    op = gimple_cond_lhs (last);
    /* TODO: handle conditionals like
       var = op0 < 4;
!      if (var != 0).  */
!   if (TREE_CODE (op) != SSA_NAME)
!     return;
!   if (SSA_NAME_IS_DEFAULT_DEF (op))
!     {
!       index = ipa_get_param_decl_index (info, SSA_NAME_VAR (op));
!       if (index == -1)
! 	return;
!       code = gimple_cond_code (last);
!       inverted_code = invert_tree_comparison (code,
! 					      HONOR_NANS (TYPE_MODE (TREE_TYPE (op))));
! 
!       FOR_EACH_EDGE (e, ei, bb->succs)
! 	{
! 	  struct predicate p = add_condition (summary,
! 					      index,
! 					      e->flags & EDGE_TRUE_VALUE
! 					      ? code : inverted_code,
! 					      gimple_cond_rhs (last));
! 	  e->aux = pool_alloc (edge_predicate_pool);
! 	  *(struct predicate *)e->aux = p;
! 	}
!     }
! 
!   /* Special case
!      if (builtin_constant_p (op))
!        constant_code
!      else
!        nonconstant_code.
!      Here we can predicate nonconstant_code.  We can't
!      really handle constant_code since we have no predicate
!      for this and also the constant code is not known to be
!      optimized away when inliner doen't see operand is constant.
!      Other optimizers might think otherwise.  */
!   set_stmt = SSA_NAME_DEF_STMT (op);
!   if (!gimple_call_builtin_p (set_stmt, BUILT_IN_CONSTANT_P)
!       || gimple_call_num_args (set_stmt) != 1)
!     return;
!   op2 = gimple_call_arg (set_stmt, 0);
!   if (!SSA_NAME_IS_DEFAULT_DEF (op2))
!     return;
!   index = ipa_get_param_decl_index (info, SSA_NAME_VAR (op2));
!   if (index == -1)
!     return;
!   if (gimple_cond_code (last) != NE_EXPR
!       || !integer_zerop (gimple_cond_rhs (last)))
!     return;
!   FOR_EACH_EDGE (e, ei, bb->succs)
!     if (e->flags & EDGE_FALSE_VALUE)
!       {
! 	struct predicate p = add_condition (summary,
! 					    index,
! 					    IS_NOT_CONSTANT,
! 					    NULL);
! 	e->aux = pool_alloc (edge_predicate_pool);
! 	*(struct predicate *)e->aux = p;
!       }
! }
! 
! 
! /* If BB ends by a switch we can turn into predicates, attach corresponding
!    predicates to the CFG edges.   */
! 
! static void
! set_switch_stmt_execution_predicate (struct ipa_node_params *info,
! 			           struct inline_summary *summary,
! 			           basic_block bb)
! {
!   gimple last;
!   tree op;
!   int index;
!   edge e;
!   edge_iterator ei;
!   size_t n;
!   size_t case_idx;
! 
!   last = last_stmt (bb);
!   if (!last
!       || gimple_code (last) != GIMPLE_SWITCH)
!     return;
!   op = gimple_switch_index (last);
    if (TREE_CODE (op) != SSA_NAME
        || !SSA_NAME_IS_DEFAULT_DEF (op))
!     return;
    index = ipa_get_param_decl_index (info, SSA_NAME_VAR (op));
    if (index == -1)
!     return;
! 
!   FOR_EACH_EDGE (e, ei, bb->succs)
!     {
!       e->aux = pool_alloc (edge_predicate_pool);
!       *(struct predicate *)e->aux = false_predicate ();
!     }
!   n = gimple_switch_num_labels(last);
!   for (case_idx = 0; case_idx < n; ++case_idx)
!     {
!       tree cl = gimple_switch_label (last, case_idx);
!       tree min, max;
!       struct predicate p;
! 
!       e = find_edge (bb, label_to_block (CASE_LABEL (cl)));
!       min = CASE_LOW (cl);
!       max = CASE_HIGH (cl);
! 
!       /* For default we might want to construct predicate that none
! 	 of cases is met, but it is bit hard to do not having negations
! 	 of conditionals handy.  */
!       if (!min && !max)
! 	p = true_predicate ();
!       else if (!max)
! 	p = add_condition (summary, index,
! 			   EQ_EXPR,
! 			   min);
!       else
! 	{
! 	  struct predicate p1, p2;
! 	  p1 = add_condition (summary, index,
! 			      GE_EXPR,
! 			      min);
! 	  p2 = add_condition (summary, index,
! 			      LE_EXPR,
! 			      max);
! 	  p = and_predicates (&p1, &p2);
! 	}
!       *(struct predicate *)e->aux
! 	= or_predicates (&p, (struct predicate *)e->aux);
!     }
! }
! 
  
! /* For each BB in NODE attach to its AUX pointer predicate under
!    which it is executable.  */
! 
! static void
! compute_bb_predicates (struct cgraph_node *node,
! 		       struct ipa_node_params *parms_info,
! 		       struct inline_summary *summary)
! {
!   struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
!   bool done = false;
!   basic_block bb;
! 
!   FOR_EACH_BB_FN (bb, my_function)
!     {
!       set_cond_stmt_execution_predicate (parms_info, summary, bb);
!       set_switch_stmt_execution_predicate (parms_info, summary, bb);
!     }
! 
!   /* Entry block is always executable.  */
!   ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function)->aux = pool_alloc (edge_predicate_pool);
!   *(struct predicate *)ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function)->aux
!     = true_predicate ();
! 
!   /* A simple dataflow propagation of predicates forward in the CFG.
!      TODO: work in reverse postorder.  */
!   while (!done)
!     {
!       done = true;
!       FOR_EACH_BB_FN (bb, my_function)
! 	{
!           struct predicate p = false_predicate ();
!           edge e;
!           edge_iterator ei;
! 	  FOR_EACH_EDGE (e, ei, bb->preds)
! 	    {
! 	      if (e->src->aux)
! 		{
! 		  struct predicate this_bb_predicate = *(struct predicate *)e->src->aux;
! 		  if (e->aux)
! 		    this_bb_predicate = and_predicates (&this_bb_predicate,
! 							(struct predicate *)e->aux);
! 		  p = or_predicates (&p, &this_bb_predicate);
! 		  if (true_predicate_p (&p))
! 		    break;
! 		}
! 	    }
! 	  if (false_predicate_p (&p))
! 	    gcc_assert (!bb->aux);
! 	  else
! 	    {
! 	      if (!bb->aux)
! 		{
! 		  done = false;
! 		  bb->aux = pool_alloc (edge_predicate_pool);
! 		  *((struct predicate *)bb->aux) = p;
! 		}
! 	      else if (!predicates_equal_p (&p, (struct predicate *)bb->aux))
! 		{
! 		  done = false;
! 		  *((struct predicate *)bb->aux) = p;
! 		}
! 	    }
! 	}
!     }
  }
  
  
*************** will_be_nonconstant_predicate (struct ip
*** 956,962 ****
  
    /* What statments might be optimized away
       when their arguments are constant
!      TODO: also trivial builtins, especially builtin_constant_p.  */
    if (gimple_code (stmt) != GIMPLE_ASSIGN
        && gimple_code (stmt) != GIMPLE_COND
        && gimple_code (stmt) != GIMPLE_SWITCH)
--- 1172,1179 ----
  
    /* What statments might be optimized away
       when their arguments are constant
!      TODO: also trivial builtins.
!      builtin_constant_p is already handled later.  */
    if (gimple_code (stmt) != GIMPLE_ASSIGN
        && gimple_code (stmt) != GIMPLE_COND
        && gimple_code (stmt) != GIMPLE_SWITCH)
*************** estimate_function_body_sizes (struct cgr
*** 1050,1072 ****
    account_size_time (info, 2 * INLINE_SIZE_SCALE, 0, &bb_predicate);
  
    gcc_assert (my_function && my_function->cfg);
    FOR_EACH_BB_FN (bb, my_function)
      {
-       edge e;
-       edge_iterator ei;
- 
        freq = compute_call_stmt_bb_frequency (node->decl, bb);
  
        /* TODO: Obviously predicates can be propagated down across CFG.  */
        if (parms_info)
  	{
!           bb_predicate = false_predicate ();
! 	  FOR_EACH_EDGE (e, ei, bb->preds)
! 	    {
! 	      struct predicate ep;
! 	      ep = edge_execution_predicate (parms_info, info, e);
! 	      bb_predicate = or_predicates (&ep, &bb_predicate);
! 	    }
  	}
        else
  	bb_predicate = true_predicate ();
--- 1267,1285 ----
    account_size_time (info, 2 * INLINE_SIZE_SCALE, 0, &bb_predicate);
  
    gcc_assert (my_function && my_function->cfg);
+   if (parms_info)
+     compute_bb_predicates (node, parms_info, info);
    FOR_EACH_BB_FN (bb, my_function)
      {
        freq = compute_call_stmt_bb_frequency (node->decl, bb);
  
        /* TODO: Obviously predicates can be propagated down across CFG.  */
        if (parms_info)
  	{
! 	  if (bb->aux)
! 	    bb_predicate = *(struct predicate *)bb->aux;
! 	  else
! 	    bb_predicate = false_predicate ();
  	}
        else
  	bb_predicate = true_predicate ();
*************** estimate_function_body_sizes (struct cgr
*** 1083,1088 ****
--- 1296,1302 ----
  	  int this_size = estimate_num_insns (stmt, &eni_size_weights);
  	  int this_time = estimate_num_insns (stmt, &eni_time_weights);
  	  int prob;
+ 	  struct predicate will_be_nonconstant;
  
  	  if (dump_file && (dump_flags & TDF_DETAILS))
  	    {
*************** estimate_function_body_sizes (struct cgr
*** 1127,1135 ****
  		gcc_assert (!gimple_call_cannot_inline_p (stmt));
  	    }
  
  	  if (this_time || this_size)
  	    {
- 	      struct predicate will_be_nonconstant;
  	      struct predicate p;
  
  	      this_time *= freq;
--- 1341,1355 ----
  		gcc_assert (!gimple_call_cannot_inline_p (stmt));
  	    }
  
+ 	  /* TODO: When conditional jump or swithc is known to be constant, but
+  	     we did not translate it into the predicates, we really can account
+ 	     just maximum of the possible paths.  */
+ 	  if (parms_info)
+ 	    will_be_nonconstant
+ 	       = will_be_nonconstant_predicate (parms_info, info,
+ 						stmt, nonconstant_names);
  	  if (this_time || this_size)
  	    {
  	      struct predicate p;
  
  	      this_time *= freq;
*************** estimate_function_body_sizes (struct cgr
*** 1143,1154 ****
  		fprintf (dump_file, "\t\twill eliminated by inlining\n");
  
  	      if (parms_info)
! 		{
! 		  will_be_nonconstant
! 		     = will_be_nonconstant_predicate (parms_info, info,
! 						      stmt, nonconstant_names);
! 		  p = and_predicates (&bb_predicate, &will_be_nonconstant);
! 		}
  	      else
  		p = true_predicate ();
  
--- 1363,1369 ----
  		fprintf (dump_file, "\t\twill eliminated by inlining\n");
  
  	      if (parms_info)
! 		p = and_predicates (&bb_predicate, &will_be_nonconstant);
  	      else
  		p = true_predicate ();
  
*************** estimate_function_body_sizes (struct cgr
*** 1174,1179 ****
--- 1389,1409 ----
  	    }
  	}
      }
+   FOR_ALL_BB_FN (bb, my_function)
+     {
+       edge e;
+       edge_iterator ei;
+ 
+       if (bb->aux)
+ 	pool_free (edge_predicate_pool, bb->aux);
+       bb->aux = NULL;
+       FOR_EACH_EDGE (e, ei, bb->succs)
+ 	{
+ 	  if (e->aux)
+ 	    pool_free (edge_predicate_pool, e->aux);
+ 	  e->aux = NULL;
+ 	}
+     }
    time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
    if (time > MAX_TIME)
      time = MAX_TIME;
*************** int
*** 1677,1688 ****
  estimate_time_after_inlining (struct cgraph_node *node,
  			      struct cgraph_edge *edge)
  {
!   gcov_type time = inline_summary (node)->time + estimate_edge_time (edge);
!   if (time < 0)
!     time = 0;
!   if (time > MAX_TIME)
!     time = MAX_TIME;
!   return time;
  }
  
  
--- 1907,1923 ----
  estimate_time_after_inlining (struct cgraph_node *node,
  			      struct cgraph_edge *edge)
  {
!   struct inline_edge_summary *es = inline_edge_summary (edge);
!   if (!es->predicate || !false_predicate_p (es->predicate))
!     {
!       gcov_type time = inline_summary (node)->time + estimate_edge_time (edge);
!       if (time < 0)
! 	time = 0;
!       if (time > MAX_TIME)
! 	time = MAX_TIME;
!       return time;
!     }
!   return inline_summary (node)->time;
  }
  
  
*************** int
*** 1693,1701 ****
  estimate_size_after_inlining (struct cgraph_node *node,
  			      struct cgraph_edge *edge)
  {
!   int size = inline_summary (node)->size + estimate_edge_growth (edge);
!   gcc_assert (size >= 0);
!   return size;
  }
  
  
--- 1928,1941 ----
  estimate_size_after_inlining (struct cgraph_node *node,
  			      struct cgraph_edge *edge)
  {
!   struct inline_edge_summary *es = inline_edge_summary (edge);
!   if (!es->predicate || !false_predicate_p (es->predicate))
!     {
!       int size = inline_summary (node)->size + estimate_edge_growth (edge);
!       gcc_assert (size >= 0);
!       return size;
!     }
!   return inline_summary (node)->size;
  }
  
  
*************** read_predicate (struct lto_input_block *
*** 1826,1833 ****
  
    do 
      {
        clause = out.clause[k++] = lto_input_uleb128 (ib);
-       gcc_assert (k < MAX_CLAUSES);
      }
    while (clause);
    return out;
--- 2066,2073 ----
  
    do 
      {
+       gcc_assert (k <= MAX_CLAUSES);
        clause = out.clause[k++] = lto_input_uleb128 (ib);
      }
    while (clause);
    return out;

Re: Propagate BB predicates in ipa-inline-analysis

[H.J. Lu]

On Fri, Apr 29, 2011 at 2:18 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> Hi,
> this more or less complettes the infrastructure for predicates by adding
> logic propagating predicates across CFG.  I also added switch statement
> handling and __builtin_constant_p construct, so we "understand" functions
> using those as one in the new testcase.
>
> It also turned out that the predicate handling code should be more aggressive
> on simplification and canonicalization so the propagation converges quickly.
>
> Bootstrapped/regtested x86_64-linux, will commit it shortly.
>
> Honza
>
>        * gcc.dg/tree-ssa/inline-10.c: New testcase.
>        * gcc.dg/tree-ssa/inline-9.c: Disable partial inlining.
>        * ipa-inline.h (clause_t): Turn into unsigned int.
>        * ipa-inline-analysis.c (add_clause): Do more simplification.
>        (and_predicates): Shortcut more cases.
>        (predicates_equal_p): Move forward; check that clauses are properly
>        ordered.
>        (or_predicates): Shortcut more cases.
>        (edge_execution_predicate): Rewrite as...
>        (set_cond_stmt_execution_predicate): ... this function; handle
>        __builtin_constant_p.
>        (set_switch_stmt_execution_predicate): New .
>        (compute_bb_predicates): New.
>        (will_be_nonconstant_predicate): Update TODO.
>        (estimate_function_body_sizes): Use compute_bb_predicates
>        and free them later, always try to estimate if stmt is constant.
>        (estimate_time_after_inlining, estimate_size_after_inlining):
>        Gracefully handle optimized out edges.
>        (read_predicate): Fix off by one error.

This caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48929


-- 
H.J.

Re: Propagate BB predicates in ipa-inline-analysis

[Ulrich Weigand]

Jan Hubicka wrote:

> 	(edge_execution_predicate): Rewrite as...
> 	(set_cond_stmt_execution_predicate): ... this function; handle
> 	__builtin_constant_p.

This causes ICEs when building recent Linux kernels with the
CONFIG_TRACE_BRANCH_PROFLING option.  This reduced test case:

static inline __attribute__((always_inline)) int f (unsigned int n, unsigned int size)
{
 return (__builtin_constant_p (size != 0 && n > ~0 / size)
         ? !!(size != 0 && n > ~0 / size)
         : ({ static unsigned int count[2] = { 0, 0 };
              int r = !!(size != 0 && n > ~0 / size);
              count[r]++;
              r; }));
}

int g (unsigned int size)
{
 return f (size / 4096, 4);
}

built with -O2 (on i386) on current mainline results in:

/home/uweigand/test.i:15:1: internal compiler error: tree check: expected ssa_name, have integer_cst in set_cond_stmt_execution_predicate, at ipa-inline-analysis.c:1190

Bye,
Ulrich

-- 
  Dr. Ulrich Weigand
  GNU Toolchain for Linux on System z and Cell BE
  Ulrich.Weigand@de.ibm.com

Re: Propagate BB predicates in ipa-inline-analysis

[Richard Guenther]

On Fri, Sep 2, 2011 at 7:42 PM, Ulrich Weigand <uweigand@de.ibm.com> wrote:
> Jan Hubicka wrote:
>
>>       (edge_execution_predicate): Rewrite as...
>>       (set_cond_stmt_execution_predicate): ... this function; handle
>>       __builtin_constant_p.
>
> This causes ICEs when building recent Linux kernels with the
> CONFIG_TRACE_BRANCH_PROFLING option.  This reduced test case:
>
> static inline __attribute__((always_inline)) int f (unsigned int n, unsigned int size)
> {
>  return (__builtin_constant_p (size != 0 && n > ~0 / size)
>         ? !!(size != 0 && n > ~0 / size)
>         : ({ static unsigned int count[2] = { 0, 0 };
>              int r = !!(size != 0 && n > ~0 / size);
>              count[r]++;
>              r; }));
> }
>
> int g (unsigned int size)
> {
>  return f (size / 4096, 4);
> }
>
> built with -O2 (on i386) on current mainline results in:
>
> /home/uweigand/test.i:15:1: internal compiler error: tree check: expected ssa_name, have integer_cst in set_cond_stmt_execution_predicate, at ipa-inline-analysis.c:1190

Can you open a bugreport?

Thanks,
Richard.

> Bye,
> Ulrich
>
> --
>  Dr. Ulrich Weigand
>  GNU Toolchain for Linux on System z and Cell BE
>  Ulrich.Weigand@de.ibm.com
>

Re: Propagate BB predicates in ipa-inline-analysis

[Jan Hubicka]

> Jan Hubicka wrote:
> 
> > 	(edge_execution_predicate): Rewrite as...
> > 	(set_cond_stmt_execution_predicate): ... this function; handle
> > 	__builtin_constant_p.
> 
> This causes ICEs when building recent Linux kernels with the
> CONFIG_TRACE_BRANCH_PROFLING option.  This reduced test case:
> 
> static inline __attribute__((always_inline)) int f (unsigned int n, unsigned int size)
> {
>  return (__builtin_constant_p (size != 0 && n > ~0 / size)
>          ? !!(size != 0 && n > ~0 / size)
>          : ({ static unsigned int count[2] = { 0, 0 };
>               int r = !!(size != 0 && n > ~0 / size);
>               count[r]++;
>               r; }));
> }
> 
> int g (unsigned int size)
> {
>  return f (size / 4096, 4);
> }
> 
> built with -O2 (on i386) on current mainline results in:
> 
> /home/uweigand/test.i:15:1: internal compiler error: tree check: expected ssa_name, have integer_cst in set_cond_stmt_execution_predicate, at ipa-inline-analysis.c:1190

the code dies on:

  D.2739_10 = __builtin_constant_p (0);

it assumes that argument of __builtin_constant_p is always SSA_NAME.  I am testing the obvious fix for that.
However it is missed optimization to leave such unfolded statement.  It happens at fwprop converting:

<bb 5>:
  iftmp.1_9 = 0;

<bb 6>:
  # iftmp.1_2 = PHI <1(4), 0(5)>
  D.2739_10 = __builtin_constant_p (iftmp.1_2);

Honza
> 
> Bye,
> Ulrich
> 
> -- 
>   Dr. Ulrich Weigand
>   GNU Toolchain for Linux on System z and Cell BE
>   Ulrich.Weigand@de.ibm.com

Re: Propagate BB predicates in ipa-inline-analysis

[Richard Guenther]

On Sat, Sep 3, 2011 at 6:41 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> Jan Hubicka wrote:
>>
>> >     (edge_execution_predicate): Rewrite as...
>> >     (set_cond_stmt_execution_predicate): ... this function; handle
>> >     __builtin_constant_p.
>>
>> This causes ICEs when building recent Linux kernels with the
>> CONFIG_TRACE_BRANCH_PROFLING option.  This reduced test case:
>>
>> static inline __attribute__((always_inline)) int f (unsigned int n, unsigned int size)
>> {
>>  return (__builtin_constant_p (size != 0 && n > ~0 / size)
>>          ? !!(size != 0 && n > ~0 / size)
>>          : ({ static unsigned int count[2] = { 0, 0 };
>>               int r = !!(size != 0 && n > ~0 / size);
>>               count[r]++;
>>               r; }));
>> }
>>
>> int g (unsigned int size)
>> {
>>  return f (size / 4096, 4);
>> }
>>
>> built with -O2 (on i386) on current mainline results in:
>>
>> /home/uweigand/test.i:15:1: internal compiler error: tree check: expected ssa_name, have integer_cst in set_cond_stmt_execution_predicate, at ipa-inline-analysis.c:1190
>
> the code dies on:
>
>  D.2739_10 = __builtin_constant_p (0);
>
> it assumes that argument of __builtin_constant_p is always SSA_NAME.  I am testing the obvious fix for that.
> However it is missed optimization to leave such unfolded statement.  It happens at fwprop converting:

tree-ssa-forwprop.c I presume?  That one misses calling fold_stmt when
it propagates things.

> <bb 5>:
>  iftmp.1_9 = 0;
>
> <bb 6>:
>  # iftmp.1_2 = PHI <1(4), 0(5)>
>  D.2739_10 = __builtin_constant_p (iftmp.1_2);

But I wonder how it manages to do something to the above ... (are you
sure it's forwprop?)

Richard.

> Honza
>>
>> Bye,
>> Ulrich
>>
>> --
>>   Dr. Ulrich Weigand
>>   GNU Toolchain for Linux on System z and Cell BE
>>   Ulrich.Weigand@de.ibm.com
>

Re: Propagate BB predicates in ipa-inline-analysis

[Jan Hubicka]

> tree-ssa-forwprop.c I presume?  That one misses calling fold_stmt when
> it propagates things.

Yep.
> 
> > <bb 5>:
> >  iftmp.1_9 = 0;
> >
> > <bb 6>:
> >  # iftmp.1_2 = PHI <1(4), 0(5)>
> >  D.2739_10 = __builtin_constant_p (iftmp.1_2);
> 
> But I wonder how it manages to do something to the above ... (are you
> sure it's forwprop?)

It is fwprop, but I cut&pasted wrong function (it is the offline copy instead of inline).
we transfrom:
g (unsigned int size)
{ 
  int iftmp.1;
  int D.2765;
  unsigned int D.2764;
  unsigned int D.2763;
  static unsigned int count[2] = {0, 0};
  int r;
  static unsigned int count[2] = {0, 0};
  unsigned int D.2729;

<bb 2>:
  D.2729_2 = size_1(D) / 4096;
  if (D.2729_2 > 1073741823)
    goto <bb 4>;
  else
    goto <bb 3>;

<bb 3>:

<bb 4>:
  # iftmp.1_7 = PHI <1(2), 0(3)>
  D.2765_8 = __builtin_constant_p (iftmp.1_7);

into:
g (unsigned int size)
{
  int D.2765;
  unsigned int D.2764;
  unsigned int D.2763;
  static unsigned int count[2] = {0, 0};
  int r;
  static unsigned int count[2] = {0, 0};

<bb 2>:
  D.2765_8 = __builtin_constant_p (0);

I guess forwprop should fold then...  The extra call and control flow survives
all the way down to ccp2 (that is after IPA) that eventually folds it away.

Honza

Re: Propagate BB predicates in ipa-inline-analysis

[Jan Hubicka]

Hi,
this is patch I comitted fixing ipa-inline-analysis.  Stil I guess we should
fill in PR for missed optimization and solve the forwprop issue?

Honza

Index: ChangeLog
===================================================================
*** ChangeLog	(revision 178523)
--- ChangeLog	(working copy)
***************
*** 1,3 ****
--- 1,8 ----
+ 2011-09-04  Jan Hubicka  <jh@suse.cz>
+ 
+ 	* ipa-inline-analysis.c (set_cond_stmt_execution_predicate): Check that
+ 	parameter is SSA name.
+ 
  2011-09-04  Richard Guenther  <rguenther@suse.de>
  
  	Revert
Index: testsuite/gcc.c-torture/compile/20110902.c
===================================================================
*** testsuite/gcc.c-torture/compile/20110902.c	(revision 0)
--- testsuite/gcc.c-torture/compile/20110902.c	(revision 0)
***************
*** 0 ****
--- 1,14 ----
+ static inline __attribute__((always_inline)) int f (unsigned int n, unsigned int size)
+ {
+  return (__builtin_constant_p (size != 0 && n > ~0 / size)
+          ? !!(size != 0 && n > ~0 / size)
+          : ({ static unsigned int count[2] = { 0, 0 };
+               int r = !!(size != 0 && n > ~0 / size);
+               count[r]++;
+               r; }));
+ }
+ 
+ int g (unsigned int size)
+ {
+  return f (size / 4096, 4);
+ }
Index: testsuite/ChangeLog
===================================================================
*** testsuite/ChangeLog	(revision 178523)
--- testsuite/ChangeLog	(working copy)
***************
*** 1,3 ****
--- 1,7 ----
+ 2011-09-04  Jan Hubicka  <jh@suse.cz>
+ 
+ 	* gcc.c-torture/compile/20110902.c: new testcase.
+ 
  2011-09-04  Jason Merrill  <jason@redhat.com>
  
  	PR c++/49267
Index: ipa-inline-analysis.c
===================================================================
*** ipa-inline-analysis.c	(revision 178523)
--- ipa-inline-analysis.c	(working copy)
*************** set_cond_stmt_execution_predicate (struc
*** 1187,1192 ****
--- 1187,1194 ----
        || gimple_call_num_args (set_stmt) != 1)
      return;
    op2 = gimple_call_arg (set_stmt, 0);
+   if (TREE_CODE (op2) != SSA_NAME)
+     return;
    if (!SSA_NAME_IS_DEFAULT_DEF (op2))
      return;
    index = ipa_get_param_decl_index (info, SSA_NAME_VAR (op2));

Re: Propagate BB predicates in ipa-inline-analysis

[Richard Guenther]

On Mon, Sep 5, 2011 at 9:41 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
> Hi,
> this is patch I comitted fixing ipa-inline-analysis.  Stil I guess we should
> fill in PR for missed optimization and solve the forwprop issue?

I'm looking at it, it seems to be cfgcleanups bug

Richard.

> Honza
>
> Index: ChangeLog
> ===================================================================
> *** ChangeLog   (revision 178523)
> --- ChangeLog   (working copy)
> ***************
> *** 1,3 ****
> --- 1,8 ----
> + 2011-09-04  Jan Hubicka  <jh@suse.cz>
> +
> +       * ipa-inline-analysis.c (set_cond_stmt_execution_predicate): Check that
> +       parameter is SSA name.
> +
>  2011-09-04  Richard Guenther  <rguenther@suse.de>
>
>        Revert
> Index: testsuite/gcc.c-torture/compile/20110902.c
> ===================================================================
> *** testsuite/gcc.c-torture/compile/20110902.c  (revision 0)
> --- testsuite/gcc.c-torture/compile/20110902.c  (revision 0)
> ***************
> *** 0 ****
> --- 1,14 ----
> + static inline __attribute__((always_inline)) int f (unsigned int n, unsigned int size)
> + {
> +  return (__builtin_constant_p (size != 0 && n > ~0 / size)
> +          ? !!(size != 0 && n > ~0 / size)
> +          : ({ static unsigned int count[2] = { 0, 0 };
> +               int r = !!(size != 0 && n > ~0 / size);
> +               count[r]++;
> +               r; }));
> + }
> +
> + int g (unsigned int size)
> + {
> +  return f (size / 4096, 4);
> + }
> Index: testsuite/ChangeLog
> ===================================================================
> *** testsuite/ChangeLog (revision 178523)
> --- testsuite/ChangeLog (working copy)
> ***************
> *** 1,3 ****
> --- 1,7 ----
> + 2011-09-04  Jan Hubicka  <jh@suse.cz>
> +
> +       * gcc.c-torture/compile/20110902.c: new testcase.
> +
>  2011-09-04  Jason Merrill  <jason@redhat.com>
>
>        PR c++/49267
> Index: ipa-inline-analysis.c
> ===================================================================
> *** ipa-inline-analysis.c       (revision 178523)
> --- ipa-inline-analysis.c       (working copy)
> *************** set_cond_stmt_execution_predicate (struc
> *** 1187,1192 ****
> --- 1187,1194 ----
>        || gimple_call_num_args (set_stmt) != 1)
>      return;
>    op2 = gimple_call_arg (set_stmt, 0);
> +   if (TREE_CODE (op2) != SSA_NAME)
> +     return;
>    if (!SSA_NAME_IS_DEFAULT_DEF (op2))
>      return;
>    index = ipa_get_param_decl_index (info, SSA_NAME_VAR (op2));
>

Re: Propagate BB predicates in ipa-inline-analysis

[Ulrich Weigand]

Jan Hubicka wrote:

> this is patch I comitted fixing ipa-inline-analysis.

Thanks for fixing this!

Richard Guenther wrote:

> Can you open a bugreport?

Sorry, I didn't see this until now.  Given that the fix is
already checked in (and the problem doesn't exist on any
release branch), I guess we don't really need any PR now ...

If you'd prefer to still have one, let me know and I'll
create it.

Thanks,
Ulrich

-- 
  Dr. Ulrich Weigand
  GNU Toolchain for Linux on System z and Cell BE
  Ulrich.Weigand@de.ibm.com

Re: Propagate BB predicates in ipa-inline-analysis

[Jan Hubicka]

> Jan Hubicka wrote:
> 
> > this is patch I comitted fixing ipa-inline-analysis.
> 
> Thanks for fixing this!
> 
> Richard Guenther wrote:
> 
> > Can you open a bugreport?
> 
> Sorry, I didn't see this until now.  Given that the fix is
> already checked in (and the problem doesn't exist on any
> release branch), I guess we don't really need any PR now ...
> 
> If you'd prefer to still have one, let me know and I'll
> create it.

We should still have PR on the missing optimization in the testcase
(i.e. we really should not leak builtlin_constant_p (0) in the IL
after early cleanups. it is simply stupid).

Honza

Re: Propagate BB predicates in ipa-inline-analysis

[Richard Guenther]

On Mon, Sep 5, 2011 at 8:53 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> Jan Hubicka wrote:
>>
>> > this is patch I comitted fixing ipa-inline-analysis.
>>
>> Thanks for fixing this!
>>
>> Richard Guenther wrote:
>>
>> > Can you open a bugreport?
>>
>> Sorry, I didn't see this until now.  Given that the fix is
>> already checked in (and the problem doesn't exist on any
>> release branch), I guess we don't really need any PR now ...
>>
>> If you'd prefer to still have one, let me know and I'll
>> create it.
>
> We should still have PR on the missing optimization in the testcase
> (i.e. we really should not leak builtlin_constant_p (0) in the IL
> after early cleanups. it is simply stupid).

I committed a fix already.

> Honza
>