From patchwork Wed Feb 3 16:35:21 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wilco Dijkstra X-Patchwork-Id: 578228 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 8A1071402D9 for ; Thu, 4 Feb 2016 03:35:38 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=SnnflM5c; 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:mime-version:content-type :content-transfer-encoding; q=dns; s=default; b=rmJemz8qMrwmL5aN qBbbZuTPOYuh2EsqUtc3PQa+fprHKMw48xic8fAa1qVKxLkbUmfMWcshWIv3WYdX iKvBsVPgHBL9bjjHryP0CqmJUr3FLNNn82Kvs3Nn4EIYWuqRbGAK1u1VviTWIjGz K7kGhgwpFjVI0k3AYfu9n+2NDH0= 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:mime-version:content-type :content-transfer-encoding; s=default; bh=PnZhG1FU9Cwb81JB1zwbX+ 3Z0e0=; b=SnnflM5c9amPHa5QDRKjo/pXB6mZCdV8hzaZoAbwZGCX5f2vUongxP KqZzC608PiveMXXBZUPm2WVb7hIbZaRPBDVrn2dDDFss2wgyacwCGmGaygyg+Tb0 vJUzXnxQZNCg99ktoxU3cXxiQM8TJkjG9QSaysCmMKsSOjLOLR8SA= Received: (qmail 43064 invoked by alias); 3 Feb 2016 16:35: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 42327 invoked by uid 89); 3 Feb 2016 16:35:30 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.8 required=5.0 tests=AWL, BAYES_00, SPF_PASS autolearn=ham version=3.3.2 spammy=tmp2, threshold, Temporary, H*MI:outlook X-HELO: eu-smtp-delivery-143.mimecast.com Received: from eu-smtp-delivery-143.mimecast.com (HELO eu-smtp-delivery-143.mimecast.com) (146.101.78.143) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 03 Feb 2016 16:35:28 +0000 Received: from emea01-db3-obe.outbound.protection.outlook.com (mail-db3lrp0081.outbound.protection.outlook.com [213.199.154.81]) (Using TLS) by eu-smtp-1.mimecast.com with ESMTP id uk-mta-33-0-w94dBjSpmOk_ZNMtbrWg-1; Wed, 03 Feb 2016 16:35:22 +0000 Received: from AM3PR08MB0088.eurprd08.prod.outlook.com (2a01:111:e400:8847::18) by AM3PR08MB0088.eurprd08.prod.outlook.com (2a01:111:e400:8847::18) with Microsoft SMTP Server (TLS) id 15.1.396.15; Wed, 3 Feb 2016 16:35:22 +0000 Received: from AM3PR08MB0088.eurprd08.prod.outlook.com ([fe80::3582:10dd:6976:ddf1]) by AM3PR08MB0088.eurprd08.prod.outlook.com ([fe80::3582:10dd:6976:ddf1%15]) with mapi id 15.01.0396.020; Wed, 3 Feb 2016 16:35:22 +0000 From: Wilco Dijkstra To: "gcc-patches@gcc.gnu.org" CC: nd Subject: [PATCH] PR69619: Fix exponential issue in ccmp.c Date: Wed, 3 Feb 2016 16:35:21 +0000 Message-ID: x-microsoft-exchange-diagnostics: 1; AM3PR08MB0088; 5:8EF3MkX6UMCy/oLALETNlLeRQRVLWdapXv7OX0ernuTmvaIuZkvCVtkFNAkug9QxCfbqlpdFDAxQ9VLKr+n+jttW5sK7jTEIoG0dtXCV9ncp23ZGPc8USQUM92DUrqcCEyhD9f5OgUV+fZwCji0uKA==; 24:62vtuST/NQ16F6ejzKsV4E+of2mx/AcfrLwIzyCpZcCZU9XZiOKu8r63qnKsrs1aEG152b2NUmRHLLuIz37eOTPJmyO5YRF+Jq0NENqwreA=; 20:5zz1YrY9PRoAl57s6SE6I9qckt2Nwu/kKaTVHuvbhBoBwIQn7QlVj15zF9TpLiuPFyiCKbcKpY8NZR/eu1igIfhhpL6E/KQwkroOEP+SogiuV5k1w6d2DdR+NFqOF2064lhWq7DxpxgBg84wV8mbA9oYfmLKPMR5rTu+cjTZmrg= x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:AM3PR08MB0088; x-ms-office365-filtering-correlation-id: 183d1b58-6c9e-44d1-fd10-08d32cb802cb nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(180628864354917); x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(601004)(2401047)(8121501046)(5005006)(10201501046)(3002001); SRVR:AM3PR08MB0088; BCL:0; PCL:0; RULEID:; SRVR:AM3PR08MB0088; x-forefront-prvs: 08417837C5 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(6009001)(377424004)(54534003)(102836003)(1220700001)(5008740100001)(1096002)(2351001)(4326007)(106116001)(229853001)(586003)(40100003)(92566002)(6116002)(3846002)(450100001)(11100500001)(2906002)(3660700001)(5002640100001)(5250100002)(2501003)(3280700002)(5004730100002)(5003600100002)(2900100001)(5001960100002)(76576001)(86362001)(575784001)(54356999)(50986999)(33656002)(110136002)(189998001)(87936001)(19580405001)(74316001)(66066001)(19580395003); DIR:OUT; SFP:1101; SCL:1; SRVR:AM3PR08MB0088; H:AM3PR08MB0088.eurprd08.prod.outlook.com; FPR:; SPF:None; MLV:sfv; LANG:en; spamdiagnosticoutput: 1:23 spamdiagnosticmetadata: NSPM MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-originalarrivaltime: 03 Feb 2016 16:35:21.7836 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM3PR08MB0088 X-MC-Unique: 0-w94dBjSpmOk_ZNMtbrWg-1 This patch fixes an exponential issue in ccmp.c. When deciding which ccmp expansion to use, the tree nodes gs0 and gs1 are fully expanded twice. If they contain more CCMP opportunities, their subtrees are also expanded twice. When the trees are complex the expansion takes exponential time and memory. As a workaround in GCC6 compute the cost of the first expansion early, and only try the alternative expansion if the cost is low enough. This rarely affects real code, eg. SPECINT2006 has identical codesize. For GCC7 we should improve the way this works and simplify the backend interface. I don't see why the backend should expand tree expressions, especially when they are not part of the CCMP sequence. OK for commit? ChangeLog: 2016-02-03 Wilco Dijkstra gcc/ PR target/69619 * ccmp.c (expand_ccmp_expr_1): Avoid evaluating gs0/gs1 twice when complex. gcc/testsuite/ * gcc.dg/pr69619.c: Add new test. diff --git a/gcc/ccmp.c b/gcc/ccmp.c index 9f1ce295554d17c0c3e39676632a07cabe7d5493..dce610488f2d13d6983f3752fb884c8af7ed3bc8 100644 --- a/gcc/ccmp.c +++ b/gcc/ccmp.c @@ -183,19 +183,25 @@ expand_ccmp_expr_1 (gimple *g, rtx *prep_seq, rtx *gen_seq) gimple_assign_rhs1 (gs0), gimple_assign_rhs2 (gs0)); - tmp2 = targetm.gen_ccmp_first (&prep_seq_2, &gen_seq_2, rcode1, - gimple_assign_rhs1 (gs1), - gimple_assign_rhs2 (gs1)); - - if (!tmp && !tmp2) - return NULL_RTX; - if (tmp != NULL) { ret = expand_ccmp_next (gs1, code, tmp, &prep_seq_1, &gen_seq_1); cost1 = seq_cost (safe_as_a (prep_seq_1), speed_p); cost1 += seq_cost (safe_as_a (gen_seq_1), speed_p); } + + /* FIXME: Temporary workaround for PR69619. + Avoid exponential compile time due to expanding gs0 and gs1 twice. + If gs0 and gs1 are complex, the cost will be high, so avoid + reevaluation if above an arbitrary threshold. */ + if ((tmp == NULL) || (cost1 < 100)) + tmp2 = targetm.gen_ccmp_first (&prep_seq_2, &gen_seq_2, rcode1, + gimple_assign_rhs1 (gs1), + gimple_assign_rhs2 (gs1)); + + if (!tmp && !tmp2) + return NULL_RTX; + if (tmp2 != NULL) { ret2 = expand_ccmp_next (gs0, code, tmp2, &prep_seq_2, diff --git a/gcc/testsuite/gcc.dg/pr69619.c b/gcc/testsuite/gcc.dg/pr69619.c new file mode 100644 index 0000000000000000000000000000000000000000..a200bdf310fc2c02b008e0c13fb9c917784423f8 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr69619.c @@ -0,0 +1,20 @@ +/* { dg-do compile } */ +/* { dg-options "-O3" } */ + +int a, b, c, d; +int e[100]; +void +fn1 () +{ + int *f = &d; + c = 6; + for (; c; c--) + { + b = 0; + for (; b <= 5; b++) + { + short g = e[(b + 2) * 9 + c]; + *f = *f == a && e[(b + 2) * 9 + c]; + } + } +}