Patchwork [path] PR 54900: store data race in if-conversion pass

login
register
mail settings
Submitter Aldy Hernandez
Date Oct. 15, 2012, 12:28 p.m.
Message ID <507C015F.2090508@redhat.com>
Download mbox | patch
Permalink /patch/191553/
State New
Headers show

Comments

Aldy Hernandez - Oct. 15, 2012, 12:28 p.m.
[Ian, I am copying you because this is originally your code.  Richard, I 
am copying you because you are all things aliased :-).  And Andrew is 
here because I am unable to come up with a suitable test for the 
simulate-thread harness.].

Here we have a store data race because noce_can_store_speculate_p() 
incorrectly returns true.  The problem is that 
memory_modified_in_insn_p() returns true if an instruction *MAY* modify 
a memory location, but the store can only be speculated if we are 
absolutely sure the store will happen on all subsequent paths.

My approach is to implement a memory_SURELY_modified_in_insn_p(), which 
will trigger this optimization less often, but at least it will be correct.

I thought of restricting the speculation for "--param 
allow-store-data-race=0" or transactional code, but IMO the speculation 
is incorrect as is.

I am having a bit of a problem coming up with a generic testcase. 
Perhaps Andrew or others have an idea.

The attached testcase fails to trigger without the patch, because AFAICT 
we have no way of testing an addition of zero to a memory location:

         cmpl    $1, flag(%rip)
         setb    %al
         addl    %eax, dont_write(%rip)

In the simulate-thread harness I can test the environment before an 
instruction, and after an instruction, but adding 0 to *dont_write 
produces no measurable effects, particularly in a back-end independent 
manner.  Ideas?

Bootstrap and regtested on x86-64 Linux.

Patch OK? (Except the test itself.)
PR tree-optimization/54900
	* ifcvt.c (noce_can_store_speculate_p): Call
	memory_surely_modified_in_insn_p.
	* alias.c (memory_surely_modified_in_insn_p): New.
	(memory_modified_in_insn_p): Change comment.
Andrew MacLeod - Oct. 15, 2012, 2:01 p.m.
On 10/15/2012 08:28 AM, Aldy Hernandez wrote:
>
> I am having a bit of a problem coming up with a generic testcase. 
> Perhaps Andrew or others have an idea.
>
> The attached testcase fails to trigger without the patch, because 
> AFAICT we have no way of testing an addition of zero to a memory 
> location:
>
>         cmpl    $1, flag(%rip)
>         setb    %al
>         addl    %eax, dont_write(%rip)
>
> In the simulate-thread harness I can test the environment before an 
> instruction, and after an instruction, but adding 0 to *dont_write 
> produces no measurable effects, particularly in a back-end independent 
> manner.  Ideas?

Hum. isn't that clever.   Well, the instruction is executed pretty much 
atomically... so a write of the same value becomes very difficult to 
detect, and impossible within the existing harness. And I dont think a 
hardware watch point can catch that...

The only way I can think of is if you put 'dont_write' into a section 
which will trap if it is written to...  I don't know the details of 
doing such a thing or how you monitor the trap within the harness...

Other than that I'm not sure we can detect this with our current set of 
tools, for the longer term we'd need a write detector.  I don't suppose 
something like systemtap can detect writes like this?

Andrew
Ian Taylor - Oct. 16, 2012, 5:19 p.m.
On Mon, Oct 15, 2012 at 5:28 AM, Aldy Hernandez <aldyh@redhat.com> wrote:
>
> Here we have a store data race because noce_can_store_speculate_p()
> incorrectly returns true.  The problem is that memory_modified_in_insn_p()
> returns true if an instruction *MAY* modify a memory location, but the store
> can only be speculated if we are absolutely sure the store will happen on
> all subsequent paths.
>
> My approach is to implement a memory_SURELY_modified_in_insn_p(), which will
> trigger this optimization less often, but at least it will be correct.

I don't see a reason to add this new function.  I would just inline it
into noce_can_store_speculate_p, replacing the call to
memory_modified_in_p.  And I'm not sure I see a reason to change the
comment for memory_modified_in_p, it seems to already be accurate.

Clearly we could consider the possibility of a PARALLEL of SET insns,
but of course most the compiler won't handle that anyhow.  I suppose
that would be a reason to use memory_surely_modified_in_insn_p, but in
that case you might as well handle the PARALLEL case now.

Ian
Jakub Jelinek - Oct. 16, 2012, 5:28 p.m.
On Tue, Oct 16, 2012 at 10:19:54AM -0700, Ian Lance Taylor wrote:
> On Mon, Oct 15, 2012 at 5:28 AM, Aldy Hernandez <aldyh@redhat.com> wrote:
> I don't see a reason to add this new function.  I would just inline it
> into noce_can_store_speculate_p, replacing the call to
> memory_modified_in_p.  And I'm not sure I see a reason to change the
> comment for memory_modified_in_p, it seems to already be accurate.
> 
> Clearly we could consider the possibility of a PARALLEL of SET insns,
> but of course most the compiler won't handle that anyhow.  I suppose
> that would be a reason to use memory_surely_modified_in_insn_p, but in
> that case you might as well handle the PARALLEL case now.

I see another problem with noce_can_store_speculate_p, the return false;
checks.  The search for a store to exactly that location can be done
just on post dominator bbs, but I wonder how you can avoid looking for
volatile insns or non-const/pure calls (or insns that may modify
the address) also in other bbs.
What if there is:
  location of considered if-conversion on mem
  if (some_condition)
    call ();
  mem = something;
?  We only walk immediate post-dominators, so look at the bb containing
mem = something;, but I think a call/volatile insn/modification of mem's
address is problematic in any bb on any path in between test_bb and
the post-dominator on which the write has been found.

	Jakub
Aldy Hernandez - Oct. 16, 2012, 11:54 p.m.
On 10/16/12 13:28, Jakub Jelinek wrote:

> I see another problem with noce_can_store_speculate_p, the return false;
> checks.  The search for a store to exactly that location can be done
> just on post dominator bbs, but I wonder how you can avoid looking for
> volatile insns or non-const/pure calls (or insns that may modify
> the address) also in other bbs.
> What if there is:
>    location of considered if-conversion on mem
>    if (some_condition)
>      call ();
>    mem = something;

Are we not currently being conservative in the current code and 
returning false once we see a volatile or a non-const call?

> ?  We only walk immediate post-dominators, so look at the bb containing
> mem = something;, but I think a call/volatile insn/modification of mem's
> address is problematic in any bb on any path in between test_bb and
> the post-dominator on which the write has been found.
>
> 	Jakub
>
Ian Taylor - Oct. 17, 2012, 12:33 a.m.
On Tue, Oct 16, 2012 at 4:54 PM, Aldy Hernandez <aldyh@redhat.com> wrote:
> On 10/16/12 13:28, Jakub Jelinek wrote:
>
>> I see another problem with noce_can_store_speculate_p, the return false;
>> checks.  The search for a store to exactly that location can be done
>> just on post dominator bbs, but I wonder how you can avoid looking for
>> volatile insns or non-const/pure calls (or insns that may modify
>> the address) also in other bbs.
>> What if there is:
>>    location of considered if-conversion on mem
>>    if (some_condition)
>>      call ();
>>    mem = something;
>
>
> Are we not currently being conservative in the current code and returning
> false once we see a volatile or a non-const call?

Jakub's point is that in his example the call will not be a
post-dominator of the block.  it's a good point.  Would you mind
trying to create a test case along those lines?

Ian

Patch

diff --git a/gcc/alias.c b/gcc/alias.c
index 0c6a744..26d3797 100644
--- a/gcc/alias.c
+++ b/gcc/alias.c
@@ -2748,8 +2748,8 @@  memory_modified_1 (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
 }
 
 
-/* Return true when INSN possibly modify memory contents of MEM
-   (i.e. address can be modified).  */
+/* Return true if INSN *MAY* possibly modify the memory contents of
+   MEM (i.e. address can be modified).  */
 bool
 memory_modified_in_insn_p (const_rtx mem, const_rtx insn)
 {
@@ -2760,6 +2760,22 @@  memory_modified_in_insn_p (const_rtx mem, const_rtx insn)
   return memory_modified;
 }
 
+/* Like memory_modified_in_insn_p, but return TRUE if INSN will
+   *SURELY* modify the memory contents of MEM.  */
+bool
+memory_surely_modified_in_insn_p (const_rtx mem, const_rtx insn)
+{
+  if (!INSN_P (insn))
+    return false;
+  rtx set = single_set (insn);
+  if (set)
+    {
+      rtx dest = SET_DEST (set);
+      return rtx_equal_p (dest, mem);
+    }
+  return false;
+}
+
 /* Initialize the aliasing machinery.  Initialize the REG_KNOWN_VALUE
    array.  */
 
diff --git a/gcc/ifcvt.c b/gcc/ifcvt.c
index 2f486a2..659e464 100644
--- a/gcc/ifcvt.c
+++ b/gcc/ifcvt.c
@@ -2415,7 +2415,7 @@  noce_can_store_speculate_p (basic_block top_bb, const_rtx mem)
 		  || (CALL_P (insn) && (!RTL_CONST_CALL_P (insn)))))
 	    return false;
 
-	  if (memory_modified_in_insn_p (mem, insn))
+	  if (memory_surely_modified_in_insn_p (mem, insn))
 	    return true;
 	  if (modified_in_p (XEXP (mem, 0), insn))
 	    return false;
diff --git a/gcc/rtl.h b/gcc/rtl.h
index cd5d435..d449ee1 100644
--- a/gcc/rtl.h
+++ b/gcc/rtl.h
@@ -2614,6 +2614,7 @@  extern void init_alias_analysis (void);
 extern void end_alias_analysis (void);
 extern void vt_equate_reg_base_value (const_rtx, const_rtx);
 extern bool memory_modified_in_insn_p (const_rtx, const_rtx);
+extern bool memory_surely_modified_in_insn_p (const_rtx, const_rtx);
 extern bool may_be_sp_based_p (rtx);
 extern rtx gen_hard_reg_clobber (enum machine_mode, unsigned int);
 extern rtx get_reg_known_value (unsigned int);
diff --git a/gcc/testsuite/gcc.dg/simulate-thread/speculative-store-5.c b/gcc/testsuite/gcc.dg/simulate-thread/speculative-store-5.c
new file mode 100644
index 0000000..52daa27
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/simulate-thread/speculative-store-5.c
@@ -0,0 +1,63 @@ 
+/* { dg-do link } */
+/* { dg-options "--param allow-store-data-races=0" } */
+/* { dg-final { simulate-thread } } */
+
+#include <stdio.h>
+#include "simulate-thread.h"
+
+/* PR tree-optimization/54900 */
+
+/* This file tests that a speculative store does not happen unless we
+   are sure a store to the location would happen anyway.  */
+
+int flag = 1;
+int stuff;
+int *stuffp = &stuff;
+int dont_write = 555;
+
+void simulate_thread_other_threads() 
+{
+}
+
+int simulate_thread_step_verify()
+{
+  if (dont_write != 555)
+    {
+      printf("FAIL: dont_write variable was assigned to.  \n");
+      return 1;
+    }
+  return 0;
+}
+
+int simulate_thread_final_verify()
+{
+  return 0;
+}
+
+void outerfunc (int p1)
+{
+  *stuffp = 0;
+}
+
+int innerfunc ()
+{
+  if (flag)
+    return 0;
+  /* This store should never happen because flag is globally set to true.  */
+  ++dont_write;
+  return 0;
+}
+
+__attribute__((noinline))
+void simulate_thread_main()
+{
+  outerfunc (innerfunc ());
+  simulate_thread_done();
+}
+
+__attribute__((noinline))
+int main()
+{
+  simulate_thread_main();
+  return 0;
+}