[PATCH] Simple improvement for predicate computation in if-convert phase.

[PATCH] Simple improvement for predicate computation in if-convert phase.

[Yuri Rumyantsev]

[-- Attachment #1: Type: text/plain, Size: 747 bytes --]

Hi All,

Here is a simple enhancement for predicate computation in if-convert phase:

 We use notion of cd equivalence to get simpler predicate for
     join block, e.g. if join block has 2 predecessors with predicates
     p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
     p1 & p2 | p1 & !p2.

Bootstrap and regression testing did not show any new failures.

Is it OK for trunk?

gcc/ChangeLog
2014-10-16  Yuri Rumyantsev  <ysrumyan@gmail.com>

* tree-if-conv.c (add_to_predicate_list): Check unconditionally
that bb is always executed to early exit. Use predicate of
cd-equivalent block for join blocks if it exists.
(if_convertible_loop_p_1): Recompute POST_DOMINATOR tree.
(tree_if_conversion): Free post-dominance information.

[-- Attachment #2: if-conv.patch --]
[-- Type: application/octet-stream, Size: 2499 bytes --]

Index: tree-if-conv.c
===================================================================
--- tree-if-conv.c	(revision 216217)
+++ tree-if-conv.c	(working copy)
@@ -396,25 +396,51 @@
 }
 
 /* Add condition NC to the predicate list of basic block BB.  LOOP is
-   the loop to be if-converted.  */
+   the loop to be if-converted. Use predicate of cd-equivalent block
+   for join bb if it exists.  */
 
 static inline void
 add_to_predicate_list (struct loop *loop, basic_block bb, tree nc)
 {
   tree bc, *tp;
+  basic_block dom_bb;
+  static basic_block join_bb = NULL;
 
   if (is_true_predicate (nc))
     return;
 
-  if (!is_predicated (bb))
+  /* If dominance tells us this basic block is always executed,
+     don't record any predicates for it.  */
+  if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
+    return;
+
+  /* If predicate has been already set up for given bb using cd-equivalent
+     block predicate, simply escape.  */
+  if (join_bb == bb)
+    return;
+  dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
+  /* We use notion of cd equivalence to get simpler predicate for
+     join block, e.g. if join block has 2 predecessors with predicates
+     p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
+     p1 & p2 | p1 & !p2.  */
+  if (dom_bb != loop->header
+      && get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb) == bb)
     {
-      /* If dominance tells us this basic block is always executed, don't
-	 record any predicates for it.  */
-      if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
-	return;
+      gcc_assert (flow_bb_inside_loop_p (loop, dom_bb));
+      bc = bb_predicate (dom_bb);
+      gcc_assert (!is_true_predicate (bc));
+      set_bb_predicate (bb, bc);
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Use predicate of bb#%d for bb#%d\n",
+		 dom_bb->index, bb->index);
 
-      bc = nc;
+      /* Save bb in join_bb to not handle it once more.  */
+      join_bb = bb;
+      return;
     }
+
+  if (!is_predicated (bb))
+    bc = nc;
   else
     {
       bc = bb_predicate (bb);
@@ -1176,6 +1202,7 @@
     return false;
 
   calculate_dominance_info (CDI_DOMINATORS);
+  calculate_dominance_info (CDI_POST_DOMINATORS);
 
   /* Allow statements that can be handled during if-conversion.  */
   ifc_bbs = get_loop_body_in_if_conv_order (loop);
@@ -2148,6 +2175,7 @@
       free (ifc_bbs);
       ifc_bbs = NULL;
     }
+  free_dominance_info (CDI_POST_DOMINATORS);
 
   return todo;
 }

Re: [PATCH] Simple improvement for predicate computation in if-convert phase.

[Jeff Law]

On 10/16/14 05:52, Yuri Rumyantsev wrote:
> Hi All,
>
> Here is a simple enhancement for predicate computation in if-convert phase:
>
>   We use notion of cd equivalence to get simpler predicate for
>       join block, e.g. if join block has 2 predecessors with predicates
>       p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
>       p1 & p2 | p1 & !p2.
>
> Bootstrap and regression testing did not show any new failures.
>
> Is it OK for trunk?
>
> gcc/ChangeLog
> 2014-10-16  Yuri Rumyantsev<ysrumyan@gmail.com>
>
> * tree-if-conv.c (add_to_predicate_list): Check unconditionally
> that bb is always executed to early exit. Use predicate of
> cd-equivalent block for join blocks if it exists.
> (if_convertible_loop_p_1): Recompute POST_DOMINATOR tree.
> (tree_if_conversion): Free post-dominance information.
First, for the benefit of anyone trying to understand what you're doing, 
defining what "cd equivalent" means would be helpful.


>
>
> if-conv.patch
>
>
> Index: tree-if-conv.c
> ===================================================================
> --- tree-if-conv.c	(revision 216217)
> +++ tree-if-conv.c	(working copy)
> @@ -396,25 +396,51 @@
>   }
>
>   /* Add condition NC to the predicate list of basic block BB.  LOOP is
> -   the loop to be if-converted.  */
> +   the loop to be if-converted. Use predicate of cd-equivalent block
> +   for join bb if it exists.  */
>
>   static inline void
>   add_to_predicate_list (struct loop *loop, basic_block bb, tree nc)
>   {
>     tree bc, *tp;
> +  basic_block dom_bb;
> +  static basic_block join_bb = NULL;
>
>     if (is_true_predicate (nc))
>       return;
>
> -  if (!is_predicated (bb))
> +  /* If dominance tells us this basic block is always executed,
> +     don't record any predicates for it.  */
> +  if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
> +    return;
So, do you have a case where the dominated_by_p test above is true and 
is_predicated(bb) returns true as well?  I think this part of the change 
is largely responsible for the hack you're doing with having the 
function scoped static variable join_bb.




> +
> +  /* If predicate has been already set up for given bb using cd-equivalent
> +     block predicate, simply escape.  */
> +  if (join_bb == bb)
> +    return;
I *really* dislike the state you're carrying around via join_bb.

ISTM that if you compute that there's an equivalence, then you just set 
the predicate for the equivalent block and the right things would have 
happened if you had not changed the test above.

You also need a testcase.  It doesn't have to be extensive, but at least 
some basic "smoke test" to verify basic operation of this code.  It's 
perfectly fine to scan the debugging dumps for debug output.


jeff

Re: [PATCH] Simple improvement for predicate computation in if-convert phase.

[Yuri Rumyantsev]

[-- Attachment #1: Type: text/plain, Size: 4189 bytes --]

Jeff,

I prepared another patch that includes test-case as you requested.

Below are answers on your questions.

> First, for the benefit of anyone trying to understand what you're doing, defining what "cd equivalent" means would be >helpful.

I added the following  comment to function:

   fwe call basic blocks bb1 and bb2
   cd-equivalent if they are executed under the same condition.


Is it sufficient?

>So, do you have a case where the dominated_by_p test above is true and is_predicated(bb) returns true as well?  I think this >part of the change is largely responsible for the hack you're doing with having the function scoped static variable join_bb.

I don't have such test-case and I assume that if bb is always
executed, it is not predicated.

I also deleted "join_bb" in my changes.


Is it OK for trunk now.

Thanks.
Yuri.

2014-10-17  Yuri Rumyantsev  <ysrumyan@gmail.com>
gcc/ChangeLog

* tree-if-conv.c (add_to_predicate_list): Check unconditionally
that bb is always executed to early exit. Use predicate of
cd-equivalent block for join blocks if it exists.
(if_convertible_loop_p_1): Recompute POST_DOMINATOR tree.
(tree_if_conversion): Free post-dominance information.

gcc/testsuite/ChangeLog

* gcc/dg/tree-ssa/ifc-cd.c: New test.



2014-10-17 1:16 GMT+04:00 Jeff Law <law@redhat.com>:
> On 10/16/14 05:52, Yuri Rumyantsev wrote:
>>
>> Hi All,
>>
>> Here is a simple enhancement for predicate computation in if-convert
>> phase:
>>
>>   We use notion of cd equivalence to get simpler predicate for
>>       join block, e.g. if join block has 2 predecessors with predicates
>>       p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
>>       p1 & p2 | p1 & !p2.
>>
>> Bootstrap and regression testing did not show any new failures.
>>
>> Is it OK for trunk?
>>
>> gcc/ChangeLog
>> 2014-10-16  Yuri Rumyantsev<ysrumyan@gmail.com>
>>
>> * tree-if-conv.c (add_to_predicate_list): Check unconditionally
>> that bb is always executed to early exit. Use predicate of
>> cd-equivalent block for join blocks if it exists.
>> (if_convertible_loop_p_1): Recompute POST_DOMINATOR tree.
>> (tree_if_conversion): Free post-dominance information.
>
> First, for the benefit of anyone trying to understand what you're doing,
> defining what "cd equivalent" means would be helpful.
>
>
>>
>>
>> if-conv.patch
>>
>>
>> Index: tree-if-conv.c
>> ===================================================================
>> --- tree-if-conv.c      (revision 216217)
>> +++ tree-if-conv.c      (working copy)
>> @@ -396,25 +396,51 @@
>>   }
>>
>>   /* Add condition NC to the predicate list of basic block BB.  LOOP is
>> -   the loop to be if-converted.  */
>> +   the loop to be if-converted. Use predicate of cd-equivalent block
>> +   for join bb if it exists.  */
>>
>>   static inline void
>>   add_to_predicate_list (struct loop *loop, basic_block bb, tree nc)
>>   {
>>     tree bc, *tp;
>> +  basic_block dom_bb;
>> +  static basic_block join_bb = NULL;
>>
>>     if (is_true_predicate (nc))
>>       return;
>>
>> -  if (!is_predicated (bb))
>> +  /* If dominance tells us this basic block is always executed,
>> +     don't record any predicates for it.  */
>> +  if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
>> +    return;
>
> So, do you have a case where the dominated_by_p test above is true and
> is_predicated(bb) returns true as well?  I think this part of the change is
> largely responsible for the hack you're doing with having the function
> scoped static variable join_bb.
>
>
>
>
>> +
>> +  /* If predicate has been already set up for given bb using
>> cd-equivalent
>> +     block predicate, simply escape.  */
>> +  if (join_bb == bb)
>> +    return;
>
> I *really* dislike the state you're carrying around via join_bb.
>
> ISTM that if you compute that there's an equivalence, then you just set the
> predicate for the equivalent block and the right things would have happened
> if you had not changed the test above.
>
> You also need a testcase.  It doesn't have to be extensive, but at least
> some basic "smoke test" to verify basic operation of this code.  It's
> perfectly fine to scan the debugging dumps for debug output.
>
>
> jeff
>
>

[-- Attachment #2: if-conv.patch.new --]
[-- Type: application/octet-stream, Size: 3145 bytes --]

Index: testsuite/gcc.dg/tree-ssa/ifc-cd.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/ifc-cd.c	(revision 0)
+++ testsuite/gcc.dg/tree-ssa/ifc-cd.c	(working copy)
@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-ifcvt-details -ftree-loop-if-convert-stores" } */
+
+void foo (int *x1, int *x2, int *x3, int *x4, int *y)
+{
+  int i;
+  int a1, a2, a3, b1, b2;
+
+  for (i=0; i<128; i++)
+    {
+      a1 = x1[i];
+      a2 = x2[i];
+      a3 = x3[i];
+      y[i] = 0;
+      if (x4[i] == 0)
+	{
+	  b1 = a1 + 1;
+	  if (a2 > 0)
+	    b1++;
+	  a1++;
+	  if (a3 < 0)
+	    b1--;
+	  y[i] = b1;
+	}
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "Use predicate of bb" 8 "ifcvt" } } */
+/* { dg-final { cleanup-tree-dump "ifcvt" } } */
Index: tree-if-conv.c
===================================================================
--- tree-if-conv.c	(revision 216217)
+++ tree-if-conv.c	(working copy)
@@ -396,25 +396,44 @@
 }
 
 /* Add condition NC to the predicate list of basic block BB.  LOOP is
-   the loop to be if-converted.  */
+   the loop to be if-converted. Use predicate of cd-equivalent block
+   for join bb if it exists: we call basic blocks bb1 and bb2 
+   cd-equivalent if they are executed under the same condition.  */
 
 static inline void
 add_to_predicate_list (struct loop *loop, basic_block bb, tree nc)
 {
   tree bc, *tp;
+  basic_block dom_bb;
 
   if (is_true_predicate (nc))
     return;
 
-  if (!is_predicated (bb))
+  /* If dominance tells us this basic block is always executed,
+     don't record any predicates for it.  */
+  if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
+    return;
+
+  dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
+  /* We use notion of cd equivalence to get simpler predicate for
+     join block, e.g. if join block has 2 predecessors with predicates
+     p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
+     p1 & p2 | p1 & !p2.  */
+  if (dom_bb != loop->header
+      && get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb) == bb)
     {
-      /* If dominance tells us this basic block is always executed, don't
-	 record any predicates for it.  */
-      if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
-	return;
+      gcc_assert (flow_bb_inside_loop_p (loop, dom_bb));
+      bc = bb_predicate (dom_bb);
+      gcc_assert (!is_true_predicate (bc));
+      set_bb_predicate (bb, bc);
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Use predicate of bb#%d for bb#%d\n",
+		 dom_bb->index, bb->index);
+      return;
+    }
 
-      bc = nc;
-    }
+  if (!is_predicated (bb))
+    bc = nc;
   else
     {
       bc = bb_predicate (bb);
@@ -1176,6 +1195,7 @@
     return false;
 
   calculate_dominance_info (CDI_DOMINATORS);
+  calculate_dominance_info (CDI_POST_DOMINATORS);
 
   /* Allow statements that can be handled during if-conversion.  */
   ifc_bbs = get_loop_body_in_if_conv_order (loop);
@@ -2148,6 +2168,7 @@
       free (ifc_bbs);
       ifc_bbs = NULL;
     }
+  free_dominance_info (CDI_POST_DOMINATORS);
 
   return todo;
 }

Re: [PATCH] Simple improvement for predicate computation in if-convert phase.

[Richard Biener]

On Fri, Oct 17, 2014 at 3:08 PM, Yuri Rumyantsev <ysrumyan@gmail.com> wrote:
> Jeff,
>
> I prepared another patch that includes test-case as you requested.
>
> Below are answers on your questions.
>
>> First, for the benefit of anyone trying to understand what you're doing, defining what "cd equivalent" means would be >helpful.
>
> I added the following  comment to function:
>
>    fwe call basic blocks bb1 and bb2
>    cd-equivalent if they are executed under the same condition.
>
>
> Is it sufficient?
>
>>So, do you have a case where the dominated_by_p test above is true and is_predicated(bb) returns true as well?  I think this >part of the change is largely responsible for the hack you're doing with having the function scoped static variable join_bb.
>
> I don't have such test-case and I assume that if bb is always
> executed, it is not predicated.
>
> I also deleted "join_bb" in my changes.
>
>
> Is it OK for trunk now.

Ok.

Thanks,
Richard.

> Thanks.
> Yuri.
>
> 2014-10-17  Yuri Rumyantsev  <ysrumyan@gmail.com>
> gcc/ChangeLog
>
> * tree-if-conv.c (add_to_predicate_list): Check unconditionally
> that bb is always executed to early exit. Use predicate of
> cd-equivalent block for join blocks if it exists.
> (if_convertible_loop_p_1): Recompute POST_DOMINATOR tree.
> (tree_if_conversion): Free post-dominance information.
>
> gcc/testsuite/ChangeLog
>
> * gcc/dg/tree-ssa/ifc-cd.c: New test.
>
>
>
> 2014-10-17 1:16 GMT+04:00 Jeff Law <law@redhat.com>:
>> On 10/16/14 05:52, Yuri Rumyantsev wrote:
>>>
>>> Hi All,
>>>
>>> Here is a simple enhancement for predicate computation in if-convert
>>> phase:
>>>
>>>   We use notion of cd equivalence to get simpler predicate for
>>>       join block, e.g. if join block has 2 predecessors with predicates
>>>       p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
>>>       p1 & p2 | p1 & !p2.
>>>
>>> Bootstrap and regression testing did not show any new failures.
>>>
>>> Is it OK for trunk?
>>>
>>> gcc/ChangeLog
>>> 2014-10-16  Yuri Rumyantsev<ysrumyan@gmail.com>
>>>
>>> * tree-if-conv.c (add_to_predicate_list): Check unconditionally
>>> that bb is always executed to early exit. Use predicate of
>>> cd-equivalent block for join blocks if it exists.
>>> (if_convertible_loop_p_1): Recompute POST_DOMINATOR tree.
>>> (tree_if_conversion): Free post-dominance information.
>>
>> First, for the benefit of anyone trying to understand what you're doing,
>> defining what "cd equivalent" means would be helpful.
>>
>>
>>>
>>>
>>> if-conv.patch
>>>
>>>
>>> Index: tree-if-conv.c
>>> ===================================================================
>>> --- tree-if-conv.c      (revision 216217)
>>> +++ tree-if-conv.c      (working copy)
>>> @@ -396,25 +396,51 @@
>>>   }
>>>
>>>   /* Add condition NC to the predicate list of basic block BB.  LOOP is
>>> -   the loop to be if-converted.  */
>>> +   the loop to be if-converted. Use predicate of cd-equivalent block
>>> +   for join bb if it exists.  */
>>>
>>>   static inline void
>>>   add_to_predicate_list (struct loop *loop, basic_block bb, tree nc)
>>>   {
>>>     tree bc, *tp;
>>> +  basic_block dom_bb;
>>> +  static basic_block join_bb = NULL;
>>>
>>>     if (is_true_predicate (nc))
>>>       return;
>>>
>>> -  if (!is_predicated (bb))
>>> +  /* If dominance tells us this basic block is always executed,
>>> +     don't record any predicates for it.  */
>>> +  if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
>>> +    return;
>>
>> So, do you have a case where the dominated_by_p test above is true and
>> is_predicated(bb) returns true as well?  I think this part of the change is
>> largely responsible for the hack you're doing with having the function
>> scoped static variable join_bb.
>>
>>
>>
>>
>>> +
>>> +  /* If predicate has been already set up for given bb using
>>> cd-equivalent
>>> +     block predicate, simply escape.  */
>>> +  if (join_bb == bb)
>>> +    return;
>>
>> I *really* dislike the state you're carrying around via join_bb.
>>
>> ISTM that if you compute that there's an equivalence, then you just set the
>> predicate for the equivalent block and the right things would have happened
>> if you had not changed the test above.
>>
>> You also need a testcase.  It doesn't have to be extensive, but at least
>> some basic "smoke test" to verify basic operation of this code.  It's
>> perfectly fine to scan the debugging dumps for debug output.
>>
>>
>> jeff
>>
>>

Re: [PATCH] Simple improvement for predicate computation in if-convert phase.

[H.J. Lu]

On Fri, Oct 17, 2014 at 6:08 AM, Yuri Rumyantsev <ysrumyan@gmail.com> wrote:
> Jeff,
>
> I prepared another patch that includes test-case as you requested.
>
> Below are answers on your questions.
>
>> First, for the benefit of anyone trying to understand what you're doing, defining what "cd equivalent" means would be >helpful.
>
> I added the following  comment to function:
>
>    fwe call basic blocks bb1 and bb2
>    cd-equivalent if they are executed under the same condition.
>
>
> Is it sufficient?
>
>>So, do you have a case where the dominated_by_p test above is true and is_predicated(bb) returns true as well?  I think this >part of the change is largely responsible for the hack you're doing with having the function scoped static variable join_bb.
>
> I don't have such test-case and I assume that if bb is always
> executed, it is not predicated.
>
> I also deleted "join_bb" in my changes.
>
>
> Is it OK for trunk now.
>
> Thanks.
> Yuri.
>
> 2014-10-17  Yuri Rumyantsev  <ysrumyan@gmail.com>
> gcc/ChangeLog
>
> * tree-if-conv.c (add_to_predicate_list): Check unconditionally
> that bb is always executed to early exit. Use predicate of
> cd-equivalent block for join blocks if it exists.
> (if_convertible_loop_p_1): Recompute POST_DOMINATOR tree.
> (tree_if_conversion): Free post-dominance information.
>
> gcc/testsuite/ChangeLog
>
> * gcc/dg/tree-ssa/ifc-cd.c: New test.
>

This caused:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63941


-- 
H.J.