From patchwork Thu May 25 15:15:20 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Bin.Cheng" X-Patchwork-Id: 766989 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.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3wYXsQ2qYzz9s7y for ; Fri, 26 May 2017 01:16:09 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="QT9MJMPI"; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:in-reply-to:references:from:date:message-id :subject:to:content-type; q=dns; s=default; b=xuKbEwR9o7IQfv7MiH oOECu5dSVI1SbQCkP2w6LhR1atv0txBVdLgvamSA9XSs6Hvn4FQZ1NmQ/be3WDu2 zyijhgrTH4tv/ACs25AaHfh0E5iFpKfsDx7dhjJsVH0rh8dTyRBnGyO8GRd4Iarp PIVEFfASE7F0ye6hCOOKHcOBI= 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 :mime-version:in-reply-to:references:from:date:message-id :subject:to:content-type; s=default; bh=RmzB6A7jeJIkzKTPwzBmqlvD EK4=; b=QT9MJMPIc4qLt/HwrlusZSkiJQXnl98SirtT5KC8LxRgugO7mKXbT9z+ ZVNeVrgE6y9LdMe4pI7a04uJNoLsiBqR5LYsSEDk6i2TPTXOT0K/yKJjy9o617Iu DDVdwcqz4XacLKR7pwUs+8qSglC7dvSgGA5xHtrOQ4BAlhKn8UU= Received: (qmail 69316 invoked by alias); 25 May 2017 15:15:46 -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 69206 invoked by uid 89); 25 May 2017 15:15:36 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-24.2 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, GIT_PATCH_0, GIT_PATCH_1, 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-vk0-f51.google.com Received: from mail-vk0-f51.google.com (HELO mail-vk0-f51.google.com) (209.85.213.51) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 25 May 2017 15:15:20 +0000 Received: by mail-vk0-f51.google.com with SMTP id y190so93305293vkc.1 for ; Thu, 25 May 2017 08:15:23 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=ub8UqdUIEZMlitgO71nKStc98HkTE35iCsgo89Zj0eI=; b=WJRQ6ur0nCOdIq58+XO6zkxq0R2Qdpv03boFOJAH16xILYZr30dG8atFHQx5J7yQ7z j2URuTmFeMkmdPqxlkOV7wUX6nO7v81WzdB4etS5Bqbnr7ksYCgQ1NrHM58ijFc1UoAs VEUlCws+HafdkaJ+NAVtNNdnuVTdwHRdX0OHtcpofSMB8B2C4Q6psjkRmT5WB29xfy2D 1ofk8Ua2rMeAQEItwpSqyrmsGi7w04Kb7M6vD+TMb3Ti3S6nuo7yr4Lcgm7LMpcByftO J2f+FKjBb+9NzaAM7seFTx1/STKppD+ESeaWGyH7+QJXdYbSKxNesNb3FH3menzhMxpL 1xbQ== X-Gm-Message-State: AODbwcDwq0swpY/HtKYPG0NV0JOElM8N0baRJwLxv8IDA+wV3Vf4ZneH sI/mLieLRzkAIkZuymjWuABFk8Wd8w== X-Received: by 10.31.61.16 with SMTP id k16mr17003079vka.43.1495725321412; Thu, 25 May 2017 08:15:21 -0700 (PDT) MIME-Version: 1.0 Received: by 10.103.49.9 with HTTP; Thu, 25 May 2017 08:15:20 -0700 (PDT) In-Reply-To: <87a862zfrt.fsf@linaro.org> References: <87r2zfzch4.fsf@linaro.org> <87a862zfrt.fsf@linaro.org> From: "Bin.Cheng" Date: Thu, 25 May 2017 16:15:20 +0100 Message-ID: Subject: Re: [PATCH GCC][3/6]Fix PR80815 by handling negative DR_STEPs in runtime alias check To: "Bin.Cheng" , "gcc-patches@gcc.gnu.org" , Richard Sandiford X-IsSubscribed: yes On Wed, May 24, 2017 at 11:54 AM, Richard Sandiford wrote: > "Bin.Cheng" writes: >> On Tue, May 23, 2017 at 6:53 PM, Richard Sandiford >> wrote: >>> AIUI, the reason the old code mishandled negative steps was that the >>> associated segment lengths were stored as sizetype and so looked like >>> big unsigned values. Those values therefore satisfied tree_fits_uhwi_p >>> even though they were semantically negative. Is that right? >> Yes, and the undesired wrapping behavior when such large unsigned hwi >> is involved in computation. But I think there are possible leaks in >> the code even after this patch, as embedded below. >>> >>> Assuming yes, and quoting the change as a context diff... >>> >>>> diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c >>>> index a5f8c1c..f0799d9 100644 >>>> *** a/gcc/tree-data-ref.c >>>> --- b/gcc/tree-data-ref.c >>>> *************** >>>> *** 1259,1264 **** >>>> --- 1259,1273 ---- >>>> != tree_int_cst_compare (DR_STEP (dr_a2->dr), size_zero_node)) >>>> continue; >>>> >>>> + bool neg_step >>>> + = (tree_int_cst_compare (DR_STEP (dr_a1->dr), size_zero_node) < 0); >>>> + >>>> + /* DR_A1 and DR_A2 must have the same step if it's negative. */ >>>> + if (neg_step >>>> + && tree_int_cst_compare (DR_STEP (dr_a1->dr), >>>> + DR_STEP (dr_a2->dr)) != 0) >>>> + continue; >>>> + >>> >>> [Why do they need to be the same step?] >> There are two reasons. First is to simplify diff computation between >> dr_a1 and dr_a2, otherwise we need to adjust diff for negative steps. > > What kind of adjustment would be needed? Could you give an example? I handled negative step in updated patch by adjusting diff according to access size of references. > >> And wrapping behavior needs to be handled when adjusting diff with >> steps. The second reason is not fully handled in this patch. We now >> only set merged segment length to MAX only when both dr_a1->seg_len >> and dr_a2->seg_len are constant, as below: >> + if (tree_fits_uhwi_p (dr_a1->seg_len) >> + && tree_fits_uhwi_p (dr_a2->seg_len)) >> + new_seg_len >> + = size_int (MAX (tree_to_uhwi (dr_a1->seg_len), >> + diff + tree_to_uhwi (dr_a2->seg_len))); >> + else >> + new_seg_len >> + = size_binop (PLUS_EXPR, dr_a2->seg_len, size_int (diff)); >> In fact, we should do this for else branch too. with different steps, >> it is still possible that dr_a1-seg_len > dr_a2->seg_len + diff. Here >> I only restrict it to negative DR_STEP. Patch updated with >> explanation in comment. >>> >>>> /* Make sure dr_a1 starts left of dr_a2. */ >>>> if (tree_int_cst_lt (DR_INIT (dr_a2->dr), DR_INIT (dr_a1->dr))) >>>> std::swap (*dr_a1, *dr_a2); >>>> *************** >>>> *** 1266,1325 **** >>>> bool do_remove = false; >>>> unsigned HOST_WIDE_INT diff >>>> = (tree_to_shwi (DR_INIT (dr_a2->dr)) >>>> ! - tree_to_shwi (DR_INIT (dr_a1->dr))); >>>> >>>> ! /* If the left segment does not extend beyond the start of the >>>> ! right segment the new segment length is that of the right >>>> ! plus the segment distance. */ >>>> ! if (tree_fits_uhwi_p (dr_a1->seg_len) >>>> ! && compare_tree_int (dr_a1->seg_len, diff) <= 0) >>>> { >>>> ! dr_a1->seg_len = size_binop (PLUS_EXPR, dr_a2->seg_len, >>>> ! size_int (diff)); >>>> ! do_remove = true; >>>> } >>>> ! /* Generally the new segment length is the maximum of the >>>> ! left segment size and the right segment size plus the distance. >>>> ! ??? We can also build tree MAX_EXPR here but it's not clear this >>>> ! is profitable. */ >>>> ! else if (tree_fits_uhwi_p (dr_a1->seg_len) >>>> ! && tree_fits_uhwi_p (dr_a2->seg_len)) >>>> ! { >>>> ! unsigned HOST_WIDE_INT seg_len_a1 = tree_to_uhwi (dr_a1->seg_len); >>>> ! unsigned HOST_WIDE_INT seg_len_a2 = tree_to_uhwi (dr_a2->seg_len); >>>> ! dr_a1->seg_len = size_int (MAX (seg_len_a1, diff + seg_len_a2)); >>>> ! do_remove = true; >>>> ! } >>>> ! /* Now we check if the following condition is satisfied: >>>> >>>> ! DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B >>>> >>>> ! where DIFF = DR_A2_INIT - DR_A1_INIT. However, >>>> ! SEGMENT_LENGTH_A or SEGMENT_LENGTH_B may not be constant so we >>>> ! have to make a best estimation. We can get the minimum value >>>> ! of SEGMENT_LENGTH_B as a constant, represented by MIN_SEG_LEN_B, >>>> ! then either of the following two conditions can guarantee the >>>> ! one above: >>>> >>>> ! 1: DIFF <= MIN_SEG_LEN_B >>>> ! 2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B */ >>>> ! else >>>> { >>>> ! unsigned HOST_WIDE_INT min_seg_len_b >>>> ! = (tree_fits_uhwi_p (dr_b1->seg_len) >>>> ! ? tree_to_uhwi (dr_b1->seg_len) >>>> ! : factor); >>>> >>>> if (diff <= min_seg_len_b >>>> || (tree_fits_uhwi_p (dr_a1->seg_len) >>>> ! && diff - tree_to_uhwi (dr_a1->seg_len) < min_seg_len_b)) >>>> { >>>> ! dr_a1->seg_len = size_binop (PLUS_EXPR, >>>> ! dr_a2->seg_len, size_int (diff)); >>>> do_remove = true; >>>> } >>>> } >>>> >>>> if (do_remove) >>>> { >>>> if (dump_enabled_p ()) >>>> --- 1275,1375 ---- >>>> bool do_remove = false; >>>> unsigned HOST_WIDE_INT diff >>>> = (tree_to_shwi (DR_INIT (dr_a2->dr)) >>>> ! - tree_to_shwi (DR_INIT (dr_a1->dr))); >>>> ! tree new_seg_len; >>>> ! unsigned HOST_WIDE_INT min_seg_len_b; >>>> >>>> ! if (tree_fits_uhwi_p (dr_b1->seg_len)) >>>> { >>>> ! min_seg_len_b = tree_to_uhwi (dr_b1->seg_len); >>>> ! if (tree_int_cst_sign_bit (dr_b1->seg_len)) >>>> ! min_seg_len_b = 0 - min_seg_len_b; >>>> } >>>> ! else >>>> ! min_seg_len_b = factor; >>> >>> ...I'm not sure how safe this or the later neg_step handling is >>> for 16-bit and 32-bit sizetypes. It might be better to use wide_int >> I think it could be a problem in case sizetype is smaller than >> unsigned_type_for(ptr). > > But I think it would a problem even for "normal" 32-bit and 16-bit > targets, because you're doing uhwi (i.e. 64-bit) negation on things that > come from 32-bit and 16-bit unsigned values. E.g. a segment length of > -32 on a 32-bit target would be 0xffffffe0. If you read that as a uhwi > and negate it, you get 0xffffffff00000020 rather than 32. > > Using wide_ints would avoid that. I don't think the existing code > needed it (because the existing code didn't handle negative steps > properly at all). Right, patch updated using wide_int to compare diff and compute merged segment length. Bootstrap and test on x86_64 and AArch64. Thanks, bin > >>> instead, so that all arithmetic and comparisons happen in the precision >>> of sizetype. >> I was trying to make minimal refactoring for fixing the negative step >> issue. Also I guess your SVE patches will rewrite this part entirely? > > Not sure TBH :-) I'll have to see how it works out when I merge it in. > > Thanks, > Richard From a31c45912c6b3621f926106a734087837e8e901e Mon Sep 17 00:00:00 2001 From: Bin Cheng Date: Fri, 19 May 2017 18:46:14 +0100 Subject: [PATCH 3/6] negative-step-alias-check-20170520.txt --- gcc/testsuite/gcc.dg/vect/pr80815-1.c | 38 +++++++++ gcc/testsuite/gcc.dg/vect/pr80815-2.c | 46 +++++++++++ gcc/tree-data-ref.c | 143 +++++++++++++++++++++++----------- 3 files changed, 182 insertions(+), 45 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/vect/pr80815-1.c create mode 100644 gcc/testsuite/gcc.dg/vect/pr80815-2.c diff --git a/gcc/testsuite/gcc.dg/vect/pr80815-1.c b/gcc/testsuite/gcc.dg/vect/pr80815-1.c new file mode 100644 index 0000000..98c06c0 --- /dev/null +++ b/gcc/testsuite/gcc.dg/vect/pr80815-1.c @@ -0,0 +1,38 @@ +/* { dg-require-effective-target vect_int } */ + +#include "tree-vect.h" +int arr[2048]; + +__attribute__ ((noinline)) int +foo (int *a, int *b) +{ + int i; + int *a1 = a; + int *a0 = a1 - 512; + for (i = 0; i < 500; i++) + { + *b = *a0 + *a1; + b++; + a0--; + a1--; + } + return 0; +} + +int main (void) +{ + int *a = &arr[1027]; + int *b = &arr[1024]; + + int i; + for (i = 0; i < 2048; i++) + arr[i] = i; + + foo (a, b); + + if (arr[1026] != 2053 || arr[1027] != 2054) + abort (); + + return 0; +} + diff --git a/gcc/testsuite/gcc.dg/vect/pr80815-2.c b/gcc/testsuite/gcc.dg/vect/pr80815-2.c new file mode 100644 index 0000000..83557da --- /dev/null +++ b/gcc/testsuite/gcc.dg/vect/pr80815-2.c @@ -0,0 +1,46 @@ +/* { dg-require-effective-target vect_int } */ + +#include "tree-vect.h" +int arr[2048]; +int res[100] = { 13198, 13224, 12735, 12760, 12270, 12294, + 11803, 11826, 11334, 11356, 10863, 10884, + 10390, 10410, 9915, 9934, 9438, 9456, + 8959, 8976, 8478, 8494, 7995, 8010, + 7510, 7524, 7023, 7036, 6534, 6546, + 6043, 6054, 5550, 5560, 5055, 5064, + 4558, 4566, 4059, 4066, 3558, 3564, + 3055, 3060, 2550, 2554, 2043, 0}; + +__attribute__ ((noinline)) int +foo (int *a, int *b) +{ + int i; + int *a1 = a; + int *a0 = a1 - 512; + for (i = 0; i < 50; i++) + { + *b = *a0 + *a1; + b--; + a0--; + a1--; + } + return 0; +} + +int main (void) +{ + int *a = &arr[1024]; + int *b = &arr[1022]; + + int i; + for (i = 0; i < 2048; i++) + arr[i] = i; + + foo (a, b); + + for (i = 973; i < 1020; i++) + if (arr[i] != res[i - 973]) + abort (); + + return 0; +} diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index a5f8c1c..1a28000 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -1259,63 +1259,115 @@ prune_runtime_alias_test_list (vec *alias_pairs, != tree_int_cst_compare (DR_STEP (dr_a2->dr), size_zero_node)) continue; + bool neg_step + = (tree_int_cst_compare (DR_STEP (dr_a1->dr), size_zero_node) < 0); + + /* We need to compute merged segment length at compilation time for + dr_a1 and dr_a2, which is impossible if either one has non-const + segment length. */ + if ((!tree_fits_uhwi_p (dr_a1->seg_len) + || !tree_fits_uhwi_p (dr_a2->seg_len)) + && tree_int_cst_compare (DR_STEP (dr_a1->dr), + DR_STEP (dr_a2->dr)) != 0) + continue; + /* Make sure dr_a1 starts left of dr_a2. */ if (tree_int_cst_lt (DR_INIT (dr_a2->dr), DR_INIT (dr_a1->dr))) std::swap (*dr_a1, *dr_a2); bool do_remove = false; - unsigned HOST_WIDE_INT diff - = (tree_to_shwi (DR_INIT (dr_a2->dr)) - - tree_to_shwi (DR_INIT (dr_a1->dr))); - - /* If the left segment does not extend beyond the start of the - right segment the new segment length is that of the right - plus the segment distance. */ - if (tree_fits_uhwi_p (dr_a1->seg_len) - && compare_tree_int (dr_a1->seg_len, diff) <= 0) - { - dr_a1->seg_len = size_binop (PLUS_EXPR, dr_a2->seg_len, - size_int (diff)); - do_remove = true; - } - /* Generally the new segment length is the maximum of the - left segment size and the right segment size plus the distance. - ??? We can also build tree MAX_EXPR here but it's not clear this - is profitable. */ - else if (tree_fits_uhwi_p (dr_a1->seg_len) - && tree_fits_uhwi_p (dr_a2->seg_len)) + wide_int diff = wi::sub (DR_INIT (dr_a2->dr), DR_INIT (dr_a1->dr)); + wide_int min_seg_len_b; + tree new_seg_len; + + if (tree_fits_uhwi_p (dr_b1->seg_len)) { - unsigned HOST_WIDE_INT seg_len_a1 = tree_to_uhwi (dr_a1->seg_len); - unsigned HOST_WIDE_INT seg_len_a2 = tree_to_uhwi (dr_a2->seg_len); - dr_a1->seg_len = size_int (MAX (seg_len_a1, diff + seg_len_a2)); - do_remove = true; + min_seg_len_b = dr_b1->seg_len; + if (tree_int_cst_sign_bit (dr_b1->seg_len)) + min_seg_len_b = wi::neg (min_seg_len_b); } - /* Now we check if the following condition is satisfied: + else + min_seg_len_b = wi::uhwi (factor, TYPE_PRECISION (sizetype)); + + /* Now we try to merge alias check dr_a1 & dr_b and dr_a2 & dr_b. + + Case A: + check if the following condition is satisfied: + + DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B + + where DIFF = DR_A2_INIT - DR_A1_INIT. However, + SEGMENT_LENGTH_A or SEGMENT_LENGTH_B may not be constant so we + have to make a best estimation. We can get the minimum value + of SEGMENT_LENGTH_B as a constant, represented by MIN_SEG_LEN_B, + then either of the following two conditions can guarantee the + one above: + + 1: DIFF <= MIN_SEG_LEN_B + 2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B + Because DIFF - SEGMENT_LENGTH_A is done in sizetype, we need + to take care of wrapping behavior in it. - DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B + Case B: + If the left segment does not extend beyond the start of the + right segment the new segment length is that of the right + plus the segment distance. The condition is like: - where DIFF = DR_A2_INIT - DR_A1_INIT. However, - SEGMENT_LENGTH_A or SEGMENT_LENGTH_B may not be constant so we - have to make a best estimation. We can get the minimum value - of SEGMENT_LENGTH_B as a constant, represented by MIN_SEG_LEN_B, - then either of the following two conditions can guarantee the - one above: + DIFF >= SEGMENT_LENGTH_A ;SEGMENT_LENGTH_A is a constant. - 1: DIFF <= MIN_SEG_LEN_B - 2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B */ + Note 1: Case A.2 and B combined together effectively merges every + dr_a1 & dr_b and dr_a2 & dr_b when SEGMENT_LENGTH_A is const. + + Note 2: Above description is based on positive DR_STEP, we need to + take care of negative DR_STEP for wrapping behavior. See PR80815 + for more information. */ + if (neg_step) + { + /* Adjust diff according to access size of both references. */ + tree size_a1 = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a1->dr))); + tree size_a2 = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a2->dr))); + diff = wi::add (diff, wi::sub (size_a2, size_a1)); + /* Case A.1. */ + if (wi::leu_p (diff, min_seg_len_b) + /* Case A.2 and B combined. */ + || (tree_fits_uhwi_p (dr_a2->seg_len))) + { + if (tree_fits_uhwi_p (dr_a1->seg_len) + && tree_fits_uhwi_p (dr_a2->seg_len)) + new_seg_len + = wide_int_to_tree (sizetype, + wi::umin (wi::sub (dr_a1->seg_len, + diff), + dr_a2->seg_len)); + else + new_seg_len + = size_binop (MINUS_EXPR, dr_a2->seg_len, + wide_int_to_tree (sizetype, diff)); + + dr_a2->seg_len = new_seg_len; + do_remove = true; + } + } else { - unsigned HOST_WIDE_INT min_seg_len_b - = (tree_fits_uhwi_p (dr_b1->seg_len) - ? tree_to_uhwi (dr_b1->seg_len) - : factor); - - if (diff <= min_seg_len_b - || (tree_fits_uhwi_p (dr_a1->seg_len) - && diff - tree_to_uhwi (dr_a1->seg_len) < min_seg_len_b)) + /* Case A.1. */ + if (wi::leu_p (diff, min_seg_len_b) + /* Case A.2 and B combined. */ + || (tree_fits_uhwi_p (dr_a1->seg_len))) { - dr_a1->seg_len = size_binop (PLUS_EXPR, - dr_a2->seg_len, size_int (diff)); + if (tree_fits_uhwi_p (dr_a1->seg_len) + && tree_fits_uhwi_p (dr_a2->seg_len)) + new_seg_len + = wide_int_to_tree (sizetype, + wi::umax (wi::add (dr_a2->seg_len, + diff), + dr_a1->seg_len)); + else + new_seg_len + = size_binop (PLUS_EXPR, dr_a2->seg_len, + wide_int_to_tree (sizetype, diff)); + + dr_a1->seg_len = new_seg_len; do_remove = true; } } @@ -1334,7 +1386,8 @@ prune_runtime_alias_test_list (vec *alias_pairs, dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr)); dump_printf (MSG_NOTE, "\n"); } - alias_pairs->ordered_remove (i--); + alias_pairs->ordered_remove (neg_step ? i - 1 : i); + i--; } } }