From patchwork Fri Nov 5 17:17:09 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1551481 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=VsTbHE90; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (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 4Hm6fw2px5z9s1l for ; Sat, 6 Nov 2021 04:18:48 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id EA70B3858014 for ; Fri, 5 Nov 2021 17:18:44 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org EA70B3858014 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1636132725; bh=MMpLT3sal9KeOzNN7FQ6p307N3AGeDDyq350mRbApbM=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=VsTbHE90t/Tq2cNikwy7cVaIosWrqjtuuIheas3FAVYtUGHbXCmZHiK+vvGWrSh+i R+k4NHrwr9cVIPxK1fPUhQ31pIaHf3ojB6b5ohAxVWmkV1xfSGfzeHrJIL5/RG9gcC n9XIqdW3xXHkFr59jNTwyo9gRmzk1FxpO0L0NDQE= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [216.205.24.124]) by sourceware.org (Postfix) with ESMTPS id C63C63858412 for ; Fri, 5 Nov 2021 17:17:23 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org C63C63858412 Received: from mail-qt1-f200.google.com (mail-qt1-f200.google.com [209.85.160.200]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-423-YDlfAtEDPDaQ18EF9iBsvg-1; Fri, 05 Nov 2021 13:17:22 -0400 X-MC-Unique: YDlfAtEDPDaQ18EF9iBsvg-1 Received: by mail-qt1-f200.google.com with SMTP id 13-20020ac8560d000000b0029f69548889so6447265qtr.3 for ; Fri, 05 Nov 2021 10:17:21 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:to:cc:from:subject:message-id:date:user-agent :mime-version:content-language; bh=MMpLT3sal9KeOzNN7FQ6p307N3AGeDDyq350mRbApbM=; b=QS3JmHHTGOOShbVCxgyeTsHuMWgLHEzQB0PP5HxSO82X4nwzlV9QJUWM90EIIBZ5WC +zuqkS4xL+U6IlrSfy/DOdZeynAcDxHInvG1TJz5hr55GjF3WHN2zmckmXUOoSLYH0Nw NKQzN2uczgFEVKiTLgBldaZ7ZhZt21TWxbi4PS9+uu/5lbBR8h07Sk+hAFPgINj2EPav ejc/AqrEc3k/2iI7Jl1+W/0AzrJ3bgS/7MfQ65pszkuEsX4eIo0ozQemFjNSYW1bK4NX mhqL+YdY600Cbv/Bb53ktrNBmO4UPuaB6vvDcJXpxdu0NswWv1S3bgpuNRnC7YCuloyb iAiA== X-Gm-Message-State: AOAM53003vWeJkHFhwwip86VAK3hi9duhqWM/2KnUURxEC8hG/0K4T4M 9RiY3K/bb4L/UvXpkACLNbOm5oYGq7wj3rDSPnsvW2e2Ve6bVYFyPvRQd54O25ZTG/EE9axjuzH aIQrbB5eYZh5RJqho5g== X-Received: by 2002:ac8:59c2:: with SMTP id f2mr62732701qtf.222.1636132641324; Fri, 05 Nov 2021 10:17:21 -0700 (PDT) X-Google-Smtp-Source: ABdhPJw2EStPCs+DNgY0HIltLRe49NdP7oF5ZmappOUhISmAie3g+bhB6kMOTXWe4gFIleZC5nZpUA== X-Received: by 2002:ac8:59c2:: with SMTP id f2mr62732667qtf.222.1636132641103; Fri, 05 Nov 2021 10:17:21 -0700 (PDT) Received: from ?IPv6:2607:fea8:a262:5f00::e8d1? ([2607:fea8:a262:5f00::e8d1]) by smtp.gmail.com with ESMTPSA id g1sm6420201qtb.7.2021.11.05.10.17.10 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 05 Nov 2021 10:17:12 -0700 (PDT) To: gcc-patches Subject: [COMMITTED] PR tree-optimization/102943 - Abstract ranger cache update list. Message-ID: Date: Fri, 5 Nov 2021 13:17:09 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.14.0 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-12.3 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, 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: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" OK,removing the call to vec::contains() is clearly the right move. Rather than go with the extra bitmap to track whats in the vector, I have done a couple of things.   1 - Abstracted the update list into its own class, making it easier to change the underlying mechaism from a stack to a breadth first queue or whatever else.   2 - Changed the implementation to not use vec::contains, and moved away from using the vector push/pop API. It is now implemented as a single vector over the basic blocks, in which a value of 0 indicates the block is not in the list, and otherwise it points to the next index in the list.  The list is terminated with a -1. m_head points to the head of the list, and -1 if there is no list. empty_p()  is O(1), check if m_head == -1 in_list_p(BB) is O(1),  check is vec[bb] != 0 pop() is O(1), return m_head after vec[bb] = 0, move to the next element, push() is O(1).  if (vec[bb] != 0)  {  vec[bb] = m_head, m_head = bb; } so at the expense of a single vector over BBs, we have an O(1) solution to everything. This provides some nominal improvements over all compilations, and has similar performance characteristics to the bitmap solution. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From 98244c68e77cf75f93b66ee02df059f718c3fbc0 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Thu, 4 Nov 2021 15:08:06 -0400 Subject: [PATCH 1/2] Abstract ranger cache update list. Make it more efficient by removing the call to vec::contains. PR tree-optimization/102943 * gimple-range-cache.cc (class update_list): New. (update_list::add): Replace add_to_update. (update_list::pop): New. (ranger_cache::ranger_cache): Adjust. (ranger_cache::~ranger_cache): Adjust. (ranger_cache::add_to_update): Delete. (ranger_cache::propagate_cache): Adjust to new class. (ranger_cache::propagate_updated_value): Ditto. (ranger_cache::fill_block_cache): Ditto. * gimple-range-cache.h (class ranger_cache): Adjust to update class. --- gcc/gimple-range-cache.cc | 129 +++++++++++++++++++++++++++++--------- gcc/gimple-range-cache.h | 4 +- 2 files changed, 100 insertions(+), 33 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 05010cf15bc..e5591bab0ef 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -754,14 +754,96 @@ temporal_cache::set_always_current (tree name) // -------------------------------------------------------------------------- +// This class provides an abstraction of a list of blocks to be updated +// by the cache. It is currently a stack but could be changed. It also +// maintains a list of blocks which have failed propagation, and does not +// enter any of those blocks into the list. + +// A vector over the BBs is maintained, and an entry of 0 means it is not in +// a list. Otherwise, the entry is the next block in the list. -1 terminates +// the list. m_head points to the top of the list, -1 if the list is empty. + +class update_list +{ +public: + update_list (); + ~update_list (); + void add (basic_block bb); + basic_block pop (); + inline bool empty_p () { return m_update_head == -1; } + inline void clear_failures () { bitmap_clear (m_propfail); } + inline void propagation_failed (basic_block bb) + { bitmap_set_bit (m_propfail, bb->index); } +private: + vec m_update_list; + int m_update_head; + bitmap m_propfail; +}; + +// Create an update list. + +update_list::update_list () +{ + m_update_list.create (0); + m_update_list.safe_grow_cleared (last_basic_block_for_fn (cfun) + 64); + m_update_head = -1; + m_propfail = BITMAP_ALLOC (NULL); +} + +// Destroy an update list. + +update_list::~update_list () +{ + m_update_list.release (); + BITMAP_FREE (m_propfail); +} + +// Add BB to the list of blocks to update, unless it's already in the list. + +void +update_list::add (basic_block bb) +{ + int i = bb->index; + // If propagation has failed for BB, or its already in the list, don't + // add it again. + if ((unsigned)i >= m_update_list.length ()) + m_update_list.safe_grow_cleared (i + 64); + if (!m_update_list[i] && !bitmap_bit_p (m_propfail, i)) + { + if (empty_p ()) + { + m_update_head = i; + m_update_list[i] = -1; + } + else + { + gcc_checking_assert (m_update_head > 0); + m_update_list[i] = m_update_head; + m_update_head = i; + } + } +} + +// Remove a block from the list. + +basic_block +update_list::pop () +{ + gcc_checking_assert (!empty_p ()); + basic_block bb = BASIC_BLOCK_FOR_FN (cfun, m_update_head); + int pop = m_update_head; + m_update_head = m_update_list[pop]; + m_update_list[pop] = 0; + return bb; +} + +// -------------------------------------------------------------------------- + ranger_cache::ranger_cache (int not_executable_flag) : m_gori (not_executable_flag) { m_workback.create (0); m_workback.safe_grow_cleared (last_basic_block_for_fn (cfun)); - m_update_list.create (0); - m_update_list.safe_grow_cleared (last_basic_block_for_fn (cfun)); - m_update_list.truncate (0); m_temporal = new temporal_cache; // If DOM info is available, spawn an oracle as well. if (dom_info_available_p (CDI_DOMINATORS)) @@ -779,17 +861,16 @@ ranger_cache::ranger_cache (int not_executable_flag) if (bb) m_gori.exports (bb); } - m_propfail = BITMAP_ALLOC (NULL); + m_update = new update_list (); } ranger_cache::~ranger_cache () { - BITMAP_FREE (m_propfail); + delete m_update; if (m_oracle) delete m_oracle; delete m_temporal; m_workback.release (); - m_update_list.release (); } // Dump the global caches to file F. if GORI_DUMP is true, dump the @@ -1029,17 +1110,6 @@ ranger_cache::block_range (irange &r, basic_block bb, tree name, bool calc) return m_on_entry.get_bb_range (r, name, bb); } -// Add BB to the list of blocks to update, unless it's already in the list. - -void -ranger_cache::add_to_update (basic_block bb) -{ - // If propagation has failed for BB, or its already in the list, don't - // add it again. - if (!bitmap_bit_p (m_propfail, bb->index) && !m_update_list.contains (bb)) - m_update_list.quick_push (bb); -} - // If there is anything in the propagation update_list, continue // processing NAME until the list of blocks is empty. @@ -1053,16 +1123,15 @@ ranger_cache::propagate_cache (tree name) int_range_max current_range; int_range_max e_range; - gcc_checking_assert (bitmap_empty_p (m_propfail)); // Process each block by seeing if its calculated range on entry is // the same as its cached value. If there is a difference, update // the cache to reflect the new value, and check to see if any // successors have cache entries which may need to be checked for // updates. - while (m_update_list.length () > 0) + while (!m_update->empty_p ()) { - bb = m_update_list.pop (); + bb = m_update->pop (); gcc_checking_assert (m_on_entry.bb_range_p (name, bb)); m_on_entry.get_bb_range (current_range, name, bb); @@ -1097,7 +1166,7 @@ ranger_cache::propagate_cache (tree name) bool ok_p = m_on_entry.set_bb_range (name, bb, new_range); // If the cache couldn't set the value, mark it as failed. if (!ok_p) - bitmap_set_bit (m_propfail, bb->index); + m_update->propagation_failed (bb); if (DEBUG_RANGE_CACHE) { if (!ok_p) @@ -1119,7 +1188,7 @@ ranger_cache::propagate_cache (tree name) { if (DEBUG_RANGE_CACHE) fprintf (dump_file, " bb%d",e->dest->index); - add_to_update (e->dest); + m_update->add (e->dest); } if (DEBUG_RANGE_CACHE) fprintf (dump_file, "\n"); @@ -1131,7 +1200,7 @@ ranger_cache::propagate_cache (tree name) print_generic_expr (dump_file, name, TDF_SLIM); fprintf (dump_file, "\n"); } - bitmap_clear (m_propfail); + m_update->clear_failures (); } // Check to see if an update to the value for NAME in BB has any effect @@ -1146,7 +1215,7 @@ ranger_cache::propagate_updated_value (tree name, basic_block bb) edge_iterator ei; // The update work list should be empty at this point. - gcc_checking_assert (m_update_list.length () == 0); + gcc_checking_assert (m_update->empty_p ()); gcc_checking_assert (bb); if (DEBUG_RANGE_CACHE) @@ -1160,12 +1229,12 @@ ranger_cache::propagate_updated_value (tree name, basic_block bb) // Only update active cache entries. if (m_on_entry.bb_range_p (name, e->dest)) { - add_to_update (e->dest); + m_update->add (e->dest); if (DEBUG_RANGE_CACHE) fprintf (dump_file, " UPDATE: bb%d", e->dest->index); } } - if (m_update_list.length () != 0) + if (!m_update->empty_p ()) { if (DEBUG_RANGE_CACHE) fprintf (dump_file, "\n"); @@ -1205,7 +1274,7 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) m_workback.quick_push (bb); undefined.set_undefined (); m_on_entry.set_bb_range (name, bb, undefined); - gcc_checking_assert (m_update_list.length () == 0); + gcc_checking_assert (m_update->empty_p ()); if (DEBUG_RANGE_CACHE) { @@ -1235,7 +1304,7 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) // If the pred block is the def block add this BB to update list. if (pred == def_bb) { - add_to_update (node); + m_update->add (node); continue; } @@ -1255,7 +1324,7 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) { if (DEBUG_RANGE_CACHE) fprintf (dump_file, "nonnull: update "); - add_to_update (node); + m_update->add (node); } // If the pred block already has a range, or if it can contribute @@ -1270,7 +1339,7 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) } if (!r.undefined_p () || m_gori.has_edge_range_p (name, e)) { - add_to_update (node); + m_update->add (node); if (DEBUG_RANGE_CACHE) fprintf (dump_file, "update. "); } diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index 75105008338..49c13d1e85f 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -114,7 +114,6 @@ private: ssa_global_cache m_globals; block_range_cache m_on_entry; class temporal_cache *m_temporal; - void add_to_update (basic_block bb); void fill_block_cache (tree name, basic_block bb, basic_block def_bb); void propagate_cache (tree name); @@ -122,9 +121,8 @@ private: void entry_range (irange &r, tree expr, basic_block bb); void exit_range (irange &r, tree expr, basic_block bb); - bitmap m_propfail; vec m_workback; - vec m_update_list; + class update_list *m_update; }; #endif // GCC_SSA_RANGE_CACHE_H -- 2.17.2