re:[PATCH] Fix PR34263: Cleaning up latch blocks

re:[PATCH] Fix PR34263: Cleaning up latch blocks

[Andrew MacLeod]

 > Following the RFC message
 > (http://gcc.gnu.org/ml/gcc/2007-12/msg00015.html), this patch tries
 > to clean up latch blocks in the out-of-ssa phase for the purpose of
 > restoring single-basic-block loops. This can be helpful not only in the
 > SMS perspective. Given the fact we are in stage 3 I can alternatively
 > address this inside the SMS (and not in out-of-ssa).

 > The patch was successfully tested a week ago (when I posted the RFC
 > message) on ppc64 and I am re-checking it now to verify it is still OK.

 > OK for mainline once testing completes?

So If I get this right, This patch addresses extra blocks that are 
created in circumstances like:

BB6:
a_2 = PHI <a_3(4), a_4(6)>
<...>
a_4 = expr
if (x) then BB6 else BB7
BB7:

which we currently translate to something like:

a_2 = a_3
BB6:
<...>
a_4 = expr
if (x) then BB14 else BB7
BB14:
a_2 = a_4
goto BB6:
BB7:

and with this change, we would then generate:
a_2 = a_3
BB6:
<...>
a_4 = expr
a_9 = a_2
a_2 = a_4
if (x) then BB6 else BB7
BB7:
a_2 = a_9

Effectively stashing the value of a_2 to load back in the case where we 
exit. Is this right? (except it is actually working on the coalesced 
root variables, not the actual SSA_NAMES)

Seems to me there is an older PR that involves a similar situation too , 
but I dont recall it.

The patch looks fine, except I would ask that all this logic be lifted 
out to a function which returns TRUE if it is a single block loop and 
performs the work.   So the code looks something like:

if (single_edge)
  {
    /* Add stmts to the edge unless processed specially as a 
single-block loop latch edge.  */
    if (!process_single_block_loop_latch (single_edge))   
      bsi_commit_one_edge_insert (single_edge, NULL);
    }

And a few extra comments in the body would help to read it too, just 
simple things  like:
 

               /* Find the successor edge which is not the latch edge.  */
+              FOR_EACH_EDGE (e, ei, b_loop->succs)
+                if (e->dest != b_loop)
+                  break;
+
+              b_exit = e->dest;
+
               /* Check that the exit block has only the loop as a predecessor, and that there
                  are no pending stmts on that edge as well.  */ 
+              if (EDGE_COUNT (b_exit->preds) != 1 || PENDING_STMT (e))
+                do_it = false;
+
               /* Find the predecessor edge which is used for loop entry.  */ 
+              FOR_EACH_EDGE (e, ei, b_loop->preds)
+                if (e->src != b_loop)
+                  break;
+


It just makes it a little easier to read.

Should there be some kind of limit to the number of copies being 
inserted? Ie, if there are 10 copies being inserted on the edge, I would 
think 10 extra copies in the loop would tend to start adding up and 
offset whatever gain you might get. 

As long as there isn't disagreement on whether the extra copies in and 
out of the loop are a problem, the patch istself is OK.

Andrew

re:[PATCH] Fix PR34263: Cleaning up latch blocks

[Revital1 Eres]

Hello,

Thanks for your reply!

> Effectively stashing the value of a_2 to load back in the case where we
> exit. Is this right? (except it is actually working on the coalesced
> root variables, not the actual SSA_NAMES)

Yes, that's correct.

> Seems to me there is an older PR that involves a similar situation too ,
> but I dont recall it.

It might be PR19038, which this patch was originally taken from.

> Should there be some kind of limit to the number of copies being
> inserted? Ie, if there are 10 copies being inserted on the edge, I would
> think 10 extra copies in the loop would tend to start adding up and
> offset whatever gain you might get.

That sounds reasonable, I can add a default number to consider only small
latches. (and maybe add a new --param option to tune it?)

> As long as there isn't disagreement on whether the extra copies in and
> out of the loop are a problem, the patch istself is OK.

I will address your comments and re-submit the patch.

Thanks,
Revital

Re: [PATCH] Fix PR34263: Cleaning up latch blocks

[Andrew MacLeod]

Revital1 Eres wrote:
>
>> Should there be some kind of limit to the number of copies being
>> inserted? Ie, if there are 10 copies being inserted on the edge, I would
>> think 10 extra copies in the loop would tend to start adding up and
>> offset whatever gain you might get.
>>     
>
> That sounds reasonable, I can add a default number to consider only small
> latches. (and maybe add a new --param option to tune it?)
>
>   
I dont know if we need another --param or not, I'd be just as content to 
start with a small guess. I would think most of the cases you see that 
matter have 1 or 2 stmts?

Andrew

Re: [PATCH] Fix PR34263: Cleaning up latch blocks

[Revital1 Eres]

Andrew MacLeod <amacleod@redhat.com> wrote on 14/12/2007 16:13:15:

> Revital1 Eres wrote:
> >
> >> Should there be some kind of limit to the number of copies being
> >> inserted? Ie, if there are 10 copies being inserted on the edge, I
would
> >> think 10 extra copies in the loop would tend to start adding up and
> >> offset whatever gain you might get.
> >>
> >
> > That sounds reasonable, I can add a default number to consider only
small
> > latches. (and maybe add a new --param option to tune it?)
> >
> >
> I dont know if we need another --param or not, I'd be just as content to
> start with a small guess. I would think most of the cases you see that
> matter have 1 or 2 stmts?

Yes, I'll add such restriction.

Thanks,
Revital

[PATCH] Fix PR34263: Cleaning up latch blocks

[Revital1 Eres]

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


Hello,

Following the RFC message
(http://gcc.gnu.org/ml/gcc/2007-12/msg00015.html), this patch tries
to clean up latch blocks in the out-of-ssa phase for the purpose of
restoring single-basic-block loops.  This can be helpful not only in the
SMS perspective. Given the fact we are in stage 3 I can alternatively
address this inside the SMS (and not in out-of-ssa).

The patch was successfully tested a week ago (when I posted the RFC
message) on ppc64 and I am re-checking it now to verify it is still OK.

OK for mainline once testing completes?

:ADDPATCH <tree-opt>:

Thanks,
Revital


      2007-12-06  Andrew Pinski  <andrew_pinski@playstation.sony.com>
            Mircea Namolaru  <namolaru@il.ibm.com>
            Vladimir Yanovsky  <yanov@il.ibm.com>>

        * tree-outof-ssa.c (analyze_edges_for_bb): Try to empty the
        latch bloack of a single-basic-block loop.
        (contains_tree_r): New function.

(See attached file: patch_empty_latch_6_12.txt)

[-- Attachment #2: patch_empty_latch_6_12.txt --]
[-- Type: text/plain, Size: 5044 bytes --]

Index: tree-outof-ssa.c
===================================================================
--- tree-outof-ssa.c	(revision 130626)
+++ tree-outof-ssa.c	(working copy)
@@ -871,6 +871,20 @@
   BITMAP_FREE (leader_has_match);
 }
 
+/* A helper function to be called via walk_tree.  Return DATA if it is
+  contained in subtree TP.  */
+ 
+static tree
+contains_tree_r (tree *tp, int *walk_subtrees, void *data)
+{
+  if (*tp == data)
+    {
+      *walk_subtrees = 0;
+      return data;
+    }
+  else
+    return NULL_TREE;
+}
 
 /* Look at all the incoming edges to block BB, and decide where the best place
    to insert the stmts on each edge are, and perform those insertions.  */
@@ -944,7 +958,112 @@
   if (count < 2)
     {
       if (single_edge)
-        bsi_commit_one_edge_insert (single_edge, NULL);
+        {
+          /* Loop back edges are special and should be handled that way.  
+             Try to empty the latch of a single-basic-block loop.  */
+          if (single_edge->dest == single_edge->src)
+            {
+              bool do_it = true;
+              bool before = false;
+              tree stmts = PENDING_STMT (single_edge);
+              basic_block b_exit, b_pheader, b_loop = single_edge->src;
+              edge_iterator ei;
+              edge e;
+              block_stmt_iterator bsi_exit;
+
+              if (EDGE_COUNT (b_loop->succs) != 2
+                  || EDGE_COUNT (b_loop->preds) != 2)
+                do_it = false;
+
+              FOR_EACH_EDGE (e, ei, b_loop->succs)
+                if (e->dest != b_loop)
+                  break;
+
+              b_exit = e->dest;
+
+              if (EDGE_COUNT (b_exit->preds) != 1 || PENDING_STMT (e))
+                do_it = false;
+
+              FOR_EACH_EDGE (e, ei, b_loop->preds)
+                if (e->src != b_loop)
+                  break;
+
+              b_pheader = e->src;
+
+              if (b_exit == b_pheader
+                  || b_exit == b_loop || b_pheader == b_loop)
+                do_it = false;
+
+              bsi_exit = bsi_after_labels (b_exit);
+              bsi = bsi_last (single_edge->src);
+              stmt = bsi_stmt (bsi);
+
+              /* Check if it is OK to do it.  */
+              if (TREE_CODE (stmt) == COND_EXPR)
+                {
+                  tree expr = COND_EXPR_COND (stmt);
+                  tree_stmt_iterator tsi;
+                  before = true;
+
+                  for (tsi = tsi_start (stmts); !tsi_end_p (tsi);
+                       tsi_next (&tsi))
+                    {
+                      tree stmt1 = tsi_stmt (tsi);
+                      tree var;
+
+                      if (TREE_CODE (stmt1) != GIMPLE_MODIFY_STMT)
+                        {
+                          print_generic_stmt (dump_file, stmt1, TDF_VOPS);
+                          do_it = false;
+                          break;
+                        }
+                      var = GIMPLE_STMT_OPERAND (stmt1, 0);
+                      if (TREE_THIS_VOLATILE (var) 
+                          || TYPE_VOLATILE (TREE_TYPE (var))
+                          || walk_tree (&expr, contains_tree_r, var, NULL))
+                        {
+                          do_it = false;
+                          break;
+                        }
+                    }
+                }
+              /* Insert the statements right before the condition.  */
+              if (do_it)
+                {
+                  tree_stmt_iterator tsi;
+
+                  for (tsi = tsi_start (stmts); !tsi_end_p (tsi);
+                       tsi_next (&tsi))
+                    {
+                      tree stmt1 = tsi_stmt (tsi);
+                      tree var, tmp_var, copy;
+
+                      var = GIMPLE_STMT_OPERAND (stmt1, 0);
+                      tmp_var = create_temp (var);
+                      copy =
+                        build2 (GIMPLE_MODIFY_STMT, TREE_TYPE (tmp_var),
+                                tmp_var, var);
+                      set_is_used (tmp_var);
+                      if (before)
+                        bsi_insert_before (&bsi, copy, BSI_SAME_STMT);
+                      else
+                        bsi_insert_after (&bsi, copy, BSI_NEW_STMT);
+                      copy =
+                        build2 (GIMPLE_MODIFY_STMT, TREE_TYPE (tmp_var), var,
+                                tmp_var);
+                      bsi_insert_before (&bsi_exit, copy, BSI_SAME_STMT);
+
+                    }
+                  PENDING_STMT (single_edge) = 0;
+                  if (before)
+                    bsi_insert_before (&bsi, stmts, BSI_NEW_STMT);
+                  else
+                    bsi_insert_after (&bsi, stmts, BSI_NEW_STMT);
+                  return;
+                }
+            }
+          bsi_commit_one_edge_insert (single_edge, NULL);
+        }
       return;
     }