From patchwork Tue Apr 18 10:52:18 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bin Cheng X-Patchwork-Id: 751788 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 3w6hmR1NkWz9s78 for ; Tue, 18 Apr 2017 20:52:39 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="Cn4w09I/"; 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=lzPxaLcia660qyZUoGO2m/M6vc8iuAgOibpLPgGTmop/wp6fWM uNo6ZGhX//UYK51T/ZiTcbOaY0t6RzPkzVaytgZicuk9beVb6x9SjjJZ+6WcLnQs CQfJD3pKujmUAbZvPUj4sxnEtm7KAiJUFyQMiPbhJwbol6072WQE9jugc= 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=fIqVgBw+CRvIbyCsCqheJFaX0gk=; b=Cn4w09I/YlJ8it3jB+PP aJU2xAeSRfErIXJCAjLmyYF+pQHmPHza7YxAGCoyl+1P3lwhvZ2xRp9dRI3fkaMi /X7/ByzzCJfe7uzhz2p0JoMB6YLb/6fgHAlhR3BiOHLwfQV3MJxHLTogL/NDZK1V cmjUTBegYqjj4xe7G49UsWg= Received: (qmail 27857 invoked by alias); 18 Apr 2017 10:52:22 -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 27817 invoked by uid 89); 18 Apr 2017 10:52:22 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-25.3 required=5.0 tests=AWL, 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=H*c:HHH X-HELO: EUR03-VE1-obe.outbound.protection.outlook.com Received: from mail-eopbgr50053.outbound.protection.outlook.com (HELO EUR03-VE1-obe.outbound.protection.outlook.com) (40.107.5.53) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 18 Apr 2017 10:52:19 +0000 Received: from VI1PR0802MB2176.eurprd08.prod.outlook.com (10.172.12.21) by VI1PR0802MB2173.eurprd08.prod.outlook.com (10.172.12.18) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1034.10; Tue, 18 Apr 2017 10:52:18 +0000 Received: from VI1PR0802MB2176.eurprd08.prod.outlook.com ([10.172.12.21]) by VI1PR0802MB2176.eurprd08.prod.outlook.com ([10.172.12.21]) with mapi id 15.01.1034.013; Tue, 18 Apr 2017 10:52:18 +0000 From: Bin Cheng To: "gcc-patches@gcc.gnu.org" CC: nd Subject: [PATCH GCC8][27/33]Extend candidate set if new_cp has cheaper dependence Date: Tue, 18 Apr 2017 10:52:18 +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-microsoft-exchange-diagnostics: 1; VI1PR0802MB2173; 7:UTvpqeb8qoS1ANUOV0TxuECc7RLHgLmrMaDZPRIepjEdTG3yttEXSmy7b7e59Sf9tzkcl8vTsKrKzDDNYNSo5A9Zj4P5ws90q/UEm8R1+9+EwnSTCMDYH1fmpRA4crnPuSYkEaqD5AI50RT4TfEea0oAqlwSJtEIlNFgVVvNQEXu4SRD8nijWaRkEZOCVPrxe0UVDxDkgLJzIK1a19AOaCRyX6og0S6x4Dn+Yz9zrxZRG9QpraBfyWXVjpGL5t1VY+HZfKdpAEYN0JBgbmUKqe9zG8Zb+3BYPoR9gV8UdRE5QxPPnDWukqHjxci+vrx2HavCk277yrHNVT28MIHiWQ== x-ms-office365-filtering-correlation-id: 8d8f8d27-b99c-4362-96eb-08d48648fbe1 x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001)(2017030254075)(48565401081)(201703131423075)(201703031133081)(201702281549075); SRVR:VI1PR0802MB2173; 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)(5005006)(8121501046)(10201501046)(3002001)(93006095)(93001095)(6055026)(6041248)(201703131423075)(201702281528075)(201703061421075)(20161123564025)(20161123555025)(20161123562025)(20161123560025)(6072148); SRVR:VI1PR0802MB2173; BCL:0; PCL:0; RULEID:; SRVR:VI1PR0802MB2173; x-forefront-prvs: 028166BF91 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(6009001)(39410400002)(39450400003)(39840400002)(39860400002)(39400400002)(39850400002)(5640700003)(9686003)(2906002)(3846002)(33656002)(54356999)(3280700002)(305945005)(7736002)(50986999)(38730400002)(55016002)(6116002)(99286003)(102836003)(8936002)(81166006)(122556002)(66066001)(74316002)(86362001)(53936002)(4326008)(6436002)(110136004)(189998001)(99936001)(6506006)(8676002)(2351001)(3660700001)(25786009)(5660300001)(2900100001)(2501003)(6916009)(7696004)(77096006); DIR:OUT; SFP:1101; SCL:1; SRVR:VI1PR0802MB2173; 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: 18 Apr 2017 10:52:18.6324 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR0802MB2173 X-IsSubscribed: yes Hi, Currently we only allow iv_ca extension if new_cp has cheaper cost and less deps than old_cp. This is inaccurate because it's possible the overall deps is reduced even new_cp has more deps than old_cp. This happens in case that new_cp's deps are already in iv_ca. This patch allows more iv_ca extension by checking overall deps in iv_ca. Is it OK? Thanks, bin 2017-04-11 Bin Cheng * tree-ssa-loop-ivopts.c (compare_cost_pair): New. (iv_ca_more_deps): Renamed to ... (iv_ca_compare_deps): ... this. (iv_ca_extend): Extend iv_ca if NEW_CP is cheaper than OLD_CP. From 9f45d3762e60b3c1d2de17ef3683f944be408f96 Mon Sep 17 00:00:00 2001 From: Bin Cheng Date: Fri, 31 Mar 2017 14:18:55 +0100 Subject: [PATCH 27/33] extend-cand-with-cheaper-deps-20170310.txt --- gcc/tree-ssa-loop-ivopts.c | 43 ++++++++++++++++++++++++++++++++----------- 1 file changed, 32 insertions(+), 11 deletions(-) diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index b93a589..0b9170c 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -5633,6 +5633,19 @@ cheaper_cost_pair (struct cost_pair *a, struct cost_pair *b) return false; } +/* Compare if A is a more expensive cost pair than B. Return 1, 0 and -1 + for more expensive, equal and cheaper respectively. */ + +static int +compare_cost_pair (struct cost_pair *a, struct cost_pair *b) +{ + if (cheaper_cost_pair (a, b)) + return -1; + if (cheaper_cost_pair (b, a)) + return 1; + + return 0; +} /* Returns candidate by that USE is expressed in IVS. */ @@ -5818,13 +5831,14 @@ iv_ca_cost (struct iv_ca *ivs) return ivs->cost; } -/* Returns true if applying NEW_CP to GROUP for IVS introduces more - invariants than OLD_CP. */ +/* Compare if applying NEW_CP to GROUP for IVS introduces more invariants + than OLD_CP. Return 1, 0 and -1 for more, equal and fewer invariants + respectively. */ -static bool -iv_ca_more_deps (struct ivopts_data *data, struct iv_ca *ivs, - struct iv_group *group, struct cost_pair *old_cp, - struct cost_pair *new_cp) +static int +iv_ca_compare_deps (struct ivopts_data *data, struct iv_ca *ivs, + struct iv_group *group, struct cost_pair *old_cp, + struct cost_pair *new_cp) { gcc_assert (old_cp && new_cp && old_cp != new_cp); unsigned old_n_invs = ivs->n_invs; @@ -5832,7 +5846,7 @@ iv_ca_more_deps (struct ivopts_data *data, struct iv_ca *ivs, unsigned new_n_invs = ivs->n_invs; iv_ca_set_cp (data, ivs, group, old_cp); - return (new_n_invs > old_n_invs); + return new_n_invs > old_n_invs ? 1 : (new_n_invs < old_n_invs ? -1 : 0); } /* Creates change of expressing GROUP by NEW_CP instead of OLD_CP and chains @@ -6064,11 +6078,18 @@ iv_ca_extend (struct ivopts_data *data, struct iv_ca *ivs, if (!new_cp) continue; - if (!min_ncand && iv_ca_more_deps (data, ivs, group, old_cp, new_cp)) - continue; + if (!min_ncand) + { + int cmp_invs = iv_ca_compare_deps (data, ivs, group, old_cp, new_cp); + /* Skip if new_cp depends on more invariants. */ + if (cmp_invs > 0) + continue; - if (!min_ncand && !cheaper_cost_pair (new_cp, old_cp)) - continue; + int cmp_cost = compare_cost_pair (new_cp, old_cp); + /* Skip if new_cp is not cheaper. */ + if (cmp_cost > 0 || (cmp_cost == 0 && cmp_invs == 0)) + continue; + } *delta = iv_ca_delta_add (group, old_cp, new_cp, *delta); }