From patchwork Mon Jun 7 21:35:26 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1489005 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org 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=) Authentication-Results: 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=TT2hifSj; dkim-atps=neutral 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 ozlabs.org (Postfix) with ESMTPS id 4FzRWT0v9bz9sSn for ; Tue, 8 Jun 2021 07:36:03 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id B2DF03939C2A for ; Mon, 7 Jun 2021 21:36:01 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B2DF03939C2A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1623101761; bh=PNCHNRkvtug9Nk75C7YLJ9p1vSIcx+RG2YEQ1dLfLew=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=TT2hifSjs66YzeKQVtIKSq6FAhrHL73tQQ2YgTvxlAl4Bb0j8lLXE4auJtbH9gNxb bn+7tA8TEjRo1RvOszIRrn/Sqety/3/7eA/exO0ZXOgfcK0i/w1nBjAo0WyodEScro JOnJK5y5DjCpGmOt7eRswBBYCyBLor0Lc3SQs0lk= 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 ESMTP id CE299382E832 for ; Mon, 7 Jun 2021 21:35:30 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org CE299382E832 Received: from mail-qv1-f69.google.com (mail-qv1-f69.google.com [209.85.219.69]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-527-Fnj-CNRlO3aSt8TJqmWHMw-1; Mon, 07 Jun 2021 17:35:28 -0400 X-MC-Unique: Fnj-CNRlO3aSt8TJqmWHMw-1 Received: by mail-qv1-f69.google.com with SMTP id n17-20020ad444b10000b02902157677ec50so14085265qvt.12 for ; Mon, 07 Jun 2021 14:35:28 -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=PNCHNRkvtug9Nk75C7YLJ9p1vSIcx+RG2YEQ1dLfLew=; b=XTHxQ9mR2R+IuBlTix6w5nixpn2RusqxewP3wUcoGT1pvGYexOqui6opzdPOJdjJ7E cSq/9KrNKMy1rR9iOpjiEVn+LnoO8C6MdCAnwtdnQkgt8q1UM2u6gAaiJNxkZOOom0cM BczgKHybyquIZFMMuC7F6MjNefgGPMv4kicfI5OaGZxg/lnmBBkEsuUcqJ6fKucCzDCy d5can2lRgbFpWyAVbnQqQSMi0ASbI8YfjfIfSTAP1b3cBb2fAKmPUmtw8UuvOgCBIkqU awepZ7y6MbJOIIYodSiG2DSF2bUKTiU3tlg/yVuXv+OgNrHU+Lmb7OZqsGTdiJZ0RrVZ iPTQ== X-Gm-Message-State: AOAM5303l9qFuFuakNCcuwD8MmFO0LIAjNb0oEzPpgDn+R2040Bcv4kX ml6Zrla0H4TGWZHpFeUV28XnIEhCM3UcXZA7Gux4BURiQ6B4ggYvQBWpmTuDAtslb4qXck+fVav CD6TUGEP7JsMSKoBHHQ== X-Received: by 2002:ac8:5793:: with SMTP id v19mr18560162qta.257.1623101728334; Mon, 07 Jun 2021 14:35:28 -0700 (PDT) X-Google-Smtp-Source: ABdhPJwiIHjPr1kdhRATho/SAMp2HGpZdOqmFa9huXBviSAa158/xB3m0ZPv/brbxeXJx+VTWj+mNw== X-Received: by 2002:ac8:5793:: with SMTP id v19mr18560152qta.257.1623101728169; Mon, 07 Jun 2021 14:35:28 -0700 (PDT) Received: from ?IPv6:2607:fea8:a25d:e700::1b2a? ([2607:fea8:a25d:e700::1b2a]) by smtp.gmail.com with ESMTPSA id e12sm9889328qtj.48.2021.06.07.14.35.27 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 07 Jun 2021 14:35:27 -0700 (PDT) To: gcc-patches Subject: [PATCH] PR tree-optimization/100299 - Implement a sparse bitmap representation for Rangers on-entry cache. Message-ID: Date: Mon, 7 Jun 2021 17:35:26 -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-Language: en-CA X-Spam-Status: No, score=-11.4 required=5.0 tests=BAYES_00, DKIM_INVALID, DKIM_SIGNED, GIT_PATCH_0, KAM_DMARC_STATUS, 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-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" This pair of patches provides a sparse representation of the on-entry cache for ranger.  When the number of basic blocks exceed -param=evrp-sparse-threshold=  (default to 800), ranger moves to a sparse representation rather allocating a full vector for each ssa-name. This is based on an extension of the sparse bitmap code which enables us to use multiple bits instead of single bits. We'll cache up to 15 unique ranges for any ssa_name in this implementation. Bootstrapped on x86_64-pc-linux-gnu with no new regressions. Pushed. I will also port this to gcc11 in a couple of days assuming no unforeseen issues show up. Andrew commit 5ebec2f9218a39ec582a5fc53104cfe8f9bd8a65 Author: Andrew MacLeod Date: Mon Jun 7 13:18:55 2021 -0400 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. diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index c58acf48dfb..249515fbaf5 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -235,12 +235,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; @@ -253,6 +381,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. @@ -268,9 +397,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 4af461d2aa3..ce4449a08db 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 0d0dcd216f6..18e6036c4f4 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.