From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 1539 invoked by alias); 17 Feb 2015 14:58:34 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 1529 invoked by uid 89); 17 Feb 2015 14:58:33 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-3.2 required=5.0 tests=AWL,BAYES_00,T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-HELO: mx2.suse.de Received: from cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (CAMELLIA256-SHA encrypted) ESMTPS; Tue, 17 Feb 2015 14:58:32 +0000 Received: from relay1.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 1889FACA9; Tue, 17 Feb 2015 14:58:29 +0000 (UTC) Date: Tue, 17 Feb 2015 14:58:00 -0000 From: Richard Biener To: gcc-patches@gcc.gnu.org cc: law@redhat.com Subject: Re: [PATCH] Properly valueize values we value-number to In-Reply-To: Message-ID: References: User-Agent: Alpine 2.11 (LSU 23 2013-08-11) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-SW-Source: 2015-02/txt/msg01024.txt.bz2 On Tue, 17 Feb 2015, Richard Biener wrote: > > This is something I noticed some time ago and that I remembered when > you added that looping SSA_NAME_VALUE to simplify_control_stmt_condition. > Currently DOM doesn't make sure that when setting > SSA_NAME_VALUE (x) = y that SSA_NAME_VALUE (y) == y, thus you could > get SSA_NAME_VALUE forming a chain until you reach the final value. > > Thus the following patch which fixes all occurances and removes the > looping from simplify_control_stmt_condition. Did you have any > testcase when you added that looping? > > Note that this is purely by code inspection and I don't have any > testcase where a SSA_NAME_VALUE chain causes missed optimizations > (you'd have to disable a lot of other optimizations before dom1 > to be able to create a reasonably simple one). > > Anyway - the tree-ssa-dom.c part bootstrapped and tested ok on > x86_64-unknown-linux-gnu, the tree-ssa-threadedge.c part bootstrapped > ok ontop of that and testing is still in progress. On a closer look the record_const_or_copy_1 hunk is redundant (record_equality is really a bit obfuscated...). And record_equality is where the SSA_NAME_VALUEs might end up forming chains? At least because we might record a SSA_NAME_VALUE for sth that might be the target of a SSA_NAME_VALUE, as in a_1 = b_2; SSA_NAME_VALUE (a_1) == b_2; if (b_2 == i_3(D)) ... temporarily SSA_NAME_VALUE (b_2) == i_3(D) thus under if (b_2 == i_3(D)) SSA_NAME_VALUE (a_1) == b_2 and SSA_NAME_VALUE (SSA_NAME_VALUE (a_1)) == i_3(D)? I guess we can't easily avoid that because we don't keep track of a reverse mapping (nor would we want to update that). Btw, in record_equality, the == part of the <= check for the loop depth will just randomly swap x and y while we should prefer IL canonical order. If we can't rely on the input being in IL canonical order we should prepend the whole function with if (tree_swap_operands_p (x, y, false)) std::swap (x, y); and change <= to < for the loop-depth check. For PR62217 it is that loop depth check which causes the equivalence to be recorded that ends up being harmful (well, harmful is the actual propagation of course). Btw, we already inhibit propagation into IV increments (cprop_operand) - so it looks like we may want to inhibit BIV replacement completely instead? Index: gcc/tree-ssa-dom.c =================================================================== --- gcc/tree-ssa-dom.c (revision 220755) +++ gcc/tree-ssa-dom.c (working copy) @@ -2291,11 +2291,16 @@ cprop_operand (gimple stmt, use_operand_ if (!may_propagate_copy (op, val)) return; - /* Do not propagate copies into simple IV increment statements. - See PR23821 for how this can disturb IV analysis. */ - if (TREE_CODE (val) != INTEGER_CST - && simple_iv_increment_p (stmt)) - return; + /* Do not propagate copies into BIVs. + See PR23821 and PR62217 for how this can disturb IV and + number of iteration analysis. */ + if (TREE_CODE (val) != INTEGER_CST) + { + gimple def = SSA_NAME_DEF_STMT (op); + if (gimple_code (def) == GIMPLE_PHI + && gimple_bb (def)->loop_father->header == gimple_bb (def)) + return; + } /* Dump details. */ if (dump_file && (dump_flags & TDF_DETAILS)) So it would just extend an existing heuristic. Richard. > Ok? > > Thanks, > Richard. > > 2015-02-17 Richard Biener > > * tree-ssa-dom.c (record_equivalences_from_phis): Valueize PHI arg. > (record_const_or_copy_1): Valueize y. > (record_equivalences_from_stmt): Valueize rhs. > * tree-ssa-threadedge.c (simplify_control_stmt_condition): > Remove repeated valueization. > > Index: gcc/tree-ssa-dom.c > =================================================================== > --- gcc/tree-ssa-dom.c (revision 220751) > +++ gcc/tree-ssa-dom.c (working copy) > @@ -1223,6 +1223,13 @@ record_equivalences_from_phis (basic_blo > if (lhs == t) > continue; > > + /* Valueize t. */ > + if (TREE_CODE (t) == SSA_NAME) > + { > + tree tmp = SSA_NAME_VALUE (t); > + t = tmp ? tmp : t; > + } > + > /* If we have not processed an alternative yet, then set > RHS to this alternative. */ > if (rhs == NULL) > @@ -1566,6 +1573,13 @@ record_conditions (struct edge_info *edg > static void > record_const_or_copy_1 (tree x, tree y, tree prev_x) > { > + /* Valueize y. */ > + if (TREE_CODE (y) == SSA_NAME) > + { > + tree tmp = SSA_NAME_VALUE (y); > + y = tmp ? tmp : y; > + } > + > set_ssa_name_value (x, y); > > if (dump_file && (dump_flags & TDF_DETAILS)) > @@ -2184,18 +2198,25 @@ record_equivalences_from_stmt (gimple st > if (may_optimize_p > && (TREE_CODE (rhs) == SSA_NAME > || is_gimple_min_invariant (rhs))) > - { > - if (dump_file && (dump_flags & TDF_DETAILS)) > - { > - fprintf (dump_file, "==== ASGN "); > - print_generic_expr (dump_file, lhs, 0); > - fprintf (dump_file, " = "); > - print_generic_expr (dump_file, rhs, 0); > - fprintf (dump_file, "\n"); > - } > + { > + /* Valueize rhs. */ > + if (TREE_CODE (rhs) == SSA_NAME) > + { > + tree tmp = SSA_NAME_VALUE (rhs); > + rhs = tmp ? tmp : rhs; > + } > > - set_ssa_name_value (lhs, rhs); > - } > + if (dump_file && (dump_flags & TDF_DETAILS)) > + { > + fprintf (dump_file, "==== ASGN "); > + print_generic_expr (dump_file, lhs, 0); > + fprintf (dump_file, " = "); > + print_generic_expr (dump_file, rhs, 0); > + fprintf (dump_file, "\n"); > + } > + > + set_ssa_name_value (lhs, rhs); > + } > } > > /* Make sure we can propagate &x + CST. */ > Index: gcc/tree-ssa-threadedge.c > =================================================================== > --- gcc/tree-ssa-threadedge.c (revision 220751) > +++ gcc/tree-ssa-threadedge.c (working copy) > @@ -591,29 +591,13 @@ simplify_control_stmt_condition (edge e, > cond_code = gimple_cond_code (stmt); > > /* Get the current value of both operands. */ > - if (TREE_CODE (op0) == SSA_NAME) > - { > - for (int i = 0; i < 2; i++) > - { > - if (TREE_CODE (op0) == SSA_NAME > - && SSA_NAME_VALUE (op0)) > - op0 = SSA_NAME_VALUE (op0); > - else > - break; > - } > - } > - > - if (TREE_CODE (op1) == SSA_NAME) > - { > - for (int i = 0; i < 2; i++) > - { > - if (TREE_CODE (op1) == SSA_NAME > - && SSA_NAME_VALUE (op1)) > - op1 = SSA_NAME_VALUE (op1); > - else > - break; > - } > - } > + if (TREE_CODE (op0) == SSA_NAME > + && SSA_NAME_VALUE (op0)) > + op0 = SSA_NAME_VALUE (op0); > + > + if (TREE_CODE (op1) == SSA_NAME > + && SSA_NAME_VALUE (op1)) > + op1 = SSA_NAME_VALUE (op1); > > if (handle_dominating_asserts) > { > @@ -682,22 +666,11 @@ simplify_control_stmt_condition (edge e, > tree original_lhs = cond; > cached_lhs = cond; > > - /* Get the variable's current value from the equivalence chains. > - > - It is possible to get loops in the SSA_NAME_VALUE chains > - (consider threading the backedge of a loop where we have > - a loop invariant SSA_NAME used in the condition. */ > - if (cached_lhs) > - { > - for (int i = 0; i < 2; i++) > - { > - if (TREE_CODE (cached_lhs) == SSA_NAME > - && SSA_NAME_VALUE (cached_lhs)) > - cached_lhs = SSA_NAME_VALUE (cached_lhs); > - else > - break; > - } > - } > + /* Get the variable's current value from the equivalence chains. */ > + if (cached_lhs > + && TREE_CODE (cached_lhs) == SSA_NAME > + && SSA_NAME_VALUE (cached_lhs)) > + cached_lhs = SSA_NAME_VALUE (cached_lhs); > > /* If we're dominated by a suitable ASSERT_EXPR, then > update CACHED_LHS appropriately. */ > -- Richard Biener SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Jennifer Guild, Dilip Upmanyu, Graham Norton HRB 21284 (AG Nuernberg)