From patchwork Wed Nov 3 14:51:29 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 70011 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 19B9F1007D2 for ; Thu, 4 Nov 2010 01:51:47 +1100 (EST) Received: (qmail 3819 invoked by alias); 3 Nov 2010 14:51:42 -0000 Received: (qmail 3808 invoked by uid 22791); 3 Nov 2010 14:51:40 -0000 X-SWARE-Spam-Status: No, hits=-6.2 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_HI, SPF_HELO_PASS, TW_CF, TW_TM, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 03 Nov 2010 14:51:34 +0000 Received: from int-mx02.intmail.prod.int.phx2.redhat.com (int-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.12]) by mx1.redhat.com (8.13.8/8.13.8) with ESMTP id oA3EpWmE009440 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Wed, 3 Nov 2010 10:51:32 -0400 Received: from tyan-ft48-01.lab.bos.redhat.com (tyan-ft48-01.lab.bos.redhat.com [10.16.42.4]) by int-mx02.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id oA3EpUCV008302 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Wed, 3 Nov 2010 10:51:32 -0400 Received: from tyan-ft48-01.lab.bos.redhat.com (localhost.localdomain [127.0.0.1]) by tyan-ft48-01.lab.bos.redhat.com (8.14.4/8.14.4) with ESMTP id oA3EpUbc018621; Wed, 3 Nov 2010 15:51:30 +0100 Received: (from jakub@localhost) by tyan-ft48-01.lab.bos.redhat.com (8.14.4/8.14.4/Submit) id oA3EpTXK018619; Wed, 3 Nov 2010 15:51:29 +0100 Date: Wed, 3 Nov 2010 15:51:29 +0100 From: Jakub Jelinek To: Richard Guenther Cc: gcc-patches@gcc.gnu.org Subject: [PATCH] if/else single store sinking in cselim (PR tree-optimization/46009) Message-ID: <20101103145129.GQ29412@tyan-ft48-01.lab.bos.redhat.com> Reply-To: Jakub Jelinek MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) 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! This patch implements store sinking for if (cond) mem = ssa_name_or_invariant1; else mem = ssa_name_or_invariant2; in cselim pass and fixes a few issues in cselim's cond_store_replacement. Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? 2010-11-03 Jakub Jelinek PR tree-optimization/46009 * tree-ssa-phiopt.c (tree_ssa_phiopt_worker): Call cond_if_else_store_replacement if bb1 and bb2 have the same single successor. (cond_store_replacement): Use gimple_assign_single_p, don't check if rhs is SSA_NAME or invariant. Call release_defs for assign. (cond_if_else_store_replacement): New function. * gcc.dg/vect/pr46009.c: New function. Jakub --- gcc/tree-ssa-phiopt.c.jj 2010-11-01 09:07:23.000000000 +0100 +++ gcc/tree-ssa-phiopt.c 2010-11-03 11:52:20.000000000 +0100 @@ -1,6 +1,6 @@ /* Optimization of PHI nodes by converting them into straightline code. - Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, - Inc. + Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 + Free Software Foundation, Inc. This file is part of GCC. @@ -47,6 +47,7 @@ static bool abs_replacement (basic_block edge, edge, gimple, tree, tree); static bool cond_store_replacement (basic_block, basic_block, edge, edge, struct pointer_set_t *); +static bool cond_if_else_store_replacement (basic_block, basic_block, basic_block); static struct pointer_set_t * get_non_trapping (void); static void replace_phi_edge_with_variable (basic_block, edge, gimple, tree); @@ -149,7 +150,7 @@ tree_ssa_phiopt (void) bb0: if (cond) goto bb2; else goto bb1; bb1: - *p = RHS + *p = RHS; bb2: with @@ -160,10 +161,28 @@ tree_ssa_phiopt (void) condtmp' = *p; bb2: condtmp = PHI - *p = condtmp + *p = condtmp; This transformation can only be done under several constraints, - documented below. */ + documented below. It also replaces: + + bb0: + if (cond) goto bb2; else goto bb1; + bb1: + *p = RHS1; + goto bb3; + bb2: + *p = RHS2; + bb3: + + with + + bb0: + if (cond) goto bb3; else goto bb1; + bb1: + bb3: + condtmp = PHI + *p = condtmp; */ static unsigned int tree_ssa_cs_elim (void) @@ -248,8 +267,23 @@ tree_ssa_phiopt_worker (bool do_store_el e1 = e2; e2 = e_tmp; } + else if (do_store_elim + && EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest) + { + basic_block bb3 = EDGE_SUCC (bb1, 0)->dest; + + if (!single_succ_p (bb1) + || (EDGE_SUCC (bb1, 0)->flags & EDGE_FALLTHRU) == 0 + || !single_succ_p (bb2) + || (EDGE_SUCC (bb2, 0)->flags & EDGE_FALLTHRU) == 0 + || EDGE_COUNT (bb3->preds) != 2) + continue; + if (cond_if_else_store_replacement (bb1, bb2, bb3)) + cfgchanged = true; + continue; + } else - continue; + continue; e1 = EDGE_SUCC (bb1, 0); @@ -1190,26 +1224,20 @@ cond_store_replacement (basic_block midd gimple newphi, new_stmt; gimple_stmt_iterator gsi; source_location locus; - enum tree_code code; /* Check if middle_bb contains of only one store. */ if (!assign - || gimple_code (assign) != GIMPLE_ASSIGN) + || !gimple_assign_single_p (assign)) return false; locus = gimple_location (assign); lhs = gimple_assign_lhs (assign); rhs = gimple_assign_rhs1 (assign); if (TREE_CODE (lhs) != MEM_REF - || TREE_CODE (TREE_OPERAND (lhs, 0)) != SSA_NAME) - return false; - - /* RHS is either a single SSA_NAME or a constant of register type. */ - code = gimple_assign_rhs_code (assign); - if (get_gimple_rhs_class (code) != GIMPLE_SINGLE_RHS - || (code != SSA_NAME && !is_gimple_min_invariant (rhs)) + || TREE_CODE (TREE_OPERAND (lhs, 0)) != SSA_NAME || !is_gimple_reg_type (TREE_TYPE (lhs))) return false; + /* Prove that we can move the store down. We could also check TREE_THIS_NOTRAP here, but in that case we also could move stores, whose value is not available readily, which we want to avoid. */ @@ -1221,6 +1249,7 @@ cond_store_replacement (basic_block midd gsi = gsi_for_stmt (assign); unlink_stmt_vdef (assign); gsi_remove (&gsi, true); + release_defs (assign); /* 2) Create a temporary where we can store the old content of the memory touched by the store, if we need to. */ @@ -1263,6 +1292,99 @@ cond_store_replacement (basic_block midd return true; } +/* Do the main work of conditional store replacement. We already know + that the recognized pattern looks like so: + + split: + if (cond) goto THEN_BB; else goto ELSE_BB (edge E1) + THEN_BB: + X = Y; + goto JOIN_BB; + ELSE_BB: + X = Z; + fallthrough (edge E0) + JOIN_BB: + some more + + We check that THEN_BB and ELSE_BB contain only one store + that the stores have a "simple" RHS. */ + +static bool +cond_if_else_store_replacement (basic_block then_bb, basic_block else_bb, + basic_block join_bb) +{ + gimple then_assign = last_and_only_stmt (then_bb); + gimple else_assign = last_and_only_stmt (else_bb); + tree lhs_base, lhs, then_rhs, else_rhs; + source_location then_locus, else_locus; + gimple_stmt_iterator gsi; + gimple newphi, new_stmt; + + /* Check if then_bb and else_bb contain only one store each. */ + if (then_assign == NULL + || !gimple_assign_single_p (then_assign) + || else_assign == NULL + || !gimple_assign_single_p (else_assign)) + return false; + + lhs = gimple_assign_lhs (then_assign); + if (!is_gimple_reg_type (TREE_TYPE (lhs)) + || !operand_equal_p (lhs, gimple_assign_lhs (else_assign), 0)) + return false; + + lhs_base = get_base_address (lhs); + if (lhs_base == NULL_TREE + || (!DECL_P (lhs_base) && TREE_CODE (lhs_base) != MEM_REF)) + return false; + + then_rhs = gimple_assign_rhs1 (then_assign); + else_rhs = gimple_assign_rhs1 (else_assign); + then_locus = gimple_location (then_assign); + else_locus = gimple_location (else_assign); + + /* Now we've checked the constraints, so do the transformation: + 1) Remove the stores. */ + gsi = gsi_for_stmt (then_assign); + unlink_stmt_vdef (then_assign); + gsi_remove (&gsi, true); + release_defs (then_assign); + + gsi = gsi_for_stmt (else_assign); + unlink_stmt_vdef (else_assign); + gsi_remove (&gsi, true); + release_defs (else_assign); + + /* 2) Create a temporary where we can store the old content + of the memory touched by the store, if we need to. */ + if (!condstoretemp || TREE_TYPE (lhs) != TREE_TYPE (condstoretemp)) + { + condstoretemp = create_tmp_reg (TREE_TYPE (lhs), "cstore"); + get_var_ann (condstoretemp); + } + add_referenced_var (condstoretemp); + + /* 3) Create a PHI node at the join block, with one argument + holding the old RHS, and the other holding the temporary + where we stored the old memory contents. */ + newphi = create_phi_node (condstoretemp, join_bb); + add_phi_arg (newphi, then_rhs, EDGE_SUCC (then_bb, 0), then_locus); + add_phi_arg (newphi, else_rhs, EDGE_SUCC (else_bb, 0), else_locus); + + new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi)); + + /* 4) Insert that PHI node. */ + gsi = gsi_after_labels (join_bb); + if (gsi_end_p (gsi)) + { + gsi = gsi_last_bb (join_bb); + gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT); + } + else + gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT); + + return true; +} + /* Always do these optimizations if we have SSA trees to work on. */ static bool --- gcc/testsuite/gcc.dg/vect/pr46009.c.jj 2010-11-03 11:59:27.000000000 +0100 +++ gcc/testsuite/gcc.dg/vect/pr46009.c 2010-11-03 12:05:20.000000000 +0100 @@ -0,0 +1,74 @@ +/* PR tree-optimization/46009 */ +/* { dg-require-effective-target vect_int } */ + +#include "tree-vect.h" + +int a[1024] __attribute__((aligned)); +int b[1024] __attribute__((aligned)); +int c[1024] __attribute__((aligned)); +int d[1024] __attribute__((aligned)); +int e[1024] __attribute__((aligned)); + +void __attribute__((noinline)) +foo (void) +{ + int i, g; + for (i = 0; i < 1024; i++) + { + g = a[i] + b[i] + c[i] * d[i];; + e[i] = g < 10 ? 1 : g; + } +} + +void __attribute__((noinline)) +bar (void) +{ + int i, g; + for (i = 0; i < 1024; i++) + { + g = a[i] + b[i] + c[i] * d[i];; + if (g < 10) + e[i] = 1; + else + e[i] = g; + } +} + +int +main (void) +{ + int i; + check_vect (); + for (i = 0; i < 1024; i++) + { + asm volatile ("" : "+r" (i)); + a[i] = i % 10; + b[i] = i % 10; + c[i] = 1; + d[i] = -1; + e[i] = -1; + } + foo (); + for (i = 0; i < 1024; i++) + { + int g; + asm volatile ("" : "+r" (i)); + g = 2 * (i % 10) - 1; + if (e[i] != (g < 10 ? 1 : g)) + abort (); + e[i] = -1; + } + bar (); + for (i = 0; i < 1024; i++) + { + int g; + asm volatile ("" : "+r" (i)); + g = 2 * (i % 10) - 1; + if (e[i] != (g < 10 ? 1 : g)) + abort (); + } + return 0; +} + +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect" } } */ +/* { dg-final { cleanup-tree-dump "vect" } } */