From patchwork Tue Jun 25 11:56:29 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 254129 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 CN "localhost", Issuer "www.qmailtoaster.com" (not verified)) by ozlabs.org (Postfix) with ESMTPS id 5E9012C0084 for ; Tue, 25 Jun 2013 21:56:46 +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:date :from:to:cc:subject:message-id:reply-to:mime-version :content-type; q=dns; s=default; b=KBjm2UNKMc9m923dD2rYnSbSlrVb3 yIFovrW9K1XetDWj0QNXaaEl5tLGu8L6HOSGzBMFlSyqSPBKJGE+00gfqbUav00h 64/PDm0QzSHLEDntDUcpC25t9+KSoUo/Y1tfNILM2hQgpiADi9iOIWMgYUl4v3Dl NbXUsv47OrY1qw= 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:date :from:to:cc:subject:message-id:reply-to:mime-version :content-type; s=default; bh=Lu3GEQIz3KMhULTVrRwcSp27Py0=; b=eC2 DlqITOaQxDbtIXx5PZPmbCe+rseTN5UzkrnV8s2d8c1Zs39r5MdW6Zlc58+kLT6s 1z9ndc4ngm9ZG+PKbcAlv30cr7MhKN3S4MGfHEvnbrrmWhXyODtKv4A3enI7UyTG PjIbunqyhg8E0KGjAWMOeRvaZN1nB9W4bPZcKzbc= Received: (qmail 7183 invoked by alias); 25 Jun 2013 11:56:40 -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 7161 invoked by uid 89); 25 Jun 2013 11:56:36 -0000 X-Spam-SWARE-Status: No, score=-6.8 required=5.0 tests=AWL, BAYES_00, RCVD_IN_HOSTKARMA_W, RCVD_IN_HOSTKARMA_WL, RP_MATCHES_RCVD, SPF_HELO_PASS, SPF_PASS, TW_EP, TW_TM autolearn=ham version=3.3.1 Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Tue, 25 Jun 2013 11:56:35 +0000 Received: from int-mx09.intmail.prod.int.phx2.redhat.com (int-mx09.intmail.prod.int.phx2.redhat.com [10.5.11.22]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id r5PBuX77029696 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Tue, 25 Jun 2013 07:56:33 -0400 Received: from zalov.cz (vpn1-6-77.ams2.redhat.com [10.36.6.77]) by int-mx09.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id r5PBuVgJ018250 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Tue, 25 Jun 2013 07:56:32 -0400 Received: from zalov.cz (localhost [127.0.0.1]) by zalov.cz (8.14.5/8.14.5) with ESMTP id r5PBuUSQ021051; Tue, 25 Jun 2013 13:56:30 +0200 Received: (from jakub@localhost) by zalov.cz (8.14.5/8.14.5/Submit) id r5PBuT8Z021050; Tue, 25 Jun 2013 13:56:29 +0200 Date: Tue, 25 Jun 2013 13:56:29 +0200 From: Jakub Jelinek To: Richard Biener , Richard Henderson Cc: gcc-patches@gcc.gnu.org Subject: [PATCH] Allow vectorization of IVs with non-constant step (PR tree-optimization/57705) Message-ID: <20130625115629.GN2336@tucnak.redhat.com> Reply-To: Jakub Jelinek MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) Hi! While hacking on the gomp4 simd clauses stuff, I've noticed that we don't vectorize IVs with non-constant step. The following patch implements it, basically we just can't rely that the step or VF * step is a constant and instead for VF * step need to emit a temporary with scalar VF * step value before adding a vector temporary. Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? I wasn't sure about nested loop vectorization, so I've disabled it for that case, perhaps with a testcase that exhibits it could be replaced just with a test that the step, if SSA_NAME, doesn't have definition even in the outer loop, because we still put the vector constants before the outer loop. 2013-06-25 Jakub Jelinek PR tree-optimization/57705 * tree-vect-loop.c (vect_is_simple_iv_evolution): Allow SSA_NAME step, provided that it is not defined inside the loop. (vect_analyze_scalar_cycles_1): Disallow SSA_NAME step in nested loop. (get_initial_def_for_induction): Handle SSA_NAME IV step. * gcc.dg/vect/pr57705.c: New test. * gcc.dg/vect/vect-iv-7.c: Add noclone attribute, remove xfail. Jakub --- gcc/tree-vect-loop.c.jj 2013-06-06 08:39:24.000000000 +0200 +++ gcc/tree-vect-loop.c 2013-06-25 11:17:02.947602981 +0200 @@ -500,7 +500,7 @@ vect_determine_vectorization_factor (loo /* Function vect_is_simple_iv_evolution. FORNOW: A simple evolution of an induction variables in the loop is - considered a polynomial evolution with constant step. */ + considered a polynomial evolution. */ static bool vect_is_simple_iv_evolution (unsigned loop_nb, tree access_fn, tree * init, @@ -509,6 +509,7 @@ vect_is_simple_iv_evolution (unsigned lo tree init_expr; tree step_expr; tree evolution_part = evolution_part_in_loop_num (access_fn, loop_nb); + basic_block bb; /* When there is no evolution in this loop, the evolution function is not "simple". */ @@ -534,7 +535,10 @@ vect_is_simple_iv_evolution (unsigned lo *init = init_expr; *step = step_expr; - if (TREE_CODE (step_expr) != INTEGER_CST) + if (TREE_CODE (step_expr) != INTEGER_CST + && (TREE_CODE (step_expr) != SSA_NAME + || ((bb = gimple_bb (SSA_NAME_DEF_STMT (step_expr))) + && flow_bb_inside_loop_p (get_loop (cfun, loop_nb), bb)))) { if (dump_enabled_p ()) dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, @@ -556,7 +560,7 @@ static void vect_analyze_scalar_cycles_1 (loop_vec_info loop_vinfo, struct loop *loop) { basic_block bb = loop->header; - tree dumy; + tree init, step; vec worklist; worklist.create (64); gimple_stmt_iterator gsi; @@ -605,7 +609,9 @@ vect_analyze_scalar_cycles_1 (loop_vec_i } if (!access_fn - || !vect_is_simple_iv_evolution (loop->num, access_fn, &dumy, &dumy)) + || !vect_is_simple_iv_evolution (loop->num, access_fn, &init, &step) + || (LOOP_VINFO_LOOP (loop_vinfo) != loop + && TREE_CODE (step) != INTEGER_CST)) { worklist.safe_push (phi); continue; @@ -3273,10 +3279,14 @@ get_initial_def_for_induction (gimple iv expr = build_int_cst (TREE_TYPE (step_expr), vf); new_name = fold_build2 (MULT_EXPR, TREE_TYPE (step_expr), expr, step_expr); + if (TREE_CODE (step_expr) == SSA_NAME) + new_name = vect_init_vector (iv_phi, new_name, + TREE_TYPE (step_expr), NULL); } t = unshare_expr (new_name); - gcc_assert (CONSTANT_CLASS_P (new_name)); + gcc_assert (CONSTANT_CLASS_P (new_name) + || TREE_CODE (new_name) == SSA_NAME); stepvectype = get_vectype_for_scalar_type (TREE_TYPE (new_name)); gcc_assert (stepvectype); new_vec = build_vector_from_val (stepvectype, t); @@ -3332,8 +3342,12 @@ get_initial_def_for_induction (gimple iv expr = build_int_cst (TREE_TYPE (step_expr), nunits); new_name = fold_build2 (MULT_EXPR, TREE_TYPE (step_expr), expr, step_expr); + if (TREE_CODE (step_expr) == SSA_NAME) + new_name = vect_init_vector (iv_phi, new_name, + TREE_TYPE (step_expr), NULL); t = unshare_expr (new_name); - gcc_assert (CONSTANT_CLASS_P (new_name)); + gcc_assert (CONSTANT_CLASS_P (new_name) + || TREE_CODE (new_name) == SSA_NAME); new_vec = build_vector_from_val (stepvectype, t); vec_step = vect_init_vector (iv_phi, new_vec, stepvectype, NULL); --- gcc/testsuite/gcc.dg/vect/pr57705.c.jj 2013-06-25 10:15:21.037092153 +0200 +++ gcc/testsuite/gcc.dg/vect/pr57705.c 2013-06-25 10:15:02.239733689 +0200 @@ -0,0 +1,65 @@ +/* { dg-do run } */ + +#include "tree-vect.h" + +int a[1024]; +unsigned char b[1024]; + +extern void abort (void); + +__attribute__((noinline, noclone)) void +foo (int k, int m) +{ + int i, k2 = k; + for (i = 0; i < 1024; i++) + { + a[i] = k2; + k2 += m + 1; + } +} + +__attribute__((noinline, noclone)) void +bar (int k, int m) +{ + int i, k2 = k; + for (i = 0; i < 1024; i++) + { + k2 += m + 1; + a[i] = k2; + } +} + +__attribute__((noinline, noclone)) void +baz (int k, int m) +{ + int i, k2 = k; + for (i = 0; i < 1024; i++) + { + a[i] = k2; + b[i] = i; + k2 += m + 1; + } +} + +int +main () +{ + int i; + check_vect (); + foo (5, 3); + for (i = 0; i < 1024; i++) + if (a[i] != 5 + 4 * i) + abort (); + bar (5, 3); + for (i = 0; i < 1024; i++) + if (a[i] != 9 + 4 * i) + abort (); + baz (5, 3); + for (i = 0; i < 1024; i++) + if (a[i] != 5 + 4 * i || b[i] != (unsigned char) i) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "vectorized 1 loop" 3 "vect" } } */ +/* { dg-final { cleanup-tree-dump "vect" } } */ --- gcc/testsuite/gcc.dg/vect/vect-iv-7.c.jj 2008-09-05 12:54:35.000000000 +0200 +++ gcc/testsuite/gcc.dg/vect/vect-iv-7.c 2013-06-25 10:37:35.864287369 +0200 @@ -6,7 +6,7 @@ #define N 16 int result[N] = {8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38}; -__attribute__ ((noinline)) int main1 (int X) +__attribute__ ((noinline, noclone)) int main1 (int X) { int arr[N]; int k = 3; @@ -38,5 +38,5 @@ int main (void) return main1 (2); } -/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" { xfail *-*-* } } } */ +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */ /* { dg-final { cleanup-tree-dump "vect" } } */