From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id E4ABF3838036 for ; Tue, 8 Jun 2021 14:54:36 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E4ABF3838036 Received: from mail-qt1-f197.google.com (mail-qt1-f197.google.com [209.85.160.197]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-487-axuxbIFANJuc0rICpGqTGQ-1; Tue, 08 Jun 2021 10:54:34 -0400 X-MC-Unique: axuxbIFANJuc0rICpGqTGQ-1 Received: by mail-qt1-f197.google.com with SMTP id f17-20020ac87f110000b02901e117339ea7so9506906qtk.16 for ; Tue, 08 Jun 2021 07:54:34 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:to:cc:from:subject:message-id:date:user-agent :mime-version:content-language; bh=GKEm4bMtfq38+ASqSX7kd0oIPkCZffSlihsDm9gWYsE=; b=JghR3EIMNIQJvF1QRSYg72TMOUv+zUQofQgW0cK3iTJRMoqtXg4HEzOWA6JZgYV43r X/pSiRtoH5v1V/+sVTPmiWHJHP7/lVKHpUuHAmxkmyGrPhH8ky9JU8fPjGJ1e9kMsWyo l3LliTu523zkMpnWleBCtIW9JNo+fYk/RWOyOsCt4SDcvIafoOiGJoNCffY2i/ZnhvEs dw1hZDBY2ImvRncnri84xZlAM9s0EM1sO4FDqtwaE2CPRRcTWJWXT/+tX2sZ4CimxTVI jX00+LaCb80Yt8TthW42xQSO0+ZesKX1iNbgg827Abptw6KOtZQt0LjVer9MV0HMRWmF PWKw== X-Gm-Message-State: AOAM53388O5la88Em9iLofGRQ9UVK7WLDisdCaSYdq3Wq6ma1QkizORe P3yo88syg1CreshN/YFLpn1dzffJGiwvRsiuYMOgxGsNyScDSznHUAXfFTWEW8skCIODUlEXJSx v/LelNDxqidZnzp31Fw== X-Received: by 2002:a05:620a:c8b:: with SMTP id q11mr7831564qki.101.1623164073759; Tue, 08 Jun 2021 07:54:33 -0700 (PDT) X-Google-Smtp-Source: ABdhPJz6LYc/FgB51HznblxG0TdGFRCZABUQrSJfuVSUFsUKjIhq36FrKUnTyZZA2lWNIw+9bmsCKg== X-Received: by 2002:a05:620a:c8b:: with SMTP id q11mr7831551qki.101.1623164073609; Tue, 08 Jun 2021 07:54:33 -0700 (PDT) Received: from ?IPv6:2607:fea8:a25d:e700::1b2a? ([2607:fea8:a25d:e700::1b2a]) by smtp.gmail.com with ESMTPSA id g15sm469417qtx.75.2021.06.08.07.54.32 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 08 Jun 2021 07:54:33 -0700 (PDT) To: gcc-patches Cc: Richard Biener , Jakub Jelinek From: Andrew MacLeod Subject: [PATCH] [GCC 11] tree-optimization/100299 - Cherry picked solution from trunk Message-ID: <227d4948-856f-1ea8-f769-f3375b0a4e5f@redhat.com> Date: Tue, 8 Jun 2021 10:54:31 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.10.0 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: multipart/mixed; boundary="------------8CF5A4FF53F137556A29C85B" Content-Language: en-CA X-Spam-Status: No, score=-11.0 required=5.0 tests=BAYES_00, DKIM_INVALID, DKIM_SIGNED, GIT_PATCH_0, KAM_ASCII_DIVIDERS, KAM_DMARC_STATUS, KAM_LOTSOFHASH, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) 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-List-Received-Date: Tue, 08 Jun 2021 14:54:40 -0000 This is a multi-part message in MIME format. --------------8CF5A4FF53F137556A29C85B Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit The 2 recent patches, plus the original abstraction patch can be simply cherry picked for gcc 11. I have applied the 3 patches to the current gcc 11 release, and it bootstrapped with no regressions on x86_64-pc-linux-gnu. Andrew --------------8CF5A4FF53F137556A29C85B Content-Type: text/x-patch; charset=UTF-8; name="0001-Clean-up-and-virtualize-the-on-entry-cache-interface.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0001-Clean-up-and-virtualize-the-on-entry-cache-interface.pa"; filename*1="tch" >From 58289b678064c4b4e1efeb806f78c42d86ae31a4 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Fri, 7 May 2021 12:03:01 -0400 Subject: [PATCH 1/4] Clean up and virtualize the on-entry cache interface. Cleanup/Virtualize the ssa_block_range class, and implement the current vector approach as a derived class. Allow memory allocation from the irange allocator obstack for easy freeing. * gimple-range-cache.cc (ssa_block_ranges): Virtualize. (sbr_vector): Renamed from ssa_block_cache. (sbr_vector::sbr_vector): Allocate from obstack abd initialize. (ssa_block_ranges::~ssa_block_ranges): Remove. (sbr_vector::set_bb_range): Use varying and undefined cached values. (ssa_block_ranges::set_bb_varying): Remove. (sbr_vector::get_bb_range): Adjust assert. (sbr_vector::bb_range_p): Adjust assert. (~block_range_cache): No freeing loop required. (block_range_cache::get_block_ranges): Remove. (block_range_cache::set_bb_range): Inline get_block_ranges. (block_range_cache::set_bb_varying): Remove. * gimple-range-cache.h (set_bb_varying): Remove prototype. * value-range.h (irange_allocator::get_memory): New. (cherry picked from commit 14b0f37a644d7b59e1737fb275ec4fff044972a8) --- gcc/gimple-range-cache.cc | 165 ++++++++++++++++---------------------- gcc/gimple-range-cache.h | 1 - gcc/value-range.h | 9 +++ 3 files changed, 80 insertions(+), 95 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 38e4fe1c7c0..2be83d698ab 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -107,29 +107,53 @@ non_null_ref::process_name (tree name) // ------------------------------------------------------------------------- -// This class implements a cache of ranges indexed by basic block. It -// represents all that is known about an SSA_NAME on entry to each -// block. It caches a range-for-type varying range so it doesn't need -// to be reformed all the time. If a range is ever always associated -// with a type, we can use that instead. Whenever varying is being -// set for a block, the cache simply points to this cached one rather -// than create a new one each time. +// This class represents the API into a cache of ranges for an SSA_NAME. +// Routines must be implemented to set, get, and query if a value is set. class ssa_block_ranges { public: - ssa_block_ranges (tree t, irange_allocator *allocator); - ~ssa_block_ranges (); - - void set_bb_range (const basic_block bb, const irange &r); - void set_bb_varying (const basic_block bb); - bool get_bb_range (irange &r, const basic_block bb); - bool bb_range_p (const basic_block bb); + virtual void set_bb_range (const basic_block bb, const irange &r) = 0; + virtual bool get_bb_range (irange &r, const basic_block bb) = 0; + virtual bool bb_range_p (const basic_block bb) = 0; void dump(FILE *f); -private: - vec m_tab; - irange *m_type_range; +}; + +// Print the list of known ranges for file F in a nice format. + +void +ssa_block_ranges::dump (FILE *f) +{ + basic_block bb; + int_range_max r; + + FOR_EACH_BB_FN (bb, cfun) + if (get_bb_range (r, bb)) + { + fprintf (f, "BB%d -> ", bb->index); + r.dump (f); + fprintf (f, "\n"); + } +} + +// This class implements the range cache as a linear vector, indexed by BB. +// It caches a varying and undefined range which are used instead of +// allocating new ones each time. + +class sbr_vector : public ssa_block_ranges +{ +public: + sbr_vector (tree t, irange_allocator *allocator); + + virtual void set_bb_range (const basic_block bb, const irange &r) OVERRIDE; + virtual bool get_bb_range (irange &r, const basic_block bb) OVERRIDE; + virtual bool bb_range_p (const basic_block bb) OVERRIDE; +protected: + irange **m_tab; // Non growing vector. + int m_tab_size; + int_range<2> m_varying; + int_range<2> m_undefined; tree m_type; irange_allocator *m_irange_allocator; }; @@ -137,55 +161,43 @@ private: // Initialize a block cache for an ssa_name of type T. -ssa_block_ranges::ssa_block_ranges (tree t, irange_allocator *allocator) +sbr_vector::sbr_vector (tree t, irange_allocator *allocator) { gcc_checking_assert (TYPE_P (t)); m_type = t; m_irange_allocator = allocator; - - m_tab.create (0); - m_tab.safe_grow_cleared (last_basic_block_for_fn (cfun)); + m_tab_size = last_basic_block_for_fn (cfun) + 1; + m_tab = (irange **)allocator->get_memory (m_tab_size * sizeof (irange *)); + memset (m_tab, 0, m_tab_size * sizeof (irange *)); // Create the cached type range. - m_type_range = m_irange_allocator->allocate (2); - m_type_range->set_varying (t); - - m_tab[ENTRY_BLOCK_PTR_FOR_FN (cfun)->index] = m_type_range; -} - -// Destruct block range. - -ssa_block_ranges::~ssa_block_ranges () -{ - m_tab.release (); + m_varying.set_varying (t); + m_undefined.set_undefined (); } // Set the range for block BB to be R. void -ssa_block_ranges::set_bb_range (const basic_block bb, const irange &r) +sbr_vector::set_bb_range (const basic_block bb, const irange &r) { - gcc_checking_assert ((unsigned) bb->index < m_tab.length ()); - irange *m = m_irange_allocator->allocate (r); + irange *m; + gcc_checking_assert (bb->index < m_tab_size); + if (r.varying_p ()) + m = &m_varying; + else if (r.undefined_p ()) + m = &m_undefined; + else + m = m_irange_allocator->allocate (r); m_tab[bb->index] = m; } -// Set the range for block BB to the range for the type. - -void -ssa_block_ranges::set_bb_varying (const basic_block bb) -{ - gcc_checking_assert ((unsigned) bb->index < m_tab.length ()); - m_tab[bb->index] = m_type_range; -} - // Return the range associated with block BB in R. Return false if // there is no range. bool -ssa_block_ranges::get_bb_range (irange &r, const basic_block bb) +sbr_vector::get_bb_range (irange &r, const basic_block bb) { - gcc_checking_assert ((unsigned) bb->index < m_tab.length ()); + gcc_checking_assert (bb->index < m_tab_size); irange *m = m_tab[bb->index]; if (m) { @@ -198,30 +210,12 @@ ssa_block_ranges::get_bb_range (irange &r, const basic_block bb) // Return true if a range is present. bool -ssa_block_ranges::bb_range_p (const basic_block bb) +sbr_vector::bb_range_p (const basic_block bb) { - gcc_checking_assert ((unsigned) bb->index < m_tab.length ()); + gcc_checking_assert (bb->index < m_tab_size); return m_tab[bb->index] != NULL; } - -// Print the list of known ranges for file F in a nice format. - -void -ssa_block_ranges::dump (FILE *f) -{ - basic_block bb; - int_range_max r; - - FOR_EACH_BB_FN (bb, cfun) - if (get_bb_range (r, bb)) - { - fprintf (f, "BB%d -> ", bb->index); - r.dump (f); - fprintf (f, "\n"); - } -} - // ------------------------------------------------------------------------- // Initialize the block cache. @@ -237,38 +231,36 @@ block_range_cache::block_range_cache () block_range_cache::~block_range_cache () { - unsigned x; - for (x = 0; x < m_ssa_ranges.length (); ++x) - { - if (m_ssa_ranges[x]) - delete m_ssa_ranges[x]; - } delete m_irange_allocator; // Release the vector itself. m_ssa_ranges.release (); } -// Return a reference to the ssa_block_cache for NAME. If it has not been -// accessed yet, allocate it first. +// Set the range for NAME on entry to block BB to R. +// If it has not been // accessed yet, allocate it first. -ssa_block_ranges & -block_range_cache::get_block_ranges (tree name) +void +block_range_cache::set_bb_range (tree name, const basic_block bb, + const irange &r) { unsigned v = SSA_NAME_VERSION (name); if (v >= m_ssa_ranges.length ()) m_ssa_ranges.safe_grow_cleared (num_ssa_names + 1); if (!m_ssa_ranges[v]) - m_ssa_ranges[v] = new ssa_block_ranges (TREE_TYPE (name), + { + void *r = m_irange_allocator->get_memory (sizeof (sbr_vector)); + m_ssa_ranges[v] = new (r) sbr_vector (TREE_TYPE (name), m_irange_allocator); - return *(m_ssa_ranges[v]); + } + m_ssa_ranges[v]->set_bb_range (bb, r); } // Return a pointer to the ssa_block_cache for NAME. If it has not been // accessed yet, return NULL. -ssa_block_ranges * +inline ssa_block_ranges * block_range_cache::query_block_ranges (tree name) { unsigned v = SSA_NAME_VERSION (name); @@ -277,22 +269,7 @@ block_range_cache::query_block_ranges (tree name) return m_ssa_ranges[v]; } -// Set the range for NAME on entry to block BB to R. -void -block_range_cache::set_bb_range (tree name, const basic_block bb, - const irange &r) -{ - return get_block_ranges (name).set_bb_range (bb, r); -} - -// Set the range for NAME on entry to block BB to varying. - -void -block_range_cache::set_bb_varying (tree name, const basic_block bb) -{ - return get_block_ranges (name).set_bb_varying (bb); -} // Return the range for NAME on entry to BB in R. Return true if there // is one. diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index 2b36a02654b..bccb5cc2442 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -51,7 +51,6 @@ public: ~block_range_cache (); void set_bb_range (tree name, const basic_block bb, const irange &r); - void set_bb_varying (tree name, const basic_block bb); bool get_bb_range (irange &r, tree name, const basic_block bb); bool bb_range_p (tree name, const basic_block bb); diff --git a/gcc/value-range.h b/gcc/value-range.h index bfc54a2473f..54623b97a1f 100644 --- a/gcc/value-range.h +++ b/gcc/value-range.h @@ -639,6 +639,7 @@ public: // Return a copy of SRC with the minimum amount of sub-ranges needed // to represent it. irange *allocate (const irange &src); + void *get_memory (unsigned num_bytes); private: DISABLE_COPY_AND_ASSIGN (irange_allocator); struct obstack m_obstack; @@ -656,6 +657,14 @@ irange_allocator::~irange_allocator () obstack_free (&m_obstack, NULL); } +// Provide a hunk of memory from the obstack +inline void * +irange_allocator::get_memory (unsigned num_bytes) +{ + void *r = obstack_alloc (&m_obstack, num_bytes); + return r; +} + // Return a new range with NUM_PAIRS. inline irange * -- 2.25.4 --------------8CF5A4FF53F137556A29C85B Content-Type: text/x-patch; charset=UTF-8; name="0002-Implement-multi-bit-aligned-accessors-for-sparse-bit.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0002-Implement-multi-bit-aligned-accessors-for-sparse-bit.pa"; filename*1="tch" >From e65205de9c7302a2a7d903ba8703461009cdacda Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Mon, 7 Jun 2021 13:12:01 -0400 Subject: [PATCH 2/4] Implement multi-bit aligned accessors for sparse bitmap. Provide set/get routines to allow sparse bitmaps to be treated as an array of multiple bit values. Only chunk sizes that are powers of 2 are supported. * bitmap.c (bitmap_set_aligned_chunk): New. (bitmap_get_aligned_chunk): New. (test_aligned_chunk): New. (bitmap_c_tests): Call test_aligned_chunk. * bitmap.h (bitmap_set_aligned_chunk, bitmap_get_aligned_chunk): New. (cherry picked from commit 5ad089a3c946aec655436fa3b0b50d6574b78197) --- gcc/bitmap.c | 108 +++++++++++++++++++++++++++++++++++++++++++++++++++ gcc/bitmap.h | 7 ++++ 2 files changed, 115 insertions(+) diff --git a/gcc/bitmap.c b/gcc/bitmap.c index 5a650cdfc1d..b915fdfbb54 100644 --- a/gcc/bitmap.c +++ b/gcc/bitmap.c @@ -1004,6 +1004,83 @@ bitmap_bit_p (const_bitmap head, int bit) return (ptr->bits[word_num] >> bit_num) & 1; } +/* Set CHUNK_SIZE bits at a time in bitmap HEAD. + Store CHUNK_VALUE starting at bits CHUNK * chunk_size. + This is the set routine for viewing bitmap as a multi-bit sparse array. */ + +void +bitmap_set_aligned_chunk (bitmap head, unsigned int chunk, + unsigned int chunk_size, BITMAP_WORD chunk_value) +{ + // Ensure chunk size is a power of 2 and fits in BITMAP_WORD. + gcc_checking_assert (pow2p_hwi (chunk_size)); + gcc_checking_assert (chunk_size < (sizeof (BITMAP_WORD) * CHAR_BIT)); + + // Ensure chunk_value is within range of chunk_size bits. + BITMAP_WORD max_value = (1 << chunk_size) - 1; + gcc_checking_assert (chunk_value <= max_value); + + unsigned bit = chunk * chunk_size; + unsigned indx = bit / BITMAP_ELEMENT_ALL_BITS; + bitmap_element *ptr; + if (!head->tree_form) + ptr = bitmap_list_find_element (head, indx); + else + ptr = bitmap_tree_find_element (head, indx); + unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; + unsigned bit_num = bit % BITMAP_WORD_BITS; + BITMAP_WORD bit_val = chunk_value << bit_num; + BITMAP_WORD mask = ~(max_value << bit_num); + + if (ptr != 0) + { + ptr->bits[word_num] &= mask; + ptr->bits[word_num] |= bit_val; + return; + } + + ptr = bitmap_element_allocate (head); + ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS; + ptr->bits[word_num] = bit_val; + if (!head->tree_form) + bitmap_list_link_element (head, ptr); + else + bitmap_tree_link_element (head, ptr); +} + +/* This is the get routine for viewing bitmap as a multi-bit sparse array. + Return a set of CHUNK_SIZE consecutive bits from HEAD, starting at bit + CHUNK * chunk_size. */ + +BITMAP_WORD +bitmap_get_aligned_chunk (const_bitmap head, unsigned int chunk, + unsigned int chunk_size) +{ + // Ensure chunk size is a power of 2, fits in BITMAP_WORD and is in range. + gcc_checking_assert (pow2p_hwi (chunk_size)); + gcc_checking_assert (chunk_size < (sizeof (BITMAP_WORD) * CHAR_BIT)); + + BITMAP_WORD max_value = (1 << chunk_size) - 1; + unsigned bit = chunk * chunk_size; + unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS; + const bitmap_element *ptr; + unsigned bit_num; + unsigned word_num; + + if (!head->tree_form) + ptr = bitmap_list_find_element (const_cast (head), indx); + else + ptr = bitmap_tree_find_element (const_cast (head), indx); + if (ptr == 0) + return 0; + + bit_num = bit % BITMAP_WORD_BITS; + word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; + + // Return 4 bits. + return (ptr->bits[word_num] >> bit_num) & max_value; +} + #if GCC_VERSION < 3400 /* Table of number of set bits in a character, indexed by value of char. */ static const unsigned char popcount_table[] = @@ -2857,6 +2934,33 @@ test_bitmap_single_bit_set_p () ASSERT_EQ (1066, bitmap_first_set_bit (b)); } +/* Verify accessing aligned bit chunks works as expected. */ + +static void +test_aligned_chunk (unsigned num_bits) +{ + bitmap b = bitmap_gc_alloc (); + int limit = 2 ^ num_bits; + + int index = 3; + for (int x = 0; x < limit; x++) + { + bitmap_set_aligned_chunk (b, index, num_bits, (BITMAP_WORD) x); + ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index, num_bits) == x); + ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index + 1, + num_bits) == 0); + ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index - 1, + num_bits) == 0); + index += 3; + } + index = 3; + for (int x = 0; x < limit ; x++) + { + ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index, num_bits) == x); + index += 3; + } +} + /* Run all of the selftests within this file. */ void @@ -2867,6 +2971,10 @@ bitmap_c_tests () test_clear_bit_in_middle (); test_copying (); test_bitmap_single_bit_set_p (); + /* Test 2, 4 and 8 bit aligned chunks. */ + test_aligned_chunk (2); + test_aligned_chunk (4); + test_aligned_chunk (8); } } // namespace selftest diff --git a/gcc/bitmap.h b/gcc/bitmap.h index 84632af7009..c9fd8af49d8 100644 --- a/gcc/bitmap.h +++ b/gcc/bitmap.h @@ -438,6 +438,13 @@ extern bool bitmap_set_bit (bitmap, int); /* Return true if a bit is set in a bitmap. */ extern int bitmap_bit_p (const_bitmap, int); +/* Set and get multiple bit values in a sparse bitmap. This allows a bitmap to + function as a sparse array of bit patterns where the patterns are + multiples of power of 2. This is more efficient than performing this as + multiple individual operations. */ +void bitmap_set_aligned_chunk (bitmap, unsigned int, unsigned int, BITMAP_WORD); +BITMAP_WORD bitmap_get_aligned_chunk (const_bitmap, unsigned int, unsigned int); + /* Debug functions to print a bitmap. */ extern void debug_bitmap (const_bitmap); extern void debug_bitmap_file (FILE *, const_bitmap); -- 2.25.4 --------------8CF5A4FF53F137556A29C85B Content-Type: text/x-patch; charset=UTF-8; name="0003-Implement-a-sparse-bitmap-representation-for-Rangers.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0003-Implement-a-sparse-bitmap-representation-for-Rangers.pa"; filename*1="tch" >From ec7a3bd4136639379666923573108146df024a19 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Mon, 7 Jun 2021 13:18:55 -0400 Subject: [PATCH 3/4] Implement a sparse bitmap representation for Rangers on-entry cache. Use a sparse representation for the on entry cache, and utilize it when the number of basic blocks in the function exceeds param_evrp_sparse_threshold. PR tree-optimization/PR100299 * gimple-range-cache.cc (class sbr_sparse_bitmap): New. (sbr_sparse_bitmap::sbr_sparse_bitmap): New. (sbr_sparse_bitmap::bitmap_set_quad): New. (sbr_sparse_bitmap::bitmap_get_quad): New. (sbr_sparse_bitmap::set_bb_range): New. (sbr_sparse_bitmap::get_bb_range): New. (sbr_sparse_bitmap::bb_range_p): New. (block_range_cache::block_range_cache): initialize bitmap obstack. (block_range_cache::~block_range_cache): Destruct obstack. (block_range_cache::set_bb_range): Decide when to utilze the sparse on entry cache. * gimple-range-cache.h (block_range_cache): Add bitmap obstack. * params.opt (-param=evrp-sparse-threshold): New. (cherry picked from commit 9858cd1a6827ee7a928318acb5e86389f79b4012) --- gcc/gimple-range-cache.cc | 147 +++++++++++++++++++++++++++++++++++++- gcc/gimple-range-cache.h | 1 + gcc/params.opt | 4 ++ 3 files changed, 149 insertions(+), 3 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 2be83d698ab..bc4b557b493 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -216,12 +216,140 @@ sbr_vector::bb_range_p (const basic_block bb) return m_tab[bb->index] != NULL; } +// This class implements the on entry cache via a sparse bitmap. +// It uses the quad bit routines to access 4 bits at a time. +// A value of 0 (the default) means there is no entry, and a value of +// 1 thru SBR_NUM represents an element in the m_range vector. +// Varying is given the first value (1) and pre-cached. +// SBR_NUM + 1 represents the value of UNDEFINED, and is never stored. +// SBR_NUM is the number of values that can be cached. +// Indexes are 1..SBR_NUM and are stored locally at m_range[0..SBR_NUM-1] + +#define SBR_NUM 14 +#define SBR_UNDEF SBR_NUM + 1 +#define SBR_VARYING 1 + +class sbr_sparse_bitmap : public ssa_block_ranges +{ +public: + sbr_sparse_bitmap (tree t, irange_allocator *allocator, bitmap_obstack *bm); + virtual void set_bb_range (const basic_block bb, const irange &r) OVERRIDE; + virtual bool get_bb_range (irange &r, const basic_block bb) OVERRIDE; + virtual bool bb_range_p (const basic_block bb) OVERRIDE; +private: + void bitmap_set_quad (bitmap head, int quad, int quad_value); + int bitmap_get_quad (const_bitmap head, int quad); + irange_allocator *m_irange_allocator; + irange *m_range[SBR_NUM]; + bitmap bitvec; + tree m_type; +}; + +// Initialize a block cache for an ssa_name of type T. + +sbr_sparse_bitmap::sbr_sparse_bitmap (tree t, irange_allocator *allocator, + bitmap_obstack *bm) +{ + gcc_checking_assert (TYPE_P (t)); + m_type = t; + bitvec = BITMAP_ALLOC (bm); + m_irange_allocator = allocator; + // Pre-cache varying. + m_range[0] = m_irange_allocator->allocate (2); + m_range[0]->set_varying (t); + // Pre-cache zero and non-zero values for pointers. + if (POINTER_TYPE_P (t)) + { + m_range[1] = m_irange_allocator->allocate (2); + m_range[1]->set_nonzero (t); + m_range[2] = m_irange_allocator->allocate (2); + m_range[2]->set_zero (t); + } + else + m_range[1] = m_range[2] = NULL; + // Clear SBR_NUM entries. + for (int x = 3; x < SBR_NUM; x++) + m_range[x] = 0; +} + +// Set 4 bit values in a sparse bitmap. This allows a bitmap to +// function as a sparse array of 4 bit values. +// QUAD is the index, QUAD_VALUE is the 4 bit value to set. + +inline void +sbr_sparse_bitmap::bitmap_set_quad (bitmap head, int quad, int quad_value) +{ + bitmap_set_aligned_chunk (head, quad, 4, (BITMAP_WORD) quad_value); +} + +// Get a 4 bit value from a sparse bitmap. This allows a bitmap to +// function as a sparse array of 4 bit values. +// QUAD is the index. +inline int +sbr_sparse_bitmap::bitmap_get_quad (const_bitmap head, int quad) +{ + return (int) bitmap_get_aligned_chunk (head, quad, 4); +} + +// Set the range on entry to basic block BB to R. + +void +sbr_sparse_bitmap::set_bb_range (const basic_block bb, const irange &r) +{ + if (r.undefined_p ()) + { + bitmap_set_quad (bitvec, bb->index, SBR_UNDEF); + return; + } + + // Loop thru the values to see if R is already present. + for (int x = 0; x < SBR_NUM; x++) + if (!m_range[x] || r == *(m_range[x])) + { + if (!m_range[x]) + m_range[x] = m_irange_allocator->allocate (r); + bitmap_set_quad (bitvec, bb->index, x + 1); + return; + } + // All values are taken, default to VARYING. + bitmap_set_quad (bitvec, bb->index, SBR_VARYING); + return; +} + +// Return the range associated with block BB in R. Return false if +// there is no range. + +bool +sbr_sparse_bitmap::get_bb_range (irange &r, const basic_block bb) +{ + int value = bitmap_get_quad (bitvec, bb->index); + + if (!value) + return false; + + gcc_checking_assert (value <= SBR_UNDEF); + if (value == SBR_UNDEF) + r.set_undefined (); + else + r = *(m_range[value - 1]); + return true; +} + +// Return true if a range is present. + +bool +sbr_sparse_bitmap::bb_range_p (const basic_block bb) +{ + return (bitmap_get_quad (bitvec, bb->index) != 0); +} + // ------------------------------------------------------------------------- // Initialize the block cache. block_range_cache::block_range_cache () { + bitmap_obstack_initialize (&m_bitmaps); m_ssa_ranges.create (0); m_ssa_ranges.safe_grow_cleared (num_ssa_names); m_irange_allocator = new irange_allocator; @@ -234,6 +362,7 @@ block_range_cache::~block_range_cache () delete m_irange_allocator; // Release the vector itself. m_ssa_ranges.release (); + bitmap_obstack_release (&m_bitmaps); } // Set the range for NAME on entry to block BB to R. @@ -249,9 +378,21 @@ block_range_cache::set_bb_range (tree name, const basic_block bb, if (!m_ssa_ranges[v]) { - void *r = m_irange_allocator->get_memory (sizeof (sbr_vector)); - m_ssa_ranges[v] = new (r) sbr_vector (TREE_TYPE (name), - m_irange_allocator); + // Use sparse representation if there are too many basic blocks. + if (last_basic_block_for_fn (cfun) > param_evrp_sparse_threshold) + { + void *r = m_irange_allocator->get_memory (sizeof (sbr_sparse_bitmap)); + m_ssa_ranges[v] = new (r) sbr_sparse_bitmap (TREE_TYPE (name), + m_irange_allocator, + &m_bitmaps); + } + else + { + // Otherwise use the default vector implemntation. + void *r = m_irange_allocator->get_memory (sizeof (sbr_vector)); + m_ssa_ranges[v] = new (r) sbr_vector (TREE_TYPE (name), + m_irange_allocator); + } } m_ssa_ranges[v]->set_bb_range (bb, r); } diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index bccb5cc2442..43e576a51f9 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -61,6 +61,7 @@ private: ssa_block_ranges &get_block_ranges (tree name); ssa_block_ranges *query_block_ranges (tree name); irange_allocator *m_irange_allocator; + bitmap_obstack m_bitmaps; }; // This global cache is used with the range engine as markers for what diff --git a/gcc/params.opt b/gcc/params.opt index 2e4cbdd7a71..8ba281b4cfa 100644 --- a/gcc/params.opt +++ b/gcc/params.opt @@ -126,6 +126,10 @@ Maximum size (in bytes) of objects tracked bytewise by dead store elimination. Common Joined UInteger Var(param_early_inlining_insns) Init(6) Optimization Param Maximal estimated growth of function body caused by early inlining of single call. +-param=evrp-sparse-threshold= +Common Joined UInteger Var(param_evrp_sparse_threshold) Init(800) Optimization Param +Maximum number of basic blocks before EVRP uses a sparse cache. + -param=evrp-mode= Common Joined Var(param_evrp_mode) Enum(evrp_mode) Init(EVRP_MODE_EVRP_FIRST) Param Optimization --param=evrp-mode=[legacy|ranger|legacy-first|ranger-first|ranger-trace|ranger-debug|trace|debug] Specifies the mode Early VRP should operate in. -- 2.25.4 --------------8CF5A4FF53F137556A29C85B--