From patchwork Wed Nov 10 12:00:55 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 1553397 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=YvBn/3Iw; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4Hq3Qk0zyBz9s0r for ; Wed, 10 Nov 2021 23:03:24 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id DCBAC3857C6D for ; Wed, 10 Nov 2021 12:03:21 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org DCBAC3857C6D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1636545801; bh=86twoSVu75a+TlKKg6JEwJCyzdeBJTzrIryTxPYuz0M=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=YvBn/3IwZZS2uAL0p89YTGrNbgzQ+Xh6KxZid21Mj2GUBJ0yyJ6fKTH+z8NsKD6rA 5wlL8E2Eoez2zalk1k/6Fx23lLD3IxVKY4tOl4CHI26aXIJaXYspTfGLG1yeuSc26S nNOuJi5d1iExFaSgf43UrI6F+vmdL20vUqZDUmQw= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.220.28]) by sourceware.org (Postfix) with ESMTPS id 6DEE3385781B for ; Wed, 10 Nov 2021 12:00:57 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 6DEE3385781B 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 70D4321B17 for ; Wed, 10 Nov 2021 12:00:56 +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 5178913BEA for ; Wed, 10 Nov 2021 12:00:56 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id dsm7Eni0i2GGbAAAMHmgww (envelope-from ) for ; Wed, 10 Nov 2021 12:00:56 +0000 Date: Wed, 10 Nov 2021 13:00:55 +0100 (CET) To: gcc-patches@gcc.gnu.org Subject: [PATCH] Apply TLC to control dependence compute Message-ID: MIME-Version: 1.0 X-Spam-Status: No, score=-11.9 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.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This makes the control dependence compute avoid a find_edge and optimizes allocation by embedding the bitmap head into the vector of control dependences instead of allocating all of them. It also uses a local bitmap obstack. The bitmap changes make it necessary to shuffle some includes. Bootstrapped on x86_64-unknown-linux-gnu, testing in progress. 2021-11-10 Richard Biener * cfganal.h (control_dependences::control_dependence_map): Embed bitmap_head. (control_dependences::m_bitmaps): New. * cfganal.c (control_dependences::set_control_dependence_map_bit): Adjust. (control_dependences::clear_control_dependence_bitmap): Likewise. (control_dependences::find_control_dependence): Do not find_edge for the abnormal edge test. (control_dependences::control_dependences): Instead do not add abnormal edges to the edge list. Adjust. (control_dependences::~control_dependences): Likewise. (control_dependences::get_edges_dependent_on): Likewise. * function-tests.c: Include bitmap.h. gcc/analyzer/ * supergraph.cc: Include bitmap.h. gcc/c/ * gimple-parser.c: Shuffle bitmap.h include. --- gcc/analyzer/supergraph.cc | 1 + gcc/c/gimple-parser.c | 2 +- gcc/cfganal.c | 32 ++++++++++++++++++-------------- gcc/cfganal.h | 3 ++- gcc/function-tests.c | 1 + 5 files changed, 23 insertions(+), 16 deletions(-) diff --git a/gcc/analyzer/supergraph.cc b/gcc/analyzer/supergraph.cc index 85acf44d045..be8cec32327 100644 --- a/gcc/analyzer/supergraph.cc +++ b/gcc/analyzer/supergraph.cc @@ -41,6 +41,7 @@ along with GCC; see the file COPYING3. If not see #include "graphviz.h" #include "cgraph.h" #include "tree-dfa.h" +#include "bitmap.h" #include "cfganal.h" #include "function.h" #include "json.h" diff --git a/gcc/c/gimple-parser.c b/gcc/c/gimple-parser.c index f3d99355a8e..32f22dbb8a7 100644 --- a/gcc/c/gimple-parser.c +++ b/gcc/c/gimple-parser.c @@ -56,13 +56,13 @@ along with GCC; see the file COPYING3. If not see #include "internal-fn.h" #include "cfg.h" #include "cfghooks.h" +#include "bitmap.h" #include "cfganal.h" #include "tree-cfg.h" #include "gimple-iterator.h" #include "cfgloop.h" #include "tree-phinodes.h" #include "tree-into-ssa.h" -#include "bitmap.h" /* GIMPLE parser state. */ diff --git a/gcc/cfganal.c b/gcc/cfganal.c index cec5abe30f9..11ab23623ae 100644 --- a/gcc/cfganal.c +++ b/gcc/cfganal.c @@ -362,14 +362,14 @@ control_dependences::set_control_dependence_map_bit (basic_block bb, if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)) return; gcc_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); - bitmap_set_bit (control_dependence_map[bb->index], edge_index); + bitmap_set_bit (&control_dependence_map[bb->index], edge_index); } /* Clear all control dependences for block BB. */ void control_dependences::clear_control_dependence_bitmap (basic_block bb) { - bitmap_clear (control_dependence_map[bb->index]); + bitmap_clear (&control_dependence_map[bb->index]); } /* Find the immediate postdominator PDOM of the specified basic block BLOCK. @@ -402,13 +402,6 @@ control_dependences::find_control_dependence (int edge_index) gcc_assert (get_edge_src (edge_index) != EXIT_BLOCK_PTR_FOR_FN (cfun)); - /* For abnormal edges, we don't make current_block control - dependent because instructions that throw are always necessary - anyway. */ - edge e = find_edge (get_edge_src (edge_index), get_edge_dest (edge_index)); - if (e->flags & EDGE_ABNORMAL) - return; - if (get_edge_src (edge_index) == ENTRY_BLOCK_PTR_FOR_FN (cfun)) ending_block = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)); else @@ -440,11 +433,23 @@ control_dependences::control_dependences () FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) FOR_EACH_EDGE (e, ei, bb->succs) - m_el.quick_push (std::make_pair (e->src->index, e->dest->index)); + { + /* For abnormal edges, we don't make current_block control + dependent because instructions that throw are always necessary + anyway. */ + if (e->flags & EDGE_ABNORMAL) + { + num_edges--; + continue; + } + m_el.quick_push (std::make_pair (e->src->index, e->dest->index)); + } + bitmap_obstack_initialize (&m_bitmaps); control_dependence_map.create (last_basic_block_for_fn (cfun)); + control_dependence_map.quick_grow (last_basic_block_for_fn (cfun)); for (int i = 0; i < last_basic_block_for_fn (cfun); ++i) - control_dependence_map.quick_push (BITMAP_ALLOC (NULL)); + bitmap_initialize (&control_dependence_map[i], &m_bitmaps); for (int i = 0; i < num_edges; ++i) find_control_dependence (i); @@ -455,10 +460,9 @@ control_dependences::control_dependences () control_dependences::~control_dependences () { - for (unsigned i = 0; i < control_dependence_map.length (); ++i) - BITMAP_FREE (control_dependence_map[i]); control_dependence_map.release (); m_el.release (); + bitmap_obstack_release (&m_bitmaps); } /* Returns the bitmap of edges the basic-block I is dependent on. */ @@ -466,7 +470,7 @@ control_dependences::~control_dependences () bitmap control_dependences::get_edges_dependent_on (int i) { - return control_dependence_map[i]; + return &control_dependence_map[i]; } /* Returns the edge source with index I from the edge list. */ diff --git a/gcc/cfganal.h b/gcc/cfganal.h index 31ce56ca40c..7ef4319bf1d 100644 --- a/gcc/cfganal.h +++ b/gcc/cfganal.h @@ -44,8 +44,9 @@ private: void set_control_dependence_map_bit (basic_block, int); void clear_control_dependence_bitmap (basic_block); void find_control_dependence (int); - vec control_dependence_map; + vec control_dependence_map; vec > m_el; + bitmap_obstack m_bitmaps; }; extern bool mark_dfs_back_edges (void); diff --git a/gcc/function-tests.c b/gcc/function-tests.c index 0ac1d37f8ff..83020498e48 100644 --- a/gcc/function-tests.c +++ b/gcc/function-tests.c @@ -42,6 +42,7 @@ along with GCC; see the file COPYING3. If not see #include "function.h" #include "dominance.h" #include "cfg.h" +#include "bitmap.h" #include "cfganal.h" #include "basic-block.h" #include "tree-ssa-alias.h"