From patchwork Wed Mar 21 08:31:22 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 132192 Delivered-To: patch@linaro.org Received: by 10.46.84.29 with SMTP id i29csp1861644ljb; Wed, 21 Mar 2018 01:31:43 -0700 (PDT) X-Google-Smtp-Source: AG47ELv3GjCNQHPq0vV34M99bSs6EMU/pXrEQMmzNVfP8Av/dAcbTuZPnL/KoESL0HOzhIyHexrN X-Received: by 10.101.90.203 with SMTP id d11mr13910255pgt.20.1521621103611; Wed, 21 Mar 2018 01:31:43 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1521621103; cv=none; d=google.com; s=arc-20160816; b=Eo8/ynN5GWQ3+NtffdYCTQChz9QkltlZ/FlKRJwyNLDZ3O0iuKzKeXz1BJBGCpoHuT Ix3ymMU4J++Vx7ucn4eMPvCaqAm+OUD5y3NAgJ9qtOHISVGITINmyfiS/oUGHzBHV/Wx pmvcjF/PgAMPqBqorGSQwC0gS0hGYXyx2Wdu23XJTTeDUMXcThW3uZfFVnBOcuvgHLrx sNHnfTBUXqCkKxKb/o64AF3BTC/caqVGOPFrGITKHfUfZ5lTrJT9EnSfboasrwbpLk/L I5pMUuvbckeH+6mxNMuMikw3xuTlNbCrOY3dL4OPfipYET3Z8MCby9nraJ+vBCEjnncA Am7Q== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=mime-version:user-agent:message-id:date: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=aVF7CuI1foy9y82BpuzujhkPqFsG3kcdpPnWzCCz/18=; b=Ql7J9UoEeAdyicDHn79+h6BNLBL6Z1lGF7ARz4GYaxVXp6m2zX4v+zjcLorts8iDbB BB2BUaI+HctFhn8W1HyL5SOvUcgCjBrCKW+j+RxCKxsAwdy13n6fYhJp+XEbxmHgd/Ol ZtcJOvALsY5T6QLjMhmKXAdVcO046ohnGw54ZgH1CncJvHDEWYwS2/8udX7xYWdGGnYW 3M9vz2mRoilkfQexFRLYC5lTE1tFlbUZqIGxUzx9TBL1s67H170u+4Njx29Zr5G7VDD4 8zXkuAUC6jWNZc/21kkv89DmoU/QW56N0Gb6rwXvxmLjbQiXk617VR2Cc9IH9Tx5OhGo LVIA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=IHArZtOX; spf=pass (google.com: domain of gcc-patches-return-475120-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-475120-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 l7-v6si3586256plg.82.2018.03.21.01.31.43 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 21 Mar 2018 01:31:43 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-475120-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=IHArZtOX; spf=pass (google.com: domain of gcc-patches-return-475120-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-475120-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:date:message-id:mime-version:content-type; q=dns; s= default; b=ZvSWSQa625J4xfHcU1vToEFELnZxCZtWAjUI/rTqqRm5xuNgThzHR 5fBg1A8SbbTmt3JFkGcneebRq713nUYUnBw1KkDGenVZVzEGGAbSaPeqWITjm2bp WfTNGnfkHTqFFug0vcmBRG48liBXFB9786/kwdM8V++AvzMeZo9rHk= 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:date:message-id:mime-version:content-type; s= default; bh=1crGRW2PVO2P9iuFpXETOdRlYF4=; b=IHArZtOXU0AA4gfgobdI YEMNG93ikEa4dGhhlR+PXFmEa4yB8FGGFR8kdu5ITIGqdCtfJpDxMefvcBeKYAGN edNmC2/13s+KlpyX6rKeIlFZ7iBbYzHl9WFwpXMilrDE858lBBdPBNqpYUGvDV5f Ae8SlCl1L0ujdOoB9yYrkIM= Received: (qmail 19774 invoked by alias); 21 Mar 2018 08:31:31 -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 19377 invoked by uid 89); 21 Mar 2018 08:31:30 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-10.8 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=Applying, HX-Received:Wed, positions X-HELO: mail-wr0-f182.google.com Received: from mail-wr0-f182.google.com (HELO mail-wr0-f182.google.com) (209.85.128.182) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 21 Mar 2018 08:31:27 +0000 Received: by mail-wr0-f182.google.com with SMTP id z73so4266737wrb.0 for ; Wed, 21 Mar 2018 01:31:27 -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:date:message-id :user-agent:mime-version; bh=aVF7CuI1foy9y82BpuzujhkPqFsG3kcdpPnWzCCz/18=; b=J5LWUWdjK3BtFlvpLfmuX+yG7N0ObqcX8uHUaI+38QX9hWP6Dj2s2qIFRRWXgB4LiB LkXWpxJ6Jb+uRJF34SGF9eS7BkCNN7ayj/MOD2mySJSnJZHI8DAqcYCNPi4o+RAA31Ez Ooh6LdjmZBE4xJZXMyZ/48Lo5ZR586MnPIOxnlsX95qRUgYAUc2Zm3pma9A4+rlMUnFU 5f893VJqK+/KHZ5QqKlimYe9Kngd531QUaZA/zG4UQLqLnB5hQbaU0gXW+SS7xxDAOuw sWTdCG7lbHEFbZC2AFrKopjfcu8BL1jxee1SGJP5JDwNSaFZTrZdmIv89WzTpi0BIRLz NfIg== X-Gm-Message-State: AElRT7FeYvaF5DcxngVbUW+QABQRm8D2KwBpTIKn4JPdW8gGFa030jjU lMcCem8pSixaIHG0s8vDuZQ8GeXMaoU= X-Received: by 10.223.186.18 with SMTP id o18mr16536427wrg.158.1521621085304; Wed, 21 Mar 2018 01:31:25 -0700 (PDT) Received: from localhost ([217.140.96.141]) by smtp.gmail.com with ESMTPSA id e17sm4417804wmf.1.2018.03.21.01.31.23 for (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Wed, 21 Mar 2018 01:31:24 -0700 (PDT) From: Richard Sandiford To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@linaro.org Subject: poly_span_traits fixes (PR 84811) Date: Wed, 21 Mar 2018 08:31:22 +0000 Message-ID: <87605pzv6t.fsf@linaro.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.3 (gnu/linux) MIME-Version: 1.0 This patch fixes incorrect results for HOST_WIDE_INT positions at opposite extremes when used with HOST_WIDE_INT sizes. It also fixes UB when comparing such positions with unsigned HOST_WIDE_INT sizes (although the results in that case were wrapv-correct). Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install? Richard 2018-03-21 Richard Sandiford gcc/ PR tree-optimization/84811 * poly-int.h (poly_span_traits): Remove the T3 parameter and promote HOST_WIDE_INT T2 - T1 results to unsigned HOST_WIDE_INT. (maybe_in_range_p, known_in_range_p, ranges_known_overlap_p): (known_subrange_p): Update accordingly. Cast each value involved in the size comparison, rather than casting the result of the subtraction. gcc/testsuite/ PR tree-optimization/84811 * gcc.dg/torture/pr84811.c: New test. Index: gcc/poly-int.h =================================================================== --- gcc/poly-int.h 2018-01-14 08:42:44.497155977 +0000 +++ gcc/poly-int.h 2018-03-21 08:28:14.656720617 +0000 @@ -2399,30 +2399,34 @@ print_dec (const poly_int_pod &val poly_coeff_traits::signedness ? SIGNED : UNSIGNED); } -/* Helper for correctly comparing Pos - Start with Size in cases where - known_ge (Pos, Start), Pos and Start are potentially signed, and Size is - potentially unsigned. Applying the cast function to the result of - Pos - Start gives the value that should be compared with the size. - - Try to avoid doing any unnecessary arithmetic or copying. */ -template +/* Helper for calculating the distance between two points P1 and P2, + in cases where known_le (P1, P2). T1 and T2 are the types of the + two positions, in either order. The coefficients of P2 - P1 have + type unsigned HOST_WIDE_INT if the coefficients of both T1 and T2 + have C++ primitive type, otherwise P2 - P1 has its usual + wide-int-based type. + + The actual subtraction should look something like this: + + typedef poly_span_traits span_traits; + span_traits::cast (P2) - span_traits::cast (P1) + + Applying the cast before the subtraction avoids undefined overflow + for signed T1 and T2. + + The implementation of the cast tries to avoid unnecessary arithmetic + or copying. */ +template struct poly_span_traits { - /* Assume no cast is needed. We'll get a warning about signed vs. - unsigned comparisons if the assumption is wrong. */ template static const T &cast (const T &x) { return x; } }; -/* The only case a change in type is needed is this one, in which the - subtraction would give a HOST_WIDE_INT-based result if done on poly_ints - and adding a zero size would give an unsigned HOST_WIDE_INT-based - result. Since we know known_ge (Pos, Start), it is safe to treat - Pos - Start as an unsigned HOST_WIDE_INT. */ -template -struct poly_span_traits +template +struct poly_span_traits { template static typename if_nonpoly::type @@ -2451,7 +2455,8 @@ known_size_p (const T &a) inline bool maybe_in_range_p (const T1 &val, const T2 &pos, const T3 &size) { - typedef poly_span_traits span; + typedef poly_span_traits start_span; + typedef poly_span_traits size_span; if (known_lt (val, pos)) return false; if (!known_size_p (size)) @@ -2462,7 +2467,8 @@ maybe_in_range_p (const T1 &val, const T /* In this case we don't know whether VAL >= POS is true at compile time, so we can't prove that VAL >= POS + SIZE. */ return true; - return maybe_lt (span::cast (val - pos), size); + return maybe_lt (start_span::cast (val) - start_span::cast (pos), + size_span::cast (size)); } /* Return true if range [POS, POS + SIZE) is known to include VAL. @@ -2473,10 +2479,12 @@ maybe_in_range_p (const T1 &val, const T inline bool known_in_range_p (const T1 &val, const T2 &pos, const T3 &size) { - typedef poly_span_traits span; + typedef poly_span_traits start_span; + typedef poly_span_traits size_span; return (known_size_p (size) && known_ge (val, pos) - && known_lt (span::cast (val - pos), size)); + && known_lt (start_span::cast (val) - start_span::cast (pos), + size_span::cast (size))); } /* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2) @@ -2504,8 +2512,9 @@ ranges_maybe_overlap_p (const T1 &pos1, ranges_known_overlap_p (const T1 &pos1, const T2 &size1, const T3 &pos2, const T4 &size2) { - typedef poly_span_traits span1; - typedef poly_span_traits span2; + typedef poly_span_traits start_span; + typedef poly_span_traits size1_span; + typedef poly_span_traits size2_span; /* known_gt (POS1 + SIZE1, POS2) [infinite precision] --> known_gt (SIZE1, POS2 - POS1) [infinite precision] --> known_gt (SIZE1, POS2 - lower_bound (POS1, POS2)) [infinite precision] @@ -2520,8 +2529,12 @@ ranges_known_overlap_p (const T1 &pos1, which the indeterminate is zero (the minimum value). */ return (known_size_p (size1) && known_size_p (size2) - && known_lt (span1::cast (pos2 - lower_bound (pos1, pos2)), size1) - && known_lt (span2::cast (pos1 - lower_bound (pos1, pos2)), size2)); + && known_lt (start_span::cast (pos2) + - start_span::cast (lower_bound (pos1, pos2)), + size1_span::cast (size1)) + && known_lt (start_span::cast (pos1) + - start_span::cast (lower_bound (pos1, pos2)), + size2_span::cast (size2))); } /* Return true if range [POS1, POS1 + SIZE1) is known to be a subrange of @@ -2534,15 +2547,16 @@ known_subrange_p (const T1 &pos1, const const T3 &pos2, const T4 &size2) { typedef typename poly_int_traits::coeff_type C2; - typedef POLY_BINARY_COEFF (T2, T4) size_diff_type; - typedef poly_span_traits span; + typedef poly_span_traits start_span; + typedef poly_span_traits size_span; return (known_gt (size1, POLY_INT_TYPE (T2) (0)) && (poly_coeff_traits::signedness > 0 || known_size_p (size1)) && known_size_p (size2) && known_ge (pos1, pos2) && known_le (size1, size2) - && known_le (span::cast (pos1 - pos2), size2 - size1)); + && known_le (start_span::cast (pos1) - start_span::cast (pos2), + size_span::cast (size2) - size_span::cast (size1))); } /* Return true if the endpoint of the range [POS, POS + SIZE) can be Index: gcc/testsuite/gcc.dg/torture/pr84811.c =================================================================== --- /dev/null 2018-03-17 08:19:33.716019995 +0000 +++ gcc/testsuite/gcc.dg/torture/pr84811.c 2018-03-21 08:28:14.660640089 +0000 @@ -0,0 +1,20 @@ +/* { dg-do compile { target lp64 } } */ + +int a; +long b[1][9]; +typedef long V __attribute__((vector_size (16), may_alias)); + +void +foo () +{ + V *c = (V *) ((char *) b + -9060696663385964544); + *c = (V) { 1, 1 }; + c++; + *c = (V) { 1, 1 }; + c++; + *c = (V) { 1, 1 }; + c++; + *c = (V) { 1, 1 }; + long __attribute__((may_alias)) *d = (long *) ((char *) b + 162675373468811328); + *d = 1; +}