Patchwork [PR50672] Fix ice triggered by -ftree-tail-merge: verify_ssa failed: no immediate_use list

login
register
mail settings
Submitter Tom de Vries
Date Oct. 13, 2011, 11:12 p.m.
Message ID <4E97705E.6070205@mentor.com>
Download mbox | patch
Permalink /patch/119661/
State New
Headers show

Comments

Tom de Vries - Oct. 13, 2011, 11:12 p.m.
On 10/12/2011 02:19 PM, Richard Guenther wrote:
> On Wed, Oct 12, 2011 at 8:35 AM, Tom de Vries <vries@codesourcery.com> wrote:
>> Richard,
>>
>> I have a patch for PR50672.
>>
>> When compiling the testcase from the PR with -ftree-tail-merge, the scenario is
>> as follows:
>>
>> We start out tail_merge_optimize with blocks 14 and 20, which are alike, but not
>> equal, since they have different successors:
>> ...
>>  # BLOCK 14 freq:690
>>  # PRED: 25 [61.0%]  (false,exec)
>>
>>  if (wD.2197_57(D) != 0B)
>>    goto <bb 15>;
>>  else
>>    goto <bb 16>;
>>  # SUCC: 15 [78.4%]  (true,exec) 16 [21.6%]  (false,exec)
>>
>>
>>  # BLOCK 20 freq:2900
>>  # PRED: 29 [100.0%]  (fallthru) 31 [100.0%]  (fallthru)
>>
>>  # .MEMD.2447_209 = PHI <.MEMD.2447_125(29), .MEMD.2447_129(31)>
>>  if (wD.2197_57(D) != 0B)
>>    goto <bb 5>;
>>  else
>>    goto <bb 6>;
>>  # SUCC: 5 [85.0%]  (true,exec) 6 [15.0%]  (false,exec)
>> ...
>>
>> In the first iteration, we merge block 5 with block 15 and block 6 with block
>> 16. After that, the blocks 14 and 20 are equal.
>>
>> In the second iteration, the blocks 14 and 20 are merged, by redirecting the
>> incoming edges of block 20 to block 14, and removing block 20.
>>
>> Block 20 also contains the definition of .MEMD.2447_209. Removing the definition
>> delinks the vuse of .MEMD.2447_209 in block 5:
>> ...
>>  # BLOCK 5 freq:6036
>>  # PRED: 20 [85.0%]  (true,exec)
>>
>>  # PT = nonlocal escaped
>>  D.2306_58 = &thisD.2200_10(D)->D.2156;
>>  # .MEMD.2447_132 = VDEF <.MEMD.2447_209>
>>  # USE = anything
>>  # CLB = anything
>>  drawLineD.2135 (D.2306_58, wD.2197_57(D), gcD.2198_59(D));
>>  goto <bb 17>;
>>  # SUCC: 17 [100.0%]  (fallthru,exec)
>> ...
> 
> And block 5 is retained and block 15 is discarded?
> 

Indeed.

>> After the pass, when executing the TODO_update_ssa_only_virtuals, we update the
>> drawLine call in block 5 using rewrite_update_stmt, which calls
>> maybe_replace_use for the vuse operand.
>>
>> However, maybe_replace_use doesn't have an effect since the old vuse and the new
>> vuse happen to be the same (rdef == use), so SET_USE is not called and the vuse
>> remains delinked:
>> ...
>>  if (rdef && rdef != use)
>>    SET_USE (use_p, rdef);
>> ...
>>
>> The patch fixes this by forcing SET_USE for delinked uses.
> 
> That isn't the correct fix.  Whoever unlinks the vuse (by removing its
> definition) has to replace it with something valid, which is either the
> bare symbol .MEM, or the VUSE associated with the removed VDEF
> (thus, as unlink_stmt_vdef does).
> 

Another try. For each deleted bb, we call unlink_stmt_vdef for the statements,
and replace the .MEM phi uses with the bare .MEM symbol.

Bootstrapped and reg-tested on x86_64.

Ok for trunk?

Thanks,
- Tom

> Richard.
> 


2011-10-14  Tom de Vries  <tom@codesourcery.com>

	PR tree-optimization/50672
	* tree-ssa-tail-merge.c (release_vdefs): New function.
	(purge_bbs): Add update_vops parameter.  Call release_vdefs for each
	deleted basic block.
	(tail_merge_optimize): Add argument to call to purge_bbs.
Richard Guenther - Oct. 14, 2011, 10 a.m.
On Fri, Oct 14, 2011 at 1:12 AM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> On 10/12/2011 02:19 PM, Richard Guenther wrote:
>> On Wed, Oct 12, 2011 at 8:35 AM, Tom de Vries <vries@codesourcery.com> wrote:
>>> Richard,
>>>
>>> I have a patch for PR50672.
>>>
>>> When compiling the testcase from the PR with -ftree-tail-merge, the scenario is
>>> as follows:
>>>
>>> We start out tail_merge_optimize with blocks 14 and 20, which are alike, but not
>>> equal, since they have different successors:
>>> ...
>>>  # BLOCK 14 freq:690
>>>  # PRED: 25 [61.0%]  (false,exec)
>>>
>>>  if (wD.2197_57(D) != 0B)
>>>    goto <bb 15>;
>>>  else
>>>    goto <bb 16>;
>>>  # SUCC: 15 [78.4%]  (true,exec) 16 [21.6%]  (false,exec)
>>>
>>>
>>>  # BLOCK 20 freq:2900
>>>  # PRED: 29 [100.0%]  (fallthru) 31 [100.0%]  (fallthru)
>>>
>>>  # .MEMD.2447_209 = PHI <.MEMD.2447_125(29), .MEMD.2447_129(31)>
>>>  if (wD.2197_57(D) != 0B)
>>>    goto <bb 5>;
>>>  else
>>>    goto <bb 6>;
>>>  # SUCC: 5 [85.0%]  (true,exec) 6 [15.0%]  (false,exec)
>>> ...
>>>
>>> In the first iteration, we merge block 5 with block 15 and block 6 with block
>>> 16. After that, the blocks 14 and 20 are equal.
>>>
>>> In the second iteration, the blocks 14 and 20 are merged, by redirecting the
>>> incoming edges of block 20 to block 14, and removing block 20.
>>>
>>> Block 20 also contains the definition of .MEMD.2447_209. Removing the definition
>>> delinks the vuse of .MEMD.2447_209 in block 5:
>>> ...
>>>  # BLOCK 5 freq:6036
>>>  # PRED: 20 [85.0%]  (true,exec)
>>>
>>>  # PT = nonlocal escaped
>>>  D.2306_58 = &thisD.2200_10(D)->D.2156;
>>>  # .MEMD.2447_132 = VDEF <.MEMD.2447_209>
>>>  # USE = anything
>>>  # CLB = anything
>>>  drawLineD.2135 (D.2306_58, wD.2197_57(D), gcD.2198_59(D));
>>>  goto <bb 17>;
>>>  # SUCC: 17 [100.0%]  (fallthru,exec)
>>> ...
>>
>> And block 5 is retained and block 15 is discarded?
>>
>
> Indeed.
>
>>> After the pass, when executing the TODO_update_ssa_only_virtuals, we update the
>>> drawLine call in block 5 using rewrite_update_stmt, which calls
>>> maybe_replace_use for the vuse operand.
>>>
>>> However, maybe_replace_use doesn't have an effect since the old vuse and the new
>>> vuse happen to be the same (rdef == use), so SET_USE is not called and the vuse
>>> remains delinked:
>>> ...
>>>  if (rdef && rdef != use)
>>>    SET_USE (use_p, rdef);
>>> ...
>>>
>>> The patch fixes this by forcing SET_USE for delinked uses.
>>
>> That isn't the correct fix.  Whoever unlinks the vuse (by removing its
>> definition) has to replace it with something valid, which is either the
>> bare symbol .MEM, or the VUSE associated with the removed VDEF
>> (thus, as unlink_stmt_vdef does).
>>
>
> Another try. For each deleted bb, we call unlink_stmt_vdef for the statements,
> and replace the .MEM phi uses with the bare .MEM symbol.
>
> Bootstrapped and reg-tested on x86_64.
>
> Ok for trunk?

Better.  For

+
+      FOR_EACH_IMM_USE_STMT (use_stmt, iter, res)
+       {
+         FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
+           SET_USE (use_p, SSA_NAME_VAR (res));
+       }

you can use mark_virtual_phi_result_for_renaming (phi) instead.

+  for (i = gsi_last_bb (bb); !gsi_end_p (i); gsi_prev_nondebug (&i))
+    unlink_stmt_vdef (gsi_stmt (i));

is that actually necessary?  That is, isn't the block that follows a
deleted block always starting with a vitual PHI?  If not it should
be enough to walk to the first stmt that uses a virtual operand
and similar to the PHI case replace all its uses with the bare
symbol.  But as I said, I believe handling PHIs should be sufficient?

Thanks,
Richard.


> Thanks,
> - Tom
>
>> Richard.
>>
>
>
> 2011-10-14  Tom de Vries  <tom@codesourcery.com>
>
>        PR tree-optimization/50672
>        * tree-ssa-tail-merge.c (release_vdefs): New function.
>        (purge_bbs): Add update_vops parameter.  Call release_vdefs for each
>        deleted basic block.
>        (tail_merge_optimize): Add argument to call to purge_bbs.
>

Patch

Index: gcc/tree-ssa-tail-merge.c
===================================================================
--- gcc/tree-ssa-tail-merge.c (revision 179773)
+++ gcc/tree-ssa-tail-merge.c (working copy)
@@ -773,18 +773,53 @@  same_succ_flush_bbs (bitmap bbs)
     }
 }
 
+/* Release all vdefs in BB, either normal or phi results.  */
+
+static void
+release_vdefs (basic_block bb)
+{
+  gimple_stmt_iterator i;
+
+  for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
+    {
+      gimple phi = gsi_stmt (i);
+      tree res = gimple_phi_result (phi);
+      use_operand_p use_p;
+      imm_use_iterator iter;
+      gimple use_stmt;
+
+      if (is_gimple_reg (res))
+	continue;
+
+      FOR_EACH_IMM_USE_STMT (use_stmt, iter, res)
+	{
+	  FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
+	    SET_USE (use_p, SSA_NAME_VAR (res));
+	}
+    }
+  
+  for (i = gsi_last_bb (bb); !gsi_end_p (i); gsi_prev_nondebug (&i))
+    unlink_stmt_vdef (gsi_stmt (i));
+}
+
 /* Delete all deleted_bbs.  */
 
 static void
-purge_bbs (void)
+purge_bbs (bool update_vops)
 {
   unsigned int i;
   bitmap_iterator bi;
+  basic_block bb;
 
   same_succ_flush_bbs (deleted_bbs);
 
   EXECUTE_IF_SET_IN_BITMAP (deleted_bbs, 0, i, bi)
-    delete_basic_block (BASIC_BLOCK (i));
+    {
+      bb = BASIC_BLOCK (i);
+      if (!update_vops)
+	release_vdefs (bb);
+      delete_basic_block (bb);
+    }
 
   bitmap_and_compl_into (deleted_bb_preds, deleted_bbs);
   bitmap_clear (deleted_bbs);
@@ -1665,7 +1700,7 @@  tail_merge_optimize (unsigned int todo)
 	break;
 
       free_dominance_info (CDI_DOMINATORS);
-      purge_bbs ();
+      purge_bbs (update_vops);
 
       if (iteration_nr == max_iterations)
 	break;