From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29]) by sourceware.org (Postfix) with ESMTPS id 5314D387237D for ; Tue, 31 Jan 2023 14:45:45 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 5314D387237D 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-out2.suse.de (Postfix) with ESMTPS id 5D00B2069F; Tue, 31 Jan 2023 14:45:44 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1675176344; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=6uVXAE27Vc91svXM8dI3HI8rHVD3XqGX47GoANJnAqk=; b=xH5nFJZxjektkKSXOpubcbK5l/2AHHde/SMQDuthT6wH6RvffvuBwgO0qcRF60Mun+vqvC aQ7FreEM/2Ge6HWvnnBc5U7AKV+qWUsQlSAwBPAdeJXkXFSLICcFuJm3tqYI2Ny0DZRuDg +wg2Gy4hfb9xkJv9NhPzMQ+9/ikkVhE= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1675176344; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=6uVXAE27Vc91svXM8dI3HI8rHVD3XqGX47GoANJnAqk=; b=x2a2/dMlC29JwMROCTthLZ3A3GnpC2NOwSgazM20n5K5HtgUgG4Pl+rbclx/in/WuTuKMo l1gVdBzQqGYt2PCw== 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 452FD13585; Tue, 31 Jan 2023 14:45:44 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id mprHD5gp2WNKTQAAMHmgww (envelope-from ); Tue, 31 Jan 2023 14:45:44 +0000 Date: Tue, 31 Jan 2023 15:45:43 +0100 (CET) From: Richard Biener To: gcc-patches@gcc.gnu.org cc: Jakub Jelinek Subject: [PATCH] middle-end/108500 - replace recursive domtree DFS traversal MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Message-Id: <20230131144544.452FD13585@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 List-Id: 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. Bootstrapped and tested on x86_64-unknown-linux-gnu. 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. OK for trunk and later branch(es)? Thanks, Richard. PR middle-end/108500 * dominance.cc (assign_dfs_numbers): Replace recursive DFS with tree traversal algorithm. --- gcc/dominance.cc | 27 +++++++++++++++++---------- 1 file changed, 17 insertions(+), 10 deletions(-) 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 = (*num)++; - - if (node->son) + et_node *n = node; + while (1) { - assign_dfs_numbers (node->son, num); - for (son = node->son->right; son != node->son; son = son->right) - assign_dfs_numbers (son, num); + n->dfs_num_in = (*num)++; + if (n->son) + n = n->son; + else + { + while (!n->right || n->right == n->father->son) + { + n->dfs_num_out = (*num)++; + if (n == node) + return; + n = n->father; + } + n->dfs_num_out = (*num)++; + n = n->right; + } } - - node->dfs_num_out = (*num)++; } /* Compute the data necessary for fast resolving of dominator queries in a -- 2.35.3