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 <[email protected]>
>> wrote:
>>> On 10/14/2011 12:00 PM, Richard Guenther wrote:
>>>> On Fri, Oct 14, 2011 at 1:12 AM, Tom de Vries <[email protected]>
>>>> wrote:
>>>>> On 10/12/2011 02:19 PM, Richard Guenther wrote:
>>>>>> On Wed, Oct 12, 2011 at 8:35 AM, Tom de Vries <[email protected]>
>>>>>> 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 <[email protected]>
PR tree-optimization/50672
* g++.dg/pr50672.C: New test.
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);
+ }
+}
