[trans-mem][rfc] Improvements to uninstrumented code paths

[trans-mem][rfc] Improvements to uninstrumented code paths

[Richard Henderson]

I wrote the second of these patches first, and I'm uncertain about the
desirability of the first of the patches.

While working on the uninstrumented code path bulk patch, I noticed that
nested transactions within the copy of the outermost transaction were
not being processed for an uninstrumented code path, and so were only
receiving an instrumented path.  This is clearly less than ideal when
considering HTM.

Now, it seemed to me that if we're already in an uninstrumented code
path, we're extremely likely to want to stay in one.  This is certainly
true for HTM, as well as when we've selected the serialirr method.  I
can't think off hand of any other reason we'd be on the uninstrumented
code path.

Therefore the second patch arranges for all nested transactions in the
uninstrumented path to _only_ have uninstrumented paths themselves.

While reviewing the results of this second patch in detail, I noticed
that nested transactions on the instrumented code paths were not 
generating both instrumented and uninstrumented code paths.  My first
reaction was that this was a bug, and so I wrote the first patch to
fix it.

But as I was reviewing the patch to write the changelog, I began to
wonder whether the same logic concerning the original instrumented/
uninstrumented choice applies as well to the instrumented path.

Is it ever likely that we'd choose an uninstrumented path for a
nested transaction, given that we're already executing the instrumented
path for an outer transaction?

It now seems to me that the only time we'd switch from instrumented
to uninstrumented code path would be during a transaction restart,
after having selected to retry with a serialirr method.

Which means that I should apply the second patch only,

Thoughts?


r~

Re: [trans-mem][rfc] Improvements to uninstrumented code paths

[Richard Henderson]

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

On 11/07/2012 03:01 PM, Richard Henderson wrote:
> Thoughts?

Now with 100% more patches per mail!


r~


[-- Attachment #2: 0001-tm-Handle-nested-transactions-in-ipa_uninstrument_tr.patch --]
[-- Type: text/x-patch, Size: 2528 bytes --]

From 6e97eb1f7086b4392545cc73254037cd3ff09fe6 Mon Sep 17 00:00:00 2001
From: Richard Henderson <rth@redhat.com>
Date: Wed, 7 Nov 2012 14:32:21 -0800
Subject: [PATCH 1/2] tm: Handle nested transactions in
 ipa_uninstrument_transaction

        * trans-mem.c (ipa_uninstrument_transaction0): Rename from
        ipa_uninstrument_transaction.
        (ipa_uninstrument_transaction): New function.
---
 gcc/ChangeLog   |  4 ++++
 gcc/trans-mem.c | 23 ++++++++++++++++++++---
 2 files changed, 24 insertions(+), 3 deletions(-)

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 24d9845..dc1909c 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,9 @@
 2012-11-07  Richard Henderson  <rth@redhat.com>
 
+	* trans-mem.c (ipa_uninstrument_transaction0): Rename from
+	ipa_uninstrument_transaction.
+	(ipa_uninstrument_transaction): New function.
+
 	* trans-mem.c (pass_ipa_tm): Don't use TODO_update_ssa.
 
 2012-11-07  Peter Bergner  <bergner@vnet.ibm.com>
diff --git a/gcc/trans-mem.c b/gcc/trans-mem.c
index a7b4a9c..478ce71 100644
--- a/gcc/trans-mem.c
+++ b/gcc/trans-mem.c
@@ -3882,12 +3882,12 @@ maybe_push_queue (struct cgraph_node *node,
    code path.  QUEUE are the basic blocks inside the transaction
    represented in REGION.
 
-   Later in split_code_paths() we will add the conditional to choose
+   Later in expand_transaction we will add the conditional to choose
    between the two alternatives.  */
 
 static void
-ipa_uninstrument_transaction (struct tm_region *region,
-			      VEC (basic_block, heap) *queue)
+ipa_uninstrument_transaction0 (struct tm_region *region,
+			       VEC (basic_block, heap) *queue)
 {
   gimple transaction = region->transaction_stmt;
   basic_block transaction_bb = gimple_bb (transaction);
@@ -3907,6 +3907,23 @@ ipa_uninstrument_transaction (struct tm_region *region,
   free (new_bbs);
 }
 
+static void
+ipa_uninstrument_transaction (struct tm_region *region,
+			      VEC (basic_block, heap) *bbs)
+{
+  ipa_uninstrument_transaction0 (region, bbs);
+
+  // Recurse for the inner transactions to make sure they all have
+  // uninstrumented code paths.
+  for (region = region->inner; region; region = region->next)
+    {
+      bbs = get_tm_region_blocks (region->entry_block, region->exit_blocks,
+				  NULL, NULL, false);
+      ipa_uninstrument_transaction (region, bbs);
+      VEC_free (basic_block, heap, bbs);
+    }
+}
+
 /* A subroutine of ipa_tm_scan_calls_transaction and ipa_tm_scan_calls_clone.
    Queue all callees within block BB.  */
 
-- 
1.7.11.7


[-- Attachment #3: 0002-tm-Optimize-nested-transactions-in-an-uninstrumented.patch --]
[-- Type: text/x-patch, Size: 7112 bytes --]

From 9253d4138a0cdb76c40345a1e32694968f375a86 Mon Sep 17 00:00:00 2001
From: Richard Henderson <rth@redhat.com>
Date: Wed, 7 Nov 2012 14:36:01 -0800
Subject: [PATCH 2/2] tm: Optimize nested transactions in an uninstrumented
 code path

        * trans-mem.c (tm_region_init_0): Consider all edges when looking
        for the entry_block.
        (collect_bb2reg): Handle uninstrumented only transactions.
        (generate_tm_state): Likewise.
        (expand_transaction): Likewise.
        (execute_tm_memopt): Likewise.
        (ipa_uninstrument_transaction0): Convert nested transactions in
        the uninstrumented code path to uninstrumented only.
---
 gcc/ChangeLog   |  9 ++++++++
 gcc/trans-mem.c | 66 ++++++++++++++++++++++++++++++++++++++++++++-------------
 2 files changed, 60 insertions(+), 15 deletions(-)

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index dc1909c..8555e8c 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,14 @@
 2012-11-07  Richard Henderson  <rth@redhat.com>
 
+	* trans-mem.c (tm_region_init_0): Consider all edges when looking
+	for the entry_block.
+	(collect_bb2reg): Handle uninstrumented only transactions.
+	(generate_tm_state): Likewise.
+	(expand_transaction): Likewise.
+	(execute_tm_memopt): Likewise.
+	(ipa_uninstrument_transaction0): Convert nested transactions in
+	the uninstrumented code path to uninstrumented only.
+
 	* trans-mem.c (ipa_uninstrument_transaction0): Rename from
 	ipa_uninstrument_transaction.
 	(ipa_uninstrument_transaction): New function.
diff --git a/gcc/trans-mem.c b/gcc/trans-mem.c
index 478ce71..c0987dc 100644
--- a/gcc/trans-mem.c
+++ b/gcc/trans-mem.c
@@ -868,10 +868,13 @@ typedef struct tm_log_entry
 {
   /* Address to save.  */
   tree addr;
+
   /* Entry block for the transaction this address occurs in.  */
   basic_block entry_block;
+
   /* Dominating statements the store occurs in.  */
   gimple_vec stmts;
+
   /* Initially, while we are building the log, we place a nonzero
      value here to mean that this address *will* be saved with a
      save/restore sequence.  Later, when generating the save sequence
@@ -1721,8 +1724,8 @@ struct tm_region
   /* Return value from BUILT_IN_TM_START.  */
   tree tm_state;
 
-  /* The entry block to this region.  This will always be the first
-     block of the body of the transaction.  */
+  /* The entry block to the instrumented code path for this region.
+     This will always be the first block of the body of the transaction.  */
   basic_block entry_block;
 
   /* The first block after an expanded call to _ITM_beginTransaction.  */
@@ -1732,7 +1735,7 @@ struct tm_region
      These blocks are still a part of the region (i.e., the border is
      inclusive). Note that this set is only complete for paths in the CFG
      starting at ENTRY_BLOCK, and that there is no exit block recorded for
-     the edge to the "over" label.  */
+     the TM_ABORT edge nor for the body of the uninstrumented code path.  */
   bitmap exit_blocks;
 
   /* The set of all blocks that have an TM_IRREVOCABLE call.  */
@@ -1779,11 +1782,19 @@ tm_region_init_0 (struct tm_region *outer, basic_block bb, gimple stmt)
   region->original_transaction_was_outer = false;
   region->tm_state = NULL;
 
-  /* There are either one or two edges out of the block containing
-     the GIMPLE_TRANSACTION, one to the actual region and one to the
-     "over" label if the region contains an abort.  The former will
-     always be the one marked FALLTHRU.  */
-  region->entry_block = FALLTHRU_EDGE (bb)->dest;
+  // There are three possible edges out of GIMPLE_TRANSACTION.
+  // The "entry_block" always refers to the instrumented code path.
+  region->entry_block = NULL;
+  {
+    edge_iterator ei;
+    edge e;
+    FOR_EACH_EDGE (e, ei, bb->succs)
+      if (!(e->flags & (EDGE_TM_ABORT | EDGE_TM_UNINSTRUMENTED)))
+	{
+	  region->entry_block = e->dest;
+	  break;
+	}
+  }
 
   region->exit_blocks = BITMAP_ALLOC (&tm_obstack);
   region->irr_blocks = BITMAP_ALLOC (&tm_obstack);
@@ -2453,6 +2464,10 @@ collect_bb2reg (struct tm_region *region, void *data)
   unsigned int i;
   basic_block bb;
 
+  // Don't run on transactions with only uninstrumented code paths.
+  if (region->entry_block == NULL)
+    return NULL;
+
   queue = get_tm_region_blocks (region->entry_block,
 				region->exit_blocks,
 				region->irr_blocks,
@@ -2564,9 +2579,8 @@ expand_transaction (struct tm_region *region, void *data ATTRIBUTE_UNUSED)
 	  uninst_edge = e;
 	else
 	  inst_edge = e;
-        if (e->flags & EDGE_FALLTHRU)
-	  fallthru_edge = e;
       }
+    fallthru_edge = (inst_edge ? inst_edge : uninst_edge);
   }
 
   /* ??? There are plenty of bits here we're not computing.  */
@@ -2780,7 +2794,7 @@ generate_tm_state (struct tm_region *region, void *data ATTRIBUTE_UNUSED)
 
   // Reset the subcode, post optimizations.  We'll fill this in
   // again as we process blocks.
-  if (region->exit_blocks)
+  if (region->entry_block && region->exit_blocks)
     {
       unsigned int subcode
 	= gimple_transaction_subcode (region->transaction_stmt);
@@ -3695,6 +3709,10 @@ execute_tm_memopt (void)
       size_t i;
       basic_block bb;
 
+      // Don't run on transactions with only uninstrumented code paths.
+      if (region->entry_block == NULL)
+	continue;
+
       bitmap_obstack_initialize (&tm_memopt_obstack);
 
       /* Save all BBs for the current region.  */
@@ -3894,15 +3912,33 @@ ipa_uninstrument_transaction0 (struct tm_region *region,
   int n = VEC_length (basic_block, queue);
   basic_block *new_bbs = XNEWVEC (basic_block, n);
 
+  // We will have a GIMPLE_ATOMIC with 3 possible edges out of it.
+  //   a) EDGE_FALLTHRU to the instrumented blocks,
+  //   b) EDGE_TM_UNINSTRUMENTED to the uninstrumented blocks,
+  //   c) EDGE_TM_ABORT out of the transaction
+
   copy_bbs (VEC_address (basic_block, queue), n, new_bbs,
 	    NULL, 0, NULL, NULL, transaction_bb);
   edge e = make_edge (transaction_bb, new_bbs[0], EDGE_TM_UNINSTRUMENTED);
   add_phi_args_after_copy (new_bbs, n, e);
 
-  // Now we will have a GIMPLE_ATOMIC with 3 possible edges out of it.
-  //   a) EDGE_FALLTHRU into the transaction
-  //   b) EDGE_TM_ABORT out of the transaction
-  //   c) EDGE_TM_UNINSTRUMENTED into the uninstrumented blocks.
+  // Note that the region that we copied can contain transactions.  Given
+  // that these are on a code path that we've just designated uninstrumented,
+  // there's no point in having these nested transactions have instrumented
+  // code paths.  Which means that there's no point processing these new
+  // transactions into new tm_regions so that they could be processed by
+  // ipa_tm_scan_calls_transaction.  What we would like to do is change the
+  // fallthru (instrumented) edges to uninstrumented.
+  for (int i = 0; i < n; ++i)
+    {
+      gimple_stmt_iterator gsi = gsi_last_bb (new_bbs[i]);
+      if (!gsi_end_p (gsi)
+          && gimple_code (gsi_stmt (gsi)) == GIMPLE_TRANSACTION)
+	{
+	  edge e = FALLTHRU_EDGE (new_bbs[i]);
+	  e->flags = EDGE_TM_UNINSTRUMENTED;
+	}
+    }
 
   free (new_bbs);
 }
-- 
1.7.11.7

Re: [trans-mem][rfc] Improvements to uninstrumented code paths

[Andi Kleen]

Richard Henderson <rth@redhat.com> writes:
>
> Is it ever likely that we'd choose an uninstrumented path for a
> nested transaction, given that we're already executing the instrumented
> path for an outer transaction?

I don't see why not. A small inner transaction may well succeed 
in HTM, even if the big outer one does not.

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only

Re: [trans-mem][rfc] Improvements to uninstrumented code paths

[Torvald Riegel]

On Wed, 2012-11-07 at 15:01 -0800, Richard Henderson wrote:
> I wrote the second of these patches first, and I'm uncertain about the
> desirability of the first of the patches.
> 
> While working on the uninstrumented code path bulk patch, I noticed that
> nested transactions within the copy of the outermost transaction

I assume "within" refers to within the same static scope of the
function?

> were
> not being processed for an uninstrumented code path, and so were only
> receiving an instrumented path.  This is clearly less than ideal when
> considering HTM.

Yes, it would be better if nested transactions would have an
uninstrumented code path too.

> Now, it seemed to me that if we're already in an uninstrumented code
> path, we're extremely likely to want to stay in one.  This is certainly
> true for HTM, as well as when we've selected the serialirr method.  I
> can't think off hand of any other reason we'd be on the uninstrumented
> code path.
> 
> Therefore the second patch arranges for all nested transactions in the
> uninstrumented path to _only_ have uninstrumented paths themselves.

This is only possible if the nested transaction cannot abort.  If it
potentially can, then we must have an instrumented code path for it.

> While reviewing the results of this second patch in detail, I noticed
> that nested transactions on the instrumented code paths were not 
> generating both instrumented and uninstrumented code paths.  My first
> reaction was that this was a bug, and so I wrote the first patch to
> fix it.
> 
> But as I was reviewing the patch to write the changelog, I began to
> wonder whether the same logic concerning the original instrumented/
> uninstrumented choice applies as well to the instrumented path.
> 
> Is it ever likely that we'd choose an uninstrumented path for a
> nested transaction, given that we're already executing the instrumented
> path for an outer transaction?

It could be a performance benefit in cases like

__transaction_relaxed {
  // something
  if (foo) {
    unsafe_action();
    transaction_relaxed {
      // lots of code
    }
  }
}

Here, we go serial at unsafe_action and can then cause less overall
slowdown when running "lots of code" as uninstrumented (but it's just
avoiding the per-memory-access function calls).  If the txn can acquire
the serial lock and commit afterwards, then it doesn't have to restart
at the outermost txn.

I can't say whether such cases would appear often enough in practice to
offset the code size increase (and thus potential slowdowns) caused by
having uninstrumented code paths available too.

> It now seems to me that the only time we'd switch from instrumented
> to uninstrumented code path would be during a transaction restart,
> after having selected to retry with a serialirr method.
> 
> Which means that I should apply the second patch only,
> 
> Thoughts?

Another thing to consider is whether flat nesting could be used: for
nested transactions that have hasNoAbort set, we can elide txn
begin/commit calls and just embed the nested txn body in the enclosing
txn.
This would be a benefit on uninstrumented/uninstrumented code path pairs
because the nested txn can't do anything but keep running.  For
instrumented/instrumented (with hasNoAbort set), we could also flatten
but there is a performance trade-off: the TM runtime lib could do closed
nesting on data conflicts, so that it tries to roll back only the inner
txn on a conflict.  The potential benefit of such a scheme depends a lot
on the workload, and libitm currently also flattens txns that do not
abort.  OTOH, the overhead of the begin/commit calls for nested txns
should also be relatively small compared to overall STM/instrumented
overheads.

So, to summarize:
- If the txn could abort, then it must have instrumented and could have
uninstrumented.
- If the nested txn does not abort, then:
  - For uninstrumented / uninstrumented nesting, flat nesting makes
    sense (and thus we don't need instrumented for the nested).
  - For instrumented / instrumented, we could flatten, but unsure
    whether that significantly improves performance.
  - Nested uninstrumented could be useful with enclosing nested, but
    perhaps this doesn't happen often enough to offset the code size
    increase.

Thoughts?

Torvald

Re: [trans-mem][rfc] Improvements to uninstrumented code paths

[Torvald Riegel]

On Wed, 2012-11-07 at 15:08 -0800, Andi Kleen wrote:
> Richard Henderson <rth@redhat.com> writes:
> >
> > Is it ever likely that we'd choose an uninstrumented path for a
> > nested transaction, given that we're already executing the instrumented
> > path for an outer transaction?
> 
> I don't see why not. A small inner transaction may well succeed 
> in HTM, even if the big outer one does not.

It could succeed, but this would require a HyTM scheme: when the
enclosing txn is a SW txn synchronizing with other SW txns, then the
nested HW txn would have to synchronize with those other SW txns too.
So, if the STM has a serialized commit phase or something like that,
then you can run the uninstrumented code path from within HW txns
(because the HyTM part can be done on begin).  But for all HyTMs that do
need instrumentation, it wouldn't work.

Re: [trans-mem][rfc] Improvements to uninstrumented code paths

[Torvald Riegel]

On Thu, 2012-11-08 at 13:33 +0100, Torvald Riegel wrote:
> On Wed, 2012-11-07 at 15:01 -0800, Richard Henderson wrote:
> > I wrote the second of these patches first, and I'm uncertain about the
> > desirability of the first of the patches.
> > 
> > While working on the uninstrumented code path bulk patch, I noticed that
> > nested transactions within the copy of the outermost transaction
> 
> I assume "within" refers to within the same static scope of the
> function?
> 
> > were
> > not being processed for an uninstrumented code path, and so were only
> > receiving an instrumented path.  This is clearly less than ideal when
> > considering HTM.
> 
> Yes, it would be better if nested transactions would have an
> uninstrumented code path too.
> 
> > Now, it seemed to me that if we're already in an uninstrumented code
> > path, we're extremely likely to want to stay in one.  This is certainly
> > true for HTM, as well as when we've selected the serialirr method.  I
> > can't think off hand of any other reason we'd be on the uninstrumented
> > code path.
> > 
> > Therefore the second patch arranges for all nested transactions in the
> > uninstrumented path to _only_ have uninstrumented paths themselves.
> 
> This is only possible if the nested transaction cannot abort.  If it
> potentially can, then we must have an instrumented code path for it.
> 
> > While reviewing the results of this second patch in detail, I noticed
> > that nested transactions on the instrumented code paths were not 
> > generating both instrumented and uninstrumented code paths.  My first
> > reaction was that this was a bug, and so I wrote the first patch to
> > fix it.
> > 
> > But as I was reviewing the patch to write the changelog, I began to
> > wonder whether the same logic concerning the original instrumented/
> > uninstrumented choice applies as well to the instrumented path.
> > 
> > Is it ever likely that we'd choose an uninstrumented path for a
> > nested transaction, given that we're already executing the instrumented
> > path for an outer transaction?
> 
> It could be a performance benefit in cases like
> 
> __transaction_relaxed {
>   // something
>   if (foo) {
>     unsafe_action();
>     transaction_relaxed {
>       // lots of code
>     }
>   }
> }
> 
> Here, we go serial at unsafe_action and can then cause less overall
> slowdown when running "lots of code" as uninstrumented (but it's just
> avoiding the per-memory-access function calls).  If the txn can acquire
> the serial lock and commit afterwards, then it doesn't have to restart
> at the outermost txn.
> 
> I can't say whether such cases would appear often enough in practice to
> offset the code size increase (and thus potential slowdowns) caused by
> having uninstrumented code paths available too.
> 
> > It now seems to me that the only time we'd switch from instrumented
> > to uninstrumented code path would be during a transaction restart,
> > after having selected to retry with a serialirr method.
> > 
> > Which means that I should apply the second patch only,
> > 
> > Thoughts?
> 
> Another thing to consider is whether flat nesting could be used: for
> nested transactions that have hasNoAbort set, we can elide txn
> begin/commit calls and just embed the nested txn body in the enclosing
> txn.
> This would be a benefit on uninstrumented/uninstrumented code path pairs
> because the nested txn can't do anything but keep running.  For
> instrumented/instrumented (with hasNoAbort set), we could also flatten
> but there is a performance trade-off: the TM runtime lib could do closed
> nesting on data conflicts, so that it tries to roll back only the inner
> txn on a conflict.  The potential benefit of such a scheme depends a lot
> on the workload, and libitm currently also flattens txns that do not
> abort.  OTOH, the overhead of the begin/commit calls for nested txns
> should also be relatively small compared to overall STM/instrumented
> overheads.
> 
> So, to summarize:
> - If the txn could abort, then it must have instrumented and could have
> uninstrumented.
> - If the nested txn does not abort, then:
>   - For uninstrumented / uninstrumented nesting, flat nesting makes
>     sense (and thus we don't need instrumented for the nested).
>   - For instrumented / instrumented, we could flatten, but unsure
>     whether that significantly improves performance.
>   - Nested uninstrumented could be useful with enclosing nested, but
>     perhaps this doesn't happen often enough to offset the code size
>     increase.

One addition for cases like:

__transaction_atomic {
  __transaction_atomic { /* ... */ }
  if (foo) __transaction_cancel;
}

Here, the enclosing txn may abort.  In this case, we must have
instrumented code paths for all nested txns too, and we could have
uninstrumented code paths for them (to allow for running those with HTMs
that can abort txns).


Torvald