Patchwork [trans-mem] PR47690: redirect recursive calls in a clone correctly

login
register
mail settings
Submitter Aldy Hernandez
Date Feb. 15, 2011, 6:34 p.m.
Message ID <4D5AC74B.3090506@redhat.com>
Download mbox | patch
Permalink /patch/83278/
State New
Headers show

Comments

Aldy Hernandez - Feb. 15, 2011, 6:34 p.m.
Sorry, mailer problems.  Now with patch.
PR 47690
	* trans-mem.c (ipa_tm_transform_calls_1): Abstract edge
	redirection logic...
	(ipa_tm_transform_calls_redirect): ...here.  Redirect recursive
	clone calls even if we have scanned past the end of the
	transaction.
	(call_past_tm_end): New.
	(ipa_tm_scan_calls_transaction): Make sure callee is really inside
	a transaction.
	(ipa_tm_note_irrevocable): Same.
Richard Henderson - Feb. 15, 2011, 7:24 p.m.
On 02/15/2011 10:34 AM, Aldy Hernandez wrote:
> +/* Find CALL in the BB in which it appears.  Return TRUE if the call
> +   appears beyond one of the built-ins that end a transaction.  */
> +static bool
> +call_past_tm_end (gimple call)
> +{
> +  basic_block bb = gimple_bb (call);
> +  gimple_stmt_iterator gsi = gsi_start_bb (bb);
> +  bool past_tm_end = false;
> +
> +  /* We're only interested in honest to good calls.  */
> +  if (is_transactional_stmt (call))
> +    return false;
> +
> +  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> +    {
> +      gimple stmt = gsi_stmt (gsi);
> +      tree fndecl;
> +
> +      if (gimple_code (stmt) == GIMPLE_CALL)
> +	{
> +	  fndecl = gimple_call_fndecl (stmt);
> +	  if (fndecl && is_tm_ending_fndecl (fndecl))
> +	    past_tm_end = true;
> +	}
> +      if (stmt == call)
> +	return past_tm_end;
> +    }
> +  gcc_unreachable ();
> +}
> +
>  /* Scan all calls in NODE that are within a transaction region,
>     and push the resulting nodes into the callee queue.  */
>  
> @@ -3526,6 +3556,12 @@ ipa_tm_scan_calls_transaction (struct cg
>  	if (is_tm_pure_call (e->call_stmt))
>  	  continue;
>  
> +	/* The callee can be in a transactional region, but beyond a
> +	   built-in forcing a transaction end.  If so, that doesn't
> +	   count as inside of a transaction.  */
> +	if (call_past_tm_end (e->call_stmt))
> +	  continue;

Hum.  Quadratic.

This is fallout from Andrew's patch that got rid of the in-transaction
bit on the calls.  We had previously checked is_tm_ending_fndecl when
setting that bit, so these calls had been known to be outside of the
transaction.

There are two possible fixes for this, both of which avoid the O(N**2)
bit above:

(1) Rearrange the function such that we iterate over the blocks in the
    bitmap and the stmts in the blocks, rather than over the callees in
    the function.  While we're examining each stmt, check is_tm_ending_fndecl
    and stop processing the block.

(2) Make is_tm_ending_fndecl imply is_ctrl_altering_stmt to force the 
    basic block to end.  We're eventually going to split the block there
    during pass_tm_edges, but before that we don't have another edge to
    drop in.  IF there's no other fallout from this change, it's probably
    the easiest change to make.  I'm not sure why else I wouldn't have 
    done this in the first place, except for the lack-of-an-edge thing.


r~
Aldy Hernandez - Feb. 15, 2011, 7:31 p.m.
> (2) Make is_tm_ending_fndecl imply is_ctrl_altering_stmt to force the
>      basic block to end.  We're eventually going to split the block there
>      during pass_tm_edges, but before that we don't have another edge to
>      drop in.  IF there's no other fallout from this change, it's probably
>      the easiest change to make.  I'm not sure why else I wouldn't have
>      done this in the first place, except for the lack-of-an-edge thing.

This was my first idea, but I didn't pursue it, thinking you would've 
had a reason not to split the BB in the first place.

I'll play around with this a bit and report back.

Thanks for the prompt review.

Patch

Index: testsuite/gcc.dg/tm/pr47690.c
===================================================================
--- testsuite/gcc.dg/tm/pr47690.c	(revision 0)
+++ testsuite/gcc.dg/tm/pr47690.c	(revision 0)
@@ -0,0 +1,22 @@ 
+/* { dg-do compile } */
+/* { dg-options "-fgnu-tm" } */
+
+int george;
+
+void q1()
+{
+  __transaction [[atomic]] {
+      george=999;
+  }
+  q1();
+}
+
+__attribute__((transaction_callable))
+void q2()
+{
+  __transaction [[atomic]]
+    {
+      george=999;
+    }
+  q2();
+}
Index: trans-mem.c
===================================================================
--- trans-mem.c	(revision 170142)
+++ trans-mem.c	(working copy)
@@ -3507,6 +3507,36 @@  maybe_push_queue (struct cgraph_node *no
     }
 }
 
+/* Find CALL in the BB in which it appears.  Return TRUE if the call
+   appears beyond one of the built-ins that end a transaction.  */
+static bool
+call_past_tm_end (gimple call)
+{
+  basic_block bb = gimple_bb (call);
+  gimple_stmt_iterator gsi = gsi_start_bb (bb);
+  bool past_tm_end = false;
+
+  /* We're only interested in honest to good calls.  */
+  if (is_transactional_stmt (call))
+    return false;
+
+  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gimple stmt = gsi_stmt (gsi);
+      tree fndecl;
+
+      if (gimple_code (stmt) == GIMPLE_CALL)
+	{
+	  fndecl = gimple_call_fndecl (stmt);
+	  if (fndecl && is_tm_ending_fndecl (fndecl))
+	    past_tm_end = true;
+	}
+      if (stmt == call)
+	return past_tm_end;
+    }
+  gcc_unreachable ();
+}
+
 /* Scan all calls in NODE that are within a transaction region,
    and push the resulting nodes into the callee queue.  */
 
@@ -3526,6 +3556,12 @@  ipa_tm_scan_calls_transaction (struct cg
 	if (is_tm_pure_call (e->call_stmt))
 	  continue;
 
+	/* The callee can be in a transactional region, but beyond a
+	   built-in forcing a transaction end.  If so, that doesn't
+	   count as inside of a transaction.  */
+	if (call_past_tm_end (e->call_stmt))
+	  continue;
+
 	replacement = find_tm_replacement_function (e->callee->decl);
 	if (replacement)
 	  continue;
@@ -3587,7 +3623,8 @@  ipa_tm_note_irrevocable (struct cgraph_n
 
       gcc_assert (gimple_bb (e->call_stmt) != NULL);
       /* Check if the callee is in a transactional region. */ 
-      if (bitmap_bit_p (bb_in_TM_region, gimple_bb (e->call_stmt)->index))
+      if (bitmap_bit_p (bb_in_TM_region, gimple_bb (e->call_stmt)->index)
+	  && !call_past_tm_end (e->call_stmt))
 	d->want_irr_scan_normal = true;
       maybe_push_queue (e->caller, worklist_p, &d->in_worklist);
     }
@@ -4279,6 +4316,89 @@  ipa_tm_insert_gettmclone_call (struct cg
   return true;
 }
 
+/* Helper function for ipa_tm_transform_calls*.  Given a call
+   statement in GSI which resides inside transaction REGION, redirect
+   the call to either its wrapper function, or its clone.
+   PAST_TM_ENDING_STMT is true if we have scanned past the end of one
+   of the TM ending statements.  */
+
+static void
+ipa_tm_transform_calls_redirect (struct cgraph_node *node,
+				 struct tm_region *region,
+				 gimple_stmt_iterator *gsi,
+				 bool past_tm_ending_stmt,
+				 bool *need_ssa_rename_p)
+{
+  gimple stmt = gsi_stmt (*gsi);
+  struct cgraph_node *new_node;
+  struct cgraph_edge *e = cgraph_edge (node, stmt);
+  tree fndecl = gimple_call_fndecl (stmt);
+
+  /* We only redirect calls inside of a transaction, with the
+     exception of recursive calls to the clone itself.  We must make
+     sure recursive calls in a cloned function get redirected to the
+     clone itself, not the original function.  So... bail unless we're
+     inside a transaction or we're handling this special case.  */
+  if (past_tm_ending_stmt
+      && (e->caller != e->callee
+	  || !DECL_IS_TM_CLONE (e->callee->decl)))
+    return;
+
+  /* For a recursive call to the clone, call the clone directly.  No
+     need to go through the runtime...  */
+  if (e->caller == e->callee
+      && DECL_IS_TM_CLONE (e->callee->decl))
+    fndecl = e->callee->decl;
+  else
+    {
+      /* ...otherwise start looking for a replacement.  */
+      fndecl = find_tm_replacement_function (fndecl);
+    }
+
+  /* If there is a replacement, use it, otherwise use the clone.  */
+  if (fndecl)
+    {
+      new_node = cgraph_node (fndecl);
+
+      /* ??? Mark all transaction_wrap functions tm_may_enter_irr.
+
+	 We can't do this earlier in record_tm_replacement because
+	 cgraph_remove_unreachable_nodes is called before we inject
+	 references to the node.  Further, we can't do this in some
+	 nice central place in ipa_tm_execute because we don't have
+	 the exact list of wrapper functions that would be used.
+	 Marking more wrappers than necessary results in the creation
+	 of unnecessary cgraph_nodes, which can cause some of the
+	 other IPA passes to crash.
+
+	 We do need to mark these nodes so that we get the proper
+	 result in expand_call_tm.  */
+      new_node->local.tm_may_enter_irr = 1;
+    }
+  else
+    {
+      struct tm_ipa_cg_data *d = get_cg_data (e->callee);
+      new_node = d->clone;
+
+      /* As we've already skipped pure calls and appropriate builtins,
+	 and we've already marked irrevocable blocks, if we can't come
+	 up with a static replacement, then ask the runtime.  */
+      if (new_node == NULL)
+	{
+	  *need_ssa_rename_p |=
+	    ipa_tm_insert_gettmclone_call (node, region, gsi, stmt);
+	  cgraph_remove_edge (e);
+	  return;
+	}
+
+      fndecl = new_node->decl;
+    }
+
+  cgraph_redirect_edge_callee (e, new_node);
+  gimple_call_set_fndecl (stmt, fndecl);
+  return;
+}
+
 /* Helper function for ipa_tm_transform_calls.  For a given BB,
    install calls to tm_irrevocable when IRR_BLOCKS are reached,
    redirect other calls to the generated transactional clone.  */
@@ -4289,6 +4409,7 @@  ipa_tm_transform_calls_1 (struct cgraph_
 {
   gimple_stmt_iterator gsi;
   bool need_ssa_rename = false;
+  bool past_tm_ending_stmt = false;
 
   if (irr_blocks && bitmap_bit_p (irr_blocks, bb->index))
     {
@@ -4299,8 +4420,6 @@  ipa_tm_transform_calls_1 (struct cgraph_
   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     {
       gimple stmt = gsi_stmt (gsi);
-      struct cgraph_edge *e;
-      struct cgraph_node *new_node;
       tree fndecl;
 
       if (!is_gimple_call (stmt))
@@ -4310,61 +4429,26 @@  ipa_tm_transform_calls_1 (struct cgraph_
 
       fndecl = gimple_call_fndecl (stmt);
 
-      /* For indirect calls, pass the address through the runtime.  */
-      if (fndecl == NULL)
-	{
-	  need_ssa_rename |=
-	    ipa_tm_insert_gettmclone_call (node, region, &gsi, stmt);
-	  continue;
-	}
-
-      /* Don't scan past the end of the transaction.  */
-      if (is_tm_ending_fndecl (fndecl))
-	break;
-      e = cgraph_edge (node, stmt);
-
-      /* If there is a replacement, use it, otherwise use the clone.  */
-      fndecl = find_tm_replacement_function (fndecl);
-      if (fndecl)
-	{
-	  new_node = cgraph_node (fndecl);
-
-	  /* ??? Mark all transaction_wrap functions tm_may_enter_irr.
-
-	     We can't do this earlier in record_tm_replacement because
-	     cgraph_remove_unreachable_nodes is called before we inject
-	     references to the node.  Further, we can't do this in some
-	     nice central place in ipa_tm_execute because we don't have
-	     the exact list of wrapper functions that would be used.
-	     Marking more wrappers than necessary results in the creation
-	     of unnecessary cgraph_nodes, which can cause some of the
-	     other IPA passes to crash.
-
-	     We do need to mark these nodes so that we get the proper
-	     result in expand_call_tm.  */
-	  new_node->local.tm_may_enter_irr = 1;
-	}
-      else
+      if (!past_tm_ending_stmt)
 	{
-	  struct tm_ipa_cg_data *d = get_cg_data (e->callee);
-	  new_node = d->clone;
-
-	  /* As we've already skipped pure calls and appropriate builtins,
-	     and we've already marked irrevocable blocks, if we can't come
-	     up with a static replacement, then ask the runtime.  */
-	  if (new_node == NULL)
+	  /* For indirect calls, pass the address through the runtime.  */
+	  if (fndecl == NULL)
 	    {
 	      need_ssa_rename |=
-	        ipa_tm_insert_gettmclone_call (node, region, &gsi, stmt);
-	      cgraph_remove_edge (e);
+		ipa_tm_insert_gettmclone_call (node, region, &gsi, stmt);
 	      continue;
 	    }
 
-	  fndecl = new_node->decl;
+	  if (is_tm_ending_fndecl (fndecl))
+	    past_tm_ending_stmt = true;
 	}
 
-      cgraph_redirect_edge_callee (e, new_node);
-      gimple_call_set_fndecl (stmt, fndecl);
+      /* Redirect edges to the appropriate replacement or clone.  This
+	 will even redirect calls outside of a transaction, but only
+	 if they're recursive calls to the clone.  */
+      ipa_tm_transform_calls_redirect (node, region, &gsi,
+				       past_tm_ending_stmt,
+				       &need_ssa_rename);
     }
 
   return need_ssa_rename;