From patchwork Sat Sep 28 01:28:47 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Cong Hou X-Patchwork-Id: 278699 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 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 243322C016E for ; Sat, 28 Sep 2013 11:28:58 +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=SxFt9kCGp/o/r8q6nLtc4sLdz6nLRXu/UJscnbevaGx D2ghQraIvWPHlrwupuWanKMhN8PmkqjcatXLmwhYpJyQ5eyyPVn6WWAYHsxtvxNI OVLPHF/bqKHtwrS5WFBjgGPMh9qsT5YqNuWNvsjtAGBPko6OlhJcvWIJX3c3Cpug = 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=uT07NptdnlDgjtjOhJ2rNGS3M7g=; b=xA/xKTqDGIuD2aWKF uxuklnOOekG4W8E79Sb02a7qRY+en1GFV+8kgjVIDdn4Zl4uEbIv9rkpr/jhW1Ym JhqZWi9oyPpMzycZ3/C/48s+44ibaYMYHJ1NcxTV+beiWr5ViSUWbjy46kJDe/Qp tT4hS2Wji1v0wShEjhL84SuoY0= Received: (qmail 22864 invoked by alias); 28 Sep 2013 01:28:51 -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 22846 invoked by uid 89); 28 Sep 2013 01:28:50 -0000 Received: from mail-ie0-f182.google.com (HELO mail-ie0-f182.google.com) (209.85.223.182) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Sat, 28 Sep 2013 01:28:50 +0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.6 required=5.0 tests=AWL, BAYES_00, NO_RELAYS autolearn=ham version=3.3.2 X-HELO: mail-ie0-f182.google.com Received: by mail-ie0-f182.google.com with SMTP id aq17so5692271iec.27 for ; Fri, 27 Sep 2013 18:28:47 -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=2KpT5bielGZenET9Uz9mTlOUBWrbmOAAUI/oENf/1Ro=; b=DsFd6mbZaQQPc0fsoVhtA/Ojoi0wQYZ5Talz6nWL09so5w6L+L5cfBBuxUQ10t77Ow 8idBMM1Pn7qBxlADWRS/VpkGUE241lcDZPjpf2zdSMurOMl98LpLnejKD7dRdMoSJhnf J95IkUYIn9eO2kPc9Nm0IlqcHs+2PL039HCoRozNsfft8Xb/4cbBTMTdyWV3EhcsU4m8 LoeE8+YdnyEf/yTSN0N7VaQmPOuDXvdCeouI+/5squiY5iG8L6DSZMmhz+ia/z1jj1yS LjM5fOjjK181xKjccar8WJd3TZSM1Cfq5bfEMSZac6cm+rqtK/qRguaPTyYT4TVXPjWC uQeQ== X-Gm-Message-State: ALoCoQm43DNkhgJSXkJdbahY04ZJEgT4amn2qwvsf65np09dSASDv6uEvNRIwu4fzgk0rwxTw++f2Ooq5Uy4Ubxn/fcLRPdOnqi4ZhekJbPJm0iii1yGuC7PEfTUSu2x4TUkDIpf9GdnMQnardwIYnxAnO5ctI3Bne3Ns29zTyuRds+hlfg+twK+FVlPfE5HqKYi/QsABnxcCLhoEpJWYARyjRcpJ30F8g== MIME-Version: 1.0 X-Received: by 10.50.13.66 with SMTP id f2mr4805779igc.17.1380331727519; Fri, 27 Sep 2013 18:28:47 -0700 (PDT) Received: by 10.64.236.37 with HTTP; Fri, 27 Sep 2013 18:28:47 -0700 (PDT) Date: Fri, 27 Sep 2013 18:28:47 -0700 Message-ID: Subject: [PATCH] Relax the requirement of reduction pattern in GCC vectorizer. From: Cong Hou To: GCC Patches Cc: David Li The current GCC vectorizer requires the following pattern as a simple reduction computation: loop_header: a1 = phi < a0, a2 > a3 = ... a2 = operation (a3, a1) But a3 can also be defined outside of the loop. For example, the following loop can benefit from vectorization but the GCC vectorizer fails to vectorize it: int foo(int v) { int s = 1; ++v; for (int i = 0; i < 100000; ++i) s *= v; return s; } This patch relaxes the original requirement by also considering the following pattern: a3 = ... loop_header: a1 = phi < a0, a2 > a2 = operation (a3, a1) A test case is also added. The patch is tested on x86-64. thanks, Cong ================================ diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 39c786e..45c1667 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,9 @@ +2013-09-27 Cong Hou + + * tree-vect-loop.c: Relax the requirement of the reduction + pattern so that one operand of the reduction operation can + come from outside of the loop. + 2013-09-25 Tom Tromey * Makefile.in (PARTITION_H, LTO_SYMTAB_H, COMMON_TARGET_DEF_H) diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 09644d2..90496a2 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2013-09-27 Cong Hou + + * gcc.dg/vect/vect-reduc-pattern-3.c: New test. + 2013-09-25 Marek Polacek PR sanitizer/58413 diff --git a/gcc/tree-vect-loop.c b/gcc/tree-vect-loop.c index 2871ba1..3c51c3b 100644 --- a/gcc/tree-vect-loop.c +++ b/gcc/tree-vect-loop.c @@ -2091,6 +2091,13 @@ vect_is_slp_reduction (loop_vec_info loop_info, gimple phi, gimple first_stmt) a3 = ... a2 = operation (a3, a1) + or + + a3 = ... + loop_header: + a1 = phi < a0, a2 > + a2 = operation (a3, a1) + such that: 1. operation is commutative and associative and it is safe to change the order of the computation (if CHECK_REDUCTION is true) @@ -2451,6 +2458,7 @@ vect_is_simple_reduction_1 (loop_vec_info loop_info, gimple phi, if (def2 && def2 == phi && (code == COND_EXPR || !def1 || gimple_nop_p (def1) + || !flow_bb_inside_loop_p (loop, gimple_bb (def1)) || (def1 && flow_bb_inside_loop_p (loop, gimple_bb (def1)) && (is_gimple_assign (def1) || is_gimple_call (def1) @@ -2469,6 +2477,7 @@ vect_is_simple_reduction_1 (loop_vec_info loop_info, gimple phi, if (def1 && def1 == phi && (code == COND_EXPR || !def2 || gimple_nop_p (def2) + || !flow_bb_inside_loop_p (loop, gimple_bb (def2)) || (def2 && flow_bb_inside_loop_p (loop, gimple_bb (def2)) && (is_gimple_assign (def2) || is_gimple_call (def2) diff --git gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c new file mode 100644 index 0000000..06a9416 --- /dev/null +++ gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c @@ -0,0 +1,41 @@ +/* { dg-require-effective-target vect_int } */ + +#include +#include "tree-vect.h" + +#define N 10 +#define RES 1024 + +/* A reduction pattern in which there is no data ref in + the loop and one operand is defined outside of the loop. */ + +__attribute__ ((noinline)) int +foo (int v) +{ + int i; + int result = 1; + + ++v; + for (i = 0; i < N; i++) + result *= v; + + return result; +} + +int +main (void) +{ + int res; + + check_vect (); + + res = foo (1); + if (res != RES) + abort (); + + return 0; +} + +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */ +/* { dg-final { cleanup-tree-dump "vect" } } */ +