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

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

[Tom de Vries]

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

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)
...

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.

Bootstrapped and reg-tested on x86_64.

OK for trunk?

Thanks,
- Tom

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

	PR tree-optimization/50672
	* tree-into-ssa.c (maybe_replace_use): Force SET_USE for delinked uses.

[-- Attachment #2: pr50672.patch --]
[-- Type: text/x-patch, Size: 432 bytes --]

Index: gcc/tree-into-ssa.c
===================================================================
--- gcc/tree-into-ssa.c (revision 179592)
+++ gcc/tree-into-ssa.c (working copy)
@@ -1908,7 +1908,7 @@ maybe_replace_use (use_operand_p use_p)
   else if (is_old_name (use))
     rdef = get_reaching_def (use);
 
-  if (rdef && rdef != use)
+  if (rdef && (rdef != use || (!use_p->next && !use_p->prev)))
     SET_USE (use_p, rdef);
 }
 

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

[Richard Guenther]

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?

> 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).

Richard.

> Bootstrapped and reg-tested on x86_64.
>
> OK for trunk?
>
> Thanks,
> - Tom
>
> 2011-10-12  Tom de Vries  <tom@codesourcery.com>
>
>        PR tree-optimization/50672
>        * tree-into-ssa.c (maybe_replace_use): Force SET_USE for delinked uses.
>

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

[Tom de Vries]

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

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.

[-- Attachment #2: pr50672.2.patch --]
[-- Type: text/x-patch, Size: 1684 bytes --]

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;

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

[Richard Guenther]

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.
>

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

[Tom de Vries]

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

On 10/14/2011 12:00 PM, Richard Guenther wrote:
> 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 virtual PHI?

Block 20 is deleted. Block 5 follows the deleted block 20. Block 5 does not
start with a virtual 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. 

I think we need to handle the exposed uses (meaning outside the block) of vdefs
in each deleted block. The only vdef that can have exposed uses is the last vdef
in the block. So we should find the last vdef (gimple with gimple_vdef or
virtual PHI) and handle the related uses.

Bootstrapped and regtested on x86_64. OK for trunk?

Thanks,
- Tom

> But as I said, I believe handling PHIs should be sufficient?
> 
> Thanks,
> Richard.
> 
> 
>> Thanks,
>> - Tom
>>
>>> Richard.
>>>
>>

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

	PR tree-optimization/50672
	* tree-ssa-tail-merge.c (release_last_vdef): New function.
	(purge_bbs): Add update_vops parameter.  Call release_last_vdef for each
	deleted basic block.
	(tail_merge_optimize): Add argument to call to purge_bbs.

[-- Attachment #2: pr50672.3.patch --]
[-- Type: text/x-patch, Size: 1654 bytes --]

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,56 @@ same_succ_flush_bbs (bitmap bbs)
     }
 }
 
+/* Release the last vdef in BB, either normal or phi result.  */
+
+static void
+release_last_vdef (basic_block bb)
+{
+  gimple_stmt_iterator i;
+
+  for (i = gsi_last_bb (bb); !gsi_end_p (i); gsi_prev_nondebug (&i))
+    {
+      gimple stmt = gsi_stmt (i);
+      if (gimple_vdef (stmt) == NULL_TREE)
+	continue;
+
+      unlink_stmt_vdef (stmt);
+      return;
+    }
+
+  for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
+    {
+      gimple phi = gsi_stmt (i);
+      tree res = gimple_phi_result (phi);
+
+      if (is_gimple_reg (res))
+	continue;
+
+      mark_virtual_phi_result_for_renaming (phi);
+      return;
+    }
+  
+}
+
 /* 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_last_vdef (bb);
+
+      delete_basic_block (bb);
+    }
 
   bitmap_and_compl_into (deleted_bb_preds, deleted_bbs);
   bitmap_clear (deleted_bbs);
@@ -1665,7 +1703,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;

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

[Richard Guenther]

On Sun, Oct 16, 2011 at 12:05 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> On 10/14/2011 12:00 PM, Richard Guenther wrote:
>> 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 virtual PHI?
>
> Block 20 is deleted. Block 5 follows the deleted block 20. Block 5 does not
> start with a virtual 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.
>
> I think we need to handle the exposed uses (meaning outside the block) of vdefs
> in each deleted block. The only vdef that can have exposed uses is the last vdef
> in the block. So we should find the last vdef (gimple with gimple_vdef or
> virtual PHI) and handle the related uses.
>
> Bootstrapped and regtested on x86_64. OK for trunk?

Hmmm.  I can see that this will fail when the block has a store
but not a virtual PHI node, thus, when renaming does not reach
a bare .MEM symbol walking the use-def chain from the VUSE
of the store.  What release_last_vdef should do is trigger a rename
of subsequent VUSEs in successors of the deleted block.  Which
requires you to do something like

static void
rename_last_vdef (basic_block bb)
{
+  gimple_stmt_iterator i;
+
+  for (i = gsi_last_bb (bb); !gsi_end_p (i); gsi_prev_nondebug (&i))
+    {
+      gimple stmt = gsi_stmt (i);
+      if (gimple_vdef (stmt) == NULL_TREE)
+       continue;
+
+      mark_virtual_operand_for_renaming (gimple_vdef (stmt));
        return;
      }

+  for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
+    {
+      gimple phi = gsi_stmt (i);
+      tree res = gimple_phi_result (phi);
+
+      if (is_gimple_reg (res))
+       continue;
+
+      mark_virtual_phi_result_for_renaming (phi);
+      return;
+    }
}

And split out the

  result_var = SSA_NAME_VAR (result_ssa);
  FOR_EACH_IMM_USE_STMT (stmt, iter, result_ssa)
    {
      FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
        SET_USE (use_p, result_var);
      update_stmt (stmt);
      used = true;
    }
  if (used)
    mark_sym_for_renaming (result_var);

part of mark_virtual_phi_result_for_renaming into the new function
mark_virtual_operand_for_renaming (basically rename it and
make mark_virtual_phi_result_for_renaming a wrapper around it,
passing gimple_phi_result).

Ok with a change as suggested above.

Thanks,
Richard.

> Thanks,
> - Tom
>
>> But as I said, I believe handling PHIs should be sufficient?
>>
>> Thanks,
>> Richard.
>>
>>
>>> Thanks,
>>> - Tom
>>>
>>>> Richard.
>>>>
>>>
>
> 2011-10-16  Tom de Vries  <tom@codesourcery.com>
>
>        PR tree-optimization/50672
>        * tree-ssa-tail-merge.c (release_last_vdef): New function.
>        (purge_bbs): Add update_vops parameter.  Call release_last_vdef for each
>        deleted basic block.
>        (tail_merge_optimize): Add argument to call to purge_bbs.
>

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

[Tom de Vries]

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

On 10/17/2011 01:51 PM, Richard Guenther wrote:
> On Sun, Oct 16, 2011 at 12:05 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>> On 10/14/2011 12:00 PM, Richard Guenther wrote:
>>> 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 virtual PHI?
>>
>> Block 20 is deleted. Block 5 follows the deleted block 20. Block 5 does not
>> start with a virtual 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.
>>
>> I think we need to handle the exposed uses (meaning outside the block) of vdefs
>> in each deleted block. The only vdef that can have exposed uses is the last vdef
>> in the block. So we should find the last vdef (gimple with gimple_vdef or
>> virtual PHI) and handle the related uses.
>>
>> Bootstrapped and regtested on x86_64. OK for trunk?
> 
> Hmmm.  I can see that this will fail when the block has a store
> but not a virtual PHI node, thus, when renaming does not reach
> a bare .MEM symbol walking the use-def chain from the VUSE
> of the store.  What release_last_vdef should do is trigger a rename
> of subsequent VUSEs in successors of the deleted block.  Which
> requires you to do something like
> 
> static void
> rename_last_vdef (basic_block bb)
> {
> +  gimple_stmt_iterator i;
> +
> +  for (i = gsi_last_bb (bb); !gsi_end_p (i); gsi_prev_nondebug (&i))
> +    {
> +      gimple stmt = gsi_stmt (i);
> +      if (gimple_vdef (stmt) == NULL_TREE)
> +       continue;
> +
> +      mark_virtual_operand_for_renaming (gimple_vdef (stmt));
>         return;
>       }
> 
> +  for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
> +    {
> +      gimple phi = gsi_stmt (i);
> +      tree res = gimple_phi_result (phi);
> +
> +      if (is_gimple_reg (res))
> +       continue;
> +
> +      mark_virtual_phi_result_for_renaming (phi);
> +      return;
> +    }
> }
> 
> And split out the
> 
>   result_var = SSA_NAME_VAR (result_ssa);
>   FOR_EACH_IMM_USE_STMT (stmt, iter, result_ssa)
>     {
>       FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
>         SET_USE (use_p, result_var);
>       update_stmt (stmt);
>       used = true;
>     }
>   if (used)
>     mark_sym_for_renaming (result_var);
> 
> part of mark_virtual_phi_result_for_renaming into the new function
> mark_virtual_operand_for_renaming (basically rename it and
> make mark_virtual_phi_result_for_renaming a wrapper around it,
> passing gimple_phi_result).
> 
> Ok with a change as suggested above.
> 

Retested on x86_64 and committed.

Thanks,
- Tom

> Thanks,
> Richard.
> 

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

	PR tree-optimization/50672
	* tree-ssa-dce.c (mark_virtual_operand_for_renaming): New function,
	factored out of ...
	(mark_virtual_phi_result_for_renaming): Use
	mark_virtual_operand_for_renaming.
	* tree-flow.h (mark_virtual_operand_for_renaming): Declare.
	* tree-ssa-tail-merge.c (release_last_vdef): New function.
	(purge_bbs): Add update_vops parameter.  Call release_last_vdef for each
	deleted basic block.
	(tail_merge_optimize): Add argument to call to purge_bbs.

[-- Attachment #2: pr50672.4.patch --]
[-- Type: text/x-patch, Size: 3899 bytes --]

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,56 @@ same_succ_flush_bbs (bitmap bbs)
     }
 }
 
+/* Release the last vdef in BB, either normal or phi result.  */
+
+static void
+release_last_vdef (basic_block bb)
+{
+  gimple_stmt_iterator i;
+
+  for (i = gsi_last_bb (bb); !gsi_end_p (i); gsi_prev_nondebug (&i))
+    {
+      gimple stmt = gsi_stmt (i);
+      if (gimple_vdef (stmt) == NULL_TREE)
+	continue;
+
+      mark_virtual_operand_for_renaming (gimple_vdef (stmt));
+      return;
+    }
+
+  for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
+    {
+      gimple phi = gsi_stmt (i);
+      tree res = gimple_phi_result (phi);
+
+      if (is_gimple_reg (res))
+	continue;
+
+      mark_virtual_phi_result_for_renaming (phi);
+      return;
+    }
+  
+}
+
 /* 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_last_vdef (bb);
+
+      delete_basic_block (bb);
+    }
 
   bitmap_and_compl_into (deleted_bb_preds, deleted_bbs);
   bitmap_clear (deleted_bbs);
@@ -1665,7 +1703,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;
Index: gcc/tree-ssa-dce.c
===================================================================
--- gcc/tree-ssa-dce.c (revision 179773)
+++ gcc/tree-ssa-dce.c (working copy)
@@ -982,18 +982,36 @@ propagate_necessity (struct edge_list *e
     }
 }
 
-/* Replace all uses of result of PHI by underlying variable and mark it
+/* Replace all uses of NAME by underlying variable and mark it
    for renaming.  */
 
 void
-mark_virtual_phi_result_for_renaming (gimple phi)
+mark_virtual_operand_for_renaming (tree name)
 {
   bool used = false;
   imm_use_iterator iter;
   use_operand_p use_p;
   gimple stmt;
-  tree result_ssa, result_var;
+  tree name_var;
+
+  name_var = SSA_NAME_VAR (name);
+  FOR_EACH_IMM_USE_STMT (stmt, iter, name)
+    {
+      FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
+        SET_USE (use_p, name_var);
+      update_stmt (stmt);
+      used = true;
+    }
+  if (used)
+    mark_sym_for_renaming (name_var);
+}
 
+/* Replace all uses of result of PHI by underlying variable and mark it
+   for renaming.  */
+
+void
+mark_virtual_phi_result_for_renaming (gimple phi)
+{
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       fprintf (dump_file, "Marking result for renaming : ");
@@ -1001,19 +1019,10 @@ mark_virtual_phi_result_for_renaming (gi
       fprintf (dump_file, "\n");
     }
 
-  result_ssa = gimple_phi_result (phi);
-  result_var = SSA_NAME_VAR (result_ssa);
-  FOR_EACH_IMM_USE_STMT (stmt, iter, result_ssa)
-    {
-      FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
-        SET_USE (use_p, result_var);
-      update_stmt (stmt);
-      used = true;
-    }
-  if (used)
-    mark_sym_for_renaming (result_var);
+  mark_virtual_operand_for_renaming (gimple_phi_result (phi));
 }
 
+
 /* Remove dead PHI nodes from block BB.  */
 
 static bool
Index: gcc/tree-flow.h
===================================================================
--- gcc/tree-flow.h (revision 179773)
+++ gcc/tree-flow.h (working copy)
@@ -715,6 +715,7 @@ bool stmt_dominates_stmt_p (gimple, gimp
 void mark_virtual_ops_for_renaming (gimple);
 
 /* In tree-ssa-dce.c */
+void mark_virtual_operand_for_renaming (tree);
 void mark_virtual_phi_result_for_renaming (gimple);
 
 /* In tree-ssa-threadedge.c */

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

[Tom de Vries]

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

On 10/18/2011 11:06 AM, Tom de Vries wrote:
> On 10/17/2011 01:51 PM, Richard Guenther wrote:
>> On Sun, Oct 16, 2011 at 12:05 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>>> On 10/14/2011 12:00 PM, Richard Guenther wrote:
>>>> 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 virtual PHI?
>>>
>>> Block 20 is deleted. Block 5 follows the deleted block 20. Block 5 does not
>>> start with a virtual 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.
>>>
>>> I think we need to handle the exposed uses (meaning outside the block) of vdefs
>>> in each deleted block. The only vdef that can have exposed uses is the last vdef
>>> in the block. So we should find the last vdef (gimple with gimple_vdef or
>>> virtual PHI) and handle the related uses.
>>>
>>> Bootstrapped and regtested on x86_64. OK for trunk?
>>
>> Hmmm.  I can see that this will fail when the block has a store
>> but not a virtual PHI node, thus, when renaming does not reach
>> a bare .MEM symbol walking the use-def chain from the VUSE
>> of the store.  What release_last_vdef should do is trigger a rename
>> of subsequent VUSEs in successors of the deleted block.  Which
>> requires you to do something like
>>
>> static void
>> rename_last_vdef (basic_block bb)
>> {
>> +  gimple_stmt_iterator i;
>> +
>> +  for (i = gsi_last_bb (bb); !gsi_end_p (i); gsi_prev_nondebug (&i))
>> +    {
>> +      gimple stmt = gsi_stmt (i);
>> +      if (gimple_vdef (stmt) == NULL_TREE)
>> +       continue;
>> +
>> +      mark_virtual_operand_for_renaming (gimple_vdef (stmt));
>>         return;
>>       }
>>
>> +  for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
>> +    {
>> +      gimple phi = gsi_stmt (i);
>> +      tree res = gimple_phi_result (phi);
>> +
>> +      if (is_gimple_reg (res))
>> +       continue;
>> +
>> +      mark_virtual_phi_result_for_renaming (phi);
>> +      return;
>> +    }
>> }
>>
>> And split out the
>>
>>   result_var = SSA_NAME_VAR (result_ssa);
>>   FOR_EACH_IMM_USE_STMT (stmt, iter, result_ssa)
>>     {
>>       FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
>>         SET_USE (use_p, result_var);
>>       update_stmt (stmt);
>>       used = true;
>>     }
>>   if (used)
>>     mark_sym_for_renaming (result_var);
>>
>> part of mark_virtual_phi_result_for_renaming into the new function
>> mark_virtual_operand_for_renaming (basically rename it and
>> make mark_virtual_phi_result_for_renaming a wrapper around it,
>> passing gimple_phi_result).
>>
>> Ok with a change as suggested above.
>>
> 

Committed test-case.

Thanks,
- Tom

2011-11-02  Tom de Vries  <tom@codesourcery.com>

	PR tree-optimization/50672
	* g++.dg/pr50672.C: New test.


[-- Attachment #2: pr50672.test.patch --]
[-- Type: text/x-patch, Size: 3444 bytes --]

Index: gcc/testsuite/g++.dg/pr50672.C
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/g++.dg/pr50672.C (revision 0)
@@ -0,0 +1,101 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftree-tail-merge" } */
+typedef int BoxCoordinate;
+typedef int BoxDimension;
+const BoxDimension X = 0;
+const BoxDimension Y = 1;
+const BoxDimension NDimensions = 2;
+class BoxPoint {
+    BoxCoordinate point[NDimensions];
+public:
+    bool isValid() const;
+    void operator += (const BoxPoint& p)     {
+        if (isValid() && p.isValid())  {
+            point[X] += p.point[X];
+        }
+    }
+    const BoxCoordinate& operator [] (const BoxDimension& dimension) const {
+        return point[dimension];
+    }
+};
+class BoxRegion {
+public:
+    BoxCoordinate& origin(BoxDimension d) const;
+    BoxCoordinate& space(BoxDimension d) const;
+};
+inline bool operator <= (const BoxPoint& p, const BoxRegion& r) {
+    for (BoxDimension d = X;
+         d <= Y;
+         d++)  if (p[d] < r.origin(d) || p[d] >= r.origin(d) + r.space(d))     
+return false;
+    return true;
+}
+typedef struct _WidgetRec *Widget;
+struct GraphGC {
+    BoxPoint offsetIfSelected;
+};
+class GraphNode;
+class GraphEdge {
+public:
+    GraphNode *from() const;
+    GraphNode *to() const;
+};
+class LineGraphEdge: public GraphEdge {
+protected:
+    virtual void drawLine(Widget w,      const GraphGC& gc) const;
+    void _print(const GraphGC &gc) const;
+};
+class ArcGraphEdge: public LineGraphEdge {
+    static bool center(const BoxPoint& p1, const BoxPoint& p2,
+                       const BoxPoint& p3, double& x, double& y);
+    void makeLine(Widget w,     const GraphGC& gc) const;
+};
+class GraphNode {
+public:
+    bool& selected();
+    GraphEdge *firstTo() const;
+    GraphEdge *nextTo(GraphEdge *ref) const;
+    virtual const BoxPoint& pos() const = 0;
+    virtual const BoxRegion& region(const GraphGC& gc) const = 0;
+    virtual bool isHint() const;
+};
+class PosGraphNode: public GraphNode { };
+class RegionGraphNode: public PosGraphNode { };
+class HintGraphNode: public RegionGraphNode { };
+void ArcGraphEdge::makeLine(Widget w, const GraphGC& gc) const {
+    HintGraphNode *arc_hint = 0;
+    RegionGraphNode *arc_from = 0;
+    RegionGraphNode *arc_to = 0;
+    bool make_arc = true;
+    if (from()->isHint() && to()->isHint())     {
+        make_arc = false;
+    }
+    else if (from()->isHint() && from()->firstTo() != 0)     {
+        if (arc_hint == 0 || arc_from == 0 || arc_to == 0
+            || arc_hint->nextTo(arc_hint->firstTo()) != 0)  {
+            make_arc = false;
+        }
+    }
+    if (!make_arc)     {
+        if (w != 0)      LineGraphEdge::drawLine(w, gc);
+        else      LineGraphEdge::_print(gc);
+        return;
+    }
+    BoxPoint pos_from = arc_from->pos();
+    BoxRegion region_from = arc_from->region(gc);
+    BoxPoint pos_to = arc_to->pos();
+    BoxRegion region_to = arc_to->region(gc);
+    BoxPoint pos_hint = arc_hint->pos();
+    if (arc_hint->selected())     {
+        pos_hint += gc.offsetIfSelected;
+    }
+    if (pos_hint <= region_from || pos_hint <= region_to)     {
+        return;
+    }
+    double cx, cy;
+    bool ok = center(pos_from, pos_hint, pos_to, cx, cy);
+    if (!ok)     {
+        if (w != 0)      LineGraphEdge::drawLine(w, gc);
+        else      LineGraphEdge::_print(gc);
+    }
+}