From patchwork Fri Sep 14 09:43:48 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 183860 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 01CD62C0080 for ; Fri, 14 Sep 2012 19:47:01 +1000 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1348220822; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Date: From:To:Cc:Subject:In-Reply-To:Message-ID:References:User-Agent: MIME-Version:Content-Type:Mailing-List:Precedence:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:Sender: Delivered-To; bh=qtIOaZqiB2mh6uySXZ13SM4WEGQ=; b=MichUEPcnEwyBib LS/47VR+9sCEUEy8La2d8pbMyAd/CtZ1eiaNFGsQUL0Xc/gXYuoFNTsmAzf3mSy+ w60Qxm3+ZvhHjkymxx/2LMM288kHbRnTBv+R9NpKBcGetUgyvwaQfEe3hjozKZ3D SbgKd6phn1RUMStbLTp7UJkWt+5Y= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Date:From:To:Cc:Subject:In-Reply-To:Message-ID:References:User-Agent:MIME-Version:Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=qCXrylbcC91X/wPDw+/ALCMiTM0jxYAOWf18uKjI4HgeW2H1FTePdSuFfStTHR mBKQ+m2gq1DxQyviNly+fh30t5wmLGAqmO7FLhMdrMVmFXqxnIkaXcUVrIEwCsaS zlgLnK0Kqr4Ud3u9JAWEUwtHbcgskwxjzXK6OtvhvqRBQ=; Received: (qmail 28878 invoked by alias); 14 Sep 2012 09:46:58 -0000 Received: (qmail 28869 invoked by uid 22791); 14 Sep 2012 09:46:56 -0000 X-SWARE-Spam-Status: No, hits=-6.4 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, KHOP_THREADED, RCVD_IN_DNSWL_HI, RP_MATCHES_RCVD, TW_TM X-Spam-Check-By: sourceware.org Received: from cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 14 Sep 2012 09:46:41 +0000 Received: from relay1.suse.de (unknown [195.135.220.254]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mx2.suse.de (Postfix) with ESMTP id 239BBA2111; Fri, 14 Sep 2012 11:46:40 +0200 (CEST) Date: Fri, 14 Sep 2012 11:43:48 +0200 (CEST) From: Richard Guenther To: Steven Bosscher Cc: gcc-patches@gcc.gnu.org Subject: Re: [PATCH] Fix PR54489 - FRE needing AVAIL_OUT In-Reply-To: Message-ID: References: User-Agent: Alpine 2.00 (LNX 1167 2008-08-23) MIME-Version: 1.0 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 Fri, 14 Sep 2012, Richard Guenther wrote: > On Thu, 13 Sep 2012, Steven Bosscher wrote: > > > On Wed, Sep 12, 2012 at 4:52 PM, Steven Bosscher wrote: > > > On Wed, Sep 12, 2012 at 4:02 PM, Richard Guenther wrote: > > >> for a followup (and I bet sth else than PRE blows up at -O2 as well). > > > > > > Actually, the only thing that really blows up is that enemy of scalability, VRP. > > > > FWIW, this appears to be due to the well-known problem with the equiv > > set, but also due to the liveness computations that tree-vrp performs, > > since your commit in r139263. > > > > Any reason why you didn't just re-use the tree-ssa-live machinery? > > Probably I didn't know about it or didn't want to keep the full life > problem life (it tries to free things as soon as possible). > > > And any reason why you don't let a DEF kill a live SSA name? AFAICT > > you're exposing all SSA names up without ever killing a USE :-) > > Eh ;) We also should traverse blocks backward I suppose. Also > the RPO traversal suffers from the same issue I noticed in PRE > and for what I invented my_rev_post_order_compute ... > (pre_and_rev_post_order_compute doesn't compute an optimal > reverse post order). > > Patch fixing the liveness below, untested sofar, apart from on > tree-ssa.exp where it seems to regress gcc.dg/tree-ssa/pr21086.c :/ The following not. Queued for testing (though I doubt it will help memory usage due to the use of sbitmaps). I think jump threading special-casing asserts and the equiv bitmaps are the real problem of VRP. What testcase did you notice the live issue on? Thanks, Richard. 2012-09-14 Richard Guenther * tree-vrp.c (register_new_assert_for): Simplify for backward walk. (find_assert_locations_1): Walk the basic-block backwards, properly add/prune from live. Use live for asserts derived from stmts. Index: gcc/tree-vrp.c =================================================================== --- gcc/tree-vrp.c (revision 191289) +++ gcc/tree-vrp.c (working copy) @@ -4384,24 +4384,7 @@ register_new_assert_for (tree name, tree && (loc->expr == expr || operand_equal_p (loc->expr, expr, 0))) { - /* If the assertion NAME COMP_CODE VAL has already been - registered at a basic block that dominates DEST_BB, then - we don't need to insert the same assertion again. Note - that we don't check strict dominance here to avoid - replicating the same assertion inside the same basic - block more than once (e.g., when a pointer is - dereferenced several times inside a block). - - An exception to this rule are edge insertions. If the - new assertion is to be inserted on edge E, then it will - dominate all the other insertions that we may want to - insert in DEST_BB. So, if we are doing an edge - insertion, don't do this dominance check. */ - if (e == NULL - && dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb)) - return; - - /* Otherwise, if E is not a critical edge and DEST_BB + /* If E is not a critical edge and DEST_BB dominates the existing location for the assertion, move the assertion up in the dominance tree by updating its location information. */ @@ -5439,7 +5422,6 @@ find_assert_locations_1 (basic_block bb, { gimple_stmt_iterator si; gimple last; - gimple phi; bool need_assert; need_assert = false; @@ -5462,7 +5444,7 @@ find_assert_locations_1 (basic_block bb, /* Traverse all the statements in BB marking used names and looking for statements that may infer assertions for their used operands. */ - for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) + for (si = gsi_last_bb (bb); !gsi_end_p (si); gsi_prev (&si)) { gimple stmt; tree op; @@ -5479,8 +5461,10 @@ find_assert_locations_1 (basic_block bb, tree value; enum tree_code comp_code; - /* Mark OP in our live bitmap. */ - SET_BIT (live, SSA_NAME_VERSION (op)); + /* If op is not live beyond this stmt, do not bother to insert + asserts for it. */ + if (!TEST_BIT (live, SSA_NAME_VERSION (op))) + continue; /* If OP is used in such a way that we can infer a value range for it, and we don't find a previous assertion for @@ -5520,25 +5504,28 @@ find_assert_locations_1 (basic_block bb, } } - /* If OP is used only once, namely in this STMT, don't - bother creating an ASSERT_EXPR for it. Such an - ASSERT_EXPR would do nothing but increase compile time. */ - if (!has_single_use (op)) - { - register_new_assert_for (op, op, comp_code, value, - bb, NULL, si); - need_assert = true; - } + register_new_assert_for (op, op, comp_code, value, bb, NULL, si); + need_assert = true; } } + + /* Update live. */ + FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE) + SET_BIT (live, SSA_NAME_VERSION (op)); + FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF) + RESET_BIT (live, SSA_NAME_VERSION (op)); } - /* Traverse all PHI nodes in BB marking used operands. */ + /* Traverse all PHI nodes in BB, updating live. */ for (si = gsi_start_phis (bb); !gsi_end_p(si); gsi_next (&si)) { use_operand_p arg_p; ssa_op_iter i; - phi = gsi_stmt (si); + gimple phi = gsi_stmt (si); + tree res = gimple_phi_result (phi); + + if (virtual_operand_p (res)) + continue; FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE) { @@ -5546,6 +5533,8 @@ find_assert_locations_1 (basic_block bb, if (TREE_CODE (arg) == SSA_NAME) SET_BIT (live, SSA_NAME_VERSION (arg)); } + + RESET_BIT (live, SSA_NAME_VERSION (res)); } return need_assert;