From patchwork Fri Jul 22 10:09:53 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Li, Pan2 via Gcc-patches" X-Patchwork-Id: 124 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:f503:0:0:0:0:0 with SMTP id q3csp161129wro; Fri, 22 Jul 2022 03:10:40 -0700 (PDT) X-Google-Smtp-Source: AGRyM1tQZeQgQMyPzKjXFrQIytv0DA5zq7cIoKYJns8FomvAP7zTymrv1P+jVCKhenOjDs6oc4yX X-Received: by 2002:a05:6402:35c2:b0:43a:c5ba:36f0 with SMTP id z2-20020a05640235c200b0043ac5ba36f0mr2705558edc.80.1658484640796; Fri, 22 Jul 2022 03:10:40 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1658484640; cv=none; d=google.com; s=arc-20160816; b=jd4sMc7xI/6lNFBWuomTlYKXaMiKrCp31F8kyNef+T4m/n/T7whMdcY7fEa15bJczP Gsm/r7/n52M3yKJjnL6ECqmpe4SSzRYdE1l5U4f6nn+CHJbKKHgkkrQ9BnKUymdauGWV NJELU1TyBwTJnAXL6WhyqVNsHbDTBWrGAtIaIjXsU7w0m8PMROalsyf8om4CdyNVAmFJ Tn2xg7a5kbt5bCU5pp4R+9NdNfUjyEwWX1gXfNSIoTV0r1mVuYGGmw35j5/dnlPmMx0c FhB3unUmxnv+2ReKJqGtn7YlPJopwnUzOnJU92PCmhkXWWucYYW9e4T+ngPg7oxEjZ3Q fufw== 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:mime-version :user-agent:message-id:date:subject:mail-followup-to:to:dmarc-filter :delivered-to:dkim-signature:dkim-filter; bh=JUrhC29FLgnMkJuJJpOTtJy0l/14VQnkaA1hiEhHhPc=; b=iW5aZYQshAmJQfQXCOwHNVAqwQgTFhL2UBoqMZnMt/pCFmiwkLO9H49QcAWNwD0aEJ eAdugJnb17sVsYj/PANLiNqtjFyz7MYZktfP4pYlmvGKBuLJ2RDpn+75Hk46yM6Fxop9 OAP5ufWX9jxhTDP3KT3d2oWAf9GqSRUkl88wEhEHyysBtY7mgY0IWx8E3g6rQMW1b8Jz qtus5XKDMzIavyCM5qe/ObNNlcYu5OA3ZCNRkqUh8NEOLCmzAfJiaA9EPmjWxjy+vmxD DQkAp8k5yJClvafXEkDkfdFk4Ufrof7/FcckjjDrw6/s42OwoQeB8srdvyoIIUQNxETd WKOQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=fRNvYlSv; 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 v9-20020a1709064e8900b0072ac7a2727asi4669373eju.959.2022.07.22.03.10.40 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 22 Jul 2022 03:10:40 -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=fRNvYlSv; 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 BE1483834E43 for ; Fri, 22 Jul 2022 10:10:38 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org BE1483834E43 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1658484638; bh=JUrhC29FLgnMkJuJJpOTtJy0l/14VQnkaA1hiEhHhPc=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=fRNvYlSv3srmmIF032WmTQubn7MOI/C/pEhxU+gx4Haew0UFC5TL/zos4PCch/UBa l5qk2WQJzDsUpnJkwkRxHm49ky03vc9d76OxoY1Z/uM6QbV9Kr5sL2BrHXUoymt2XN 5eEim6d1Kc1Uz90MknCqDQd2aMctkOW2+T3WwWG4= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by sourceware.org (Postfix) with ESMTP id E15733857C5D for ; Fri, 22 Jul 2022 10:09:55 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E15733857C5D Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 0F0181063 for ; Fri, 22 Jul 2022 03:09:56 -0700 (PDT) Received: from localhost (e121540-lin.manchester.arm.com [10.32.98.37]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 292E53F766 for ; Fri, 22 Jul 2022 03:09:55 -0700 (PDT) To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@arm.com Subject: [PATCH] graphds: Fix description of SCC algorithm Date: Fri, 22 Jul 2022 11:09:53 +0100 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) MIME-Version: 1.0 X-Spam-Status: No, score=-53.7 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_NONE, KAM_DMARC_STATUS, KAM_LAZY_DOMAIN_SECURITY, SPF_HELO_NONE, SPF_NONE, 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 Sandiford via Gcc-patches From: "Li, Pan2 via Gcc-patches" Reply-To: Richard Sandiford 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?1739047191172340418?= X-GMAIL-MSGID: =?utf-8?q?1739047191172340418?= graphds_scc says that it uses Tarjan's algorithm, but it looks like it uses Kosaraju's algorithm instead (dfs one way followed by dfs the other way). OK to install? Richard gcc/ * graphds.cc (graphds_scc): Fix algorithm attribution. --- gcc/graphds.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/gcc/graphds.cc b/gcc/graphds.cc index f4c83e81cf9..91a2ca5c225 100644 --- a/gcc/graphds.cc +++ b/gcc/graphds.cc @@ -276,7 +276,7 @@ graphds_dfs (struct graph *g, int *qs, int nq, vec *qt, } /* Determines the strongly connected components of G, using the algorithm of - Tarjan -- first determine the postorder dfs numbering in reversed graph, + Kosaraju -- first determine the postorder dfs numbering in reversed graph, then run the dfs on the original graph in the order given by decreasing numbers assigned by the previous pass. If SUBGRAPH is not NULL, it specifies the subgraph of G whose strongly connected components we want