From patchwork Fri Apr 25 00:32:54 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Cong Hou X-Patchwork-Id: 342540 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]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 7E980140155 for ; Fri, 25 Apr 2014 10:33:06 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:date:message-id:subject:from:to:cc:content-type; q=dns; s=default; b=jH3EAm5vijebFhJ58zYl6pHBfN+zQfydmVTaCeSYfto lTzfy1C3bII1YmTHMBj2zQK/QHvDavRg1XZhtBoMXJCiy/gLhZCmnGWMwnlyvPUf X6J5dJPQ3J/XsA2FceI2dSaj8bUlVfoMGnj4taeGvBUlgVw+2Wcot+DHDqrns4UE = DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:date:message-id:subject:from:to:cc:content-type; s=default; bh=q4+u+J5TOS3905/HdHPliBC0YbI=; b=DxiIXrg7DaoJI5rMS J83/PDi3xcA8lUp0OUmuXo8zBCnxIwG5uw3AU95tkNHeHWtxrsb5WQkZWTeezBYT Xq3aaOliuZ6/+whu+65jy4eXmJz6CQ+oT4QHKkJxFjPOSoPsRY6OBGpHVxKaYfvg U3sPUXNj45bBOdK8DXt0YXqMsc= Received: (qmail 22775 invoked by alias); 25 Apr 2014 00:32:58 -0000 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 Received: (qmail 22759 invoked by uid 89); 25 Apr 2014 00:32:57 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.1 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_LOW, RP_MATCHES_RCVD, SPF_PASS, UNSUBSCRIBE_BODY autolearn=no version=3.3.2 X-HELO: mail-ig0-f169.google.com Received: from mail-ig0-f169.google.com (HELO mail-ig0-f169.google.com) (209.85.213.169) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Fri, 25 Apr 2014 00:32:56 +0000 Received: by mail-ig0-f169.google.com with SMTP id h18so1694140igc.0 for ; Thu, 24 Apr 2014 17:32:54 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:date:message-id:subject:from:to:cc :content-type; bh=CwvwPkAFd/jF0By1hFoNL7c5veg8cAxJ0LgXr3Blm7A=; b=Nry5T7PivqCaNxPw9lXoSyPI7abT+rmDAaOAUQ8HVW3q9OM5FMGk9geQKsb/zkJ3b0 on9jGycgDHHyb5tF/jDeXZ30iq3iSL+DL6locAkH9x6JkYwBn9fs+gS5I+0ncwxdwfqo X6n1pXkAri/zyrsmVHT35w6RBjJyovkj66dqq+N0TO+AgRQCUqJg+/8nOYZVWkaiTInY YSMP7ykz6d1v+S0CbiyM1DlEaQuelUgTy/hNUhrZbc7H6vvtogH+7GrqgKOmENoBPKZK SL8YHELpPAH3AvgV5mfcYBkJSxlvnyUKS0atQCbxRecJPGwenidnRrbL4YzOBiSX2/ud 4G3A== X-Gm-Message-State: ALoCoQn8kvhomXEW4VDM2L4qOcntylRHFkDBxspJlpEPC4Grz43XA9+qWZvAttLc5fywYPzsCOQnq4zPmJXx6YrWzGj2F3zXdS3WVYgiGxfOqJb9hZnMJhhXTTzovPVi8zpGfZ37mxnuOikdSViB4jsQpi/aDPEknrAsoTFWX7t9IQXn3jn8ZVwGpIBBhR8mODbbAawh8DJ5awh4W/wNbZqcues5wq9LqA== MIME-Version: 1.0 X-Received: by 10.42.44.4 with SMTP id z4mr4791780ice.34.1398385974326; Thu, 24 Apr 2014 17:32:54 -0700 (PDT) Received: by 10.64.224.227 with HTTP; Thu, 24 Apr 2014 17:32:54 -0700 (PDT) Date: Thu, 24 Apr 2014 17:32:54 -0700 Message-ID: Subject: [PATCH] A new reload-rewrite pattern recognizer for GCC vectorizer. From: Cong Hou To: GCC Patches Cc: Richard Biener In this patch a new reload-rewrite pattern detector is composed to handle the following pattern in the loop being vectorized: x = *p; ... y = *p; or *p = x; ... y = *p; In both cases, *p is reloaded because there may exist other defs to another memref that may alias with p. However, aliasing is eliminated with alias checks. Then we can safely replace the last statement in above cases by y = x. The following rewrite pattern is also detected: *p = x; ... *p = y; The first write is redundant due to the fact that there is no aliasing between p and other pointers. In this case we don't need to vectorize this write. Here we replace it with a dummy statement z = x. Bootstrapped and tested on x86-64. OK for trunk? thanks, Cong diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 117cdd0..59a4388 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,10 @@ +2014-04-23 Cong Hou + + * tree-vect-patterns.c (vect_recog_reload_rewrite_pattern): + New function. + (vect_vect_recog_func_ptrs): Add new pattern. + * tree-vectorizer.h (NUM_PATTERNS): Update the pattern count. + 2014-04-23 David Malcolm * is-a.h: Update comments to reflect the following changes to the diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 62b07f4..2116cd3 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2014-04-23 Cong Hou + + * gcc.dg/vect/vect-reload-rewrite-pattern.c: New test. + 2014-04-23 Jeff Law PR tree-optimization/60902 diff --git a/gcc/testsuite/gcc.dg/vect/vect-reload-rewrite-pattern.c b/gcc/testsuite/gcc.dg/vect/vect-reload-rewrite-pattern.c new file mode 100644 index 0000000..e75f969 --- /dev/null +++ b/gcc/testsuite/gcc.dg/vect/vect-reload-rewrite-pattern.c @@ -0,0 +1,61 @@ +/* { dg-do compile } */ +/* { dg-require-effective-target vect_int } */ + +#define N 1000 +int a[N]; + +void test1 (int *b, int *c) +{ + int i; + for (i = 0; i < N; ++i) + { + a[i] = c[i]; + /* Reload of c[i]. */ + b[i] = c[i]; + } +} + +void test2 (int *b, int *c) +{ + int i; + for (i = 0; i < N; ++i) + { + c[i] = a[i] + 10; + /* Reload of a[i]. */ + a[i]++; + /* Reload of c[i]. */ + b[i] = c[i]; + } +} + +void test3 (int *b, int *c) +{ + int i; + for (i = 0; i < N; ++i) + { + c[i] = a[i] & 63; + /* Reload of a[i]. */ + a[i]++; + /* Reload of c[i]. */ + /* Rewrite to c[i]. */ + c[i]--; + } +} + +void test4 (_Complex int *b, _Complex int *c, _Complex int *d) +{ + int i; + for (i = 0; i < N; ++i) + { + b[i] = c[i] + d[i]; + /* Reload of REALPART_EXPR (c[i]). */ + /* Reload of IMAGPART_EXPR (c[i]). */ + /* Reload of REALPART_EXPR (d[i]). */ + /* Reload of IMAGPART_EXPR (d[i]). */ + c[i] = c[i] - d[i]; + } +} + +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 4 "vect"} } */ +/* { dg-final { scan-tree-dump-times "vect_recog_reload_rewrite_pattern: detected" 10 "vect" } } */ +/* { dg-final { cleanup-tree-dump "vect" } } */ diff --git a/gcc/tree-vect-patterns.c b/gcc/tree-vect-patterns.c index 5daaf24..38a0fec 100644 --- a/gcc/tree-vect-patterns.c +++ b/gcc/tree-vect-patterns.c @@ -40,6 +40,7 @@ along with GCC; see the file COPYING3. If not see #include "ssa-iterators.h" #include "stringpool.h" #include "tree-ssanames.h" +#include "tree-ssa-sccvn.h" #include "cfgloop.h" #include "expr.h" #include "optabs.h" @@ -70,6 +71,7 @@ static gimple vect_recog_divmod_pattern (vec *, static gimple vect_recog_mixed_size_cond_pattern (vec *, tree *, tree *); static gimple vect_recog_bool_pattern (vec *, tree *, tree *); +static gimple vect_recog_reload_rewrite_pattern (vec *, tree *, tree *); static vect_recog_func_ptr vect_vect_recog_func_ptrs[NUM_PATTERNS] = { vect_recog_widen_mult_pattern, vect_recog_widen_sum_pattern, @@ -81,6 +83,7 @@ static vect_recog_func_ptr vect_vect_recog_func_ptrs[NUM_PATTERNS] = { vect_recog_vector_vector_shift_pattern, vect_recog_divmod_pattern, vect_recog_mixed_size_cond_pattern, + vect_recog_reload_rewrite_pattern, vect_recog_bool_pattern}; static inline void @@ -3019,6 +3022,160 @@ vect_recog_bool_pattern (vec *stmts, tree *type_in, return NULL; } +/* Function vect_recog_reload_rewrite_pattern + + Try to find the following reload pattern: + + x = *p; + ... + y = *p; + + or + + *p = x; + ... + y = *p; + + In both cases, *p is reloaded because there may exist other defs to another + memref that may alias with p. However, aliasing is eliminated with alias + checks. Then we can safely replace the last statement in above cases by + y = x. + + Also try to detect rewrite pattern: + + *p = x; + ... + *p = y; + + The first write is redundant due to the fact that there is no aliasing + between p and other pointers. In this case we don't need to vectorize + the first write. Here we replace it by a dummy statement z = x. + + Input: + + * STMTS: Contains a stmt from which the pattern search begins. + + Output: + + * TYPE_IN: The type of the input arguments to the pattern. + + * TYPE_OUT: The type of the output of this pattern. + + * Return value: A new stmt that will be used to replace the sequence of + stmts that constitute the pattern. In this case it will be y = x; + for reload pattern, and z = x; for rewrite pattern. */ + +static gimple +vect_recog_reload_rewrite_pattern (vec *stmts, tree *type_in, + tree *type_out) +{ + gimple last_stmt = (*stmts)[0]; + + /* We only consider this pattern for loops (alias checks are only + done for loops). */ + stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt); + loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo); + if (!loop_vinfo) + return NULL; + + if (!is_gimple_assign (last_stmt)) + return NULL; + + /* Check if LAST_STMT is a load or write. */ + bool load = false; + tree lhs_oprnd = gimple_assign_lhs (last_stmt); + enum tree_code code = gimple_assign_rhs_code (last_stmt); + + if (TREE_CODE (lhs_oprnd) == SSA_NAME + && (code == ARRAY_REF + || code == BIT_FIELD_REF + || code == INDIRECT_REF + || code == COMPONENT_REF + || code == IMAGPART_EXPR + || code == REALPART_EXPR + || code == MEM_REF)) + load = true; + else if (TREE_CODE (lhs_oprnd) != ARRAY_REF + && TREE_CODE (lhs_oprnd) != BIT_FIELD_REF + && TREE_CODE (lhs_oprnd) != INDIRECT_REF + && TREE_CODE (lhs_oprnd) != COMPONENT_REF + && TREE_CODE (lhs_oprnd) != IMAGPART_EXPR + && TREE_CODE (lhs_oprnd) != REALPART_EXPR + && TREE_CODE (lhs_oprnd) != MEM_REF) + return NULL; + + tree new_val = NULL_TREE; + + if (load) + { + /* If LAST_STMT is a load, check if there is any load or write to + the same memref before LAST_STMT. */ + + tree memref = gimple_assign_rhs1 (last_stmt); + basic_block bb = gimple_bb (last_stmt); + + for (gimple_stmt_iterator si = gsi_start_bb (bb); + !gsi_end_p (si); gsi_next (&si)) + { + gimple stmt = gsi_stmt (si); + if (stmt == last_stmt) + break; + if (!is_gimple_assign (stmt)) + continue; + + if (expressions_equal_p (memref, gimple_assign_rhs1 (stmt))) + new_val = gimple_assign_lhs (stmt); + else if (expressions_equal_p (memref, gimple_assign_lhs (stmt))) + new_val = gimple_assign_rhs1 (stmt); + } + } + else + { + /* If LAST_STMT is a write, check if there is any write to + the same memref after LAST_STMT. */ + + tree memref = gimple_assign_lhs (last_stmt); + basic_block bb = gimple_bb (last_stmt); + + gimple_stmt_iterator si = gsi_start_bb (bb); + while (gsi_stmt (si) != last_stmt) + gsi_next (&si); + gsi_next (&si); + + for (; !gsi_end_p (si); gsi_next (&si)) + { + gimple stmt = gsi_stmt (si); + if (is_gimple_assign (stmt) + && expressions_equal_p (memref, gimple_assign_lhs (stmt))) + { + new_val = gimple_assign_rhs1 (last_stmt); + break; + } + } + } + + if (new_val == NULL_TREE) + return NULL; + + *type_in = *type_out = STMT_VINFO_VECTYPE (stmt_vinfo); + + tree type = gimple_expr_type (last_stmt); + tree new_var = vect_recog_temp_ssa_var (type, NULL); + /* Pattern detected. Create a stmt to be used to replace the pattern. */ + gimple pattern_stmt = gimple_build_assign_with_ops (NOP_EXPR, new_var, + new_val, NULL); + + if (dump_enabled_p ()) + { + dump_printf_loc (MSG_NOTE, vect_location, + "vect_recog_reload_rewrite_pattern: detected: "); + dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0); + dump_printf (MSG_NOTE, "\n"); + dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, pattern_stmt, 0); + } + + return pattern_stmt; +} /* Mark statements that are involved in a pattern. */ diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h index c5cb037..e91474d 100644 --- a/gcc/tree-vectorizer.h +++ b/gcc/tree-vectorizer.h @@ -1123,7 +1123,7 @@ extern void vect_slp_transform_bb (basic_block); Additional pattern recognition functions can (and will) be added in the future. */ typedef gimple (* vect_recog_func_ptr) (vec *, tree *, tree *); -#define NUM_PATTERNS 11 +#define NUM_PATTERNS 12 void vect_pattern_recog (loop_vec_info, bb_vec_info); /* In tree-vectorizer.c. */