asm goto vs simulate_block

asm goto vs simulate_block

[Richard Henderson]

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

The kernel folk here at Red Hat have given me a test case (which I'll be 
happy to forward, along a complete patch vs mainline) which gets 
miscompiled because we never get around to adding all of the appropriate 
blocks outgoing from an asm-goto to the simulation.

I can't figure out why the VARYING that we get in simulate_stmt and 
subsequent calls to add_control_edge are not enough to DTRT.  All I know 
is that the attached patch does in fact work around the problem, 
changing the .028t.ccp1 dump:

...
  Lattice value changed to VARYING.  Adding SSA edges to worklist.
+Adding Destination of edge (13 -> 14) to worklist
+
+
+Simulating block 14
...

Can someone give me a good explanation as to why this patch would be needed?


r~

[-- Attachment #2: d-asmgoto-5 --]
[-- Type: text/plain, Size: 1395 bytes --]

diff --git a/gcc/tree-ssa-propagate.c b/gcc/tree-ssa-propagate.c
index a3a87cb..29d27aa 100644
--- a/gcc/tree-ssa-propagate.c
+++ b/gcc/tree-ssa-propagate.c
@@ -430,13 +430,14 @@ simulate_block (basic_block block)
       unsigned int normal_edge_count;
       edge e, normal_edge;
       edge_iterator ei;
+      gimple stmt = NULL;
 
       /* Note that we have simulated this block.  */
       SET_BIT (executable_blocks, block->index);
 
       for (j = gsi_start_bb (block); !gsi_end_p (j); gsi_next (&j))
 	{
-	  gimple stmt = gsi_stmt (j);
+	  stmt = gsi_stmt (j);
 
 	  /* If this statement is already in the worklist then
 	     "cancel" it.  The reevaluation implied by the worklist
@@ -449,6 +450,17 @@ simulate_block (basic_block block)
 	  simulate_stmt (stmt);
 	}
 
+      /* ??? I can't figure out why this wouldn't have been taken care
+	 of in simulate_stmt, because the asm is considered VARYING.
+	 But it's also true that we'll never be able to predict which
+	 edge is going to be taken, so we might as well push them early.  */
+      if (stmt && gimple_code (stmt) == GIMPLE_ASM && stmt_ends_bb_p (stmt))
+	{
+	  FOR_EACH_EDGE (e, ei, block->succs)
+	    add_control_edge (e);
+	  return;
+	}
+
       /* We can not predict when abnormal and EH edges will be executed, so
 	 once a block is considered executable, we consider any
 	 outgoing abnormal edges as executable.

Re: asm goto vs simulate_block

[Daniel Berlin]

My guess, witjout seeing the testcase.
In ccp_initialize we have:

      for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
        {
          gimple stmt = gsi_stmt (i);
          bool is_varying = surely_varying_stmt_p (stmt);

          if (is_varying)
            {
              tree def;
              ssa_op_iter iter;

              /* If the statement will not produce a constant, mark
                 all its outputs VARYING.  */
              FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
                set_value_varying (def);
            }
          prop_set_simulate_again (stmt, !is_varying);

This code looks clearly broken if the statement is control altering
(like your asm), since it will cause us to never simulate it and add
the outgoing edges (since the outgoing edges are only added in
simulate_stmt).

Without hacking through the abstraction (since it's ssa propagate that
adds the outgoing edges on simulation), the only thing i can see to do
would be to change the conditional to if (is_varying &&
!stmt_ends_bb_p (bb)) (or the equivalent) so that it simulates them.
Or add a way to tell the propagator about edges it should add
initially to the control worklist.




On Thu, Aug 27, 2009 at 1:23 PM, Richard Henderson<rth@twiddle.net> wrote:
> The kernel folk here at Red Hat have given me a test case (which I'll be
> happy to forward, along a complete patch vs mainline) which gets miscompiled
> because we never get around to adding all of the appropriate blocks outgoing
> from an asm-goto to the simulation.
>
> I can't figure out why the VARYING that we get in simulate_stmt and
> subsequent calls to add_control_edge are not enough to DTRT.  All I know is
> that the attached patch does in fact work around the problem, changing the
> .028t.ccp1 dump:
>
> ...
>  Lattice value changed to VARYING.  Adding SSA edges to worklist.
> +Adding Destination of edge (13 -> 14) to worklist
> +
> +
> +Simulating block 14
> ...
>
> Can someone give me a good explanation as to why this patch would be needed?
>
>
> r~
>

Re: asm goto vs simulate_block

[Richard Henderson]

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

> My guess, witjout seeing the testcase.
> In ccp_initialize we have:
>
>       for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
>         {
>           gimple stmt = gsi_stmt (i);
>           bool is_varying = surely_varying_stmt_p (stmt);
>
>           if (is_varying)
>             {
>               tree def;
>               ssa_op_iter iter;
>
>               /* If the statement will not produce a constant, mark
>                  all its outputs VARYING.  */
>               FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
>                 set_value_varying (def);
>             }
>           prop_set_simulate_again (stmt, !is_varying);
>
> This code looks clearly broken if the statement is control altering
> (like your asm), since it will cause us to never simulate it and add
> the outgoing edges (since the outgoing edges are only added in
> simulate_stmt).

Your guess is absolutely correct.  We already correctly
handle this case in init_copy_prop, but do not in two
other places.

And I just ran into this with my exception rewrite too,
which has an EH_DISPATCH control statement with multiple
normal edges plus a fallthru.  The only thing "weird"
about this statement is that it has multiple normal edges
and nothing currently visible in the program that determines
which edge will be taken.

The following patch appears to work for both.  I'll commit
it after a bootstrap and test cycle completes.


r~

[-- Attachment #2: d-asmgoto-5b --]
[-- Type: text/plain, Size: 1669 bytes --]

	* tree-ssa-ccp.c (ccp_initialize): Make sure to simulate 
	stmt_ends_pp_p statements at least once.
	* tree-vrp.c (vrp_initialize): Likewise.

diff --git a/gcc/tree-ssa-ccp.c b/gcc/tree-ssa-ccp.c
index b359d4c..949c4b5 100644
--- a/gcc/tree-ssa-ccp.c
+++ b/gcc/tree-ssa-ccp.c
@@ -650,7 +650,15 @@ ccp_initialize (void)
       for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
         {
 	  gimple stmt = gsi_stmt (i);
-	  bool is_varying = surely_varying_stmt_p (stmt);
+	  bool is_varying;
+
+	  /* If the statement is a control insn, then we do not
+	     want to avoid simulating the statement once.  Failure
+	     to do so means that those edges will never get added.  */
+	  if (stmt_ends_bb_p (stmt))
+	    is_varying = false;
+	  else
+	    is_varying = surely_varying_stmt_p (stmt);
 
 	  if (is_varying)
 	    {
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 5379b75..7e8a952 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -5317,7 +5317,12 @@ vrp_initialize (void)
         {
 	  gimple stmt = gsi_stmt (si);
 
-	  if (!stmt_interesting_for_vrp (stmt))
+ 	  /* If the statement is a control insn, then we do not
+ 	     want to avoid simulating the statement once.  Failure
+ 	     to do so means that those edges will never get added.  */
+	  if (stmt_ends_bb_p (stmt))
+	    prop_set_simulate_again (stmt, true);
+	  else if (!stmt_interesting_for_vrp (stmt))
 	    {
 	      ssa_op_iter i;
 	      tree def;
@@ -5326,9 +5331,7 @@ vrp_initialize (void)
 	      prop_set_simulate_again (stmt, false);
 	    }
 	  else
-	    {
-	      prop_set_simulate_again (stmt, true);
-	    }
+	    prop_set_simulate_again (stmt, true);
 	}
     }
 }

Re: asm goto vs simulate_block

[Richard Henderson]

On 08/31/2009 05:06 PM, Richard Henderson wrote:
> The following patch appears to work for both. I'll commit
> it after a bootstrap and test cycle completes.

Committed with one additional change, to prevent VRP
from crashing.


r~


          (vrp_visit_stmt): Be prepared for non-interesting stmts.


  @@ -6087,7 +6090,9 @@ vrp_visit_stmt (gimple stmt, edge *taken_edge_p, 
tree *output_p)
         fprintf (dump_file, "\n");
       }

  -  if (is_gimple_assign (stmt) || is_gimple_call (stmt))
  +  if (!stmt_interesting_for_vrp (stmt))
  +    gcc_assert (stmt_ends_bb_p (stmt));
  +  else if (is_gimple_assign (stmt) || is_gimple_call (stmt))
       {
         /* In general, assignments with virtual operands are not useful
           for deriving ranges, with the obvious exception of calls to