From patchwork Fri Oct 21 09:16:20 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 6599 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4242:0:0:0:0:0 with SMTP id s2csp582098wrr; Fri, 21 Oct 2022 02:17:07 -0700 (PDT) X-Google-Smtp-Source: AMsMyM5Dx49JQxLGWLGGWxrBcYYlLjzan81bzdCft5QIglcO9vUpIq8BLIAPYhDs18cfZkhFkXIk X-Received: by 2002:a05:6402:34ce:b0:45d:14c9:c522 with SMTP id w14-20020a05640234ce00b0045d14c9c522mr16204344edc.160.1666343827822; Fri, 21 Oct 2022 02:17:07 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1666343827; cv=none; d=google.com; s=arc-20160816; b=h2VYUvel+tVsfE+h2eqNWbQiqkQSDqWkYsvEioT0Pj5fkLqMYIlYKW0pCV3o01y3gW AXK4iSKcS+MX+rFLLtvd7j1uFX72J9kGpeJjhSW0SOXoogssNH58sfG5rO9p+2bXDZXM f7F5RoYA+xzjlo/dSnWCgPYCMkYlTNd/pEyPpiawgxkq9X9pLXc3cxrUSJ3K3sDUy9bo zk1t/i419LJcpSsV1BX073TO+Lj9WHqZa12Nl0qa1LUmk/daMKp5Bv1LuD6sO8+Ai87y fPIO1v6gKK/YgMe/ibeWT5UbfEkxaZIpMG5orRwIqFsOr8wP5/pZXtEpdFyKYC6pMNT8 Zp2A== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence:message-id :mime-version:subject:to:date:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=Xg5L1aS4QHlaM9P2Ncsf9bFoyx4y6VdLNtOyl6bnb5Q=; b=JTUBXz8JEOJPXDlAoeGN7zEc2BQWjfhFBv/sS43MyHs/iIpnvJNpwX5rndbowwaiHY iIwobX8KeHjI/dkHVPY5udFc+dr+f7afErROtPJOpEnmWPM5/hSw22wKiBKLOkKJebv1 otrvKTfGf5ZRTR4p8VDoHbqTXwJ7miRtRstFm7q4cr1Z22xxWXkMdMJIWx0FfH3IVulZ GBbRrnFmdEKo3/Rn3hYkjHCRLJ7cLpnGAWZDolWS05ZiFY2RAoxp8zT1X2A9id9FKO15 hcHlXK84gqEnGkA/JWiivBy16yCE7XVV4DFyxlaRO8lLvdqX3GONIRbTG5ihjQBC/O/K 0F6A== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=ZfxTOnPx; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id k15-20020a170906680f00b0078db717cf44si15676111ejr.303.2022.10.21.02.17.07 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 21 Oct 2022 02:17:07 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=ZfxTOnPx; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 86E4F385483F for ; Fri, 21 Oct 2022 09:17:06 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 86E4F385483F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1666343826; bh=Xg5L1aS4QHlaM9P2Ncsf9bFoyx4y6VdLNtOyl6bnb5Q=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=ZfxTOnPxfiat0Qbui7dvm2BUm8VofmgViAwG4wCkCZy+J69xoLgyXeAxosTP0BYCr ArSiDWyaKTID8rr9cmREU3J2nQ3I9XEL0/98dWSnrBL98zcT+nzyNIE5+kLGIbNtXx rsHj9E4V/IbaqCg+F9Oj4u0ZGRMD6GFtb1HjBnaU= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29]) by sourceware.org (Postfix) with ESMTPS id 66C8A385480D for ; Fri, 21 Oct 2022 09:16:22 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 66C8A385480D Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out2.suse.de (Postfix) with ESMTPS id 469BD1F8B4 for ; Fri, 21 Oct 2022 09:16:21 +0000 (UTC) Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 335F21331A for ; Fri, 21 Oct 2022 09:16:21 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id JudoC2VjUmNbcQAAMHmgww (envelope-from ) for ; Fri, 21 Oct 2022 09:16:21 +0000 Date: Fri, 21 Oct 2022 11:16:20 +0200 (CEST) To: gcc-patches@gcc.gnu.org Subject: [PATCH] tree-optimization/107323 - loop distribution partition ordering issue MIME-Version: 1.0 Message-Id: <20221021091621.335F21331A@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Richard Biener via Gcc-patches From: Richard Biener Reply-To: Richard Biener Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1747288145616898237?= X-GMAIL-MSGID: =?utf-8?q?1747288145616898237?= The following reverts part of the PR94125 fix which causes us to use a bogus partition ordering after applying versioning for alias to the testcase in PR107323. Instead PR94125 is fixed by appropriately considering to be merged SCCs when skipping edges we want to ignore because of the alias versioning. Bootstrapped and tested on x86_64-unknown-linux-gnu, on the 10 branch where reverting the part of PR94125 reproduces the original issue and that's fixed by the adjustment, on the 12 branch where the PR107323 bug can be reproduced, and on trunk. Pushed to trunk and gcc-12 sofar. PR tree-optimization/107323 * tree-loop-distribution.cc (pg_unmark_merged_alias_ddrs): New function. (loop_distribution::break_alias_scc_partitions): Revert postorder save/restore from the PR94125 fix. Instead make sure to not ignore edges from SCCs we are going to merge. * gcc.dg/tree-ssa/pr107323.c: New testcase. --- gcc/testsuite/gcc.dg/tree-ssa/pr107323.c | 28 +++++++++++++ gcc/tree-loop-distribution.cc | 50 +++++++++++++++++------- 2 files changed, 64 insertions(+), 14 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr107323.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr107323.c b/gcc/testsuite/gcc.dg/tree-ssa/pr107323.c new file mode 100644 index 00000000000..1204b6e36d5 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr107323.c @@ -0,0 +1,28 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fno-tree-vectorize" } */ + +int A[4]; +int B[4]; + +static const char *__attribute__((noipa)) foo() +{ + return "1"; +} + +int main() +{ + const char *s = foo(); + + A[0] = 1000; + for(int i = 1; i < 4; ++i) { + B[i] = 0; + A[i] = 0; + if(s[0]) + B[i] = 1; + A[i] = A[i - 1]; + } + + if (A[3] != 1000) + __builtin_abort (); + return 0; +} diff --git a/gcc/tree-loop-distribution.cc b/gcc/tree-loop-distribution.cc index e1948fb452a..ed3dd73e1a9 100644 --- a/gcc/tree-loop-distribution.cc +++ b/gcc/tree-loop-distribution.cc @@ -2201,8 +2201,6 @@ struct pg_edge_callback_data bitmap sccs_to_merge; /* Array constains component information for all vertices. */ int *vertices_component; - /* Array constains postorder information for all vertices. */ - int *vertices_post; /* Vector to record all data dependence relations which are needed to break strong connected components by runtime alias checks. */ vec *alias_ddrs; @@ -2452,6 +2450,33 @@ pg_collect_alias_ddrs (struct graph *g, struct graph_edge *e, void *data) cbdata->alias_ddrs->safe_splice (edata->alias_ddrs); } +/* Callback function for traversing edge E. DATA is private + callback data. */ + +static void +pg_unmark_merged_alias_ddrs (struct graph *, struct graph_edge *e, void *data) +{ + int i, j, component; + struct pg_edge_callback_data *cbdata; + struct pg_edata *edata = (struct pg_edata *) e->data; + + if (edata == NULL || edata->alias_ddrs.length () == 0) + return; + + cbdata = (struct pg_edge_callback_data *) data; + i = e->src; + j = e->dest; + component = cbdata->vertices_component[i]; + /* Make sure to not skip vertices inside SCCs we are going to merge. */ + if (component == cbdata->vertices_component[j] + && bitmap_bit_p (cbdata->sccs_to_merge, component)) + { + edata->alias_ddrs.release (); + delete edata; + e->data = NULL; + } +} + /* This is the main function breaking strong conected components in PARTITIONS giving reduced depdendence graph RDG. Store data dependence relations for runtime alias check in ALIAS_DDRS. */ @@ -2511,7 +2536,6 @@ loop_distribution::break_alias_scc_partitions (struct graph *rdg, cbdata.sccs_to_merge = sccs_to_merge; cbdata.alias_ddrs = alias_ddrs; cbdata.vertices_component = XNEWVEC (int, pg->n_vertices); - cbdata.vertices_post = XNEWVEC (int, pg->n_vertices); /* Record the component information which will be corrupted by next graph scc finding call. */ for (i = 0; i < pg->n_vertices; ++i) @@ -2520,17 +2544,18 @@ loop_distribution::break_alias_scc_partitions (struct graph *rdg, /* Collect data dependences for runtime alias checks to break SCCs. */ if (bitmap_count_bits (sccs_to_merge) != (unsigned) num_sccs) { - /* Record the postorder information which will be corrupted by next - graph SCC finding call. */ - for (i = 0; i < pg->n_vertices; ++i) - cbdata.vertices_post[i] = pg->vertices[i].post; + /* For SCCs we want to merge clear all alias_ddrs for edges + inside the component. */ + for_each_edge (pg, pg_unmark_merged_alias_ddrs, &cbdata); /* Run SCC finding algorithm again, with alias dependence edges skipped. This is to topologically sort partitions according to compilation time known dependence. Note the topological order is stored in the form of pg's post order number. */ num_sccs_no_alias = graphds_scc (pg, NULL, pg_skip_alias_edge); - gcc_assert (partitions->length () == (unsigned) num_sccs_no_alias); + /* We cannot assert partitions->length () == num_sccs_no_alias + since we are not ignoring alias edges in cycles we are + going to merge. That's required to compute correct postorder. */ /* With topological order, we can construct two subgraphs L and R. L contains edge where x < y in terms of post order, while R contains edge where x > y. Edges for compilation time @@ -2565,16 +2590,14 @@ loop_distribution::break_alias_scc_partitions (struct graph *rdg, first->type = PTYPE_SEQUENTIAL; } } - /* Restore the postorder information if it's corrupted in finding SCC - with alias dependence edges skipped. If reduction partition's SCC is - broken by runtime alias checks, we force a negative post order to it - making sure it will be scheduled in the last. */ + /* If reduction partition's SCC is broken by runtime alias checks, + we force a negative post order to it making sure it will be scheduled + in the last. */ if (num_sccs_no_alias > 0) { j = -1; for (i = 0; i < pg->n_vertices; ++i) { - pg->vertices[i].post = cbdata.vertices_post[i]; struct pg_vdata *data = (struct pg_vdata *)pg->vertices[i].data; if (data->partition && partition_reduction_p (data->partition)) { @@ -2587,7 +2610,6 @@ loop_distribution::break_alias_scc_partitions (struct graph *rdg, } free (cbdata.vertices_component); - free (cbdata.vertices_post); } sort_partitions_by_post_order (pg, partitions);