From patchwork Tue Apr 18 10:50:40 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bin Cheng X-Patchwork-Id: 751785 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 3w6hkY120Wz9s3s for ; Tue, 18 Apr 2017 20:51:00 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="NsK+E4t2"; 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=Qurt6fgBUOm4pTn5grbsuOk7I9bD51uPlfb7zHiW/50jAZ7gyQ tmJNhqWkT9JXAssWPTCeL4zo+M7Ho6FM+hz2RpL73uU0oy2EtUnrsIldnoQV0nza NXUSxTrb9BB9jkiFCXFZfJUrQEP6qJI2diyXaV8Yqi0kIrgKEz3y9l20c= 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=qxKh+QVZT920E2lUrs6mE5dPKvg=; b=NsK+E4t2nyFHBjh0ZTq7 pnDSFYAzIF+ggiw3Hd+IaugH8vb5quPsbQ8PyMgqDLgcFLAzgnUdU+V7qRDY5l87 EKfwNxKUqQ7UO9ilIaxiFAbYBr2LtY5/jOU1rmrgMjq/nam+YK7S6gn12bR8gomc X8fhqZEn3Z3LTTTUDAQAgFE= Received: (qmail 20639 invoked by alias); 18 Apr 2017 10:50:48 -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 20518 invoked by uid 89); 18 Apr 2017 10:50:44 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-25.2 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: EUR02-AM5-obe.outbound.protection.outlook.com Received: from mail-eopbgr00066.outbound.protection.outlook.com (HELO EUR02-AM5-obe.outbound.protection.outlook.com) (40.107.0.66) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 18 Apr 2017 10:50:42 +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:50:41 +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:50:41 +0000 From: Bin Cheng To: "gcc-patches@gcc.gnu.org" CC: nd Subject: [PATCH 24/33]New parameter bound on number of selected candidates Date: Tue, 18 Apr 2017 10:50:40 +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:/OfsNU7BTuvcgQi9yftpqjWyVhcwlJ71kf/8BSiMEIiYhbvlSHx+M4u5uda2jqRXha5nOCxbvxJrOgAKh6CT5BMUWr+7FqI+slB3t6R4jnm0ZkNdRfTFCBPgnJ54MMRgkcmtksbWPE8k49t/zrPDBcmqRrbP6BqTuTuohkbpQ8u4yoi5JMkyMYWJHfF8+lk0rtzejU6dyGfm61n98uLEr2nHP2sdhBHuDR1db+zZV5RuG7kWU84Z/dbOMPxNBCyjZp/3trLA30lQDfBq07C/r7qMimVGweONCMR78t9+7HLAWm0UP/guvnFe5Oww2Ydw6wA+cdfYDOnmXKETVci2Lg== x-ms-office365-filtering-correlation-id: b470ebf9-9196-4d32-1e34-08d48648c1ad x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001)(2017030254075)(48565401081)(201703131423075)(201703031133081); SRVR:VI1PR0802MB2173; nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(180628864354917)(17755550239193); 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:50:40.9936 (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, IVOPTs still have difficulty for outer loop (especially for large loop nest), and tend to select too many candidates. It's generally bad because of unavoidable register spilling. In this case, we probably want to compute iv_uses with small number of bivs. Though this results in more computation inside of loop, it could improve spilling. This patch adds new parameter bound on number of selected candidates, it simply gives up if too many candidates are selected. So far it works loop by loop, I am not sure if we want to by pass whole loop nest once this bound is hit. Is it OK? Thanks, bin 2017-04-11 Bin Cheng * doc/invoke.texi (iv-max-selected-candidates): New. * params.def (PARAM_IV_MAX_SELECTED_CANDIDATES): New. * tree-ssa-loop-ivopts.c (MAX_SELECTED_CANDIDATES): New. (tree_ssa_iv_optimize_loop): Skip if too many cands are selected. From 40517ca836f868b8bd79bde56aa7c053ffef4fc2 Mon Sep 17 00:00:00 2001 From: Bin Cheng Date: Tue, 7 Mar 2017 13:53:04 +0000 Subject: [PATCH 24/33] add-bound-on-selected-cands-20170221.txt --- gcc/doc/invoke.texi | 4 ++++ gcc/params.def | 8 ++++++++ gcc/tree-ssa-loop-ivopts.c | 8 +++++++- 3 files changed, 19 insertions(+), 1 deletion(-) diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 19a85b6..f9cbdbb 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -9922,6 +9922,10 @@ If the number of candidates in the set is smaller than this value, always try to remove unnecessary ivs from the set when adding a new one. +@item iv-max-selected-candidates +The induction variable optimizations give up on loops that more induction +variable candidates are selected. + @item avg-loop-niter Average number of iterations of a loop. diff --git a/gcc/params.def b/gcc/params.def index 1b058e4..7daab14 100644 --- a/gcc/params.def +++ b/gcc/params.def @@ -527,6 +527,14 @@ DEFPARAM(PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND, "If number of candidates in the set is smaller, we always try to remove unused ivs during its optimization.", 10, 0, 0) +/* The induction variable optimizations give up on loops that more induction + variable candidates are selected. */ + +DEFPARAM(PARAM_IV_MAX_SELECTED_CANDIDATES, + "iv-max-selected-candidates", + "Bound on number of selected iv candidates for loops in iv optimizations.", + 48, 0, 0) + DEFPARAM(PARAM_AVG_LOOP_NITER, "avg-loop-niter", "Average number of iterations of a loop.", diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index dcc4618..8469782 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -667,6 +667,12 @@ struct iv_ca_delta #define ALWAYS_PRUNE_CAND_SET_BOUND \ ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND)) +/* If there are more candidates slected, we just give up because it usually + causes high register pressure issue. */ + +#define MAX_SELECTED_CANDIDATES \ + ((unsigned) PARAM_VALUE (PARAM_IV_MAX_SELECTED_CANDIDATES)) + /* The list of trees for that the decl_rtl field must be reset is stored here. */ @@ -7382,7 +7388,7 @@ tree_ssa_iv_optimize_loop (struct ivopts_data *data, struct loop *loop) /* Find the optimal set of induction variables (item 3, part 2). */ iv_ca = find_optimal_iv_set (data); - if (!iv_ca) + if (!iv_ca || iv_ca->n_cands > MAX_SELECTED_CANDIDATES) goto finish; changed = true;