From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out1.suse.de (smtp-out1.suse.de [IPv6:2001:67c:2178:6::1c]) by sourceware.org (Postfix) with ESMTPS id D587D3858D28 for ; Tue, 31 Jan 2023 18:20:48 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org D587D3858D28 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de 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-out1.suse.de (Postfix) with ESMTPS id C631922C91; Tue, 31 Jan 2023 18:20:47 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1675189247; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=9FcIk77pruEX3HTm2u5Hq/0mnUs+qwnHRL0BhOlquT4=; b=ODtqPurWmGaKFs1aQwTeVrPRLFlMLoHE/b97FpYJm0fvJniDbcC20MuwOBTBtFtLPLMp1I XBRa1tNCECInI5m7aXRyNz8d68cV3HSmUgvRMkeJ3163PkzaPy2Y68k70PI03zG5utaO6m X1zUMb0CdJE8Ht/HYaJQpFazqHT14N4= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1675189247; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=9FcIk77pruEX3HTm2u5Hq/0mnUs+qwnHRL0BhOlquT4=; b=1IeqJBUvNdm+r2EF+Ob7fXEy15RHZB0egwMH9EBnrTCmV44m/2VeU2CFhjMQJA3EcPUIkf UDtjGtwNnmtD5OBg== 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 B27FD138E8; Tue, 31 Jan 2023 18:20:47 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id NsmBK/9b2WO8IgAAMHmgww (envelope-from ); Tue, 31 Jan 2023 18:20:47 +0000 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable From: Richard Biener Mime-Version: 1.0 (1.0) Subject: Re: [PATCH] middle-end/108500 - replace recursive domtree DFS traversal Date: Tue, 31 Jan 2023 19:20:37 +0100 Message-Id: <90BD28AC-CE2D-4002-B4B1-F8510BCD681A@suse.de> References: Cc: gcc-patches@gcc.gnu.org In-Reply-To: To: Jakub Jelinek X-Mailer: iPhone Mail (20D47) X-Spam-Status: No, score=-11.7 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 List-Id: > Am 31.01.2023 um 16:59 schrieb Jakub Jelinek via Gcc-patches : >=20 > =EF=BB=BFOn Tue, Jan 31, 2023 at 03:45:43PM +0100, Richard Biener wrote: >> The following replaces the recursive DFS traversal of the dominator >> tree in assign_dfs_numbers with a tree traversal using the fact >> that we have recorded parents. >>=20 >> Bootstrapped and tested on x86_64-unknown-linux-gnu. >>=20 >> This makes r13-5325 somewhat obsolete, though not computing the >> DFS numbers at all is beneficial in the cases where we perform >> immediate CFG manipulations. >>=20 >> OK for trunk and later branch(es)? >>=20 >> Thanks, >> Richard. >>=20 >> PR middle-end/108500 >> * dominance.cc (assign_dfs_numbers): Replace recursive DFS >> with tree traversal algorithm. >=20 > LGTM. >=20 >> diff --git a/gcc/dominance.cc b/gcc/dominance.cc >> index 099b8fd3f24..34fabe40c18 100644 >> --- a/gcc/dominance.cc >> +++ b/gcc/dominance.cc >> @@ -639,18 +639,25 @@ dom_info::calc_idoms () >> static void >> assign_dfs_numbers (struct et_node *node, int *num) >> { >> - struct et_node *son; >> - >> - node->dfs_num_in =3D (*num)++; >> - >> - if (node->son) >> + et_node *n =3D node; >> + while (1) >> { >> - assign_dfs_numbers (node->son, num); >> - for (son =3D node->son->right; son !=3D node->son; son =3D son->ri= ght) >> - assign_dfs_numbers (son, num); >> + n->dfs_num_in =3D (*num)++; >> + if (n->son) >> + n =3D n->son; >> + else >> + { >> + while (!n->right || n->right =3D=3D n->father->son) >=20 > Am I right that we could replace !n->right with n =3D=3D node here too > (i.e. only node can have NULL father and in that case also NULL > left/right? =20 Yes. > Though !n->right might result in better code because > we need to load it anyway for the second comparison. >=20 >> + { >> + n->dfs_num_out =3D (*num)++; >> + if (n =3D=3D node) >> + return; >> + n =3D n->father; >> + } >> + n->dfs_num_out =3D (*num)++; >> + n =3D n->right; >> + } >> } >> - >> - node->dfs_num_out =3D (*num)++; >> } >>=20 >=20 > Jakub >=20