From patchwork Tue May 23 16:22:54 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bin Cheng X-Patchwork-Id: 766082 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 3wXLRn6CCcz9sPK for ; Wed, 24 May 2017 02:23:17 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="dZKU2vry"; 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:from :to:cc:subject:date:message-id:content-type:mime-version; q=dns; s=default; b=VRVYfISYyGFFsF41110AtyBGFHtcRLpRVHZ5wIrYs/V2aCNUDl Zv4/+xHaTvlmoiz0v0+bf8bp5VAtNoC8BiMkfDHd0KaipK6t1Qi63YmuyCP8Lv6u bAEQhdbZxKKARM1JPPFdL1ykn9NQQCzmPsGuLqjjdq12JL226/ZfZIsT0= 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:date:message-id:content-type:mime-version; s= default; bh=DgHOHZ17rhDJN7JLa7l5ASRj6cc=; b=dZKU2vryb151hWbNFlqe ECwJK+1WlbUWyPOGsqtKle8/U8kWzh+VRUD5NKWMe7CSkDmCtPiTnNng3EtArvi6 5izGEi8xKeXUAvHOcPBDwcsMafmh3rjOJ/GCeL+gM4rmy18n2RxQaMVSUiGXhQ9Q lU8vkZbXdNdDoibhB3XJBk8= Received: (qmail 117624 invoked by alias); 23 May 2017 16:23:04 -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 117045 invoked by uid 89); 23 May 2017 16:22:59 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_HELO_PASS, SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: EUR01-HE1-obe.outbound.protection.outlook.com Received: from mail-he1eur01on0074.outbound.protection.outlook.com (HELO EUR01-HE1-obe.outbound.protection.outlook.com) (104.47.0.74) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 23 May 2017 16:22:54 +0000 Received: from VI1PR0802MB2176.eurprd08.prod.outlook.com (10.172.12.21) by VI1PR0802MB2176.eurprd08.prod.outlook.com (10.172.12.21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1124.9; Tue, 23 May 2017 16:22:54 +0000 Received: from VI1PR0802MB2176.eurprd08.prod.outlook.com ([fe80::e034:7dd7:6bad:908a]) by VI1PR0802MB2176.eurprd08.prod.outlook.com ([fe80::e034:7dd7:6bad:908a%16]) with mapi id 15.01.1124.009; Tue, 23 May 2017 16:22:54 +0000 From: Bin Cheng To: "gcc-patches@gcc.gnu.org" CC: nd Subject: [PATCH GCC][2/6]Factor out code pruning runtime alias checks Date: Tue, 23 May 2017 16:22:54 +0000 Message-ID: authentication-results: arm.com; dkim=none (message not signed) header.d=none; arm.com; dmarc=none action=none header.from=arm.com; x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1; VI1PR0802MB2176; 7:d30TqB90IKgoYna7J1NNDB64GYyxi81kwuZB4Fwrz/xd1Sr3/inLk/2SA+Hu4w+B13W4jQrMqUG/OLztZvO+gUvRwyEShxTviGu+In/kE2/8q34JqDmbUTkxdM9JuCdjqmK9SvVt7WZxmmTTFttG0F2cCj35v1a3TR9Bhx198Id91oDcpkQm2Oz7H00YHq/TjMSMVq+wUJ1/V4BSabEg+tMZSpGkrUw+ajns0AdICU3/U9hvYTopZTvdsyTDydERhFd6NVrMsVLNaUBuQhBRzutq/iabJVFdlju/LtpkXgVfJRwihdzF3TQhZ5FkNxrYN1C0X0PWZf+sLvbNVwQQCw== x-ms-traffictypediagnostic: VI1PR0802MB2176: x-ms-office365-filtering-correlation-id: d7a74e32-ba0f-47ec-1e50-08d4a1f7f742 x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001)(2017030254075)(48565401081)(201703131423075)(201703031133081)(201702281549075); SRVR:VI1PR0802MB2176; nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(180628864354917); x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(102415395)(6040450)(601004)(2401047)(8121501046)(5005006)(93006095)(93001095)(10201501046)(3002001)(6055026)(6041248)(201703131423075)(201702281528075)(201703061421075)(201703061406153)(20161123562025)(20161123560025)(20161123558100)(20161123555025)(20161123564025)(6072148); SRVR:VI1PR0802MB2176; BCL:0; PCL:0; RULEID:; SRVR:VI1PR0802MB2176; x-forefront-prvs: 0316567485 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(6009001)(39450400003)(39410400002)(39400400002)(39860400002)(39840400002)(39850400002)(377424004)(5250100002)(6506006)(5640700003)(4326008)(2501003)(99936001)(74316002)(54356999)(50986999)(3280700002)(33656002)(3660700001)(6436002)(99286003)(7696004)(6916009)(25786009)(9686003)(2900100001)(2906002)(55016002)(6116002)(189998001)(110136004)(38730400002)(478600001)(2351001)(305945005)(53936002)(7736002)(72206003)(5660300001)(8936002)(86362001)(81166006)(8676002); DIR:OUT; SFP:1101; SCL:1; SRVR:VI1PR0802MB2176; H:VI1PR0802MB2176.eurprd08.prod.outlook.com; FPR:; SPF:None; MLV:sfv; LANG:en; spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-originalarrivaltime: 23 May 2017 16:22:54.2288 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR0802MB2176 X-IsSubscribed: yes Hi, This is the second patch in the set, it factors out code pruning runtime alias checks from file tree-vect-data-refs.c to tree-data-ref.c. It also introduces new interface prune_runtime_alias_test_list so that we can use it in pass like loop distribution. Bootstrap and test on x86_64 and AArch64, is it OK? Thanks, bin 2017-05-22 Bin Cheng * tree-vect-data-refs.c (Operator==, comp_dr_with_seg_len_pair): Move from ... * tree-data-ref.c (Operator==, comp_dr_with_seg_len_pair): To here. * tree-vect-data-refs.c (vect_prune_runtime_alias_test_list): Factor out code pruning runtime alias checks. * tree-data-ref.c (prune_runtime_alias_test_list): New function factored out from above. * tree-vectorizer.h (struct dr_with_seg_len, dr_with_seg_len_pair_t): Move from ... * tree-data-ref.h (struct dr_with_seg_len, dr_with_seg_len_pair_t): ... to here. (prune_runtime_alias_test_list): New decalaration. From 030967c7b1d6af95f2becd1159dad7823cdaecd9 Mon Sep 17 00:00:00 2001 From: Bin Cheng Date: Tue, 23 May 2017 17:11:19 +0100 Subject: [PATCH 2/6] prune-runtime-alias-check-20170516 --- gcc/tree-data-ref.c | 233 ++++++++++++++++++++++++++++++++++++++++++++++ gcc/tree-data-ref.h | 28 ++++++ gcc/tree-vect-data-refs.c | 228 +-------------------------------------------- gcc/tree-vectorizer.h | 28 ------ 4 files changed, 263 insertions(+), 254 deletions(-) diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 2480f4e..a5f8c1c 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -1107,6 +1107,239 @@ create_data_ref (loop_p nest, loop_p loop, tree memref, gimple *stmt, return dr; } +/* Operator == between two dr_with_seg_len objects. + + This equality operator is used to make sure two data refs + are the same one so that we will consider to combine the + aliasing checks of those two pairs of data dependent data + refs. */ + +static bool +operator == (const dr_with_seg_len& d1, + const dr_with_seg_len& d2) +{ + return operand_equal_p (DR_BASE_ADDRESS (d1.dr), + DR_BASE_ADDRESS (d2.dr), 0) + && compare_tree (DR_OFFSET (d1.dr), DR_OFFSET (d2.dr)) == 0 + && compare_tree (DR_INIT (d1.dr), DR_INIT (d2.dr)) == 0 + && compare_tree (d1.seg_len, d2.seg_len) == 0; +} + +/* Comparison function for sorting objects of dr_with_seg_len_pair_t + so that we can combine aliasing checks in one scan. */ + +static int +comp_dr_with_seg_len_pair (const void *pa_, const void *pb_) +{ + const dr_with_seg_len_pair_t* pa = (const dr_with_seg_len_pair_t *) pa_; + const dr_with_seg_len_pair_t* pb = (const dr_with_seg_len_pair_t *) pb_; + const dr_with_seg_len &a1 = pa->first, &a2 = pa->second; + const dr_with_seg_len &b1 = pb->first, &b2 = pb->second; + + /* For DR pairs (a, b) and (c, d), we only consider to merge the alias checks + if a and c have the same basic address snd step, and b and d have the same + address and step. Therefore, if any a&c or b&d don't have the same address + and step, we don't care the order of those two pairs after sorting. */ + int comp_res; + + if ((comp_res = compare_tree (DR_BASE_ADDRESS (a1.dr), + DR_BASE_ADDRESS (b1.dr))) != 0) + return comp_res; + if ((comp_res = compare_tree (DR_BASE_ADDRESS (a2.dr), + DR_BASE_ADDRESS (b2.dr))) != 0) + return comp_res; + if ((comp_res = compare_tree (DR_STEP (a1.dr), DR_STEP (b1.dr))) != 0) + return comp_res; + if ((comp_res = compare_tree (DR_STEP (a2.dr), DR_STEP (b2.dr))) != 0) + return comp_res; + if ((comp_res = compare_tree (DR_OFFSET (a1.dr), DR_OFFSET (b1.dr))) != 0) + return comp_res; + if ((comp_res = compare_tree (DR_INIT (a1.dr), DR_INIT (b1.dr))) != 0) + return comp_res; + if ((comp_res = compare_tree (DR_OFFSET (a2.dr), DR_OFFSET (b2.dr))) != 0) + return comp_res; + if ((comp_res = compare_tree (DR_INIT (a2.dr), DR_INIT (b2.dr))) != 0) + return comp_res; + + return 0; +} + +/* Merge alias checks recorded in ALIAS_PAIRS and remove redundant ones. + FACTOR is number of iterations that each data reference is accessed. + + Basically, for each pair of dependent data refs store_ptr_0 & load_ptr_0, + we create an expression: + + ((store_ptr_0 + store_segment_length_0) <= load_ptr_0) + || (load_ptr_0 + load_segment_length_0) <= store_ptr_0)) + + for aliasing checks. However, in some cases we can decrease the number + of checks by combining two checks into one. For example, suppose we have + another pair of data refs store_ptr_0 & load_ptr_1, and if the following + condition is satisfied: + + load_ptr_0 < load_ptr_1 && + load_ptr_1 - load_ptr_0 - load_segment_length_0 < store_segment_length_0 + + (this condition means, in each iteration of vectorized loop, the accessed + memory of store_ptr_0 cannot be between the memory of load_ptr_0 and + load_ptr_1.) + + we then can use only the following expression to finish the alising checks + between store_ptr_0 & load_ptr_0 and store_ptr_0 & load_ptr_1: + + ((store_ptr_0 + store_segment_length_0) <= load_ptr_0) + || (load_ptr_1 + load_segment_length_1 <= store_ptr_0)) + + Note that we only consider that load_ptr_0 and load_ptr_1 have the same + basic address. */ + +void +prune_runtime_alias_test_list (vec *alias_pairs, + unsigned HOST_WIDE_INT factor) +{ + /* Sort the collected data ref pairs so that we can scan them once to + combine all possible aliasing checks. */ + alias_pairs->qsort (comp_dr_with_seg_len_pair); + + /* Scan the sorted dr pairs and check if we can combine alias checks + of two neighboring dr pairs. */ + for (size_t i = 1; i < alias_pairs->length (); ++i) + { + /* Deal with two ddrs (dr_a1, dr_b1) and (dr_a2, dr_b2). */ + dr_with_seg_len *dr_a1 = &(*alias_pairs)[i-1].first, + *dr_b1 = &(*alias_pairs)[i-1].second, + *dr_a2 = &(*alias_pairs)[i].first, + *dr_b2 = &(*alias_pairs)[i].second; + + /* Remove duplicate data ref pairs. */ + if (*dr_a1 == *dr_a2 && *dr_b1 == *dr_b2) + { + if (dump_enabled_p ()) + { + dump_printf (MSG_NOTE, "found equal ranges "); + dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a1->dr)); + dump_printf (MSG_NOTE, ", "); + dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b1->dr)); + dump_printf (MSG_NOTE, " and "); + dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a2->dr)); + dump_printf (MSG_NOTE, ", "); + dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr)); + dump_printf (MSG_NOTE, "\n"); + } + alias_pairs->ordered_remove (i--); + continue; + } + + if (*dr_a1 == *dr_a2 || *dr_b1 == *dr_b2) + { + /* We consider the case that DR_B1 and DR_B2 are same memrefs, + and DR_A1 and DR_A2 are two consecutive memrefs. */ + if (*dr_a1 == *dr_a2) + { + std::swap (dr_a1, dr_b1); + std::swap (dr_a2, dr_b2); + } + + if (!operand_equal_p (DR_BASE_ADDRESS (dr_a1->dr), + DR_BASE_ADDRESS (dr_a2->dr), 0) + || !operand_equal_p (DR_OFFSET (dr_a1->dr), + DR_OFFSET (dr_a2->dr), 0) + || !tree_fits_shwi_p (DR_INIT (dr_a1->dr)) + || !tree_fits_shwi_p (DR_INIT (dr_a2->dr))) + continue; + + /* Only merge const step data references. */ + if (TREE_CODE (DR_STEP (dr_a1->dr)) != INTEGER_CST + || TREE_CODE (DR_STEP (dr_a2->dr)) != INTEGER_CST) + continue; + + /* DR_A1 and DR_A2 must goes in the same direction. */ + if (tree_int_cst_compare (DR_STEP (dr_a1->dr), size_zero_node) + != tree_int_cst_compare (DR_STEP (dr_a2->dr), size_zero_node)) + 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)) + { + 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 ()) + { + dump_printf (MSG_NOTE, "merging ranges for "); + dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a1->dr)); + dump_printf (MSG_NOTE, ", "); + dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b1->dr)); + dump_printf (MSG_NOTE, " and "); + dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a2->dr)); + dump_printf (MSG_NOTE, ", "); + dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr)); + dump_printf (MSG_NOTE, "\n"); + } + alias_pairs->ordered_remove (i--); + } + } + } +} + /* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical expressions. */ static bool diff --git a/gcc/tree-data-ref.h b/gcc/tree-data-ref.h index 3a54120..75c32b3 100644 --- a/gcc/tree-data-ref.h +++ b/gcc/tree-data-ref.h @@ -148,6 +148,32 @@ struct data_reference typedef struct data_reference *data_reference_p; +/* This struct is used to store the information of a data reference, + including the data ref itself and the segment length for aliasing + checks. This is used to merge alias checks. */ + +struct dr_with_seg_len +{ + dr_with_seg_len (data_reference_p d, tree len) + : dr (d), seg_len (len) {} + + data_reference_p dr; + tree seg_len; +}; + +/* This struct contains two dr_with_seg_len objects with aliasing data + refs. Two comparisons are generated from them. */ + +struct dr_with_seg_len_pair_t +{ + dr_with_seg_len_pair_t (const dr_with_seg_len& d1, + const dr_with_seg_len& d2) + : first (d1), second (d2) {} + + dr_with_seg_len first; + dr_with_seg_len second; +}; + enum data_dependence_direction { dir_positive, dir_negative, @@ -342,6 +368,8 @@ extern bool dr_may_alias_p (const struct data_reference *, extern bool dr_equal_offsets_p (struct data_reference *, struct data_reference *); +extern void prune_runtime_alias_test_list (vec *, + unsigned HOST_WIDE_INT); /* Return true when the base objects of data references A and B are the same memory object. */ diff --git a/gcc/tree-vect-data-refs.c b/gcc/tree-vect-data-refs.c index 7b835ae..06580f0 100644 --- a/gcc/tree-vect-data-refs.c +++ b/gcc/tree-vect-data-refs.c @@ -2813,66 +2813,6 @@ vect_analyze_data_ref_accesses (vec_info *vinfo) return true; } - -/* Operator == between two dr_with_seg_len objects. - - This equality operator is used to make sure two data refs - are the same one so that we will consider to combine the - aliasing checks of those two pairs of data dependent data - refs. */ - -static bool -operator == (const dr_with_seg_len& d1, - const dr_with_seg_len& d2) -{ - return operand_equal_p (DR_BASE_ADDRESS (d1.dr), - DR_BASE_ADDRESS (d2.dr), 0) - && compare_tree (DR_OFFSET (d1.dr), DR_OFFSET (d2.dr)) == 0 - && compare_tree (DR_INIT (d1.dr), DR_INIT (d2.dr)) == 0 - && compare_tree (d1.seg_len, d2.seg_len) == 0; -} - -/* Function comp_dr_with_seg_len_pair. - - Comparison function for sorting objects of dr_with_seg_len_pair_t - so that we can combine aliasing checks in one scan. */ - -static int -comp_dr_with_seg_len_pair (const void *pa_, const void *pb_) -{ - const dr_with_seg_len_pair_t* pa = (const dr_with_seg_len_pair_t *) pa_; - const dr_with_seg_len_pair_t* pb = (const dr_with_seg_len_pair_t *) pb_; - const dr_with_seg_len &a1 = pa->first, &a2 = pa->second; - const dr_with_seg_len &b1 = pb->first, &b2 = pb->second; - - /* For DR pairs (a, b) and (c, d), we only consider to merge the alias checks - if a and c have the same basic address snd step, and b and d have the same - address and step. Therefore, if any a&c or b&d don't have the same address - and step, we don't care the order of those two pairs after sorting. */ - int comp_res; - - if ((comp_res = compare_tree (DR_BASE_ADDRESS (a1.dr), - DR_BASE_ADDRESS (b1.dr))) != 0) - return comp_res; - if ((comp_res = compare_tree (DR_BASE_ADDRESS (a2.dr), - DR_BASE_ADDRESS (b2.dr))) != 0) - return comp_res; - if ((comp_res = compare_tree (DR_STEP (a1.dr), DR_STEP (b1.dr))) != 0) - return comp_res; - if ((comp_res = compare_tree (DR_STEP (a2.dr), DR_STEP (b2.dr))) != 0) - return comp_res; - if ((comp_res = compare_tree (DR_OFFSET (a1.dr), DR_OFFSET (b1.dr))) != 0) - return comp_res; - if ((comp_res = compare_tree (DR_INIT (a1.dr), DR_INIT (b1.dr))) != 0) - return comp_res; - if ((comp_res = compare_tree (DR_OFFSET (a2.dr), DR_OFFSET (b2.dr))) != 0) - return comp_res; - if ((comp_res = compare_tree (DR_INIT (a2.dr), DR_INIT (b2.dr))) != 0) - return comp_res; - - return 0; -} - /* Function vect_vfa_segment_size. Create an expression that computes the size of segment @@ -2987,34 +2927,6 @@ vect_prune_runtime_alias_test_list (loop_vec_info loop_vinfo) if (may_alias_ddrs.is_empty ()) return true; - /* Basically, for each pair of dependent data refs store_ptr_0 - and load_ptr_0, we create an expression: - - ((store_ptr_0 + store_segment_length_0) <= load_ptr_0) - || (load_ptr_0 + load_segment_length_0) <= store_ptr_0)) - - for aliasing checks. However, in some cases we can decrease - the number of checks by combining two checks into one. For - example, suppose we have another pair of data refs store_ptr_0 - and load_ptr_1, and if the following condition is satisfied: - - load_ptr_0 < load_ptr_1 && - load_ptr_1 - load_ptr_0 - load_segment_length_0 < store_segment_length_0 - - (this condition means, in each iteration of vectorized loop, - the accessed memory of store_ptr_0 cannot be between the memory - of load_ptr_0 and load_ptr_1.) - - we then can use only the following expression to finish the - alising checks between store_ptr_0 & load_ptr_0 and - store_ptr_0 & load_ptr_1: - - ((store_ptr_0 + store_segment_length_0) <= load_ptr_0) - || (load_ptr_1 + load_segment_length_1 <= store_ptr_0)) - - Note that we only consider that load_ptr_0 and load_ptr_1 have the - same basic address. */ - comp_alias_ddrs.create (may_alias_ddrs.length ()); /* First, we collect all data ref pairs for aliasing checks. */ @@ -3083,144 +2995,8 @@ vect_prune_runtime_alias_test_list (loop_vec_info loop_vinfo) comp_alias_ddrs.safe_push (dr_with_seg_len_pair); } - /* Second, we sort the collected data ref pairs so that we can scan - them once to combine all possible aliasing checks. */ - comp_alias_ddrs.qsort (comp_dr_with_seg_len_pair); - - /* Third, we scan the sorted dr pairs and check if we can combine - alias checks of two neighboring dr pairs. */ - for (size_t i = 1; i < comp_alias_ddrs.length (); ++i) - { - /* Deal with two ddrs (dr_a1, dr_b1) and (dr_a2, dr_b2). */ - dr_with_seg_len *dr_a1 = &comp_alias_ddrs[i-1].first, - *dr_b1 = &comp_alias_ddrs[i-1].second, - *dr_a2 = &comp_alias_ddrs[i].first, - *dr_b2 = &comp_alias_ddrs[i].second; - - /* Remove duplicate data ref pairs. */ - if (*dr_a1 == *dr_a2 && *dr_b1 == *dr_b2) - { - if (dump_enabled_p ()) - { - dump_printf_loc (MSG_NOTE, vect_location, - "found equal ranges "); - dump_generic_expr (MSG_NOTE, TDF_SLIM, - DR_REF (dr_a1->dr)); - dump_printf (MSG_NOTE, ", "); - dump_generic_expr (MSG_NOTE, TDF_SLIM, - DR_REF (dr_b1->dr)); - dump_printf (MSG_NOTE, " and "); - dump_generic_expr (MSG_NOTE, TDF_SLIM, - DR_REF (dr_a2->dr)); - dump_printf (MSG_NOTE, ", "); - dump_generic_expr (MSG_NOTE, TDF_SLIM, - DR_REF (dr_b2->dr)); - dump_printf (MSG_NOTE, "\n"); - } - - comp_alias_ddrs.ordered_remove (i--); - continue; - } - - if (*dr_a1 == *dr_a2 || *dr_b1 == *dr_b2) - { - /* We consider the case that DR_B1 and DR_B2 are same memrefs, - and DR_A1 and DR_A2 are two consecutive memrefs. */ - if (*dr_a1 == *dr_a2) - { - std::swap (dr_a1, dr_b1); - std::swap (dr_a2, dr_b2); - } - - if (!operand_equal_p (DR_BASE_ADDRESS (dr_a1->dr), - DR_BASE_ADDRESS (dr_a2->dr), 0) - || !operand_equal_p (DR_OFFSET (dr_a1->dr), - DR_OFFSET (dr_a2->dr), 0) - || !tree_fits_shwi_p (DR_INIT (dr_a1->dr)) - || !tree_fits_shwi_p (DR_INIT (dr_a2->dr))) - 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)) - { - 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) - : vect_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 ()) - { - dump_printf_loc (MSG_NOTE, vect_location, - "merging ranges for "); - dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a1->dr)); - dump_printf (MSG_NOTE, ", "); - dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b1->dr)); - dump_printf (MSG_NOTE, " and "); - dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a2->dr)); - dump_printf (MSG_NOTE, ", "); - dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr)); - dump_printf (MSG_NOTE, "\n"); - } - comp_alias_ddrs.ordered_remove (i--); - } - } - } - + prune_runtime_alias_test_list (&comp_alias_ddrs, + (unsigned HOST_WIDE_INT) vect_factor); dump_printf_loc (MSG_NOTE, vect_location, "improved number of alias checks from %d to %d\n", may_alias_ddrs.length (), comp_alias_ddrs.length ()); diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h index 12bb904..7978bbd 100644 --- a/gcc/tree-vectorizer.h +++ b/gcc/tree-vectorizer.h @@ -146,34 +146,6 @@ typedef struct _slp_instance { -/* This struct is used to store the information of a data reference, - including the data ref itself and the segment length for aliasing - checks. This is used to merge alias checks. */ - -struct dr_with_seg_len -{ - dr_with_seg_len (data_reference_p d, tree len) - : dr (d), seg_len (len) {} - - data_reference_p dr; - tree seg_len; -}; - -/* This struct contains two dr_with_seg_len objects with aliasing data - refs. Two comparisons are generated from them. */ - -struct dr_with_seg_len_pair_t -{ - dr_with_seg_len_pair_t (const dr_with_seg_len& d1, - const dr_with_seg_len& d2) - : first (d1), second (d2) {} - - dr_with_seg_len first; - dr_with_seg_len second; -}; - - - /* Vectorizer state common between loop and basic-block vectorization. */ struct vec_info { enum { bb, loop } kind;