From patchwork Tue Jun 8 14:54:31 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1489473 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=gKh+DNNz; 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 4FztZp3fpdz9sWl for ; Wed, 9 Jun 2021 00:55:28 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 822613959C64 for ; Tue, 8 Jun 2021 14:55:25 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 822613959C64 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1623164125; bh=GKEm4bMtfq38+ASqSX7kd0oIPkCZffSlihsDm9gWYsE=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=gKh+DNNzypbMEBKwynTvXXeWb+jZlULhHlLVnesPzMOeiqQwDMorJl1qr3RL9UFlH OzlJZh19BXCd1MIoEIZZeca+AtP5QYRiphQRjajdtEVAGQ5v8zjET6zLHraK3MOIi+ 0bNP4UWfI+GTZ12syfLnwrYLBFBpatJawfkL7cDU= 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 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 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-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-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Cc: Jakub Jelinek Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" 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 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