From patchwork Tue Oct 17 14:50:21 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bin Cheng X-Patchwork-Id: 827061 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-464341-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="YdKS87UT"; dkim-atps=neutral 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 3yGdR06pZgz9rxl for ; Wed, 18 Oct 2017 01:50:36 +1100 (AEDT) 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=rxsPOxPo9E85PCU5NyYOnFMHa+E7LqtK882Qxdawy2Cw9+j324 jLDa6MGitJUMLRILAQm61X0hd3NeTFCAYq1h7GlQVqHyoNpIWBp21T5mfTDQ+hX/ BFeGGF6PR0oqduYwTVJaDIXg52FX6fQTqamJJnRPqwUuTqzn+U+gXW2fw= 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=yx5kDW5pUYgwPdcdzqZcAEwt/T8=; b=YdKS87UTDOEJL/9ZcXqd CFyTuUpDVjxqzdlhw6EwmeZsPApxu9VyBLktZaKEJrDVT4SWgQu002Ymr++Aej6u PhI705MqmqMhHDwYqO126LKSxGXsumPTbpuG21NiDFZAaYj5ugZeuwtLL0s5UBmv 6KP8A+tsO/SwYHPiRSonpek= Received: (qmail 89728 invoked by alias); 17 Oct 2017 14:50:29 -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 89717 invoked by uid 89); 17 Oct 2017 14:50:28 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-25.8 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=rdg X-HELO: EUR01-VE1-obe.outbound.protection.outlook.com Received: from mail-ve1eur01on0071.outbound.protection.outlook.com (HELO EUR01-VE1-obe.outbound.protection.outlook.com) (104.47.1.71) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 17 Oct 2017 14:50:26 +0000 Received: from DB5PR0801MB2742.eurprd08.prod.outlook.com (10.166.176.26) by DB5PR0801MB2743.eurprd08.prod.outlook.com (10.166.176.27) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P256) id 15.20.77.7; Tue, 17 Oct 2017 14:50:22 +0000 Received: from DB5PR0801MB2742.eurprd08.prod.outlook.com ([10.166.176.26]) by DB5PR0801MB2742.eurprd08.prod.outlook.com ([10.166.176.26]) with mapi id 15.20.0077.022; Tue, 17 Oct 2017 14:50:21 +0000 From: Bin Cheng To: "gcc-patches@gcc.gnu.org" CC: nd Subject: [PATCH PR82574]Check that datref must be executed exactly once per iteration against outermost loop in nest Date: Tue, 17 Oct 2017 14:50:21 +0000 Message-ID: authentication-results: spf=none (sender IP is ) smtp.mailfrom=Bin.Cheng@arm.com; x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1; DB5PR0801MB2743; 6:eSNl2RT7TwTqQq0Og3T0jmRtNr9pAMkI35FsjqiTqOiN+GZDQMPm1WH0dbLWp2H3ihbBmxUfR4hEZKm2G9UdrNsfoVfujMBnh6x8vGpowQvlapzEfM5i24AG/89D2dhYE8sxWHsFecuPBlRhRdWKIjLz4jA23oO2DmUMn/lxmoTlDG/lH8RmGcApc1sQo58/HLau6ndVzNqlgLvskg7j1uIYVPNYv7LKYVZ3BepwuTYxkVDqPH0CFRYxHZlTWbGpGW9OVhNpXYJhP4QuqK6W08o0bUolG6kZyrXN/UwhqcoCIdZaMKAaA+o6s7NVkCw+R4PC4ORa8eVWsuE+lsdyuA==; 5:fV3l1lrpprSiPP2Moy6iWxRHuwMl4zPC6mbW0CnUbaNf1MlGALFwTF+zosFGByJE389e3dcB4c2vbrzGttQ9URoXFvuz2wutk6Bstm0CdqppxnMlnk+cq72hSYuwF1dWk9mAWwbY46JxcqHAmdAxvQ==; 24:1oSF7oq0gVi5q2SogsYVK/+DiH5NToIZy9p9QZXxEs2/YT+8PMVvIBEBqdqsdwD7JsC1x4btdgCQR2pUkXQgyQ8ElBj+luMs0dfKhz1Hl+4=; 7:t73TFnrpsp1SZntjdPZ8Sb+nwrdHZp7FUbws0kCVSeMAnNwWuQ1NMh8ZagOB3GcPc9hBm0+5hWh0Mm7W44dVlLR7pjAyGcthACKDTxQvdB7bVuPCPZSFbS9S7bDcmQpaTNMM1KYY5bRpp6cphfSvD/cjXlPs5QLYH2yuS/KlTCOvduzL9fWmyAzNELstJls4YY6LC67+5Pi+Xm+I8snA/NvMgDxDegvjlc+2CW/7MoQ= x-ms-exchange-antispam-srfa-diagnostics: SSOS; x-ms-office365-filtering-correlation-id: 6706b529-ecb9-4aaa-2282-08d5156e6458 x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001)(2017030254152)(48565401081)(2017052603199)(49563074)(201703131423075)(201703031133081)(201702281549075); SRVR:DB5PR0801MB2743; x-ms-traffictypediagnostic: DB5PR0801MB2743: nodisclaimer: True x-exchange-antispam-report-test: UriScan:(180628864354917); x-microsoft-antispam-prvs: x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(100000700101)(100105000095)(100000701101)(100105300095)(100000702101)(100105100095)(102415395)(6040450)(2401047)(8121501046)(5005006)(93006095)(93001095)(3002001)(10201501046)(100000703101)(100105400095)(6055026)(6041248)(20161123558100)(20161123564025)(20161123560025)(20161123562025)(20161123555025)(201703131423075)(201702281528075)(201703061421075)(201703061406153)(6072148)(201708071742011)(100000704101)(100105200095)(100000705101)(100105500095); SRVR:DB5PR0801MB2743; BCL:0; PCL:0; RULEID:(100000800101)(100110000095)(100000801101)(100110300095)(100000802101)(100110100095)(100000803101)(100110400095)(100000804101)(100110200095)(100000805101)(100110500095); SRVR:DB5PR0801MB2743; x-forefront-prvs: 04631F8F77 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(6009001)(376002)(346002)(39860400002)(199003)(189002)(377424004)(102836003)(6506006)(6116002)(3846002)(68736007)(77096006)(106356001)(25786009)(105586002)(66066001)(3660700001)(33656002)(2351001)(3280700002)(50986999)(99936001)(2501003)(189998001)(97736004)(2906002)(54356999)(86362001)(5640700003)(14454004)(6436002)(4001150100001)(55016002)(101416001)(305945005)(72206003)(99286003)(9686003)(6916009)(316002)(7736002)(53936002)(81166006)(81156014)(8676002)(478600001)(7696004)(8936002)(5660300001)(2900100001)(4326008)(74316002); DIR:OUT; SFP:1101; SCL:1; SRVR:DB5PR0801MB2743; H:DB5PR0801MB2742.eurprd08.prod.outlook.com; FPR:; SPF:None; PTR:InfoNoRecords; A:1; MX:1; LANG:en; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-originalarrivaltime: 17 Oct 2017 14:50:21.6407 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB5PR0801MB2743 X-IsSubscribed: yes Hi, The patch fixes ICE reported in PR82574. In order to distribute builtin partition, we need to check that data reference must be executed exactly once per iteration. In distribution for loop nest, this has to be checked against each loop in the nest. One optimization can be done is we only need to check against the outermost loop for perfect nest. Bootstrap and test on x86_64. Is it OK? Thanks, bin 2017-10-17 Bin Cheng PR tree-optimization/82574 * tree-loop-distribution.c (find_single_drs): New parameter. Check that data reference must be executed exactly once per iteration against the outermost loop in nest. (classify_partition): Update call to above function. gcc/testsuite 2017-10-17 Bin Cheng PR tree-optimization/82574 * gcc.dg/tree-ssa/pr82574.c: New test. diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr82574.c b/gcc/testsuite/gcc.dg/tree-ssa/pr82574.c new file mode 100644 index 0000000..8fc4596 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr82574.c @@ -0,0 +1,19 @@ +/* { dg-do run } */ +/* { dg-options "-O3" } */ + +unsigned char a, b, c, d[200][200]; + +void abort (void); + +int main () +{ + for (; a < 200; a++) + for (b = 0; b < 200; b++) + if (c) + d[a][b] = 1; + + if ((c && d[0][0] != 1) || (!c && d[0][0] != 0)) + abort (); + + return 0; +} diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c index 5e835be..d029f98 100644 --- a/gcc/tree-loop-distribution.c +++ b/gcc/tree-loop-distribution.c @@ -1283,12 +1283,12 @@ build_rdg_partition_for_vertex (struct graph *rdg, int v) return partition; } -/* Given PARTITION of RDG, record single load/store data references for - builtin partition in SRC_DR/DST_DR, return false if there is no such +/* Given PARTITION of LOOP and RDG, record single load/store data references + for builtin partition in SRC_DR/DST_DR, return false if there is no such data references. */ static bool -find_single_drs (struct graph *rdg, partition *partition, +find_single_drs (struct loop *loop, struct graph *rdg, partition *partition, data_reference_p *dst_dr, data_reference_p *src_dr) { unsigned i; @@ -1344,10 +1344,12 @@ find_single_drs (struct graph *rdg, partition *partition, && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (single_st), 1))) return false; - /* Data reference must be executed exactly once per iteration. */ + /* Data reference must be executed exactly once per iteration of each + loop in the loop nest. We only need to check dominant information + against the outermost one in a perfect loop nest because a bb can't + dominate outermost loop's latch without dominating inner loop's. */ basic_block bb_st = gimple_bb (DR_STMT (single_st)); - struct loop *inner = bb_st->loop_father; - if (!dominated_by_p (CDI_DOMINATORS, inner->latch, bb_st)) + if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb_st)) return false; if (single_ld) @@ -1365,14 +1367,16 @@ find_single_drs (struct graph *rdg, partition *partition, /* Load and store must be in the same loop nest. */ basic_block bb_ld = gimple_bb (DR_STMT (single_ld)); - if (inner != bb_ld->loop_father) + if (bb_st->loop_father != bb_ld->loop_father) return false; - /* Data reference must be executed exactly once per iteration. */ - if (!dominated_by_p (CDI_DOMINATORS, inner->latch, bb_ld)) + /* Data reference must be executed exactly once per iteration. + Same as single_st, we only need to check against the outermost + loop. */ + if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb_ld)) return false; - edge e = single_exit (inner); + edge e = single_exit (bb_st->loop_father); bool dom_ld = dominated_by_p (CDI_DOMINATORS, e->src, bb_ld); bool dom_st = dominated_by_p (CDI_DOMINATORS, e->src, bb_st); if (dom_ld != dom_st) @@ -1611,7 +1615,7 @@ classify_partition (loop_p loop, struct graph *rdg, partition *partition, return; /* Find single load/store data references for builtin partition. */ - if (!find_single_drs (rdg, partition, &single_st, &single_ld)) + if (!find_single_drs (loop, rdg, partition, &single_st, &single_ld)) return; /* Classify the builtin kind. */