From patchwork Wed Dec 6 15:25:39 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 120870 Delivered-To: patch@linaro.org Received: by 10.140.22.227 with SMTP id 90csp7190417qgn; Wed, 6 Dec 2017 07:26:06 -0800 (PST) X-Google-Smtp-Source: AGs4zMaUiML/kHq1SxKV8EmVrL3bJCaT4BU2+Xs75nl6G2b8q/K8mYTzQqeYXZ0rgEzyO1kL4FeC X-Received: by 10.84.140.1 with SMTP id 1mr22304595pls.114.1512573966657; Wed, 06 Dec 2017 07:26:06 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1512573966; cv=none; d=google.com; s=arc-20160816; b=s3kZN9cC8dNjFBCnOEocjnV5V86LnDX8GqDkk6sfw9Bedj//yPNPm39NA0X2L8oady 3TqYGUNvqT38HBKro0axKX+wsN3HmxTO1VEy5AHavzrP2a16nlbTn1Bs6WcRIW1PhCRm /SlImXG2gmLkaVb6CdgPoyIy16AAcPBGb2u42mdfEYvIinUqVO9p6OPsvPrOFjti/mfl eNpDk4fsFlip4U06m+A8XDW5/pg2zsQ4cRWRA0AeZqUKZ8bvrj7MvtSUpL6DQZv21xb6 vQm+D6oZCJXCLSMedd1pTrW8GC8IT4Q/9Y/ttuJ6UfqM1KnS5e0DpgnqyHaE/8/4km+o WKlw== 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:cc: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=mCb1tGcolP8dID2nU84yoT9tIVrwHBIdFYASAtyCue0=; b=xWzTx5Ft49Cn3YzHVsy7s+4IO6T0MGOZGHDEiVvWu72WTvGH31lwqV3vOuAIjDfjsN ybAPsaJqA4YyuWXk6djxiXQsMbuWG+yxB6cNm0s8XFzm/oPpVvi4F3gPvR93WsFtU1jO dokDvJg64jKVIWcABV7Sf3h2AMtdtguosf6FxnZ57OdwjiRdgYNo6nWo2DT8bnVrWHoC ypQrBQUCqEzOq1aLUGZLAB2f3oG0jpAarpAeHckvYNyAS9Dk50xKWtftDP/OTsk6b+iy 94RwjIkxDY5ypM30jSDCCCVDUD8o02xqnpQwqkI7X/GTGKx6+JwwH1zKHULeAdfoKItk 7mRg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=Ly+K4nVD; spf=pass (google.com: domain of gcc-patches-return-468616-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-468616-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 f8si2170744pli.451.2017.12.06.07.26.06 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 06 Dec 2017 07:26:06 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-return-468616-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=Ly+K4nVD; spf=pass (google.com: domain of gcc-patches-return-468616-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-468616-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:cc:subject:references:date:in-reply-to:message-id :mime-version:content-type; q=dns; s=default; b=lMdcV8mKYIrOLEmq AvT4xLOc4G6G5ITZNz1s/5r9a3CjH3xHQIlvgXH2gf3ziZ2K1vU6iAlpvy+O8aJw XhquwBbfLjFyOm77yw0J5DldmgjOAFPZAo6y2wEmIrmvMbxSRBp4ZbdSm86MhxiD kaN9NQs4WmGIYJ41C14KVtTwbnw= 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:cc:subject:references:date:in-reply-to:message-id :mime-version:content-type; s=default; bh=LcA/k8lUcggWpit9pNgUUm BPDqs=; b=Ly+K4nVDwspDAI7Byr6tqZXnFOIUA+LTLFS0BnSKHD6Wjj6LDtT5bY /f2GZjg6ImjExumYbgkGTfLoKAs/nKQ8ddn7Cwt8FXQCaO1vAnllQpM2D/HroLtS sLGBUythZMHCRpbXn8TZgBTscPr3sFWIZuKt8QGLyLIe/vK693bJ8= Received: (qmail 25225 invoked by alias); 6 Dec 2017 15:25:54 -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 22919 invoked by uid 89); 6 Dec 2017 15:25:47 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-15.5 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mail-wr0-f169.google.com Received: from mail-wr0-f169.google.com (HELO mail-wr0-f169.google.com) (209.85.128.169) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 06 Dec 2017 15:25:44 +0000 Received: by mail-wr0-f169.google.com with SMTP id x49so4292236wrb.13 for ; Wed, 06 Dec 2017 07:25:44 -0800 (PST) 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:cc:subject:references :date:in-reply-to:message-id:user-agent:mime-version; bh=mCb1tGcolP8dID2nU84yoT9tIVrwHBIdFYASAtyCue0=; b=Ag22T3lnjvx+Ixc0Zzsc7sDLwfEDAHAI7yPS89f3hHL7PKTDUACXBa1+seQy7d+uKA n8OTnVKv7jZijmfk0S6K9UJzbnm4zOKydBJeP1FIyW7b7LbRfarRT1Zu5eK6DB6tFvWg knkLtjCa9EZTy/SVCcBivTZN5nbKC4l7G/DvZUZQTvzO5vjgzN0rWeOq+p5eFTlfygt5 7QUr1Ayf7CCN1X5JBYxmN+7QHI5Apg1767408EENhT4ux+SAp2oTQF62CvWVBbYRQlBU qqgSYI0E1DFfIgeem11ekGwl9oAS+sHzQDdBHpgcszYxLhUlBRvsSaK2F6JAl2CUzblK ByrA== X-Gm-Message-State: AJaThX7QZ0/1ims+1Cm1mmVhFY0xLk4dRQnXAP1stu4cbcqHs2L5FWCO 6outL3tG5Uk8wvoRAPC33M5WPJI26rs= X-Received: by 10.223.160.61 with SMTP id k58mr19146090wrk.252.1512573942348; Wed, 06 Dec 2017 07:25:42 -0800 (PST) Received: from localhost (188.29.165.206.threembb.co.uk. [188.29.165.206]) by smtp.gmail.com with ESMTPSA id u5sm3062153wmf.47.2017.12.06.07.25.41 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Wed, 06 Dec 2017 07:25:41 -0800 (PST) From: Richard Sandiford To: Richard Biener Mail-Followup-To: Richard Biener , GCC Patches , richard.sandiford@linaro.org Cc: GCC Patches Subject: Make gimple_build_vector take a tree_vector_builder References: <87shcxl2ka.fsf@linaro.org> <87efohkohu.fsf@linaro.org> <87efof9a6h.fsf@linaro.org> <87fu8nao27.fsf@linaro.org> Date: Wed, 06 Dec 2017 15:25:39 +0000 In-Reply-To: <87fu8nao27.fsf@linaro.org> (Richard Sandiford's message of "Wed, 06 Dec 2017 15:11:44 +0000") Message-ID: <87vahj98uk.fsf_-_@linaro.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.3 (gnu/linux) MIME-Version: 1.0 This patch changes gimple_build_vector so that it takes a tree_vector_builder instead of a size and a vector of trees. Tested on aarch64-linux-gnu, x86_64-linux-gnu and powerpc64le-linux-gnu. Also spot-checked on sparc64-linux-gnu. OK to install? Thanks, Richard 2017-12-06 Richard Sandiford gcc/ * vector-builder.h (vector_builder::derived): New const overload. (vector_builder::elt): New function. * tree-vector-builder.h (tree_vector_builder::type): New function. (tree_vector_builder::apply_step): Declare. * tree-vector-builder.c (tree_vector_builder::apply_step): New function. * gimple-fold.h (tree_vector_builder): Declare. (gimple_build_vector): Take a tree_vector_builder instead of a type and vector of elements. * gimple-fold.c (gimple_build_vector): Likewise. * tree-vect-loop.c (get_initial_def_for_reduction): Update call accordingly. (get_initial_defs_for_reduction): Likewise. (vectorizable_induction): Likewise. Index: gcc/vector-builder.h =================================================================== --- gcc/vector-builder.h 2017-12-06 14:46:14.133599820 +0000 +++ gcc/vector-builder.h 2017-12-06 14:49:04.289693414 +0000 @@ -68,6 +68,10 @@ #define GCC_VECTOR_BUILDER_H given integral_p (ELT1) && integral_p (ELT2). There is no fixed choice of StepType. + T apply_step (T base, unsigned int factor, StepType step) const; + + Return a vector element with the value BASE + FACTOR * STEP. + bool can_elide_p (T elt) const; Return true if we can drop element ELT, even if the retained @@ -91,6 +95,7 @@ #define GCC_VECTOR_BUILDER_H unsigned int nelts_per_pattern () const { return m_nelts_per_pattern; } unsigned int encoded_nelts () const; bool encoded_full_vector_p () const; + T elt (unsigned int) const; void finalize (); @@ -163,6 +168,38 @@ vector_builder::new_vector ( this->truncate (0); } +/* Return the value of vector element I, which might or might not be + encoded explicitly. */ + +template +T +vector_builder::elt (unsigned int i) const +{ + /* This only makes sense if the encoding has been fully populated. */ + gcc_checking_assert (encoded_nelts () <= this->length ()); + + /* First handle elements that are already present in the underlying + vector, regardless of whether they're part of the encoding or not. */ + if (i < this->length ()) + return (*this)[i]; + + /* Identify the pattern that contains element I and work out the index of + the last encoded element for that pattern. */ + unsigned int pattern = i % m_npatterns; + unsigned int count = i / m_npatterns; + unsigned int final_i = encoded_nelts () - m_npatterns + pattern; + T final = (*this)[final_i]; + + /* If there are no steps, the final encoded value is the right one. */ + if (m_nelts_per_pattern <= 2) + return final; + + /* Otherwise work out the value from the last two encoded elements. */ + T prev = (*this)[final_i - m_npatterns]; + return derived ()->apply_step (final, count - 2, + derived ()->step (prev, final)); +} + /* Change the encoding to NPATTERNS patterns of NELTS_PER_PATTERN each, but without changing the underlying vector. */ Index: gcc/tree-vector-builder.h =================================================================== --- gcc/tree-vector-builder.h 2017-12-06 14:49:00.386854068 +0000 +++ gcc/tree-vector-builder.h 2017-12-06 14:49:04.289693414 +0000 @@ -45,6 +45,7 @@ #define GCC_TREE_VECTOR_BUILDER_H bool allow_steps_p () const; bool integral_p (const_tree) const; wide_int step (const_tree, const_tree) const; + tree apply_step (tree, unsigned int, const wide_int &) const; bool can_elide_p (const_tree) const; void note_representative (tree *, tree); Index: gcc/tree-vector-builder.c =================================================================== --- gcc/tree-vector-builder.c 2017-12-06 14:49:00.386854068 +0000 +++ gcc/tree-vector-builder.c 2017-12-06 14:49:04.289693414 +0000 @@ -96,6 +96,16 @@ tree_vector_builder::new_binary_operatio return true; } +/* Return a vector element with the value BASE + FACTOR * STEP. */ + +tree +tree_vector_builder::apply_step (tree base, unsigned int factor, + const wide_int &step) const +{ + return wide_int_to_tree (TREE_TYPE (base), + wi::to_wide (base) + factor * step); +} + /* Return a VECTOR_CST for the current constant. */ tree Index: gcc/gimple-fold.h =================================================================== --- gcc/gimple-fold.h 2017-11-29 11:06:33.003002371 +0000 +++ gcc/gimple-fold.h 2017-12-06 14:49:04.288693455 +0000 @@ -135,11 +135,13 @@ gimple_build_vector_from_val (gimple_seq return gimple_build_vector_from_val (seq, UNKNOWN_LOCATION, type, op); } -extern tree gimple_build_vector (gimple_seq *, location_t, tree, vec); +class tree_vector_builder; +extern tree gimple_build_vector (gimple_seq *, location_t, + tree_vector_builder *); inline tree -gimple_build_vector (gimple_seq *seq, tree type, vec elts) +gimple_build_vector (gimple_seq *seq, tree_vector_builder *builder) { - return gimple_build_vector (seq, UNKNOWN_LOCATION, type, elts); + return gimple_build_vector (seq, UNKNOWN_LOCATION, builder); } extern bool gimple_stmt_nonnegative_warnv_p (gimple *, bool *, int = 0); Index: gcc/gimple-fold.c =================================================================== --- gcc/gimple-fold.c 2017-12-06 14:48:52.888162175 +0000 +++ gcc/gimple-fold.c 2017-12-06 14:49:04.288693455 +0000 @@ -7178,23 +7178,30 @@ gimple_build_vector_from_val (gimple_seq return res; } -/* Build a vector of type TYPE in which the elements have the values - given by ELTS. Return a gimple value for the result, appending any - new instructions to SEQ. */ +/* Build a vector from BUILDER, handling the case in which some elements + are non-constant. Return a gimple value for the result, appending any + new instructions to SEQ. + + BUILDER must not have a stepped encoding on entry. This is because + the function is not geared up to handle the arithmetic that would + be needed in the variable case, and any code building a vector that + is known to be constant should use BUILDER->build () directly. */ tree -gimple_build_vector (gimple_seq *seq, location_t loc, tree type, - vec elts) +gimple_build_vector (gimple_seq *seq, location_t loc, + tree_vector_builder *builder) { - unsigned int nelts = elts.length (); - gcc_assert (nelts == TYPE_VECTOR_SUBPARTS (type)); - for (unsigned int i = 0; i < nelts; ++i) - if (!TREE_CONSTANT (elts[i])) + gcc_assert (builder->nelts_per_pattern () <= 2); + unsigned int encoded_nelts = builder->encoded_nelts (); + for (unsigned int i = 0; i < encoded_nelts; ++i) + if (!TREE_CONSTANT ((*builder)[i])) { + tree type = builder->type (); + unsigned int nelts = TYPE_VECTOR_SUBPARTS (type); vec *v; vec_alloc (v, nelts); for (i = 0; i < nelts; ++i) - CONSTRUCTOR_APPEND_ELT (v, NULL_TREE, elts[i]); + CONSTRUCTOR_APPEND_ELT (v, NULL_TREE, builder->elt (i)); tree res; if (gimple_in_ssa_p (cfun)) @@ -7206,7 +7213,7 @@ gimple_build_vector (gimple_seq *seq, lo gimple_seq_add_stmt_without_update (seq, stmt); return res; } - return build_vector (type, elts); + return builder->build (); } /* Return true if the result of assignment STMT is known to be non-negative. Index: gcc/tree-vect-loop.c =================================================================== --- gcc/tree-vect-loop.c 2017-12-06 14:48:52.889162134 +0000 +++ gcc/tree-vect-loop.c 2017-12-06 14:49:04.289693414 +0000 @@ -3968,11 +3968,9 @@ 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; 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; @@ -3980,7 +3978,6 @@ get_initial_def_for_reduction (gimple *s gimple_seq stmts = NULL; gcc_assert (vectype); - nunits = TYPE_VECTOR_SUBPARTS (vectype); gcc_assert (POINTER_TYPE_P (scalar_type) || INTEGRAL_TYPE_P (scalar_type) || SCALAR_FLOAT_TYPE_P (scalar_type)); @@ -4053,11 +4050,10 @@ get_initial_def_for_reduction (gimple *s else { /* Option2: the first element is INIT_VAL. */ - auto_vec elts (nunits); + tree_vector_builder elts (vectype, 1, 2); elts.quick_push (init_val); - for (i = 1; i < nunits; ++i) - elts.quick_push (def_for_init); - init_def = gimple_build_vector (&stmts, vectype, elts); + elts.quick_push (def_for_init); + init_def = gimple_build_vector (&stmts, &elts); } } break; @@ -4182,7 +4178,7 @@ get_initial_defs_for_reduction (slp_tree number_of_copies = nunits * number_of_vectors / group_size; number_of_places_left_in_vector = nunits; - auto_vec elts (nunits); + tree_vector_builder elts (vector_type, nunits, 1); elts.quick_grow (nunits); for (j = 0; j < number_of_copies; j++) { @@ -4205,12 +4201,14 @@ get_initial_defs_for_reduction (slp_tree if (number_of_places_left_in_vector == 0) { gimple_seq ctor_seq = NULL; - tree init = gimple_build_vector (&ctor_seq, vector_type, elts); + tree init = gimple_build_vector (&ctor_seq, &elts); if (ctor_seq != NULL) gsi_insert_seq_on_edge_immediate (pe, ctor_seq); voprnds.quick_push (init); number_of_places_left_in_vector = nunits; + elts.new_vector (vector_type, nunits, 1); + elts.quick_grow (nunits); } } } @@ -6698,7 +6696,7 @@ vectorizable_induction (gimple *phi, unsigned ivn; for (ivn = 0; ivn < nivs; ++ivn) { - auto_vec elts (nunits); + tree_vector_builder elts (vectype, nunits, 1); stmts = NULL; for (unsigned eltn = 0; eltn < nunits; ++eltn) { @@ -6708,7 +6706,7 @@ vectorizable_induction (gimple *phi, elt, step_expr); elts.quick_push (elt); } - vec_init = gimple_build_vector (&stmts, vectype, elts); + vec_init = gimple_build_vector (&stmts, &elts); if (stmts) { new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts); @@ -6815,7 +6813,7 @@ vectorizable_induction (gimple *phi, stmts = NULL; new_name = gimple_convert (&stmts, TREE_TYPE (vectype), init_expr); - auto_vec elts (nunits); + tree_vector_builder elts (vectype, nunits, 1); elts.quick_push (new_name); for (i = 1; i < nunits; i++) { @@ -6826,7 +6824,7 @@ vectorizable_induction (gimple *phi, } /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */ - vec_init = gimple_build_vector (&stmts, vectype, elts); + vec_init = gimple_build_vector (&stmts, &elts); if (stmts) { new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);