diff mbox

Improve probability/profile distribution in ORIF expansion

Message ID CAAe5K+U=mgCcLj5aTcr=6BLdHuvbf=k2axAwOwBf=DCUrjAkhw@mail.gmail.com
State New
Headers show

Commit Message

Teresa Johnson Oct. 2, 2013, 5:23 p.m. UTC 
On Wed, Oct 2, 2013 at 9:03 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> 2013-10-01  Teresa Johnson  <tejohnson@google.com>
>>
>>         * dojump.c (do_jump_1): Divide probability between
>>         both conditions of a TRUTH_ORIF_EXPR.
>>
>> +      {
>> +        /* Spread the probability evenly between the two conditions. So
>> +           the first condition has half the total probability of being true.
>> +           The second condition has the other half of the total probability,
>> +           so its jump has a probability of half the total, relative to
>> +           the probability we reached it (i.e. the first condition
>> was false).  */
>> +        int op0_prob = prob / 2;
>> +        int op1_prob = GCOV_COMPUTE_SCALE ((prob / 2), inv (op0_prob));
>
> Documentation of the functions says that PROB may be -1 when it is unknown, In that
> case you want to arrange op0_prob=op1_prob = -1.

Fixed.

>
> What about TRUTH_ANDIF_EXPR code above?  I think it needs similar adjusting

Yes. When I first looked at it yesterday I thought it was ok, but I
see we need to do something similar. Essentially, the probability that
either condition is false is half the probability the entire ANDIF
expression is false. So basically we do the same computation, but on
the expression's false probability, and invert the resulting false
condition probabilities.

Here is the new patch I am testing. Will commit after testing completes.
Thanks,
Teresa

2013-10-02  Teresa Johnson  <tejohnson@google.com>

        * dojump.c (do_jump_1): Divide probability between
        both conditions of a TRUTH_ANDIF_EXPR/TRUTH_ORIF_EXPR.

     default:
       gcc_unreachable ();



>
> Patch is preaproved with these changes.
>
> Thanks!
> Honza
diff mbox

Patch

Index: dojump.c
===================================================================
--- dojump.c    (revision 203077)
+++ dojump.c    (working copy)
@@ -311,32 +311,66 @@  do_jump_1 (enum tree_code code, tree op0, tree op1
       break;

     case TRUTH_ANDIF_EXPR:
-      if (if_false_label == NULL_RTX)
-        {
-         drop_through_label = gen_label_rtx ();
-         do_jump (op0, drop_through_label, NULL_RTX, prob);
-         do_jump (op1, NULL_RTX, if_true_label, prob);
-       }
-      else
-       {
-         do_jump (op0, if_false_label, NULL_RTX, prob);
-         do_jump (op1, if_false_label, if_true_label, prob);
-       }
-      break;
+      {
+        /* Spread the probability that the expression is false evenly between
+           the two conditions. So the first condition is false half the total
+           probability of being false. The second condition is false the other
+           half of the total probability of being false, so its jump
has a false
+           probability of half the total, relative to the probability we
+           reached it (i.e. the first condition was true).  */
+        int op0_prob = -1;
+        int op1_prob = -1;
+        if (prob != -1)
+          {
+            int false_prob = inv (prob);
+            int op0_false_prob = false_prob / 2;
+            int op1_false_prob = GCOV_COMPUTE_SCALE ((false_prob / 2),
+                                                     inv (op0_false_prob));
+            /* Get the probability that each jump below is true.  */
+            op0_prob = inv (op0_false_prob);
+            op1_prob = inv (op1_false_prob);
+          }
+        if (if_false_label == NULL_RTX)
+          {
+            drop_through_label = gen_label_rtx ();
+            do_jump (op0, drop_through_label, NULL_RTX, op0_prob);
+            do_jump (op1, NULL_RTX, if_true_label, op1_prob);
+          }
+        else
+          {
+            do_jump (op0, if_false_label, NULL_RTX, op0_prob);
+            do_jump (op1, if_false_label, if_true_label, op1_prob);
+          }
+        break;
+      }

     case TRUTH_ORIF_EXPR:
-      if (if_true_label == NULL_RTX)
-       {
-          drop_through_label = gen_label_rtx ();
-         do_jump (op0, NULL_RTX, drop_through_label, prob);
-         do_jump (op1, if_false_label, NULL_RTX, prob);
-       }
-      else
-       {
-         do_jump (op0, NULL_RTX, if_true_label, prob);
-         do_jump (op1, if_false_label, if_true_label, prob);
-       }
-      break;
+      {
+        /* Spread the probability evenly between the two conditions. So
+           the first condition has half the total probability of being true.
+           The second condition has the other half of the total probability,
+           so its jump has a probability of half the total, relative to
+           the probability we reached it (i.e. the first condition
was false).  */
+        int op0_prob = -1;
+        int op1_prob = -1;
+        if (prob != -1)
+          {
+            op0_prob = prob / 2;
+            op1_prob = GCOV_COMPUTE_SCALE ((prob / 2), inv (op0_prob));
+          }
+        if (if_true_label == NULL_RTX)
+          {
+            drop_through_label = gen_label_rtx ();
+            do_jump (op0, NULL_RTX, drop_through_label, op0_prob);
+            do_jump (op1, if_false_label, NULL_RTX, op1_prob);
+          }
+        else
+          {
+            do_jump (op0, NULL_RTX, if_true_label, op0_prob);
+            do_jump (op1, if_false_label, if_true_label, op1_prob);
+          }
+        break;
+      }