From patchwork Mon Oct 23 17:28:54 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 116815 Delivered-To: patch@linaro.org Received: by 10.140.22.164 with SMTP id 33csp4893249qgn; Mon, 23 Oct 2017 10:29:25 -0700 (PDT) X-Received: by 10.99.96.15 with SMTP id u15mr12664316pgb.424.1508779765556; Mon, 23 Oct 2017 10:29:25 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1508779765; cv=none; d=google.com; s=arc-20160816; b=veF85f1nS4db/4CDERJ/W4xiqkU9zOJ2Zhs+6Z/nZFNERrfn2DASZf4UNPNWs6Uneo AboLKsBHRVazc1D0D1xYz+GlDa+6r2F1rE9HgDXcJjMBareFFyD/3blhXtJjcrFUELqX bi8y7+ZpkCK42zKyyXUD3RNJ09iUCSAmRJDN6vOzHpvHdBI9BIm6D/DwKBlzT9/eOgnj mvkpRnocBeJ05DoKduD5KdMCK+36uX56aXaRm15ZcOiXM9T4G1vW1aXf1rGsb+o2nXAL NPe4SMu16B7uz/dlDoSb5JMQN3J17C/Xhvu8hO5dxC+JLr+EFFocBN/F+pG37PYZ1x/g 2Oow== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=mime-version:user-agent:message-id:in-reply-to:date:references :subject:mail-followup-to:to:from:delivered-to:sender:list-help :list-post:list-archive:list-unsubscribe:list-id:precedence :mailing-list:dkim-signature:domainkey-signature :arc-authentication-results; bh=l3GOF5I9WvFS/ibg+hNYgc39EA/yW5JP6m1amKwKLaM=; b=FhTjjPYNeT98UFVdebPs7dOmedocGKeg7+4qRmz1pknV5qEqlIrhx+Y/mjgUK2I5Uv F7XU5ZAvQT7zIzwnM0ZZ+7yayOnSODoHwVGDSbj4U0hj2lD03xCYguTWQ5/MMSX7C0FA zNNopvb8rVDgehVccfPmY/vsHVR6wPBsLrc1/vQPUnkb4ABqFHMxW4HbuIMpEQ/uktJe xEEhiGIGnKE9px1DFCxbvKInFCZPpwXcdyGr0KCfLW/9I/BPH4tDO2/danQ158njOGfK VWQ7/fX3vSSV36YM9choRMoiYL4rB5+xK9BNF6T5h0Dnw1XDDfqHCwGQrHHbszDhbqgP TXdQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=E6QMmvkK; spf=pass (google.com: domain of gcc-patches-return-464846-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-464846-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id q13si4179799plk.376.2017.10.23.10.29.25 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 23 Oct 2017 10:29:25 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-464846-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=E6QMmvkK; spf=pass (google.com: domain of gcc-patches-return-464846-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-464846-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:references:date:in-reply-to:message-id:mime-version :content-type; q=dns; s=default; b=RZAS1TW5k96mowBUsSms2GH9o6dp6 +OCyf5Cw1YIJTfEZ7hyDG44+UQQY7mHEPlLh+QNdyGwMZPJS/0ccRJEXqbQjWncu fKiHEVXwRd6i/MAiLGjEAMDmKOfhgYNrAVVshFKR0QCPlpiDD8bhQxo9uQuS16cc yHXuBNSSgoZTVU= 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:from :to:subject:references:date:in-reply-to:message-id:mime-version :content-type; s=default; bh=AYhpbgG3Ub4EoGyRJ84oddUhD4E=; b=E6Q MmvkK3BKpLCknzumpgK1AE9i8CU8V+WyTiewG590h8x87/8REXvQoKnKi3sgvRy1 WNvAATkb01onh18ifKGl8nmkFhyW2Rm5u54TqyC9+avPzHu/7n1CvjZS9qiuuKtd vyJ+0bsYGsRKZDXhagk7RpZ9uxJfxVH8aOe6hJ3Q= Received: (qmail 70270 invoked by alias); 23 Oct 2017 17:29:00 -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 70065 invoked by uid 89); 23 Oct 2017 17:29:00 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-10.6 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM, SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mail-wr0-f174.google.com Received: from mail-wr0-f174.google.com (HELO mail-wr0-f174.google.com) (209.85.128.174) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 23 Oct 2017 17:28:58 +0000 Received: by mail-wr0-f174.google.com with SMTP id y9so5967075wrb.2 for ; Mon, 23 Oct 2017 10:28:57 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:mail-followup-to:subject:references:date :in-reply-to:message-id:user-agent:mime-version; bh=l3GOF5I9WvFS/ibg+hNYgc39EA/yW5JP6m1amKwKLaM=; b=aZqS+9oFnzH950F5jI8Qztbx+Il7usKJXM14oyk2EuiFmUyRPwNOrgFuKV0218d2xu pYGad/JwpG/o0Bh5CyXJReIvyQoL0JoVCUOMwoSj9Ti9pSK1GOiCW/+HyeNaZH3MQU8c Yrbz/Jq8oSI+XFxjHKSYiSeHJ0wnkjgB2MBeTPI1ZJzUUm5s+8YwOSVmLLvY2GiO5tgE oHPUN8v0qn+iUtyjJ4bagmsNaobxek76YXJs+TyD4vgZhcbwvZg0wpCPd8QzljdWMN5g EKh0QX/eSTc/LDG/lLp0OagFjPrKKm74p1G4wPxPqF5Bz/7kQQADpBOMR/nuFjkIP2sd T6zw== X-Gm-Message-State: AMCzsaXhvCHqCHBRqy6HnA9ObHc+e0gi9MEOadWDj+9LL2Ol+yLI06fD 6uM+T6XNgv+ucMPaBbhSSOs8jff4twQ= X-Google-Smtp-Source: ABhQp+R0UJnR8HzVfX9DtYhfM4//BWMyHQgxgZbwHbtZHU58z8CtMyXhIfYoTP9ahTS8W+bvC2w6VA== X-Received: by 10.223.161.20 with SMTP id o20mr3295893wro.276.1508779735616; Mon, 23 Oct 2017 10:28:55 -0700 (PDT) Received: from localhost ([2.26.27.199]) by smtp.gmail.com with ESMTPSA id p128sm5571786wmb.1.2017.10.23.10.28.54 for (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Mon, 23 Oct 2017 10:28:54 -0700 (PDT) From: Richard Sandiford To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@linaro.org Subject: [070/nnn] poly_int: vectorizable_reduction References: <871sltvm7r.fsf@linaro.org> Date: Mon, 23 Oct 2017 18:28:54 +0100 In-Reply-To: <871sltvm7r.fsf@linaro.org> (Richard Sandiford's message of "Mon, 23 Oct 2017 17:54:32 +0100") Message-ID: <87h8upixih.fsf@linaro.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.2 (gnu/linux) MIME-Version: 1.0 This patch makes vectorizable_reduction cope with variable-length vectors. We can handle the simple case of an inner loop reduction for which the target has native support for the epilogue operation. For now we punt on other cases, but patches after the main SVE submission allow SLP and double reductions too. 2017-10-23 Richard Sandiford Alan Hayward David Sherwood gcc/ * tree.h (build_index_vector): Declare. * tree.c (build_index_vector): New function. * tree-vect-loop.c (get_initial_def_for_reduction): Treat the number of units as polynomial, forcibly converting it to a constant if vectorizable_reduction has already enforced the condition. (get_initial_defs_for_reduction): Likewise. (vect_create_epilog_for_reduction): Likewise. Use build_index_vector to create a {1,2,3,...} vector. (vectorizable_reduction): Treat the number of units as polynomial. Choose vectype_in based on the largest scalar element size rather than the smallest number of units. Enforce the restrictions relied on above. Index: gcc/tree.h =================================================================== --- gcc/tree.h 2017-10-23 17:22:32.736226191 +0100 +++ gcc/tree.h 2017-10-23 17:22:35.831905077 +0100 @@ -4050,6 +4050,7 @@ extern tree build_vector (tree, vec *); extern tree build_vector_from_val (tree, tree); extern tree build_vec_series (tree, tree, tree); +extern tree build_index_vector (tree, poly_uint64, poly_uint64); extern void recompute_constructor_flags (tree); extern void verify_constructor_flags (tree); extern tree build_constructor (tree, vec *); Index: gcc/tree.c =================================================================== --- gcc/tree.c 2017-10-23 17:22:32.734226398 +0100 +++ gcc/tree.c 2017-10-23 17:22:35.830905181 +0100 @@ -1974,6 +1974,37 @@ build_vec_series (tree type, tree base, return build2 (VEC_SERIES_EXPR, type, base, step); } +/* Return a vector with the same number of units and number of bits + as VEC_TYPE, but in which the elements are a linear series of unsigned + integers { BASE, BASE + STEP, BASE + STEP * 2, ... }. */ + +tree +build_index_vector (tree vec_type, poly_uint64 base, poly_uint64 step) +{ + tree index_vec_type = vec_type; + tree index_elt_type = TREE_TYPE (vec_type); + poly_uint64 nunits = TYPE_VECTOR_SUBPARTS (vec_type); + if (!INTEGRAL_TYPE_P (index_elt_type) || !TYPE_UNSIGNED (index_elt_type)) + { + index_elt_type = build_nonstandard_integer_type + (GET_MODE_BITSIZE (SCALAR_TYPE_MODE (index_elt_type)), true); + index_vec_type = build_vector_type (index_elt_type, nunits); + } + + unsigned HOST_WIDE_INT count; + if (nunits.is_constant (&count)) + { + auto_vec v (count); + for (unsigned int i = 0; i < count; ++i) + v.quick_push (build_int_cstu (index_elt_type, base + i * step)); + return build_vector (index_vec_type, v); + } + + return build_vec_series (index_vec_type, + build_int_cstu (index_elt_type, base), + build_int_cstu (index_elt_type, step)); +} + /* Something has messed with the elements of CONSTRUCTOR C after it was built; calculate TREE_CONSTANT and TREE_SIDE_EFFECTS. */ Index: gcc/tree-vect-loop.c =================================================================== --- gcc/tree-vect-loop.c 2017-10-23 17:22:32.727227124 +0100 +++ gcc/tree-vect-loop.c 2017-10-23 17:22:35.829905285 +0100 @@ -3997,11 +3997,10 @@ get_initial_def_for_reduction (gimple *s struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); tree scalar_type = TREE_TYPE (init_val); tree vectype = get_vectype_for_scalar_type (scalar_type); - int nunits; + poly_uint64 nunits; enum tree_code code = gimple_assign_rhs_code (stmt); tree def_for_init; tree init_def; - int i; bool nested_in_vect_loop = false; REAL_VALUE_TYPE real_init_val = dconst0; int int_init_val = 0; @@ -4082,9 +4081,13 @@ get_initial_def_for_reduction (gimple *s else { /* Option2: the first element is INIT_VAL. */ - auto_vec elts (nunits); + + /* Enforced by vectorizable_reduction (which disallows double + reductions with variable-length vectors). */ + unsigned int count = nunits.to_constant (); + auto_vec elts (count); elts.quick_push (init_val); - for (i = 1; i < nunits; ++i) + for (unsigned int i = 1; i < count; ++i) elts.quick_push (def_for_init); init_def = gimple_build_vector (&stmts, vectype, elts); } @@ -4144,6 +4147,8 @@ get_initial_defs_for_reduction (slp_tree vector_type = STMT_VINFO_VECTYPE (stmt_vinfo); scalar_type = TREE_TYPE (vector_type); + /* vectorizable_reduction has already rejected SLP reductions on + variable-length vectors. */ nunits = TYPE_VECTOR_SUBPARTS (vector_type); gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def); @@ -4510,8 +4515,7 @@ vect_create_epilog_for_reduction (vec vtemp (nunits_out); - for (k = 0; k < nunits_out; ++k) - vtemp.quick_push (build_int_cst (cr_index_scalar_type, k + 1)); - tree series_vect = build_vector (cr_index_vector_type, vtemp); + tree series_vect = build_index_vector (cr_index_vector_type, 1, 1); /* Create a vector of the step value. */ tree step = build_int_cst (cr_index_scalar_type, nunits_out); @@ -4911,8 +4912,11 @@ vect_create_epilog_for_reduction (vec= 1); vec_mode = TYPE_MODE (vectype_in); + poly_uint64 nunits_out = TYPE_VECTOR_SUBPARTS (vectype_out); if (code == COND_EXPR) { @@ -6205,8 +6213,8 @@ vectorizable_reduction (gimple *stmt, gi int scalar_precision = GET_MODE_PRECISION (SCALAR_TYPE_MODE (scalar_type)); cr_index_scalar_type = make_unsigned_type (scalar_precision); - cr_index_vector_type = build_vector_type - (cr_index_scalar_type, TYPE_VECTOR_SUBPARTS (vectype_out)); + cr_index_vector_type = build_vector_type (cr_index_scalar_type, + nunits_out); optab = optab_for_tree_code (REDUC_MAX_EXPR, cr_index_vector_type, optab_default); @@ -6215,6 +6223,15 @@ vectorizable_reduction (gimple *stmt, gi epilog_reduc_code = REDUC_MAX_EXPR; } + if (epilog_reduc_code == ERROR_MARK && !nunits_out.is_constant ()) + { + if (dump_enabled_p ()) + dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, + "missing target support for reduction on" + " variable-length vectors.\n"); + return false; + } + if ((double_reduc || STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) != TREE_CODE_REDUCTION) && ncopies > 1) @@ -6226,6 +6243,27 @@ vectorizable_reduction (gimple *stmt, gi return false; } + if (double_reduc && !nunits_out.is_constant ()) + { + /* The current double-reduction code creates the initial value + element-by-element. */ + if (dump_enabled_p ()) + dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, + "double reduction not supported for variable-length" + " vectors.\n"); + return false; + } + + if (slp_node && !nunits_out.is_constant ()) + { + /* The current SLP code creates the initial value element-by-element. */ + if (dump_enabled_p ()) + dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, + "SLP reduction not supported for variable-length" + " vectors.\n"); + return false; + } + /* In case of widenning multiplication by a constant, we update the type of the constant to be the type of the other operand. We check that the constant fits the type in the pattern recognition pass. */