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 [63.128.21.124]) by sourceware.org (Postfix) with ESMTP id D14473893C35 for ; Wed, 10 Mar 2021 17:04:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org D14473893C35 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-302-aja5tOPANOe0q4zGPg4E7A-1; Wed, 10 Mar 2021 12:04:44 -0500 X-MC-Unique: aja5tOPANOe0q4zGPg4E7A-1 Received: from smtp.corp.redhat.com (int-mx05.intmail.prod.int.phx2.redhat.com [10.5.11.15]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id A2752107465F for ; Wed, 10 Mar 2021 17:04:43 +0000 (UTC) Received: from t14s.localdomain.com (ovpn-114-98.phx2.redhat.com [10.3.114.98]) by smtp.corp.redhat.com (Postfix) with ESMTP id 302925B6BF; Wed, 10 Mar 2021 17:04:43 +0000 (UTC) From: David Malcolm To: gcc-patches@gcc.gnu.org Subject: [committed] analyzer: factor out new class feasibility_state Date: Wed, 10 Mar 2021 12:04:41 -0500 Message-Id: <20210310170441.3047930-1-dmalcolm@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.15 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset="US-ASCII" X-Spam-Status: No, score=-13.9 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, 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: Wed, 10 Mar 2021 17:04:52 -0000 As preparatory work for a fix to PR analyzer/96374, this patch moves the core state-update logic from the loop in exploded_path::feasible_p into a new class feasibility_state. No functional change intended. Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu. Pushed to trunk as r11-7609-g44fd4dc0b684e06c6c6d08b3994df23135bf2fbc. gcc/analyzer/ChangeLog: PR analyzer/96374 * engine.cc (exploded_path::feasible_p): Move "snodes_visited" and "model" locals into a new class feasibility_state. Move heart of per-edge processing into feasibility_state::maybe_update_for_edge. (feasibility_state::feasibility_state): New. (feasibility_state::maybe_update_for_edge): New, based on loop body in exploded_path::feasible_p. * exploded-graph.h (class feasibility_state): New. --- gcc/analyzer/engine.cc | 251 ++++++++++++++++++++-------------- gcc/analyzer/exploded-graph.h | 22 +++ 2 files changed, 172 insertions(+), 101 deletions(-) diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc index 5339ea39712..fef482364c4 100644 --- a/gcc/analyzer/engine.cc +++ b/gcc/analyzer/engine.cc @@ -3404,11 +3404,10 @@ exploded_path::feasible_p (logger *logger, feasibility_problem **out, { LOG_SCOPE (logger); - auto_sbitmap snodes_visited (eg->get_supergraph ().m_nodes.length ()); - bitmap_clear (snodes_visited); + feasibility_state state (eng->get_model_manager (), + eg->get_supergraph ()); - /* Traverse the path, updating this model. */ - region_model model (eng->get_model_manager ()); + /* Traverse the path, updating this state. */ for (unsigned edge_idx = 0; edge_idx < m_edges.length (); edge_idx++) { const exploded_edge *eedge = m_edges[edge_idx]; @@ -3417,106 +3416,23 @@ exploded_path::feasible_p (logger *logger, feasibility_problem **out, edge_idx, eedge->m_src->m_index, eedge->m_dest->m_index); - const exploded_node &src_enode = *eedge->m_src; - const program_point &src_point = src_enode.get_point (); - if (logger) - { - logger->start_log_line (); - src_point.print (logger->get_printer (), format (false)); - logger->end_log_line (); - } - - /* Update state for the stmts that were processed in each enode. */ - for (unsigned stmt_idx = 0; stmt_idx < src_enode.m_num_processed_stmts; - stmt_idx++) - { - const gimple *stmt = src_enode.get_processed_stmt (stmt_idx); - - /* Update cfun and input_location in case of ICE: make it easier to - track down which source construct we're failing to handle. */ - auto_cfun sentinel (src_point.get_function ()); - input_location = stmt->location; - - if (const gassign *assign = dyn_cast (stmt)) - model.on_assignment (assign, NULL); - else if (const greturn *return_ = dyn_cast (stmt)) - model.on_return (return_, NULL); - } - - const superedge *sedge = eedge->m_sedge; - if (sedge) - { - if (logger) - logger->log (" sedge: SN:%i -> SN:%i %s", - sedge->m_src->m_index, - sedge->m_dest->m_index, - sedge->get_description (false)); - - const gimple *last_stmt = src_point.get_supernode ()->get_last_stmt (); - rejected_constraint *rc = NULL; - if (!model.maybe_update_for_edge (*sedge, last_stmt, NULL, &rc)) - { - if (logger) - { - logger->log ("rejecting due to region model"); - model.dump_to_pp (logger->get_printer (), true, false); - } - if (out) - *out = new feasibility_problem (edge_idx, *eedge, - last_stmt, rc); - else - delete rc; - return false; - } - } - else - { - /* Special-case the initial eedge from the origin node to the - initial function by pushing a frame for it. */ - if (edge_idx == 0) - { - gcc_assert (eedge->m_src->m_index == 0); - gcc_assert (src_point.get_kind () == PK_ORIGIN); - gcc_assert (eedge->m_dest->get_point ().get_kind () - == PK_BEFORE_SUPERNODE); - function *fun = eedge->m_dest->get_function (); - gcc_assert (fun); - model.push_frame (fun, NULL, NULL); - if (logger) - logger->log (" pushing frame for %qD", fun->decl); - } - else if (eedge->m_custom_info) - { - eedge->m_custom_info->update_model (&model, *eedge); - } - } - /* Handle phi nodes on an edge leaving a PK_BEFORE_SUPERNODE (to - a PK_BEFORE_STMT, or a PK_AFTER_SUPERNODE if no stmts). - This will typically not be associated with a superedge. */ - if (src_point.get_from_edge ()) + rejected_constraint *rc = NULL; + if (!state.maybe_update_for_edge (logger, eedge, &rc)) { - const cfg_superedge *last_cfg_superedge - = src_point.get_from_edge ()->dyn_cast_cfg_superedge (); - const exploded_node &dst_enode = *eedge->m_dest; - const unsigned dst_snode_idx = dst_enode.get_supernode ()->m_index; - if (last_cfg_superedge) + gcc_assert (rc); + if (out) { - if (logger) - logger->log (" update for phis"); - model.update_for_phis (src_enode.get_supernode (), - last_cfg_superedge, - NULL); - /* If we've entering an snode that we've already visited on this - epath, then we need do fix things up for loops; see the - comment for store::loop_replay_fixup. - Perhaps we should probably also verify the callstring, - and track program_points, but hopefully doing it by supernode - is good enough. */ - if (bitmap_bit_p (snodes_visited, dst_snode_idx)) - model.loop_replay_fixup (dst_enode.get_state ().m_region_model); + const exploded_node &src_enode = *eedge->m_src; + const program_point &src_point = src_enode.get_point (); + const gimple *last_stmt + = src_point.get_supernode ()->get_last_stmt (); + *out = new feasibility_problem (edge_idx, *eedge, + last_stmt, rc); } - bitmap_set_bit (snodes_visited, dst_snode_idx); + else + delete rc; + return false; } if (logger) @@ -3526,7 +3442,7 @@ exploded_path::feasible_p (logger *logger, feasibility_problem **out, eedge->m_src->m_index, eedge->m_dest->m_index); logger->start_log_line (); - model.dump_to_pp (logger->get_printer (), true, false); + state.get_model ().dump_to_pp (logger->get_printer (), true, false); logger->end_log_line (); } } @@ -3587,6 +3503,139 @@ feasibility_problem::dump_to_pp (pretty_printer *pp) const } } +/* class feasibility_state. */ + +/* Ctor for feasibility_state, at the beginning of a path. */ + +feasibility_state::feasibility_state (region_model_manager *manager, + const supergraph &sg) +: m_model (manager), + m_snodes_visited (sg.m_nodes.length ()) +{ + bitmap_clear (m_snodes_visited); +} + +/* Copy ctor for feasibility_state, for extending a path. */ + +feasibility_state::feasibility_state (const feasibility_state &other) +: m_model (other.m_model), + m_snodes_visited (const_sbitmap (other.m_snodes_visited)->n_bits) +{ + bitmap_copy (m_snodes_visited, other.m_snodes_visited); +} + +/* The heart of feasibility-checking. + + Attempt to update this state in-place based on traversing EEDGE + in a path. + Update the model for the stmts in the src enode. + Attempt to add constraints for EEDGE. + + If feasible, return true. + Otherwise, return false and write to *OUT_RC. */ + +bool +feasibility_state::maybe_update_for_edge (logger *logger, + const exploded_edge *eedge, + rejected_constraint **out_rc) +{ + const exploded_node &src_enode = *eedge->m_src; + const program_point &src_point = src_enode.get_point (); + if (logger) + { + logger->start_log_line (); + src_point.print (logger->get_printer (), format (false)); + logger->end_log_line (); + } + + /* Update state for the stmts that were processed in each enode. */ + for (unsigned stmt_idx = 0; stmt_idx < src_enode.m_num_processed_stmts; + stmt_idx++) + { + const gimple *stmt = src_enode.get_processed_stmt (stmt_idx); + + /* Update cfun and input_location in case of ICE: make it easier to + track down which source construct we're failing to handle. */ + auto_cfun sentinel (src_point.get_function ()); + input_location = stmt->location; + + if (const gassign *assign = dyn_cast (stmt)) + m_model.on_assignment (assign, NULL); + else if (const greturn *return_ = dyn_cast (stmt)) + m_model.on_return (return_, NULL); + } + + const superedge *sedge = eedge->m_sedge; + if (sedge) + { + if (logger) + logger->log (" sedge: SN:%i -> SN:%i %s", + sedge->m_src->m_index, + sedge->m_dest->m_index, + sedge->get_description (false)); + + const gimple *last_stmt = src_point.get_supernode ()->get_last_stmt (); + if (!m_model.maybe_update_for_edge (*sedge, last_stmt, NULL, out_rc)) + { + if (logger) + { + logger->log ("rejecting due to region model"); + m_model.dump_to_pp (logger->get_printer (), true, false); + } + return false; + } + } + else + { + /* Special-case the initial eedge from the origin node to the + initial function by pushing a frame for it. */ + if (src_point.get_kind () == PK_ORIGIN) + { + gcc_assert (eedge->m_src->m_index == 0); + gcc_assert (eedge->m_dest->get_point ().get_kind () + == PK_BEFORE_SUPERNODE); + function *fun = eedge->m_dest->get_function (); + gcc_assert (fun); + m_model.push_frame (fun, NULL, NULL); + if (logger) + logger->log (" pushing frame for %qD", fun->decl); + } + else if (eedge->m_custom_info) + { + eedge->m_custom_info->update_model (&m_model, *eedge); + } + } + + /* Handle phi nodes on an edge leaving a PK_BEFORE_SUPERNODE (to + a PK_BEFORE_STMT, or a PK_AFTER_SUPERNODE if no stmts). + This will typically not be associated with a superedge. */ + if (src_point.get_from_edge ()) + { + const cfg_superedge *last_cfg_superedge + = src_point.get_from_edge ()->dyn_cast_cfg_superedge (); + const exploded_node &dst_enode = *eedge->m_dest; + const unsigned dst_snode_idx = dst_enode.get_supernode ()->m_index; + if (last_cfg_superedge) + { + if (logger) + logger->log (" update for phis"); + m_model.update_for_phis (src_enode.get_supernode (), + last_cfg_superedge, + NULL); + /* If we've entering an snode that we've already visited on this + epath, then we need do fix things up for loops; see the + comment for store::loop_replay_fixup. + Perhaps we should probably also verify the callstring, + and track program_points, but hopefully doing it by supernode + is good enough. */ + if (bitmap_bit_p (m_snodes_visited, dst_snode_idx)) + m_model.loop_replay_fixup (dst_enode.get_state ().m_region_model); + } + bitmap_set_bit (m_snodes_visited, dst_snode_idx); + } + return true; +} + /* A family of cluster subclasses for use when generating .dot output for exploded graphs (-fdump-analyzer-exploded-graph), for grouping the enodes into hierarchical boxes. diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h index 871cb78b73a..da1cebb1aef 100644 --- a/gcc/analyzer/exploded-graph.h +++ b/gcc/analyzer/exploded-graph.h @@ -906,6 +906,28 @@ public: rejected_constraint *m_rc; }; +/* A class for capturing the state of a node when checking a path + through the exploded_graph for feasibility. */ + +class feasibility_state +{ +public: + feasibility_state (region_model_manager *manager, + const supergraph &sg); + feasibility_state (const feasibility_state &other); + + bool maybe_update_for_edge (logger *logger, + const exploded_edge *eedge, + rejected_constraint **out_rc); + + const region_model &get_model () const { return m_model; } + const auto_sbitmap &get_snodes_visited () const { return m_snodes_visited; } + +private: + region_model m_model; + auto_sbitmap m_snodes_visited; +}; + /* Finding the shortest exploded_path within an exploded_graph. */ typedef shortest_paths shortest_exploded_paths; -- 2.26.2