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 Nov. 2, 2011, 4:30 p.m.
Message ID <4EB17021.60701@mentor.com>
Download mbox | patch
Permalink /patch/123289/
State New
Headers show

Comments

Tom de Vries - Nov. 2, 2011, 4:30 p.m.
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.

Patch

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);
+    }
+}