[PATCH] Fix PR34263: Cleaning up latch blocks (re-submission)

[PATCH] Fix PR34263: Cleaning up latch blocks (re-submission)

[Revital1 Eres]

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


Hello,

I integrated your comments in the attached patch and added a testcase.
The patch was tested (bootstrap and regtest) with -O2 on ppc64-linux
and x86_64-linux (including the new testcase).

OK for mainline?

Thanks,
Revital


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

        PR tree-optimization/34263
        * tree-outof-ssa.c (process_single_block_loop_latch,.
        contains_tree_r): New functions.
        (analyze_edges_for_bb): Call process_single_block_loop_latch
        function to empty single-basic-block latch block if possible..

testsuite:

        PR tree-optimization/34263
        * gcc.dg/pr34263.c:  New testcase.

(See attached file: patch_cleanup_latch_17_12.txt)(See attached file:
pr34263.c.txt)

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

Index: tree-outof-ssa.c
===================================================================
--- tree-outof-ssa.c	(revision 130930)
+++ tree-outof-ssa.c	(working copy)
@@ -871,7 +871,175 @@
   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;
+}
 
+/* A threshold for the number of insns contained in the latch block.
+   It is used to prevent blowing the loop with too many copies from
+   the latch.  */
+#define MAX_STMTS_IN_LATCH 2
+
+/* Return TRUE if the stmts on SINGLE-EDGE can be moved to the
+   body of the loop.  This should be permitted only if SINGLE-EDGE is a
+   single-basic-block latch edge and thus cleaning the latch will help
+   to create a single-basic-block loop.  Otherwise return FALSE.  */
+
+static bool
+process_single_block_loop_latch (edge single_edge)
+{
+  bool before = false;
+  tree stmts;
+  basic_block b_exit, b_pheader, b_loop = single_edge->src;
+  edge_iterator ei;
+  edge e;
+  block_stmt_iterator bsi, bsi_exit;
+  tree_stmt_iterator tsi;
+  tree expr, stmt;
+  unsigned int count = 0;
+
+  if (single_edge == NULL || (single_edge->dest != single_edge->src)
+      || (EDGE_COUNT (b_loop->succs) != 2)
+      || (EDGE_COUNT (b_loop->preds) != 2))
+    return false;
+
+  /* Get the stmts on the latch edge.  */
+  stmts = PENDING_STMT (single_edge);
+
+  /* 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))
+    return false;
+
+  /* Find the predecessor edge which is not the latch edge.  */
+  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)
+    return false;
+
+  bsi_exit = bsi_after_labels (b_exit);
+
+  /* Get the last stmt in the loop body.  */
+  bsi = bsi_last (single_edge->src);
+  stmt = bsi_stmt (bsi);
+
+  if (TREE_CODE (stmt) == COND_EXPR)
+    {
+      expr = COND_EXPR_COND (stmt);
+      /* If the loop block ends with a condition insert the new stmts
+         right before it.  */
+      before = true;
+    }
+  /* Iterate over the insns on the latch and count them.  */
+  for (tsi = tsi_start (stmts); !tsi_end_p (tsi); tsi_next (&tsi))
+    {
+      tree stmt1 = tsi_stmt (tsi);
+      tree var;
+
+      count++;
+      if (TREE_CODE (stmt) == COND_EXPR)
+	{
+          /* Check that the condition does not contain any new definition
+             created in the latch as the stmts from the latch intended
+             to precede it.  */
+	  if (TREE_CODE (stmt1) != GIMPLE_MODIFY_STMT)
+	    {
+	      print_generic_stmt (dump_file, stmt1, TDF_VOPS);
+	      return false;
+	    }
+	  var = GIMPLE_STMT_OPERAND (stmt1, 0);
+	  if (TREE_THIS_VOLATILE (var)
+	      || TYPE_VOLATILE (TREE_TYPE (var))
+	      || walk_tree (&expr, contains_tree_r, var, NULL))
+	    return false;
+	}
+    }
+  /* Check that the latch does not contain more than MAX_STMTS_IN_LATCH
+     insns.  The purpose of this restriction is to prevent blowing the
+     loop with too many copies from the latch.  */
+  if (count > MAX_STMTS_IN_LATCH)
+    return false;
+
+  /* Apply the transformation - clean up the latch block:  
+    
+     var = something; 
+     L1:
+     x1 = expr;
+     if (cond) goto L2 else goto L3;
+     L2:
+     var = x1;
+     goto L1
+     L3:
+     ...
+
+     ==>
+
+     var = something;
+     L1:
+     x1 = expr;
+     tmp_var = var;
+     var = x1;
+     if (cond) goto L1 else goto L2;
+     L2:
+     var = tmp_var;
+     ... 
+    */
+  for (tsi = tsi_start (stmts); !tsi_end_p (tsi); tsi_next (&tsi))
+    {
+      tree stmt1 = tsi_stmt (tsi);
+      tree var, tmp_var, copy;
+
+      /* Create a new variable to load back the value of var in case
+         we exit the loop.  */
+      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;
+  /* Insert the new stmts to the loop body.  */
+  if (before)
+    bsi_insert_before (&bsi, stmts, BSI_NEW_STMT);
+  else
+    bsi_insert_after (&bsi, stmts, BSI_NEW_STMT);
+
+  if (dump_file)
+     fprintf (dump_file,
+              "\nCleaned-up latch block of loop with single BB: %d\n\n",
+              single_edge->dest->index);
+
+  return true;
+}
+
 /* 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 +1112,12 @@
   if (count < 2)
     {
       if (single_edge)
-        bsi_commit_one_edge_insert (single_edge, NULL);
+      {
+       /* 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);
+      }
       return;
     }
 

[-- Attachment #3: pr34263.c.txt --]
[-- Type: text/plain, Size: 1104 bytes --]

/* { dg-do run } */
/* { dg-options "-O2 -fdump-tree-optimized" } */
/* Same test as 990128-1.c.  */

extern int printf (const char *,...);
extern void abort (void);

struct s { struct s *n; } *p;
struct s ss;
#define MAX     10
struct s sss[MAX];
int count = 0;

void sub( struct s *p, struct s **pp );
int look( struct s *p, struct s **pp );

main()
{
    struct s *pp;
    struct s *next;
    int i;

    p = &ss;
    next = p;
    for ( i = 0; i < MAX; i++ ) {
        next->n = &sss[i];
        next = next->n;
    }
    next->n = 0;

    sub( p, &pp );
    if (count != MAX+2)
      abort ();

    return( 0 );
}

void sub( struct s *p, struct s **pp )
{
   for ( ; look( p, pp ); ) {
        if ( p )
            p = p->n;
        else
            break;
   }
}

int look( struct s *p, struct s **pp )
{
    for ( ; p; p = p->n )
        ;
    *pp = p;
    count++;
    return( 1 );
}

/* { dg-final { scan-tree-dump "Cleaned-up latch block of loop with single BB" "optimized" } } */
/* { dg-final { cleanup-tree-dump "optimized" } } */

Re: [PATCH] Fix PR34263: Cleaning up latch blocks (re-submission)

[Diego Novillo]

On 12/17/07 04:29, Revital1 Eres wrote:

> 2007-12-17  Andrew Pinski  <andrew_pinski@playstation.sony.com>
>             Mircea Namolaru  <namolaru@il.ibm.com>
>             Vladimir Yanovsky  <yanov@il.ibm.com>>
> 
>         PR tree-optimization/34263
>         * tree-outof-ssa.c (process_single_block_loop_latch,.
>         contains_tree_r): New functions.
>         (analyze_edges_for_bb): Call process_single_block_loop_latch
>         function to empty single-basic-block latch block if possible..
> 
> testsuite:
> 
>         PR tree-optimization/34263
>         * gcc.dg/pr34263.c:  New testcase.

OK.

Diego.

Re: [PATCH] Fix PR34263: Cleaning up latch blocks (re-submission)

[Revital1 Eres]

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

Hello,

Following our off-line correspondence, I intend to commit the attached
version of the patch (if there are no objections); which is a sightly
different version then the one that was originally posted.  In the current
version we quit if the loop body does not end with a condition stmt.
(it seems like a reasonable assumption, giving the fact this is the last
stmt of the loop body).

Tested on powerpc64-linux and on x86_64-linux.

Thanks,
Revital

2008-01-04  Andrew Pinski  <andrew_pinski@playstation.sony.com>
            Mircea Namolaru  <namolaru@il.ibm.com>
            Vladimir Yanovsky  <yanov@il.ibm.com>>

        PR tree-optimization/34263
        * tree-outof-ssa.c (process_single_block_loop_latch,
        contains_tree_r): New functions.
        (analyze_edges_for_bb): Call process_single_block_loop_latch
        function to empty single-basic-block latch block if possible.

testsuite:

        PR tree-optimization/34263
        * gcc.dg/pr34263.c:  New testcase.


(See attached file: pr34263.c.txt)(See attached file: patch_24_12.txt)

[-- Attachment #2: pr34263.c.txt --]
[-- Type: text/plain, Size: 1104 bytes --]

/* { dg-do run } */
/* { dg-options "-O2 -fdump-tree-optimized" } */
/* Same test as 990128-1.c.  */

extern int printf (const char *,...);
extern void abort (void);

struct s { struct s *n; } *p;
struct s ss;
#define MAX     10
struct s sss[MAX];
int count = 0;

void sub( struct s *p, struct s **pp );
int look( struct s *p, struct s **pp );

main()
{
    struct s *pp;
    struct s *next;
    int i;

    p = &ss;
    next = p;
    for ( i = 0; i < MAX; i++ ) {
        next->n = &sss[i];
        next = next->n;
    }
    next->n = 0;

    sub( p, &pp );
    if (count != MAX+2)
      abort ();

    return( 0 );
}

void sub( struct s *p, struct s **pp )
{
   for ( ; look( p, pp ); ) {
        if ( p )
            p = p->n;
        else
            break;
   }
}

int look( struct s *p, struct s **pp )
{
    for ( ; p; p = p->n )
        ;
    *pp = p;
    count++;
    return( 1 );
}

/* { dg-final { scan-tree-dump "Cleaned-up latch block of loop with single BB" "optimized" } } */
/* { dg-final { cleanup-tree-dump "optimized" } } */


[-- Attachment #3: patch_24_12.txt --]
[-- Type: text/plain, Size: 5423 bytes --]

Index: tree-outof-ssa.c
===================================================================
--- tree-outof-ssa.c	(revision 130931)
+++ tree-outof-ssa.c	(working copy)
@@ -871,7 +871,159 @@
   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;
+}
 
+/* A threshold for the number of insns contained in the latch block.
+   It is used to prevent blowing the loop with too many copies from
+   the latch.  */
+#define MAX_STMTS_IN_LATCH 2
+
+/* Return TRUE if the stmts on SINGLE-EDGE can be moved to the
+   body of the loop.  This should be permitted only if SINGLE-EDGE is a
+   single-basic-block latch edge and thus cleaning the latch will help
+   to create a single-basic-block loop.  Otherwise return FALSE.  */
+
+static bool
+process_single_block_loop_latch (edge single_edge)
+{
+  tree stmts;
+  basic_block b_exit, b_pheader, b_loop = single_edge->src;
+  edge_iterator ei;
+  edge e;
+  block_stmt_iterator bsi, bsi_exit;
+  tree_stmt_iterator tsi;
+  tree expr, stmt;
+  unsigned int count = 0;
+
+  if (single_edge == NULL || (single_edge->dest != single_edge->src)
+      || (EDGE_COUNT (b_loop->succs) != 2)
+      || (EDGE_COUNT (b_loop->preds) != 2))
+    return false;
+
+  /* Get the stmts on the latch edge.  */
+  stmts = PENDING_STMT (single_edge);
+
+  /* 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))
+    return false;
+
+  /* Find the predecessor edge which is not the latch edge.  */
+  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)
+    return false;
+
+  bsi_exit = bsi_after_labels (b_exit);
+
+  /* Get the last stmt in the loop body.  */
+  bsi = bsi_last (single_edge->src);
+  stmt = bsi_stmt (bsi);
+
+  if (TREE_CODE (stmt) != COND_EXPR)
+    return false;
+
+  expr = COND_EXPR_COND (stmt);
+  /* Iterate over the insns on the latch and count them.  */
+  for (tsi = tsi_start (stmts); !tsi_end_p (tsi); tsi_next (&tsi))
+    {
+      tree stmt1 = tsi_stmt (tsi);
+      tree var;
+
+      count++;
+      /* Check that the condition does not contain any new definition
+         created in the latch as the stmts from the latch intended
+         to precede it.  */
+      if (TREE_CODE (stmt1) != GIMPLE_MODIFY_STMT)
+        return false;
+      var = GIMPLE_STMT_OPERAND (stmt1, 0);
+      if (TREE_THIS_VOLATILE (var)
+	  || TYPE_VOLATILE (TREE_TYPE (var))
+	  || walk_tree (&expr, contains_tree_r, var, NULL))
+	return false;
+    }
+  /* Check that the latch does not contain more than MAX_STMTS_IN_LATCH
+     insns.  The purpose of this restriction is to prevent blowing the
+     loop with too many copies from the latch.  */
+  if (count > MAX_STMTS_IN_LATCH)
+    return false;
+
+  /* Apply the transformation - clean up the latch block:  
+
+     var = something; 
+     L1:
+     x1 = expr;
+     if (cond) goto L2 else goto L3;
+     L2:
+     var = x1;
+     goto L1
+     L3:
+     ...
+
+     ==>
+
+     var = something;
+     L1:
+     x1 = expr;
+     tmp_var = var;
+     var = x1;
+     if (cond) goto L1 else goto L2;
+     L2:
+     var = tmp_var;
+     ... 
+   */
+  for (tsi = tsi_start (stmts); !tsi_end_p (tsi); tsi_next (&tsi))
+    {
+      tree stmt1 = tsi_stmt (tsi);
+      tree var, tmp_var, copy;
+
+      /* Create a new variable to load back the value of var in case
+         we exit the loop.  */
+      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);
+      bsi_insert_before (&bsi, copy, BSI_SAME_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;
+  /* Insert the new stmts to the loop body.  */
+  bsi_insert_before (&bsi, stmts, BSI_NEW_STMT);
+
+  if (dump_file)
+    fprintf (dump_file,
+	     "\nCleaned-up latch block of loop with single BB: %d\n\n",
+	     single_edge->dest->index);
+
+  return true;
+}
+
 /* 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 +1096,12 @@
   if (count < 2)
     {
       if (single_edge)
-        bsi_commit_one_edge_insert (single_edge, NULL);
+      {
+       /* 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);
+      }
       return;
     }