From patchwork Tue May 25 23:30:29 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1483795 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@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=oDhIy/Sj; 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 4FqVgh5Mrpz9sCD for ; Wed, 26 May 2021 09:30:40 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 56F633857802; Tue, 25 May 2021 23:30:38 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 56F633857802 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1621985438; bh=AzzCBNnzDO3Nc62ymmkylGo/w2+ktgGFAgAv8AG3Stk=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=oDhIy/Sjm3NsVOokR4pCBZsrioPLnzz0mUTsh5Nzcpedf6ZQmDi7RWhK+vO4GptYE RH8h0zVmxUwGZZpKwaWmKcard5vnh3o8BFTvCKkK82nRJnppbJEBNxkLjmqOaThoz/ v837nEWF0Y1Sa4MpQlJaJLdz1M5ezeyf+b4y4vDk= 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 B14FC385803D for ; Tue, 25 May 2021 23:30:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org B14FC385803D Received: from mail-qv1-f72.google.com (mail-qv1-f72.google.com [209.85.219.72]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-505-uA_oqy0hNMeBY881OyVhSQ-1; Tue, 25 May 2021 19:30:31 -0400 X-MC-Unique: uA_oqy0hNMeBY881OyVhSQ-1 Received: by mail-qv1-f72.google.com with SMTP id b24-20020a0cb3d80000b02901e78b82d74aso31954113qvf.20 for ; Tue, 25 May 2021 16:30:31 -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=TPYxgLMXdT7VUhqhRhARUWNHG/HKm0GiWw5jA4vIw4w=; b=ugxqyocWAmzfsDhe0loc7tiWQdaS89CObHfyDmW+QfLVkLWJnSYAq3T9YhTmtuH0xD /W4TLXu2OZfiNeAuOzd8i13dYoo2jkQja1Qnx3hSD+i3qJfIB9ZkxWNuSDUeTmoveFqb RxpBb4odbgXQofu64gDSYejavBfU9+0uvbf6VkQJbif26ZtPXSVQ6o4YZswS8rHUANlA BbULsG+dsAD2HMe+Y7g7PkpWkB4KSdCfacIz6OigIA05R9hmvxjJ5bmHGzoLpL1KPpMx cU4cGyXLlaF7VTqeL+gi25ZJcA9WyP7DgT7rP3hycGTJA2O+FWshdgc8PHBZ4NXwblRF Y0Gg== X-Gm-Message-State: AOAM5326jdENTFHTi2xMbVUUkfKBEF0UgoeF8EeWwzkL2lK4EFU4h9Mn Inocw3vzKR6GyVyqdlQzkjRucq9Dq8IqQ3nHx8voF/SlXBQYVb6IMDzHnixr95J6S9N27YsGIdN kDXIvNKFZLkJT7pY6Cg== X-Received: by 2002:a0c:e752:: with SMTP id g18mr7212897qvn.24.1621985431245; Tue, 25 May 2021 16:30:31 -0700 (PDT) X-Google-Smtp-Source: ABdhPJwDy4sIC4sWvTit9Zr4pn7rvjHScwWfhZhsvqCd0MAR9NBTfvB6/GFCxz5JG/ud3/FvME9RMg== X-Received: by 2002:a0c:e752:: with SMTP id g18mr7212886qvn.24.1621985431115; Tue, 25 May 2021 16:30:31 -0700 (PDT) Received: from ?IPv6:2607:fea8:a25d:e700::2b5? ([2607:fea8:a25d:e700::2b5]) by smtp.gmail.com with ESMTPSA id q21sm488503qke.32.2021.05.25.16.30.30 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 25 May 2021 16:30:30 -0700 (PDT) To: gcc-patches Subject: [PATCH 3/8] Add imports and strengthen the export definition to range_def and gori_map. Message-ID: <725bf67f-d257-ede6-d215-ef140741f342@redhat.com> Date: Tue, 25 May 2021 19:30:29 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.9.1 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-11.9 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, HTML_MESSAGE, 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-Content-Filtered-By: Mailman/MimeDel 2.1.29 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@gcc.gnu.org Sender: "Gcc-patches" This patch introduced imports to range_def, and corrects some minor issues with export calculation. When gori-compute is evaluating sequences in a block:   - an "export" is defined as any ssa_name which may have a range calculated on an outgoing edge.  If the edge may CHANGE the value of ssa-name from its on-entry/exit value, then it is an export.  - an "import" is any ssa name which which may affect the outgoing value of an export.   This may be the ssa_anme itself, or and ssa_name used in the calculation of the ssa_name value. bb5: b_6 = a_4 + 5 c_5 = b_6 < z_9 if (c_5 != 0) in this small sample c_5, b_6, z_9 and a_4 are all exports, because we may be able to refine a range for any of them on one of the edges a_4 and z_9 are considered imports because those are the ssa_names which have definitions occurring outside the block which can affect the value of any an exports. This patch introduces imports to  both range_def and gori_map, as well as standardizes the dependency chain registration API so we can also cache up to 2 direct dependent names and eventually utilize that for re-computation and the temporal cache. Bootstraps on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From c21644704160710a17d1ea6c1cd212e079cd5e36 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Tue, 25 May 2021 14:15:50 -0400 Subject: [PATCH 3/8] Add imports and strengthen the export definition in range_def and gori_map. All add up to 2 direct dependencies for each ssa-name. Add gori import/export iterators. * gimple-range-gori.cc (range_def_chain::range_def_chain): init bitmap obstack. (range_def_chain::~range_def_chain): Dispose of obstack rather than each individual bitmap. (range_def_chain::set_import): New. (range_def_chain::get_imports): New. (range_def_chain::chain_import_p): New. (range_def_chain::register_dependency): Rename from build_def_chain and set imports. (range_def_chain::def_chain_in_bitmap_p): New. (range_def_chain::add_def_chain_to_bitmap): New. (range_def_chain::has_def_chain): Just check first depenedence. (range_def_chain::get_def_chain): Process imports, use generic register_dependency routine. (range_def_chain::dump): New. (gori_map::gori_map): Allocate import list. (gori_map::~gori_map): Release imports. (gori_map::exports): Check for past allocated block size. (gori_map::imports): New. (gori_map::def_chain_in_export_p): Delete. (gori_map::is_import_p): New. (gori_map::maybe_add_gori): Handle imports. (gori_map::dump): Adjust output, add imports. (gori_compute::has_edge_range_p): Remove def_chain_in_export call. (gori_export_iterator::gori_export_iterator): New. (gori_export_iterator::next): New. (gori_export_iterator::get_name): New. * gimple-range-gori.h (range_def_chain): Add imports and direct dependecies via struct rdc. (range_def_chain::depend1): New. (range_def_chain::depend2): New. (class gori_map): Adjust. (FOR_EACH_GORI_IMPORT_NAME): New. (FOR_EACH_GORI_EXPORT_NAME): New. (class gori_export_iterator): New. --- gcc/gimple-range-gori.cc | 356 ++++++++++++++++++++++++++++----------- gcc/gimple-range-gori.h | 77 ++++++++- 2 files changed, 327 insertions(+), 106 deletions(-) diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc index e30049edfbd..94640adc041 100644 --- a/gcc/gimple-range-gori.cc +++ b/gcc/gimple-range-gori.cc @@ -56,7 +56,7 @@ is_gimple_logical_p (const gimple *gs) return false; } -/* RANGE_DEF_CHAIN is used to determine what SSA names in a block can +/* RANGE_DEF_CHAIN is used to determine which SSA names in a block can have range information calculated for them, and what the dependencies on each other are. @@ -95,6 +95,7 @@ is_gimple_logical_p (const gimple *gs) range_def_chain::range_def_chain () { + bitmap_obstack_initialize (&m_bitmaps); m_def_chain.create (0); m_def_chain.safe_grow_cleared (num_ssa_names); m_logical_depth = 0; @@ -104,11 +105,8 @@ range_def_chain::range_def_chain () range_def_chain::~range_def_chain () { - unsigned x; - for (x = 0; x < m_def_chain.length (); ++x) - if (m_def_chain[x]) - BITMAP_FREE (m_def_chain[x]); m_def_chain.release (); + bitmap_obstack_release (&m_bitmaps); } // Return true if NAME is in the def chain of DEF. If BB is provided, @@ -128,26 +126,112 @@ range_def_chain::in_chain_p (tree name, tree def) return bitmap_bit_p (chain, SSA_NAME_VERSION (name)); } +// Add either IMP or the import list B to the import set of DATA. + +void +range_def_chain::set_import (struct rdc &data, tree imp, bitmap b) +{ + // If there are no imports, just return + if (imp == NULL_TREE && !b) + return; + if (!data.m_import) + data.m_import = BITMAP_ALLOC (&m_bitmaps); + if (imp != NULL_TREE) + bitmap_set_bit (data.m_import, SSA_NAME_VERSION (imp)); + else + bitmap_ior_into (data.m_import, b); +} + +// Return the import list for NAME. + +bitmap +range_def_chain::get_imports (tree name) +{ + if (!has_def_chain (name)) + get_def_chain (name); + bitmap i = m_def_chain[SSA_NAME_VERSION (name)].m_import; + // Either this is a default def, OR imports must be a subset of exports. + gcc_checking_assert (!get_def_chain (name) || !i + || !bitmap_intersect_compl_p (i, get_def_chain (name))); + return i; +} + +// Return true if IMPORT is an import to NAMEs def chain. + +bool +range_def_chain::chain_import_p (tree name, tree import) +{ + bitmap b = get_imports (name); + if (b) + return bitmap_bit_p (b, SSA_NAME_VERSION (import)); + return false; +} + // Build def_chains for NAME if it is in BB. Copy the def chain into RESULT. void -range_def_chain::build_def_chain (tree name, bitmap result, basic_block bb) +range_def_chain::register_dependency (tree name, tree dep, basic_block bb) { + if (!gimple_range_ssa_p (dep)) + return; + + unsigned v = SSA_NAME_VERSION (name); + struct rdc &src = m_def_chain[v]; + gimple *def_stmt = SSA_NAME_DEF_STMT (dep); + unsigned dep_v = SSA_NAME_VERSION (dep); bitmap b; - gimple *def_stmt = SSA_NAME_DEF_STMT (name); + + // Set the direct dependency cache entries. + if (!src.ssa1) + src.ssa1 = dep; + else if (!src.ssa2 && src.ssa1 != dep) + src.ssa2 = dep; + + // Don't calculate imports or export/dep chains if BB is not provided. + // This is usually the case for when the temporal cache wants the direct + // dependencies of a stmt. + if (!bb) + return; + + if (!src.bm) + src.bm = BITMAP_ALLOC (&m_bitmaps); + // Add this operand into the result. - bitmap_set_bit (result, SSA_NAME_VERSION (name)); + bitmap_set_bit (src.bm, dep_v); if (gimple_bb (def_stmt) == bb && !is_a(def_stmt)) { // Get the def chain for the operand. - b = get_def_chain (name); + b = get_def_chain (dep); // If there was one, copy it into result. if (b) - bitmap_ior_into (result, b); + bitmap_ior_into (src.bm, b); + // And copy the import list. + set_import (src, NULL_TREE, get_imports (dep)); } + else + // Originated outside the block, so it is an import. + set_import (src, dep, NULL); +} + +bool +range_def_chain::def_chain_in_bitmap_p (tree name, bitmap b) +{ + bitmap a = get_def_chain (name); + if (a && b) + return bitmap_intersect_p (a, b); + return false; } +void +range_def_chain::add_def_chain_to_bitmap (bitmap b, tree name) +{ + bitmap r = get_def_chain (name); + if (r) + bitmap_ior_into (b, r); +} + + // Return TRUE if NAME has been processed for a def_chain. inline bool @@ -157,9 +241,11 @@ range_def_chain::has_def_chain (tree name) unsigned v = SSA_NAME_VERSION (name); if (v >= m_def_chain.length ()) m_def_chain.safe_grow_cleared (num_ssa_names + 1); - return (m_def_chain[v] != NULL); + return (m_def_chain[v].ssa1 != 0); } + + // Calculate the def chain for NAME and all of its dependent // operands. Only using names in the same BB. Return the bitmap of // all names in the m_def_chain. This only works for supported range @@ -174,11 +260,15 @@ range_def_chain::get_def_chain (tree name) // If it has already been processed, just return the cached value. if (has_def_chain (name)) - return m_def_chain[v]; + return m_def_chain[v].bm; // No definition chain for default defs. if (SSA_NAME_IS_DEFAULT_DEF (name)) - return NULL; + { + // A Default def is always an import. + set_import (m_def_chain[v], name, NULL); + return NULL; + } gimple *stmt = SSA_NAME_DEF_STMT (name); if (gimple_range_handler (stmt)) @@ -205,30 +295,63 @@ range_def_chain::get_def_chain (tree name) ssa3 = gimple_range_ssa_p (gimple_assign_rhs3 (st)); } else - return NULL; - - basic_block bb = gimple_bb (stmt); - - m_def_chain[v] = BITMAP_ALLOC (NULL); + { + // Stmts not understood are always imports. + set_import (m_def_chain[v], name, NULL); + return NULL; + } - if (ssa1) - build_def_chain (ssa1, m_def_chain[v], bb); - if (ssa2) - build_def_chain (ssa2, m_def_chain[v], bb); - if (ssa3) - build_def_chain (ssa3, m_def_chain[v], bb); + register_dependency (name, ssa1, gimple_bb (stmt)); + register_dependency (name, ssa2, gimple_bb (stmt)); + register_dependency (name, ssa3, gimple_bb (stmt)); + // Stmts with no understandable operands are also imports. + if (!ssa1 && !ssa2 & !ssa3) + set_import (m_def_chain[v], name, NULL); if (is_logical) m_logical_depth--; - // If we run into pathological cases where the defintion chains are - // huge (ie huge basic block fully unrolled) we might be able to limit - // this by deciding here that if some criteria is satisfied, we change the - // def_chain back to be just the ssa-names. That will help prevent chains - // of a_2 = b_6 + a_8 from creating a pathological case. - return m_def_chain[v]; + return m_def_chain[v].bm; +} + +// Dump what we know for basic block BB to file F. + +void +range_def_chain::dump (FILE *f, basic_block bb, const char *prefix) +{ + unsigned x, y; + bitmap_iterator bi; + + // Dump the def chain for each SSA_NAME defined in BB. + for (x = 1; x < num_ssa_names; x++) + { + tree name = ssa_name (x); + if (!name) + continue; + gimple *stmt = SSA_NAME_DEF_STMT (name); + if (!stmt || (bb && gimple_bb (stmt) != bb)) + continue; + bitmap chain = (has_def_chain (name) ? get_def_chain (name) : NULL); + if (chain && !bitmap_empty_p (chain)) + { + fprintf (f, prefix); + print_generic_expr (f, name, TDF_SLIM); + fprintf (f, " : "); + + bitmap imports = get_imports (name); + EXECUTE_IF_SET_IN_BITMAP (chain, 0, y, bi) + { + print_generic_expr (f, ssa_name (y), TDF_SLIM); + if (imports && bitmap_bit_p (imports, y)) + fprintf (f, "(I)"); + fprintf (f, " "); + } + fprintf (f, "\n"); + } + } } + // ------------------------------------------------------------------- /* GORI_MAP is used to accumulate what SSA names in a block can @@ -256,7 +379,8 @@ gori_map::gori_map () { m_outgoing.create (0); m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun)); - bitmap_obstack_initialize (&m_bitmaps); + m_incoming.create (0); + m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun)); m_maybe_variant = BITMAP_ALLOC (&m_bitmaps); } @@ -264,7 +388,7 @@ gori_map::gori_map () gori_map::~gori_map () { - bitmap_obstack_release (&m_bitmaps); + m_incoming.release (); m_outgoing.release (); } @@ -273,11 +397,21 @@ gori_map::~gori_map () bitmap gori_map::exports (basic_block bb) { - if (!m_outgoing[bb->index]) + if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index]) calculate_gori (bb); return m_outgoing[bb->index]; } +// Return the bitmap vector of all imports to BB. Calculate if necessary. + +bitmap +gori_map::imports (basic_block bb) +{ + if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index]) + calculate_gori (bb); + return m_incoming[bb->index]; +} + // Return true if NAME is can have ranges generated for it from basic // block BB. @@ -298,17 +432,13 @@ gori_map::set_range_invariant (tree name) bitmap_clear_bit (m_maybe_variant, SSA_NAME_VERSION (name)); } -// Return true if any element in the def chain of NAME is in the -// export list for BB. +// Return true if NAME is an import to block BB. bool -gori_map::def_chain_in_export_p (tree name, basic_block bb) +gori_map::is_import_p (tree name, basic_block bb) { - bitmap a = exports (bb); - bitmap b = get_def_chain (name); - if (a && b) - return bitmap_intersect_p (a, b); - return false; + // If no BB is specified, test if it is exported anywhere in the IL. + return bitmap_bit_p (imports (bb), SSA_NAME_VERSION (name)); } // If NAME is non-NULL and defined in block BB, calculate the def @@ -319,11 +449,17 @@ gori_map::maybe_add_gori (tree name, basic_block bb) { if (name) { - gimple *s = SSA_NAME_DEF_STMT (name); - bitmap r = get_def_chain (name); - // Check if there is a def chain, and it is in this block. - if (r && gimple_bb (s) == bb) - bitmap_copy (m_outgoing[bb->index], r); + // Check if there is a def chain, regardless of the block. + add_def_chain_to_bitmap (m_outgoing[bb->index], name); + // Check for any imports. + bitmap imp = get_imports (name); + // If there were imports, add them so we can recompute + if (imp) + bitmap_ior_into (m_incoming[bb->index], imp); + // This name is always an import. + if (gimple_bb (SSA_NAME_DEF_STMT (name)) != bb) + bitmap_set_bit (m_incoming[bb->index], SSA_NAME_VERSION (name)); + // Def chain doesn't include itself, and even if there isn't a // def chain, this name should be added to exports. bitmap_set_bit (m_outgoing[bb->index], SSA_NAME_VERSION (name)); @@ -337,9 +473,13 @@ gori_map::calculate_gori (basic_block bb) { tree name; if (bb->index >= (signed int)m_outgoing.length ()) - m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun)); + { + m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun)); + m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun)); + } gcc_checking_assert (m_outgoing[bb->index] == NULL); m_outgoing[bb->index] = BITMAP_ALLOC (&m_bitmaps); + m_incoming[bb->index] = BITMAP_ALLOC (&m_bitmaps); // If this block's last statement may generate range informaiton, go // calculate it. @@ -368,65 +508,42 @@ gori_map::calculate_gori (basic_block bb) // Dump the table information for BB to file F. void -gori_map::dump (FILE *f, basic_block bb) +gori_map::dump (FILE *f, basic_block bb, bool verbose) { - bool header = false; - const char *header_string = "bb%-4d "; - const char *header2 = " "; - bool printed_something = false;; - unsigned x, y; - bitmap_iterator bi; - // BB was not processed. - if (!m_outgoing[bb->index]) + if (!m_outgoing[bb->index] || bitmap_empty_p (m_outgoing[bb->index])) return; - // Dump the def chain for each SSA_NAME defined in BB. - for (x = 1; x < num_ssa_names; x++) + tree name; + + bitmap imp = imports (bb); + if (!bitmap_empty_p (imp)) { - tree name = ssa_name (x); - if (!name) - continue; - gimple *stmt = SSA_NAME_DEF_STMT (name); - bitmap chain = (has_def_chain (name) ? get_def_chain (name) : NULL); - if (stmt && gimple_bb (stmt) == bb && chain && !bitmap_empty_p (chain)) - { - fprintf (f, header_string, bb->index); - header_string = header2; - header = true; + if (verbose) + fprintf (f, "bb<%u> Imports: ",bb->index); + else + fprintf (f, "Imports: "); + FOR_EACH_GORI_IMPORT_NAME (*this, bb, name) + { print_generic_expr (f, name, TDF_SLIM); - fprintf (f, " : "); - EXECUTE_IF_SET_IN_BITMAP (chain, 0, y, bi) - { - print_generic_expr (f, ssa_name (y), TDF_SLIM); - fprintf (f, " "); - } - fprintf (f, "\n"); + fprintf (f, " "); } + fputc ('\n', f); } - printed_something |= header; - - // Now dump the export vector. - header = false; - EXECUTE_IF_SET_IN_BITMAP (m_outgoing[bb->index], 0, y, bi) + if (verbose) + fprintf (f, "bb<%u> Exports: ",bb->index); + else + fprintf (f, "Exports: "); + // Dump the export vector. + FOR_EACH_GORI_EXPORT_NAME (*this, bb, name) { - if (!header) - { - fprintf (f, header_string, bb->index); - fprintf (f, "exports: "); - header_string = header2; - header = true; - } - print_generic_expr (f, ssa_name (y), TDF_SLIM); + print_generic_expr (f, name, TDF_SLIM); fprintf (f, " "); } - if (header) - fputc ('\n', f); + fputc ('\n', f); - printed_something |= header; - if (printed_something) - fprintf (f, "\n"); + range_def_chain::dump (f, bb, " "); } // Dump the entire GORI map structure to file F. @@ -436,11 +553,7 @@ gori_map::dump (FILE *f) { basic_block bb; FOR_EACH_BB_FN (bb, cfun) - { - dump (f, bb); - if (m_outgoing[bb->index]) - fprintf (f, "\n"); - } + dump (f, bb); } DEBUG_FUNCTION void @@ -960,8 +1073,7 @@ gori_compute::has_edge_range_p (tree name, edge e) if (!e) return is_export_p (name); - return (is_export_p (name, e->src) - || def_chain_in_export_p (name, e->src)); + return is_export_p (name, e->src); } // Dump what is known to GORI computes to listing file F. @@ -1006,6 +1118,50 @@ gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name) return false; } + +// ------------------------------------------------------------------------ +// GORI iterator. Although we have bitmap iterators, don't expose that it +// is currently a bitmap. Use an export iterator to hide future changes. + +// Construct a basic iterator over an export bitmap. + +gori_export_iterator::gori_export_iterator (bitmap b) +{ + bm = b; + if (b) + bmp_iter_set_init (&bi, b, 1, &y); +} + + +// Move to the next export bitmap spot. + +void +gori_export_iterator::next () +{ + bmp_iter_next (&bi, &y); +} + + +// Fetch the name of the next export in the export list. Return NULL if +// iteration is done. + +tree +gori_export_iterator::get_name () +{ + if (!bm) + return NULL_TREE; + + while (bmp_iter_set (&bi, &y)) + { + tree t = ssa_name (y); + if (t) + return t; + next (); + } + return NULL_TREE; +} + + // -------------------------------------------------------------------------- // Cache for SSAs that appear on the RHS of a boolean assignment. diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h index 6208931a0d8..8f44216cfcd 100644 --- a/gcc/gimple-range-gori.h +++ b/gcc/gimple-range-gori.h @@ -31,15 +31,55 @@ class range_def_chain public: range_def_chain (); ~range_def_chain (); + tree depend1 (tree name) const; + tree depend2 (tree name) const; + bool in_chain_p (tree name, tree def); + bool chain_import_p (tree name, tree import); + void register_dependency (tree name, tree ssa1, basic_block bb = NULL); + void dump (FILE *f, basic_block bb, const char *prefix = NULL); +protected: bool has_def_chain (tree name); + bool def_chain_in_bitmap_p (tree name, bitmap b); + void add_def_chain_to_bitmap (bitmap b, tree name); bitmap get_def_chain (tree name); - bool in_chain_p (tree name, tree def); + bitmap get_imports (tree name); + bitmap_obstack m_bitmaps; private: - vec m_def_chain; // SSA_NAME : def chain components. - void build_def_chain (tree name, bitmap result, basic_block bb); + struct rdc { + tree ssa1; // First direct dependency + tree ssa2; // Second direct dependency + bitmap bm; // All dependencies + bitmap m_import; + }; + vec m_def_chain; // SSA_NAME : def chain components. + void set_import (struct rdc &data, tree imp, bitmap b); int m_logical_depth; }; +// Return the first direct dependency for NAME, if there is one. +// Direct dependencies are those which occur on the defintion statement. +// Only the first 2 such names are cached. + +inline tree +range_def_chain::depend1 (tree name) const +{ + unsigned v = SSA_NAME_VERSION (name); + if (v >= m_def_chain.length ()) + return NULL_TREE; + return m_def_chain[v].ssa1; +} + +// Return the second direct dependency for NAME, if there is one. + +inline tree +range_def_chain::depend2 (tree name) const +{ + unsigned v = SSA_NAME_VERSION (name); + if (v >= m_def_chain.length ()) + return NULL_TREE; + return m_def_chain[v].ssa2; +} + // GORI_MAP is used to accumulate what SSA names in a block can // generate range information, and provides tools for the block ranger // to enable it to efficiently calculate these ranges. @@ -51,15 +91,16 @@ public: ~gori_map (); bool is_export_p (tree name, basic_block bb = NULL); - bool def_chain_in_export_p (tree name, basic_block bb); + bool is_import_p (tree name, basic_block bb); bitmap exports (basic_block bb); + bitmap imports (basic_block bb); void set_range_invariant (tree name); void dump (FILE *f); - void dump (FILE *f, basic_block bb); + void dump (FILE *f, basic_block bb, bool verbose = true); private: - bitmap_obstack m_bitmaps; vec m_outgoing; // BB: Outgoing ranges calculatable on edges + vec m_incoming; // BB: Incoming ranges which can affect exports. bitmap m_maybe_variant; // Names which might have outgoing ranges. void maybe_add_gori (tree name, basic_block bb); void calculate_gori (basic_block bb); @@ -152,6 +193,30 @@ private: }; +// For each name that is an import into BB's exports.. +#define FOR_EACH_GORI_IMPORT_NAME(gori, bb, name) \ + for (gori_export_iterator iter ((gori).imports ((bb))); \ + ((name) = iter.get_name ()); \ + iter.next ()) + +// For each name possibly exported from block BB. +#define FOR_EACH_GORI_EXPORT_NAME(gori, bb, name) \ + for (gori_export_iterator iter ((gori).exports ((bb))); \ + ((name) = iter.get_name ()); \ + iter.next ()) + +// Used to assist with iterating over the GORI export list in various ways +class gori_export_iterator { +public: + gori_export_iterator (bitmap b); + void next (); + tree get_name (); +protected: + bitmap bm; + bitmap_iterator bi; + unsigned y; +}; + // This class adds a cache to gori_computes for logical expressions. // bool result = x && y // requires calcuation of both X and Y for both true and false results. -- 2.17.2