[PATCH] Gimplify builtin_expect on short-circuiting conditionals

[Adam Nemet <anemet at caviumnetworks dot com>]

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.

Consider this testcase:

  f (int i, float j)  
  {  
    if (__builtin_expect (i > 0 && j, 0))  
      g (); 
  }

The conditional as an argument is gimplified into a conditional
expression without the builtin_expect:

  <bb 2>:
    if (i_2(D) <= 0)
      goto <bb 4>;
    else
      goto <bb 3>;
  
  <bb 3>:
    D.1583_4 = j_3(D) != 0.0;
    if (D.1583_4 == 0)
      goto <bb 4>;
    else
      goto <bb 5>;
  
  <bb 4>:
  
  <bb 5>:
    # iftmp.0_1 = PHI <1(3), 0(4)>
    D.1585_8 = (long int) iftmp.0_1;
    D.1586_9 = __builtin_expect (D.1585_8, 0);
    if (D.1586_9 != 0)
      goto <bb 6>;
    else
      goto <bb 7>;
  
  <bb 6>:
    g ();
  
  <bb 7>:
    return;

Then block 5 is basically eliminated together with the effect of the
builtin_expect.

GCC 3.4 used to take account of the builtin_expect in
expand_builtin_expect_jump.  It generated the sequence with do_jump.
Then predicted each jump insn as taken or not-taken depending on which
label it was jumping too.

This patch distributes the builtin_expect call across the operands of
TRUTH_ANDIF_EXPR and TRUTH_ORIF_EXPR in gimplify_cond_expr as we
recurse in shortcut_cond_expr and shortcut_cond_r.  Note that I don't
ever need to invert the prediction because the condition is never
inverted only the arms of the if statement are exchanged.

I tried to make the tests target-independent by using the float
comparison as the second operand.  This should prevent
LOGICAL_OP_NON_SHORT_CIRCUIT targets to turn the operators into their
non-short-circuiting counterparts.

The fifth testcase verifies that if there is a builtin_expect on an
operand it takes precedence over the one on the whole expression.

Regression tested on mipsisa64-elf, bootstrapped and regression tested
on x86_64-linux.

OK?

Adam

	* gimplify.c (remove_expected_value, add_expected_value): New
	functions.
	(shortcut_cond_expr, shortcut_cond_r): Use them to distribute
	builtin_expect across operands.  Add new argument expected.
	(split_cond_expr_p): New function.
	(gimplify_cond_expr): Use it to see through builtin_expects
	when looking for short-circuiting operators.


	* 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: gimplify.c
===================================================================
--- gimplify.c	(revision 125932)
+++ gimplify.c	(working copy)
@@ -2150,23 +2150,134 @@ gimplify_call_expr (tree *expr_p, tree *
   return ret;
 }
 
+/* If PRED is a predicate see if there is a builtin_expect call at the
+   top level and return the real predicate inside the builtin_expect.
+   In this case also return the expected value in *EXPECTED.
+   Otherwise, return the the original expression and don't change the
+   value in *EXPECTED.  */
+
+static tree
+remove_expected_value (tree pred, tree *expected)
+{
+  tree fndecl, arg0, arg1, orig = pred;
+  bool invert_pred = false;
+
+  if ((TREE_CODE (pred) == NE_EXPR
+       || TREE_CODE (pred) == EQ_EXPR))
+    {
+      tree rhs = TREE_OPERAND (pred, 1);
+
+      if (integer_onep (rhs))
+	invert_pred = TREE_CODE (pred) == NE_EXPR;
+      else if (integer_zerop (rhs))
+	invert_pred = TREE_CODE (pred) == EQ_EXPR;
+      else
+	return orig;
+
+      pred = TREE_OPERAND (pred, 0);
+    }
+
+  if (TREE_CODE (pred) != CALL_EXPR)
+    return orig;
+
+  fndecl = get_callee_fndecl (pred);
+  if (!fndecl
+      || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL
+      || DECL_FUNCTION_CODE (fndecl) != BUILT_IN_EXPECT
+      || call_expr_nargs (pred) != 2)
+    return orig;
+
+  arg0 = CALL_EXPR_ARG (pred, 0);
+  arg1 = CALL_EXPR_ARG (pred, 1);
+
+  /* See through the cast from truthvalue_type_node to long.  */
+  while (TREE_CODE (arg0) == NOP_EXPR
+	 && INTEGRAL_TYPE_P (TREE_TYPE (arg0))
+	 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 0))))
+    arg0 = TREE_OPERAND (arg0, 0);
+
+  if (TREE_CODE (TREE_TYPE (arg1)) != INTEGER_TYPE
+      || (!integer_zerop (arg1) && !integer_onep (arg1)))
+    return orig;
+
+  *expected = arg1;
+
+  arg0 = gimple_boolify (arg0);
+  if (invert_pred)
+    return invert_truthvalue (arg0);
+  else
+    return arg0;
+}
+
+/* Return true if COND_EXPR should be split using
+   shortcut_cond_expr.  */
+
+static bool
+split_cond_expr_p (tree cond_expr)
+{
+  tree pred, expected;
+
+  gcc_assert (TREE_CODE (cond_expr) == COND_EXPR);
+  pred = TREE_OPERAND (cond_expr, 0);
+
+  pred = remove_expected_value (pred, &expected);
+
+  return (TREE_CODE (pred) == TRUTH_ANDIF_EXPR
+	  || TREE_CODE (pred) == TRUTH_ORIF_EXPR);
+}
+
+/* Return a call to builtin_expect with PRED and EXPECTED as its
+   arguments.  Return the original expression PRED if EXPECTED is a
+   NULL_TREE.  */
+
+static tree
+add_expected_value (tree pred, tree expected)
+{
+  tree fn, arglist, arg_types, pred_type, expected_type, call_expr, ret_type;
+
+  if (expected == NULL_TREE)
+    return pred;
+
+  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,
+		 convert (ret_type, integer_zero_node));
+}
+
 /* Handle shortcut semantics in the predicate operand of a COND_EXPR by
    rewriting it into multiple COND_EXPRs, and possibly GOTO_EXPRs.
 
    TRUE_LABEL_P and FALSE_LABEL_P point to the labels to jump to if the
    condition is true or false, respectively.  If null, we should generate
-   our own to skip over the evaluation of this specific expression.
+   our own to skip over the evaluation of this specific expression.  If
+   EXPECTED is set then place a builtin_expect around each predicate with
+   this value.  Don't do this if a more local builtin_expect is found.
 
    This function is the tree equivalent of do_jump.
 
    shortcut_cond_r should only be called by shortcut_cond_expr.  */
 
 static tree
-shortcut_cond_r (tree pred, tree *true_label_p, tree *false_label_p)
+shortcut_cond_r (tree pred, tree *true_label_p, tree *false_label_p,
+		 tree expected)
 {
   tree local_label = NULL_TREE;
   tree t, expr = NULL;
 
+  /* Find the real predicate if this is within a builtin_expect.  */
+  pred = remove_expected_value (pred, &expected);
+
   /* OK, it's not a simple case; we need to pull apart the COND_EXPR to
      retain the shortcut semantics.  Just insert the gotos here;
      shortcut_cond_expr will append the real blocks later.  */
@@ -2181,11 +2292,12 @@ shortcut_cond_r (tree pred, tree *true_l
       if (false_label_p == NULL)
 	false_label_p = &local_label;
 
-      t = shortcut_cond_r (TREE_OPERAND (pred, 0), NULL, false_label_p);
+      t = shortcut_cond_r (TREE_OPERAND (pred, 0), NULL, false_label_p,
+			   expected);
       append_to_statement_list (t, &expr);
 
-      t = shortcut_cond_r (TREE_OPERAND (pred, 1), true_label_p,
-			   false_label_p);
+      t = shortcut_cond_r (TREE_OPERAND (pred, 1), true_label_p, false_label_p,
+			   expected);
       append_to_statement_list (t, &expr);
     }
   else if (TREE_CODE (pred) == TRUTH_ORIF_EXPR)
@@ -2199,11 +2311,12 @@ shortcut_cond_r (tree pred, tree *true_l
       if (true_label_p == NULL)
 	true_label_p = &local_label;
 
-      t = shortcut_cond_r (TREE_OPERAND (pred, 0), true_label_p, NULL);
+      t = shortcut_cond_r (TREE_OPERAND (pred, 0), true_label_p, NULL,
+			   expected);
       append_to_statement_list (t, &expr);
 
       t = shortcut_cond_r (TREE_OPERAND (pred, 1), true_label_p,
-			   false_label_p);
+			   false_label_p, expected);
       append_to_statement_list (t, &expr);
     }
   else if (TREE_CODE (pred) == COND_EXPR)
@@ -2213,15 +2326,17 @@ shortcut_cond_r (tree pred, tree *true_l
 	   if (b) goto yes; else goto no;
 	 else
 	   if (c) goto yes; else goto no;  */
-      expr = build3 (COND_EXPR, void_type_node, TREE_OPERAND (pred, 0),
+      expr = build3 (COND_EXPR, void_type_node,
+		     add_expected_value (TREE_OPERAND (pred, 0), expected),
 		     shortcut_cond_r (TREE_OPERAND (pred, 1), true_label_p,
-				      false_label_p),
+				      false_label_p, expected),
 		     shortcut_cond_r (TREE_OPERAND (pred, 2), true_label_p,
-				      false_label_p));
+				      false_label_p, expected));
     }
   else
     {
-      expr = build3 (COND_EXPR, void_type_node, pred,
+      expr = build3 (COND_EXPR, void_type_node,
+		     add_expected_value (pred, expected),
 		     build_and_jump (true_label_p),
 		     build_and_jump (false_label_p));
     }
@@ -2235,8 +2350,14 @@ shortcut_cond_r (tree pred, tree *true_l
   return expr;
 }
 
+/* EXPR is a COND_EXPR with a predicate containing TRUTH_ORIF_EXPR or
+   TRUTH_ANDIF_EXPR.  Split the COND_EXPR with shortcutting the
+   individual terms.  If EXPECTED is set then place a builtin_expect
+   around each predicate with this value.  Do not do this if a more
+   local builtin_expect is found.  */
+
 static tree
-shortcut_cond_expr (tree expr)
+shortcut_cond_expr (tree expr, tree expected)
 {
   tree pred = TREE_OPERAND (expr, 0);
   tree then_ = TREE_OPERAND (expr, 1);
@@ -2248,6 +2369,9 @@ shortcut_cond_expr (tree expr)
   bool then_se = then_ && TREE_SIDE_EFFECTS (then_);
   bool else_se = else_ && TREE_SIDE_EFFECTS (else_);
 
+  /* Find the real predicate if this is within a builtin_expect.  */
+  pred = remove_expected_value (pred, &expected);
+
   /* First do simple transformations.  */
   if (!else_se)
     {
@@ -2255,7 +2379,7 @@ shortcut_cond_expr (tree expr)
       while (TREE_CODE (pred) == TRUTH_ANDIF_EXPR)
 	{
 	  TREE_OPERAND (expr, 0) = TREE_OPERAND (pred, 1);
-	  then_ = shortcut_cond_expr (expr);
+	  then_ = shortcut_cond_expr (expr, expected);
 	  then_se = then_ && TREE_SIDE_EFFECTS (then_);
 	  pred = TREE_OPERAND (pred, 0);
 	  expr = build3 (COND_EXPR, void_type_node, pred, then_, NULL_TREE);
@@ -2270,7 +2394,7 @@ shortcut_cond_expr (tree expr)
       while (TREE_CODE (pred) == TRUTH_ORIF_EXPR)
 	{
 	  TREE_OPERAND (expr, 0) = TREE_OPERAND (pred, 1);
-	  else_ = shortcut_cond_expr (expr);
+	  else_ = shortcut_cond_expr (expr, expected);
 	  else_se = else_ && TREE_SIDE_EFFECTS (else_);
 	  pred = TREE_OPERAND (pred, 0);
 	  expr = build3 (COND_EXPR, void_type_node, pred, NULL_TREE, else_);
@@ -2280,7 +2404,10 @@ shortcut_cond_expr (tree expr)
   /* If we're done, great.  */
   if (TREE_CODE (pred) != TRUTH_ANDIF_EXPR
       && TREE_CODE (pred) != TRUTH_ORIF_EXPR)
-    return expr;
+    {
+      TREE_OPERAND (expr, 0) = add_expected_value (pred, expected);
+      return expr;
+    }
 
   /* Otherwise we need to mess with gotos.  Change
        if (a) c; else d;
@@ -2327,7 +2454,7 @@ shortcut_cond_expr (tree expr)
 
   /* If there was nothing else in our arms, just forward the label(s).  */
   if (!then_se && !else_se)
-    return shortcut_cond_r (pred, true_label_p, false_label_p);
+    return shortcut_cond_r (pred, true_label_p, false_label_p, expected);
 
   /* If our last subexpression already has a terminal label, reuse it.  */
   if (else_se)
@@ -2358,7 +2485,7 @@ shortcut_cond_expr (tree expr)
      non-void function.  */
   jump_over_else = block_may_fallthru (then_);
 
-  pred = shortcut_cond_r (pred, true_label_p, false_label_p);
+  pred = shortcut_cond_r (pred, true_label_p, false_label_p, expected);
 
   expr = NULL;
   append_to_statement_list (pred, &expr);
@@ -2507,10 +2634,9 @@ gimplify_cond_expr (tree *expr_p, tree *
   TREE_OPERAND (expr, 0) = gimple_boolify (TREE_OPERAND (expr, 0));
 
   /* Break apart && and || conditions.  */
-  if (TREE_CODE (TREE_OPERAND (expr, 0)) == TRUTH_ANDIF_EXPR
-      || TREE_CODE (TREE_OPERAND (expr, 0)) == TRUTH_ORIF_EXPR)
+  if (split_cond_expr_p (expr))
     {
-      expr = shortcut_cond_expr (expr);
+      expr = shortcut_cond_expr (expr, NULL_TREE);
 
       if (expr != *expr_p)
 	{
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,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,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,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,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,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-gimple" } */
+
+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 "gimple"} } */
+/* { dg-final { scan-tree-dump {builtin_expect[^\n]*, 0\);\n[^\n]*if} "gimple"} } */
+/* { dg-final { scan-tree-dump {builtin_expect[^\n]*, 1\);\n[^\n]*if} "gimple"} } */
+/* { dg-final { cleanup-tree-dump "gimple" } } */