Re: [PATCH] Gimplify builtin_expect on short-circuiting conditionals

[Adam Nemet <anemet at caviumnetworks dot com>]

Paolo Bonzini writes:
> Adam Nemet wrote:
> > The gimplifier treats __builtin_expect as a regular function call.
> > This does not seem to work well if the argument is a logical
> > expression with short-circuit semantics.
> 
> This is PR21513:
> 
> http://gcc.gnu.org/ml/gcc-bugs/2005-12/msg01775.html

I modified the patch to split the conditionals in built-in folder
rather than in the gimplifier.  I am still distributing builtin_expect
over the logical operations as opposed to what Paolo was recommending
which is to quote the PR:

  1. __b_e (a && b, 1) => __b_e (a, 1) && __b_e (b, 1)
  2. __b_e (a && b, 0) => a && __b_e (b, 0)
  3. __b_e (a || b, 1) => a || __b_e (b, 1)
  4. __b_e (a || b, 0) => __b_e (a, 0) || __b_e (b, 0)


For example in 2, people generally rely on short-circuiting so 'a' is
actually more likely to be zero than 'b'.  That would suggest perhaps
folding it into __b_e (a, 0) && b but I chose to keep the old behavior
of expand_builtin_expect_jump.  I am open if people think we should do
the former.

I also added folding of:

 __b_e (__b_e (a, C1), C2) -> __b_e (a, C1)

We get these now after distributing builtin_expects and the idea is
that in a complex expression we want to use the more local
builtin_expect (see the fifth test).

Tested on mipsisa64-elf, bootstrapped and regtested on x86_64-linux.

OK?

Adam

	PR tree-optimization/21513
	* builtins.c (build_builtin_expect_predicate): New function.
	(fold_builtin_expect): Add argument for expected value.
	Distribute __builtin_expect over short-circuiting operations.
	Fold nested builtin_expects.
	(fold_builtin_2): Adjust call to fold_builtin_expect.


	* gcc.dg/tree-ssa/builtin-expect-1.c: New test.
	* gcc.dg/tree-ssa/builtin-expect-2.c: New test.
	* gcc.dg/tree-ssa/builtin-expect-3.c: New test.
	* gcc.dg/tree-ssa/builtin-expect-4.c: New test.
	* gcc.dg/tree-ssa/builtin-expect-5.c: New test.

Index: builtins.c
===================================================================
*** builtins.c	(revision 125932)
--- builtins.c	(working copy)
*************** static rtx expand_builtin_sprintf (tree,
*** 147,153 ****
  static tree stabilize_va_list (tree, int);
  static rtx expand_builtin_expect (tree, rtx);
  static tree fold_builtin_constant_p (tree);
! static tree fold_builtin_expect (tree);
  static tree fold_builtin_classify_type (tree);
  static tree fold_builtin_strlen (tree);
  static tree fold_builtin_inf (tree, int);
--- 147,153 ----
  static tree stabilize_va_list (tree, int);
  static rtx expand_builtin_expect (tree, rtx);
  static tree fold_builtin_constant_p (tree);
! static tree fold_builtin_expect (tree, tree);
  static tree fold_builtin_classify_type (tree);
  static tree fold_builtin_strlen (tree);
  static tree fold_builtin_inf (tree, int);
*************** fold_builtin_constant_p (tree arg)
*** 6953,6973 ****
    return NULL_TREE;
  }
  
! /* Fold a call to __builtin_expect with argument ARG, if we expect that a
!    comparison against the argument will fold to a constant.  In practice,
!    this means a true constant or the address of a non-weak symbol.  */
  
  static tree
! fold_builtin_expect (tree arg)
  {
!   tree inner;
  
!   /* If the argument isn't invariant, then there's nothing we can do.  */
!   if (!TREE_INVARIANT (arg))
      return NULL_TREE;
  
!   /* If we're looking at an address of a weak decl, then do not fold.  */
!   inner = arg;
    STRIP_NOPS (inner);
    if (TREE_CODE (inner) == ADDR_EXPR)
      {
--- 6953,7035 ----
    return NULL_TREE;
  }
  
! /* Create builtin_expect with PRED and EXPECTED as its arguments and
!    return it as a truthvalue.  */
  
  static tree
! build_builtin_expect_predicate (tree pred, tree expected)
  {
!   tree fn, arglist, arg_types, pred_type, expected_type, call_expr, ret_type;
  
!   fn = built_in_decls[BUILT_IN_EXPECT];
!   arg_types = TYPE_ARG_TYPES (TREE_TYPE (fn));
!   ret_type = TREE_TYPE (TREE_TYPE (fn));
!   pred_type = TREE_VALUE (arg_types);
!   expected_type = TREE_VALUE (TREE_CHAIN (arg_types));
! 
!   pred = fold_convert (pred_type, pred);
!   expected = convert (expected_type, expected);
! 
!   arglist = build_tree_list (NULL_TREE, expected);
!   arglist = tree_cons (NULL_TREE, pred, arglist);
!   call_expr = build_function_call_expr (fn, arglist);
! 
!   return build2 (NE_EXPR, TREE_TYPE (pred), call_expr,
! 		 build_int_cst (ret_type, 0));
! }
! 
! /* Fold a call to builtin_expect with arguments ARG0 and ARG1.  Return
!    NULL_TREE if no simplification is possible.  */
! 
! static tree
! fold_builtin_expect (tree arg0, tree arg1)
! {
!   tree inner, fndecl;
!   enum tree_code code;
! 
!   /* If this is a builtin_expect within a builtin_expect keep the
!      inner one.  See through a comparison against a constant.  It
!      might have been added to create a thruthvalue.  */
!   inner = arg0;
!   if (COMPARISON_CLASS_P (inner)
!       && TREE_CODE (TREE_OPERAND (inner, 1)) == INTEGER_CST)
!     inner = TREE_OPERAND (inner, 0);
! 
!   if (TREE_CODE (inner) == CALL_EXPR
!       && (fndecl = get_callee_fndecl (inner))
!       && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
!       && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT)
!     return arg0;
! 
!   /* Distribute the expected value over short-circuiting operators.
!      See through the cast from truthvalue_type_node to long.  */
!   inner = arg0;
!   while (TREE_CODE (inner) == NOP_EXPR
! 	 && INTEGRAL_TYPE_P (TREE_TYPE (inner))
! 	 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (inner, 0))))
!     inner = TREE_OPERAND (inner, 0);
! 
!   code = TREE_CODE (inner);
!   if (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR)
!     {
!       tree op0 = TREE_OPERAND (inner, 0);
!       tree op1 = TREE_OPERAND (inner, 1);
! 
!       op0 = build_builtin_expect_predicate (op0, arg1);
!       op1 = build_builtin_expect_predicate (op1, arg1);
!       inner = build2 (code, TREE_TYPE (inner), op0, op1);
! 
!       return fold_convert (TREE_TYPE (arg0), inner);
!     }
! 
!   /* If the argument isn't invariant then there's nothing else we can do.  */
!   if (!TREE_INVARIANT (arg0))
      return NULL_TREE;
  
!   /* If we expect that a comparison against the argument will fold to
!      a constant return the constant.  In practice, this means a true
!      constant or the address of a non-weak symbol.  */
!   inner = arg0;
    STRIP_NOPS (inner);
    if (TREE_CODE (inner) == ADDR_EXPR)
      {
*************** fold_builtin_expect (tree arg)
*** 6981,6988 ****
  	return NULL_TREE;
      }
  
!   /* Otherwise, ARG already has the proper type for the return value.  */
!   return arg;
  }
  
  /* Fold a call to __builtin_classify_type with argument ARG.  */
--- 7043,7050 ----
  	return NULL_TREE;
      }
  
!   /* Otherwise, ARG0 already has the proper type for the return value.  */
!   return arg0;
  }
  
  /* Fold a call to __builtin_classify_type with argument ARG.  */
*************** fold_builtin_2 (tree fndecl, tree arg0, 
*** 10008,10014 ****
        return fold_builtin_strpbrk (arg0, arg1, type);
  
      case BUILT_IN_EXPECT:
!       return fold_builtin_expect (arg0);
  
      CASE_FLT_FN (BUILT_IN_POW):
        return fold_builtin_pow (fndecl, arg0, arg1, type);
--- 10070,10076 ----
        return fold_builtin_strpbrk (arg0, arg1, type);
  
      case BUILT_IN_EXPECT:
!       return fold_builtin_expect (arg0, arg1);
  
      CASE_FLT_FN (BUILT_IN_POW):
        return fold_builtin_pow (fndecl, arg0, arg1, type);
Index: testsuite/gcc.dg/tree-ssa/builtin-expect-1.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/builtin-expect-1.c	(revision 0)
--- testsuite/gcc.dg/tree-ssa/builtin-expect-1.c	(revision 0)
***************
*** 0 ****
--- 1,11 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-gimple" } */
+ 
+ f (int i, float j) 
+ { 
+   if (__builtin_expect (i > 0 && j, 0)) 
+     g ();
+ } 
+ 
+ /* { dg-final { scan-tree-dump-times {builtin_expect[^\n]*, 0\);\n[^\n]*if} 2 "gimple"} } */
+ /* { dg-final { cleanup-tree-dump "gimple" } } */
Index: testsuite/gcc.dg/tree-ssa/builtin-expect-2.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/builtin-expect-2.c	(revision 0)
--- testsuite/gcc.dg/tree-ssa/builtin-expect-2.c	(revision 0)
***************
*** 0 ****
--- 1,13 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-gimple" } */
+ 
+ f (int i, float j) 
+ { 
+   if (__builtin_expect (i > 0 || j, 0))
+     ;
+   else
+     g ();
+ } 
+ 
+ /* { dg-final { scan-tree-dump-times {builtin_expect[^\n]*, 0\);\n[^\n]*if} 2 "gimple"} } */
+ /* { dg-final { cleanup-tree-dump "gimple" } } */
Index: testsuite/gcc.dg/tree-ssa/builtin-expect-3.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/builtin-expect-3.c	(revision 0)
--- testsuite/gcc.dg/tree-ssa/builtin-expect-3.c	(revision 0)
***************
*** 0 ****
--- 1,13 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-gimple" } */
+ 
+ f (int i, float j) 
+ { 
+   if (__builtin_expect (i > 0 && j, 0))
+     a ();
+   else
+     b ();
+ } 
+ 
+ /* { dg-final { scan-tree-dump-times {builtin_expect[^\n]*, 0\);\n[^\n]*if} 2 "gimple"} } */
+ /* { dg-final { cleanup-tree-dump "gimple" } } */
Index: testsuite/gcc.dg/tree-ssa/builtin-expect-4.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/builtin-expect-4.c	(revision 0)
--- testsuite/gcc.dg/tree-ssa/builtin-expect-4.c	(revision 0)
***************
*** 0 ****
--- 1,13 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-gimple" } */
+ 
+ f (int i, float j) 
+ { 
+   if (__builtin_expect (i > 0 || j, 0))
+     a ();
+   else
+     b ();
+ } 
+ 
+ /* { dg-final { scan-tree-dump-times {builtin_expect[^\n]*, 0\);\n[^\n]*if} 2 "gimple"} } */
+ /* { dg-final { cleanup-tree-dump "gimple" } } */
Index: testsuite/gcc.dg/tree-ssa/builtin-expect-5.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/builtin-expect-5.c	(revision 0)
--- testsuite/gcc.dg/tree-ssa/builtin-expect-5.c	(revision 0)
***************
*** 0 ****
--- 1,15 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-forwprop" } */
+ 
+ f (int i, float j) 
+ { 
+   if (__builtin_expect (i > 0 && __builtin_expect (j != 0, 1), 0))
+     a ();
+   else
+     b ();
+ } 
+ 
+ /* { dg-final { scan-tree-dump-times { if } 2 "forwprop1"} } */
+ /* { dg-final { scan-tree-dump {builtin_expect[^\n]*, 0\);\n[^\n]*if} "forwprop1"} } */
+ /* { dg-final { scan-tree-dump {builtin_expect[^\n]*, 1\);\n[^\n]*if} "forwprop1"} } */
+ /* { dg-final { cleanup-tree-dump "forwprop?" } } */