From patchwork Wed Jan 25 05:36:49 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrew Pinski X-Patchwork-Id: 137709 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 CE45AB6F98 for ; Wed, 25 Jan 2012 16:37:16 +1100 (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=1328074638; h=Comment: DomainKey-Signature:Received:Received:Received:Received: MIME-Version:Received:Received:Date:Message-ID:Subject:From:To: Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:Sender:Delivered-To; bh=JPisgor 8YysxJ/Pp58PwCXd9FG4=; b=pgCnWCbSZ2rQFVFMF7UbjzXN0NrByQBtcgmUUVN 6Y+VpQe/sv9RoFkGYCzxOVu+ouxPe/PqZTjmFwAFtvwrY+miz5WwHohORiVFuNRW QRFZ/8J/ljBFuPX3Erw6nxaqckTCsWhwu/p1ocQK99LVakHRh+xeC59ZOzUCtdNR vWEI= 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:MIME-Version:Received:Received:Date:Message-ID:Subject:From:To:Content-Type:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=AwSUUsT+9LCAc71g569v2O42dInNckp0aA26KgRi4ITGuQhkXDYdma5DRhQNAX CFkljTJIhUrA29QnUVPk3x+tbe1X74ZRdenQys1phtFopFxQn0M4bPYLmRAoLCfC 9hSUBSUp6HzDyOMCzlsKKxRKPNNct3U4fOz6nkNg2F7pI=; Received: (qmail 21610 invoked by alias); 25 Jan 2012 05:37:08 -0000 Received: (qmail 21322 invoked by uid 22791); 25 Jan 2012 05:37:05 -0000 X-SWARE-Spam-Status: No, hits=-1.3 required=5.0 tests=AWL, BAYES_20, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, TW_CF, TW_TM X-Spam-Check-By: sourceware.org Received: from mail-we0-f175.google.com (HELO mail-we0-f175.google.com) (74.125.82.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 25 Jan 2012 05:36:50 +0000 Received: by werc1 with SMTP id c1so2585730wer.20 for ; Tue, 24 Jan 2012 21:36:49 -0800 (PST) MIME-Version: 1.0 Received: by 10.216.131.78 with SMTP id l56mr2684684wei.56.1327469809471; Tue, 24 Jan 2012 21:36:49 -0800 (PST) Received: by 10.216.12.209 with HTTP; Tue, 24 Jan 2012 21:36:49 -0800 (PST) Date: Tue, 24 Jan 2012 21:36:49 -0800 Message-ID: Subject: [PATCH] Partially fix 51988: value_replacement in PHIOPT should handle even the cases where there are other PHIs even with non equal value From: Andrew Pinski To: GCC Patches X-IsSubscribed: yes 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 Hi, value_replacement in PHIOPT currently works only when there is one PHI (which is non virtual). http://gcc.gnu.org/ml/gcc-patches/2012-01/msg01195.html improves the situation but we can improve it even more as replacing a PHI argument with a SSA_NAME is almost always a benefit. This patch improves the situation even more for value replacement (though it does not fix all the cases I wanted to fix but that would require much more rewrite of phiopt that I was willing to take on right now, see the bug report for the two testcases where we miss still). We improve the situation by just going through all the PHIs and seeing if we want to do value replacement and only remove the middle basic block if it is empty or we used the only assignment in the PHI (for if(p)a=&p->a;else a= 0; case). OK for 4.8? Bootstrapped and tested on x86_64-linux-gnu with no regressions. Note I have two improvements when both this and http://gcc.gnu.org/ml/gcc-patches/2012-01/msg01195.html are applied; remove the xfail and instead of gimple_seq_singleton_p use the new single_non_singleton_phi_for_edges (I will test that patch after both are applied). Currently these patches are independent and I want to keep it that way. Thanks, Andrew Pinski ChangeLog: * tree-ssa-phiopt.c: Include tree-pretty-print.h for print_generic_expr. (tree_ssa_phiopt_worker): Go through all the PHIs for value_replacement instead of just the singleton one. (value_replacement): Change return type to int. Return 0 instead of false. Allow the middle basic block to contain more than just the defining statement. Handle non empty middle basic blocks. * Makefile.in (tree-ssa-phiopt.o): Add tree-pretty-print.h testsuite/ChangeLog: * gcc.dg/tree-ssa/phi-opt-8.c: New testcase. * gcc.dg/tree-ssa/phi-opt-9.c: New testcase. Index: testsuite/gcc.dg/tree-ssa/phi-opt-8.c =================================================================== --- testsuite/gcc.dg/tree-ssa/phi-opt-8.c (revision 0) +++ testsuite/gcc.dg/tree-ssa/phi-opt-8.c (revision 0) @@ -0,0 +1,26 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-optimized -fdump-tree-phiopt1" } */ + +int g(int,int); +int f(int t, int c) +{ + int d = 0; + int e = 0; + if (t) + { + d = 1; + e = t; + } + else d = 0, e = 0; + return g(e,d); +} + +/* This testcase should be reduced to e = t; d = t != 0; in phiopt1 + but currently is not as PHI-OPT does not reduce the t PHI as we have + two phis. Note this is fixed with + http://gcc.gnu.org/ml/gcc-patches/2012-01/msg01195.html . */ +/* { dg-final { scan-tree-dump-not "if" "phiopt1" { xfail *-*-* } } } */ +/* { dg-final { scan-tree-dump "g .t_\[0-9\]*.D.," "optimized" } } */ +/* { dg-final { scan-tree-dump-times 0 "PHI" "optimized" } } */ +/* { dg-final { cleanup-tree-dump "phiopt1" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: testsuite/gcc.dg/tree-ssa/phi-opt-9.c =================================================================== --- testsuite/gcc.dg/tree-ssa/phi-opt-9.c (revision 0) +++ testsuite/gcc.dg/tree-ssa/phi-opt-9.c (revision 0) @@ -0,0 +1,21 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-optimized" } */ + +int g(int,int); +int f(int t, int c) +{ + int d = 0; + int e = 0; + if (t) + { + d = c+1; + e = t; + } + else d = 0, e = 0; + return g(e,d); +} + +/* The value e should have been replaced with t and there should be only one PHI. */ +/* { dg-final { scan-tree-dump "g .t_\[0-9\]*.D.," "optimized" } } */ +/* { dg-final { scan-tree-dump-times 1 "PHI" "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: tree-ssa-phiopt.c =================================================================== --- tree-ssa-phiopt.c (revision 183507) +++ tree-ssa-phiopt.c (working copy) @@ -36,13 +36,14 @@ along with GCC; see the file COPYING3. #include "domwalk.h" #include "cfgloop.h" #include "tree-data-ref.h" +#include "tree-pretty-print.h" static unsigned int tree_ssa_phiopt (void); static unsigned int tree_ssa_phiopt_worker (bool); static bool conditional_replacement (basic_block, basic_block, edge, edge, gimple, tree, tree); -static bool value_replacement (basic_block, basic_block, - edge, edge, gimple, tree, tree); +static int value_replacement (basic_block, basic_block, + edge, edge, gimple, tree, tree); static bool minmax_replacement (basic_block, basic_block, edge, edge, gimple, tree, tree); static bool abs_replacement (basic_block, basic_block, @@ -314,7 +315,24 @@ tree_ssa_phiopt_worker (bool do_store_el { gimple_seq phis = phi_nodes (bb2); gimple_stmt_iterator gsi; + bool candorest = true; + /* Value replacement can work with more than one PHI + so try that first. */ + for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi)) + { + phi = gsi_stmt (gsi); + arg0 = gimple_phi_arg_def (phi, e1->dest_idx); + arg1 = gimple_phi_arg_def (phi, e2->dest_idx); + if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1) == 2) + { + candorest = false; + cfgchanged = true; + break; + } + } + if (!candorest) + continue; /* Check to make sure that there is only one non-virtual PHI node. TODO: we could do it with more than one iff the other PHI nodes have the same elements for these two edges. */ @@ -343,8 +361,6 @@ tree_ssa_phiopt_worker (bool do_store_el /* Do the replacement of conditional if it can be done. */ if (conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) cfgchanged = true; - else if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) - cfgchanged = true; else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) cfgchanged = true; else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) @@ -624,12 +640,12 @@ jump_function_from_stmt (tree *arg, gimp } /* The function value_replacement does the main work of doing the value - replacement. Return true if the replacement is done. Otherwise return - false. + replacement. Return non-zero if the replacement is done. Otherwise return + 0. If we remove the middle basic block, return 2. BB is the basic block where the replacement is going to be done on. ARG0 is argument 0 from the PHI. Likewise for ARG1. */ -static bool +static int value_replacement (basic_block cond_bb, basic_block middle_bb, edge e0, edge e1, gimple phi, tree arg0, tree arg1) @@ -638,37 +654,36 @@ value_replacement (basic_block cond_bb, gimple cond; edge true_edge, false_edge; enum tree_code code; + bool emtpy_or_with_defined_p = true; /* If the type says honor signed zeros we cannot do this optimization. */ if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1)))) - return false; + return 0; - /* Allow a single statement in MIDDLE_BB that defines one of the PHI - arguments. */ + /* If there is a statement in MIDDLE_BB that defines one of the PHI + arguments, then adjust arg0 or arg1. */ gsi = gsi_after_labels (middle_bb); - if (!gsi_end_p (gsi)) + if (!gsi_end_p (gsi) && is_gimple_debug (gsi_stmt (gsi))) + gsi_next_nondebug (&gsi); + while (!gsi_end_p (gsi)) { - if (is_gimple_debug (gsi_stmt (gsi))) - gsi_next_nondebug (&gsi); - if (!gsi_end_p (gsi)) + gimple stmt = gsi_stmt (gsi); + tree lhs; + gsi_next_nondebug (&gsi); + if (!is_gimple_assign (stmt)) { - gimple stmt = gsi_stmt (gsi); - tree lhs; - gsi_next_nondebug (&gsi); - if (!gsi_end_p (gsi)) - return false; - if (!is_gimple_assign (stmt)) - return false; - /* Now try to adjust arg0 or arg1 according to the computation - in the single statement. */ - lhs = gimple_assign_lhs (stmt); - if (!((lhs == arg0 - && jump_function_from_stmt (&arg0, stmt)) - || (lhs == arg1 - && jump_function_from_stmt (&arg1, stmt)))) - return false; + emtpy_or_with_defined_p = false; + continue; } + /* Now try to adjust arg0 or arg1 according to the computation + in the statement. */ + lhs = gimple_assign_lhs (stmt); + if (!(lhs == arg0 + && jump_function_from_stmt (&arg0, stmt)) + || (lhs == arg1 + && jump_function_from_stmt (&arg1, stmt))) + emtpy_or_with_defined_p = false; } cond = last_stmt (cond_bb); @@ -676,7 +691,7 @@ value_replacement (basic_block cond_bb, /* This transformation is only valid for equality comparisons. */ if (code != NE_EXPR && code != EQ_EXPR) - return false; + return 0; /* We need to know which is the true edge and which is the false edge so that we know if have abs or negative abs. */ @@ -720,12 +735,34 @@ value_replacement (basic_block cond_bb, else arg = arg1; - replace_phi_edge_with_variable (cond_bb, e1, phi, arg); + /* If the middle basic block was empty or is defining the + PHI arguments and this is a singleton phi then we can remove + the middle basic block. */ + if (emtpy_or_with_defined_p + && gimple_seq_singleton_p (phi_nodes (gimple_bb (phi)))) + { + replace_phi_edge_with_variable (cond_bb, e1, phi, arg); + /* Note that we optimized this PHI. */ + return 2; + } + else + { + /* Replace the PHI arguments with arg. */ + SET_PHI_ARG_DEF (phi, e0->dest_idx, arg); + SET_PHI_ARG_DEF (phi, e1->dest_idx, arg); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "PHI "); + print_generic_expr (dump_file, gimple_phi_result (phi), 0); + fprintf (dump_file, " reduced for COND_EXPR in block %d to ", cond_bb->index); + print_generic_expr (dump_file, arg, 0); + fprintf (dump_file, ".\n"); + } + return 1; + } - /* Note that we optimized this PHI. */ - return true; } - return false; + return 0; } /* The function minmax_replacement does the main work of doing the minmax Index: Makefile.in =================================================================== --- Makefile.in (revision 183507) +++ Makefile.in (working copy) @@ -2356,7 +2356,7 @@ tree-ssa-phiopt.o : tree-ssa-phiopt.c $( $(TM_H) $(GGC_H) $(TREE_H) $(TM_P_H) $(BASIC_BLOCK_H) \ $(TREE_FLOW_H) $(TREE_PASS_H) $(TREE_DUMP_H) langhooks.h $(FLAGS_H) \ $(DIAGNOSTIC_H) $(TIMEVAR_H) pointer-set.h domwalk.h $(CFGLOOP_H) \ - $(TREE_DATA_REF_H) + $(TREE_DATA_REF_H) tree-pretty-print.h tree-nrv.o : tree-nrv.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \ $(TM_H) $(TREE_H) $(FUNCTION_H) $(BASIC_BLOCK_H) $(FLAGS_H) \ $(DIAGNOSTIC_H) $(TREE_FLOW_H) $(TIMEVAR_H) $(TREE_DUMP_H) $(TREE_PASS_H) \