From patchwork Wed Nov 2 16:30:25 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom de Vries X-Patchwork-Id: 123289 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 2B371B6F7B for ; Thu, 3 Nov 2011 03:31:49 +1100 (EST) Received: (qmail 27435 invoked by alias); 2 Nov 2011 16:31:39 -0000 Received: (qmail 27417 invoked by uid 22791); 2 Nov 2011 16:31:33 -0000 X-SWARE-Spam-Status: No, hits=-1.7 required=5.0 tests=AWL,BAYES_00,TW_TM X-Spam-Check-By: sourceware.org Received: from relay1.mentorg.com (HELO relay1.mentorg.com) (192.94.38.131) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 02 Nov 2011 16:31:17 +0000 Received: from svr-orw-fem-01.mgc.mentorg.com ([147.34.98.93]) by relay1.mentorg.com with esmtp id 1RLdie-0005BZ-QG from Tom_deVries@mentor.com ; Wed, 02 Nov 2011 09:31:16 -0700 Received: from SVR-IES-FEM-01.mgc.mentorg.com ([137.202.0.104]) by svr-orw-fem-01.mgc.mentorg.com over TLS secured channel with Microsoft SMTPSVC(6.0.3790.4675); Wed, 2 Nov 2011 09:31:16 -0700 Received: from [127.0.0.1] (137.202.0.76) by SVR-IES-FEM-01.mgc.mentorg.com (137.202.0.104) with Microsoft SMTP Server id 14.1.289.1; Wed, 2 Nov 2011 16:31:13 +0000 Message-ID: <4EB17021.60701@mentor.com> Date: Wed, 2 Nov 2011 17:30:25 +0100 From: Tom de Vries User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.23) Gecko/20110922 Lightning/1.0b2 Thunderbird/3.1.15 MIME-Version: 1.0 To: Richard Guenther CC: Tom de Vries , "gcc-patches@gcc.gnu.org" Subject: Re: [PR50672, PATCH] Fix ice triggered by -ftree-tail-merge: verify_ssa failed: no immediate_use list References: <4E953540.3010807@codesourcery.com> <4E97705E.6070205@mentor.com> <4E9AAC50.4000000@mentor.com> <4E9D419A.3080201@mentor.com> In-Reply-To: <4E9D419A.3080201@mentor.com> Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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 wrote: >>> On 10/14/2011 12:00 PM, Richard Guenther wrote: >>>> On Fri, Oct 14, 2011 at 1:12 AM, Tom de Vries wrote: >>>>> On 10/12/2011 02:19 PM, Richard Guenther wrote: >>>>>> On Wed, Oct 12, 2011 at 8:35 AM, Tom de Vries 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 ; >>>>>>> else >>>>>>> goto ; >>>>>>> # 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 ; >>>>>>> else >>>>>>> goto ; >>>>>>> # 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 ; >>>>>>> # 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 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); + } +}