From patchwork Mon Oct 23 17:32:03 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 116824 Delivered-To: patch@linaro.org Received: by 10.140.22.164 with SMTP id 33csp4896229qgn; Mon, 23 Oct 2017 10:32:23 -0700 (PDT) X-Received: by 10.84.171.193 with SMTP id l59mr11028020plb.13.1508779943116; Mon, 23 Oct 2017 10:32:23 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1508779943; cv=none; d=google.com; s=arc-20160816; b=Kw49xIzl26Zrte0wZOKYdrx3I14kgfxY3eEk5v/NyCQdghAAG95XbOx66035jbyvro Yfk6ippLRyD7QbhU+nCoMOauK9fpZWqKsRHlr44SoY/HLjKOpYSdvy4ntHbSp38nj8Sb YGoAKgQW6mWSDn+C/YkzdqQzecastjYrec6n7taN5hVUi3cfifJSXvTFI7W2r1vfAP8H 8sKLxW13heObq6sdwGqkrrkwRDxgyNPX1dBoLMpMDnSkbUVq+PdM/1rPMMgOxxeR/Xfn vzZDOIEEOyW52HPepihcz8uiSARiYVk+wX1ybe7ly9VS2rWwiRGEQ6nxbd48cyEBJYgu uk9A== 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=DHNYP9FfFK5d+4VP8HMU2UZhh9RXX5LEP0C8/4Ndii8=; b=qeK3eG+niao/apDUlgby/+6RE/K4sZhOzR7u3BPsE/ZHA/2D37OPOXfOy4m56f/gUO +6VR6yIgevgyp1p+ubG+BCApwILiKFRWs78E9ckO3shaMMeMAQq6BUxfWpuzvkKTAiYv pfIndjKcLVQQWIpWsncAgaPCwMQpAoEzgUSkG2YNaBCS8d8MzpPWCsHlhBQkkj+hgC5M bmNnQUDLNb36d2JXc5TaUrTxiJMr84UKHU6/oPGjCCjl1aML/ElxAp69KMVG0gS+wj+P Avj5fggxI+MoBKR7fgiVpHL9lmxlf0IIMqgVr3OXt2Wkie3MAI8JrPVk9R/4l0Bft8ga 3zVA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=WlkuxIs8; spf=pass (google.com: domain of gcc-patches-return-464855-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-464855-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 u184si5668331pfb.20.2017.10.23.10.32.22 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 23 Oct 2017 10:32:23 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-464855-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=WlkuxIs8; spf=pass (google.com: domain of gcc-patches-return-464855-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-464855-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=OMzn27tLYcrs2AR9IznfO/vLSnLk5 +/ApyzDivt1HQJqzJIvwZmE57QyEm2aJYoCoWTPp2v2Lq9KeJ3RAb9+crFxl+OIe 7rM8oaUnLohVgwjZDotV6ZIljvEho4Zoc9dhEo7PtO8ueBjoEUBwG5lyDkTsxX8z EY1lccsTMuK5ck= 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=rNKTSSEVnX98A7wuCB9c/qV2oj0=; b=Wlk uxIs8RHmT4apVIGoHlu6C6bQtAcas8i2RJRBq0RX7AxcZP6cYMHIGWrt0HPUGhEz oct+d8McgxPcfMNFPBtkBsQi5wAzMyvmFMVRZVqW3toJUpAPgpYX7r8nGzP24fIH kgKZo1LwA9egfWjrBN/WXvTwExwcnNwe6OS9WNSA= Received: (qmail 42038 invoked by alias); 23 Oct 2017 17:32:09 -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 41349 invoked by uid 89); 23 Oct 2017 17:32:08 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-11.3 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM, SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mail-wr0-f175.google.com Received: from mail-wr0-f175.google.com (HELO mail-wr0-f175.google.com) (209.85.128.175) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 23 Oct 2017 17:32:07 +0000 Received: by mail-wr0-f175.google.com with SMTP id w105so8872922wrc.0 for ; Mon, 23 Oct 2017 10:32:07 -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=DHNYP9FfFK5d+4VP8HMU2UZhh9RXX5LEP0C8/4Ndii8=; b=WdSDLuEa6swXaXHz/lmqP7cAQhoLn1Gz74WysdBqf3tmHxnOVyJXNgth/nXHCdW7g1 PGP9IEbggtei75PYYKDX1wQ14qOe81RcFUzm0PwLqP054gpP2WJakJD3pyJX0eOn4dC/ WkLIR8Oo3AWhcMMz7GbkERJ7duhLn+PSgSihusoIloh/RA2TDVZQspl1WgBRBN1AHQDY Ea+pOEwal0wasDac7bF2vBchvP1IhIv4dyjXA2Oarg8/2P9s4dmUs+qEFIim1Ku7uzIG rp2IEMsCeA4i+2BNB8X0O/jNgSQYjvCivPb4qs0pasodzfgEyaxqfBnrhCC0elZY8sEy 7zMA== X-Gm-Message-State: AMCzsaUWlvodHfcX8KNrOfUKk1zGU3uSZSxhqfS9lN8wwOSVbgiE9ck5 LTE4WK8CPItE1wNy1ORT0h4+8/FhchU= X-Google-Smtp-Source: ABhQp+SAPmTXXPs5aQMfLyIB+S+TP6R3IX0zUo5Bf5+FKh8aWNRZf3+IkaaXuCNfGSVJSU7Y2QZ9BQ== X-Received: by 10.223.197.69 with SMTP id s5mr13079501wrf.120.1508779925137; Mon, 23 Oct 2017 10:32:05 -0700 (PDT) Received: from localhost ([2.26.27.199]) by smtp.gmail.com with ESMTPSA id e8sm6026477wmc.46.2017.10.23.10.32.03 for (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Mon, 23 Oct 2017 10:32:04 -0700 (PDT) From: Richard Sandiford To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@linaro.org Subject: [079/nnn] poly_int: vect_no_alias_p References: <871sltvm7r.fsf@linaro.org> Date: Mon, 23 Oct 2017 18:32:03 +0100 In-Reply-To: <871sltvm7r.fsf@linaro.org> (Richard Sandiford's message of "Mon, 23 Oct 2017 17:54:32 +0100") Message-ID: <87efpthiss.fsf@linaro.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.2 (gnu/linux) MIME-Version: 1.0 This patch replaces the two-state vect_no_alias_p with a three-state vect_compile_time_alias that handles polynomial segment lengths. 2017-10-23 Richard Sandiford Alan Hayward David Sherwood gcc/ * tree-vect-data-refs.c (vect_no_alias_p): Replace with... (vect_compile_time_alias): ...this new function. Do the calculation on poly_ints rather than trees. (vect_prune_runtime_alias_test_list): Update call accordingly. Index: gcc/tree-vect-data-refs.c =================================================================== --- gcc/tree-vect-data-refs.c 2017-10-23 17:22:34.681024458 +0100 +++ gcc/tree-vect-data-refs.c 2017-10-23 17:22:44.864968082 +0100 @@ -2989,52 +2989,49 @@ vect_vfa_segment_size (struct data_refer /* Function vect_no_alias_p. - Given data references A and B with equal base and offset, the alias - relation can be decided at compilation time, return TRUE if they do - not alias to each other; return FALSE otherwise. SEGMENT_LENGTH_A + Given data references A and B with equal base and offset, see whether + the alias relation can be decided at compilation time. Return 1 if + it can and the references alias, 0 if it can and the references do + not alias, and -1 if we cannot decide at compile time. SEGMENT_LENGTH_A and SEGMENT_LENGTH_B are the memory lengths accessed by A and B respectively. */ -static bool -vect_no_alias_p (struct data_reference *a, struct data_reference *b, - tree segment_length_a, tree segment_length_b) +static int +vect_compile_time_alias (struct data_reference *a, struct data_reference *b, + tree segment_length_a, tree segment_length_b) { - gcc_assert (TREE_CODE (DR_INIT (a)) == INTEGER_CST - && TREE_CODE (DR_INIT (b)) == INTEGER_CST); - if (tree_int_cst_equal (DR_INIT (a), DR_INIT (b))) - return false; + poly_offset_int offset_a = wi::to_poly_offset (DR_INIT (a)); + poly_offset_int offset_b = wi::to_poly_offset (DR_INIT (b)); + poly_uint64 const_length_a; + poly_uint64 const_length_b; - tree seg_a_min = DR_INIT (a); - tree seg_a_max = fold_build2 (PLUS_EXPR, TREE_TYPE (seg_a_min), - seg_a_min, segment_length_a); /* For negative step, we need to adjust address range by TYPE_SIZE_UNIT bytes, e.g., int a[3] -> a[1] range is [a+4, a+16) instead of [a, a+12) */ if (tree_int_cst_compare (DR_STEP (a), size_zero_node) < 0) { - tree unit_size = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (a))); - seg_a_min = fold_build2 (PLUS_EXPR, TREE_TYPE (seg_a_max), - seg_a_max, unit_size); - seg_a_max = fold_build2 (PLUS_EXPR, TREE_TYPE (DR_INIT (a)), - DR_INIT (a), unit_size); + const_length_a = (-wi::to_poly_wide (segment_length_a)).force_uhwi (); + offset_a = (offset_a + vect_get_scalar_dr_size (a)) - const_length_a; } - tree seg_b_min = DR_INIT (b); - tree seg_b_max = fold_build2 (PLUS_EXPR, TREE_TYPE (seg_b_min), - seg_b_min, segment_length_b); + else + const_length_a = tree_to_poly_uint64 (segment_length_a); if (tree_int_cst_compare (DR_STEP (b), size_zero_node) < 0) { - tree unit_size = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (b))); - seg_b_min = fold_build2 (PLUS_EXPR, TREE_TYPE (seg_b_max), - seg_b_max, unit_size); - seg_b_max = fold_build2 (PLUS_EXPR, TREE_TYPE (DR_INIT (b)), - DR_INIT (b), unit_size); + const_length_b = (-wi::to_poly_wide (segment_length_b)).force_uhwi (); + offset_b = (offset_b + vect_get_scalar_dr_size (b)) - const_length_b; } + else + const_length_b = tree_to_poly_uint64 (segment_length_b); - if (tree_int_cst_le (seg_a_max, seg_b_min) - || tree_int_cst_le (seg_b_max, seg_a_min)) - return true; + if (ranges_must_overlap_p (offset_a, const_length_a, + offset_b, const_length_b)) + return 1; + + if (!ranges_may_overlap_p (offset_a, const_length_a, + offset_b, const_length_b)) + return 0; - return false; + return -1; } /* Return true if the minimum nonzero dependence distance for loop LOOP_DEPTH @@ -3176,21 +3173,26 @@ vect_prune_runtime_alias_test_list (loop comp_res = data_ref_compare_tree (DR_OFFSET (dr_a), DR_OFFSET (dr_b)); - /* Alias is known at compilation time. */ + /* See whether the alias is known at compilation time. */ if (comp_res == 0 && TREE_CODE (DR_STEP (dr_a)) == INTEGER_CST && TREE_CODE (DR_STEP (dr_b)) == INTEGER_CST - && TREE_CODE (segment_length_a) == INTEGER_CST - && TREE_CODE (segment_length_b) == INTEGER_CST) + && poly_int_tree_p (segment_length_a) + && poly_int_tree_p (segment_length_b)) { - if (vect_no_alias_p (dr_a, dr_b, segment_length_a, segment_length_b)) + int res = vect_compile_time_alias (dr_a, dr_b, + segment_length_a, + segment_length_b); + if (res == 0) continue; - if (dump_enabled_p ()) - dump_printf_loc (MSG_NOTE, vect_location, - "not vectorized: compilation time alias.\n"); - - return false; + if (res == 1) + { + if (dump_enabled_p ()) + dump_printf_loc (MSG_NOTE, vect_location, + "not vectorized: compilation time alias.\n"); + return false; + } } dr_with_seg_len_pair_t dr_with_seg_len_pair