From patchwork Fri Nov 17 07:41:28 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff Law X-Patchwork-Id: 838883 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-467085-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.b="SZ5KgVSQ"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3ydVRx2N7Pz9s71 for ; Fri, 17 Nov 2017 18:41:49 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:message-id:date:mime-version:content-type; q=dns; s= default; b=XdsJR3MZnOfe7YKx+dWEN9Xh2LpDQ18vGx+aexGMDuY5O0jElLiNF Dx4qV0taQXEPoUB0zlt+86CaWnEHh8H6UwoevCj/8jo6Tgqrko9N4ucl4pE8zkAC z/DTwI51+mp4Ta+zdUBeFMlfuiHfN00aIQMjdlgBD5M3qOJxNwh5iw= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:message-id:date:mime-version:content-type; s= default; bh=lGF7DWrHSRKcGPPkyL8kNIfascs=; b=SZ5KgVSQKXbdBRJSnzhu VQLwzS6vtXSx276XKN3Sued3lg4kskZP8KUySowFQQMZmzXNQlIh1xju7L0l563e mnRB3QqUh2zGYcux9ukXFIDXXl/iIJ5eOgNqwTqlDjRoa9bf6REQpn9rfrc4gQCt WPxZzhVYCTCo0kwk1iopj3M= Received: (qmail 44339 invoked by alias); 17 Nov 2017 07:41:34 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 44329 invoked by uid 89); 17 Nov 2017 07:41:33 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.7 required=5.0 tests=BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KB_WAM_FROM_NAME_SINGLEWORD, RP_MATCHES_RCVD, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=delegates, sensitive, delegate X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 17 Nov 2017 07:41:31 +0000 Received: from smtp.corp.redhat.com (int-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.12]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 5569EC02738B for ; Fri, 17 Nov 2017 07:41:30 +0000 (UTC) Received: from localhost.localdomain (ovpn-112-12.rdu2.redhat.com [10.10.112.12]) by smtp.corp.redhat.com (Postfix) with ESMTP id 4912760F87 for ; Fri, 17 Nov 2017 07:41:29 +0000 (UTC) From: Jeff Law To: gcc-patches Subject: [RFA][PATCH] patch 7/n Introduce evrp_range_analyzer class Message-ID: <291b7c5b-0055-f6fe-c036-dc03f1d08c95@redhat.com> Date: Fri, 17 Nov 2017 00:41:28 -0700 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.4.0 MIME-Version: 1.0 X-IsSubscribed: yes This patch introduces the evrp_range_analyzer class. This is the class we're going to be able to embed into existing dominator walkers to provide them with context sensitive range analysis. The bulk of the class is extracted from the evrp_dom_walker class. A few minor notes. Setup of the reachable/executable state for blocks/edges moves into the evrp_range_analyzer class's constructor from execute_early_vrp. It seems to bit better in the analyzer class as it sets state the analyzer uses internally. The analyzer has a enter/leave methods to call as well as a per-statement method to call. I went back and forth several times on whether or not to have a per-statement method call or hide the per-statement stuff behind the enter method. I could be easily convinced to return to the latter as it has a simpler interface for the clients. I suspect evrp_range_analyzer::get_value_range which is currently private and delegates to the embedded vr_values class to likely become a public member that continues to delegate to the embedded vr_values. Essentially it's the query interface for embedded range analysis. There's a couple other cleanups that need to happen with the goal that the vr_values data member can become private. Bootstrapped and regression tested on x86_64. OK for the trunk? jeff * gimple-ssa-evrp.c (class evrp_range_analyzer): New class extracted from evrp_dom_walker class. Various methods moved into new class. (evrp_range_analyzer::evrp_range_analyzer): Constructor for new class. (evrp_range_analyzer::enter): New method. (evrp_range_analyzer::leave): New method. (evrp_dom_walker): Remove delegators no longer needed by this class. Replace vr_values data member with evrp_range_analyzer commit 45facb8e6d15937db1135310dd9ff85f85c17d81 Author: Jeff Law Date: Fri Nov 17 02:05:27 2017 -0500 Introduce range_analyzer class diff --git a/gcc/gimple-ssa-evrp.c b/gcc/gimple-ssa-evrp.c index 7b92beb..bb56696 100644 --- a/gcc/gimple-ssa-evrp.c +++ b/gcc/gimple-ssa-evrp.c @@ -55,6 +55,72 @@ evrp_folder::get_value (tree op) return vr_values->op_with_constant_singleton_value_range (op); } +class evrp_range_analyzer +{ + public: + evrp_range_analyzer (void); + ~evrp_range_analyzer (void) { stack.release (); } + + void enter (basic_block); + void leave (basic_block); + void record_ranges_from_stmt (gimple *); + + class vr_values vr_values; + + private: + void push_value_range (tree var, value_range *vr); + value_range *pop_value_range (tree var); + value_range *try_find_new_range (tree, tree op, tree_code code, tree limit); + void record_ranges_from_incoming_edge (basic_block); + void record_ranges_from_phis (basic_block); + + /* We do not allow copying this object or initializing one from another. */ + evrp_range_analyzer (const evrp_range_analyzer &); + evrp_range_analyzer& operator= (const evrp_range_analyzer &); + + /* Cond_stack holds the old VR. */ + auto_vec > stack; + + /* Temporary delegators. */ + value_range *get_value_range (const_tree op) + { return vr_values.get_value_range (op); } + bool update_value_range (const_tree op, value_range *vr) + { return vr_values.update_value_range (op, vr); } + void extract_range_from_phi_node (gphi *phi, value_range *vr) + { vr_values.extract_range_from_phi_node (phi, vr); } + void adjust_range_with_scev (value_range *vr, struct loop *loop, + gimple *stmt, tree var) + { vr_values.adjust_range_with_scev (vr, loop, stmt, var); } + void extract_range_from_stmt (gimple *stmt, edge *taken_edge_p, + tree *output_p, value_range *vr) + { vr_values.extract_range_from_stmt (stmt, taken_edge_p, output_p, vr); } + void set_defs_to_varying (gimple *stmt) + { return vr_values.set_defs_to_varying (stmt); } + void set_vr_value (tree name, value_range *vr) + { vr_values.set_vr_value (name, vr); } + void extract_range_for_var_from_comparison_expr (tree var, + enum tree_code cond_code, + tree op, tree limit, + value_range *vr_p) + { vr_values.extract_range_for_var_from_comparison_expr (var, cond_code, + op, limit, vr_p); } +}; + +evrp_range_analyzer::evrp_range_analyzer () : stack (10) +{ + edge e; + edge_iterator ei; + basic_block bb; + + FOR_EACH_BB_FN (bb, cfun) + { + bb->flags &= ~BB_VISITED; + FOR_EACH_EDGE (e, ei, bb->preds) + e->flags |= EDGE_EXECUTABLE; + } +} + + /* evrp_dom_walker visits the basic blocks in the dominance order and set the Value Ranges (VR) for SSA_NAMEs in the scope. Use this VR to discover more VRs. */ @@ -62,8 +130,7 @@ evrp_folder::get_value (tree op) class evrp_dom_walker : public dom_walker { public: - evrp_dom_walker () - : dom_walker (CDI_DOMINATORS), stack (10) + evrp_dom_walker () : dom_walker (CDI_DOMINATORS) { need_eh_cleanup = BITMAP_ALLOC (NULL); } @@ -76,21 +143,11 @@ public: void cleanup (void); private: - void push_value_range (tree var, value_range *vr); - value_range *pop_value_range (tree var); - value_range *try_find_new_range (tree, tree op, tree_code code, tree limit); - - void record_ranges_from_incoming_edge (basic_block); - void record_ranges_from_phis (basic_block); - void record_ranges_from_stmt (gimple *); - - /* Cond_stack holds the old VR. */ - auto_vec > stack; bitmap need_eh_cleanup; auto_vec stmts_to_fixup; auto_vec stmts_to_remove; - class vr_values vr_values; + class evrp_range_analyzer evrp_range_analyzer; /* We do not allow copying this object or initializing one from another. */ evrp_dom_walker (const evrp_dom_walker &); @@ -98,40 +155,25 @@ public: /* Temporary delegators. */ value_range *get_value_range (const_tree op) - { return vr_values.get_value_range (op); } - bool update_value_range (const_tree op, value_range *vr) - { return vr_values.update_value_range (op, vr); } - void extract_range_from_phi_node (gphi *phi, value_range *vr) - { vr_values.extract_range_from_phi_node (phi, vr); } - void extract_range_for_var_from_comparison_expr (tree var, - enum tree_code cond_code, - tree op, tree limit, - value_range *vr_p) - { vr_values.extract_range_for_var_from_comparison_expr (var, cond_code, - op, limit, vr_p); } - void adjust_range_with_scev (value_range *vr, struct loop *loop, - gimple *stmt, tree var) - { vr_values.adjust_range_with_scev (vr, loop, stmt, var); } + { return evrp_range_analyzer.vr_values.get_value_range (op); } tree op_with_constant_singleton_value_range (tree op) - { return vr_values.op_with_constant_singleton_value_range (op); } - void extract_range_from_stmt (gimple *stmt, edge *taken_edge_p, - tree *output_p, value_range *vr) - { vr_values.extract_range_from_stmt (stmt, taken_edge_p, output_p, vr); } - void set_defs_to_varying (gimple *stmt) - { return vr_values.set_defs_to_varying (stmt); } - void set_vr_value (tree name, value_range *vr) - { vr_values.set_vr_value (name, vr); } - void simplify_cond_using_ranges_2 (gcond *stmt) - { vr_values.simplify_cond_using_ranges_2 (stmt); } + { return evrp_range_analyzer.vr_values.op_with_constant_singleton_value_range (op); } void vrp_visit_cond_stmt (gcond *cond, edge *e) - { vr_values.vrp_visit_cond_stmt (cond, e); } + { evrp_range_analyzer.vr_values.vrp_visit_cond_stmt (cond, e); } }; -/* Find new range for NAME such that (OP CODE LIMIT) is true. */ +void +evrp_range_analyzer::enter (basic_block bb) +{ + stack.safe_push (std::make_pair (NULL_TREE, (value_range *)NULL)); + record_ranges_from_incoming_edge (bb); + record_ranges_from_phis (bb); +} +/* Find new range for NAME such that (OP CODE LIMIT) is true. */ value_range * -evrp_dom_walker::try_find_new_range (tree name, - tree op, tree_code code, tree limit) +evrp_range_analyzer::try_find_new_range (tree name, + tree op, tree_code code, tree limit) { value_range vr = VR_INITIALIZER; value_range *old_vr = get_value_range (name); @@ -158,10 +200,8 @@ evrp_dom_walker::try_find_new_range (tree name, then derive ranges implied by traversing that edge. */ void -evrp_dom_walker::record_ranges_from_incoming_edge (basic_block bb) +evrp_range_analyzer::record_ranges_from_incoming_edge (basic_block bb) { -/* See if there is any new scope is entered with new VR and set that VR to - ssa_name before visiting the statements in the scope. */ edge pred_e = single_pred_edge_ignoring_loop_edges (bb, false); if (pred_e) { @@ -210,10 +250,8 @@ evrp_dom_walker::record_ranges_from_incoming_edge (basic_block bb) } } -/* Record ranges from any PHI nodes at the start of basic block BB. */ - void -evrp_dom_walker::record_ranges_from_phis (basic_block bb) +evrp_range_analyzer::record_ranges_from_phis (basic_block bb) { /* Visit PHI stmts and discover any new VRs possible. */ bool has_unvisited_preds = false; @@ -234,15 +272,10 @@ evrp_dom_walker::record_ranges_from_phis (basic_block bb) tree lhs = PHI_RESULT (phi); if (virtual_operand_p (lhs)) continue; + value_range vr_result = VR_INITIALIZER; bool interesting = stmt_interesting_for_vrp (phi); - if (interesting && dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Visiting PHI node "); - print_gimple_stmt (dump_file, phi, 0); - } - if (!has_unvisited_preds - && interesting) + if (!has_unvisited_preds && interesting) extract_range_from_phi_node (phi, &vr_result); else { @@ -255,7 +288,7 @@ evrp_dom_walker::record_ranges_from_phis (basic_block bb) if (interesting && (l = loop_containing_stmt (phi)) && l->header == gimple_bb (phi)) - adjust_range_with_scev (&vr_result, l, phi, lhs); + adjust_range_with_scev (&vr_result, l, phi, lhs); } update_value_range (lhs, &vr_result); @@ -284,7 +317,7 @@ evrp_dom_walker::record_ranges_from_phis (basic_block bb) /* Record any ranges created by statement STMT. */ void -evrp_dom_walker::record_ranges_from_stmt (gimple *stmt) +evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt) { tree output = NULL_TREE; @@ -303,8 +336,8 @@ evrp_dom_walker::record_ranges_from_stmt (gimple *stmt) if (INTEGRAL_TYPE_P (TREE_TYPE (output))) { if ((vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE) - && (TREE_CODE (vr.min) == INTEGER_CST) - && (TREE_CODE (vr.max) == INTEGER_CST)) + && (TREE_CODE (vr.min) == INTEGER_CST) + && (TREE_CODE (vr.max) == INTEGER_CST)) set_range_info (output, vr.type, wi::to_wide (vr.min), wi::to_wide (vr.max)); @@ -375,9 +408,7 @@ evrp_dom_walker::before_dom_children (basic_block bb) if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "Visiting BB%d\n", bb->index); - stack.safe_push (std::make_pair (NULL_TREE, (value_range *)NULL)); - record_ranges_from_incoming_edge (bb); - record_ranges_from_phis (bb); + evrp_range_analyzer.enter (bb); for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi); gsi_next (&gpi)) @@ -414,7 +445,8 @@ evrp_dom_walker::before_dom_children (basic_block bb) print_gimple_stmt (dump_file, stmt, 0); } - record_ranges_from_stmt (stmt); + evrp_range_analyzer.record_ranges_from_stmt (stmt); + if (gcond *cond = dyn_cast (stmt)) { vrp_visit_cond_stmt (cond, &taken_edge); @@ -435,10 +467,10 @@ evrp_dom_walker::before_dom_children (basic_block bb) output = get_output_for_vrp (stmt); if (output) { + tree val; vr = *get_value_range (output); /* Mark stmts whose output we fully propagate for removal. */ - tree val; if ((vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE) && (val = op_with_constant_singleton_value_range (output)) && may_propagate_copy (output, val) @@ -453,7 +485,7 @@ evrp_dom_walker::before_dom_children (basic_block bb) /* Try folding stmts with the VR discovered. */ class evrp_folder evrp_folder; - evrp_folder.vr_values = &vr_values; + evrp_folder.vr_values = &evrp_range_analyzer.vr_values; bool did_replace = evrp_folder.replace_uses_in (stmt); if (fold_stmt (&gsi, follow_single_use_edges) || did_replace) @@ -511,10 +543,16 @@ evrp_dom_walker::before_dom_children (basic_block bb) return taken_edge; } +void +evrp_dom_walker::after_dom_children (basic_block bb) +{ + evrp_range_analyzer.leave (bb); +} + /* Restore/pop VRs valid only for BB when we leave BB. */ void -evrp_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED) +evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED) { gcc_checking_assert (!stack.is_empty ()); while (stack.last ().first != NULL_TREE) @@ -525,7 +563,7 @@ evrp_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED) /* Push the Value Range of VAR to the stack and update it with new VR. */ void -evrp_dom_walker::push_value_range (tree var, value_range *vr) +evrp_range_analyzer::push_value_range (tree var, value_range *vr) { if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -542,7 +580,7 @@ evrp_dom_walker::push_value_range (tree var, value_range *vr) /* Pop the Value Range from the vrp_stack and update VAR with it. */ value_range * -evrp_dom_walker::pop_value_range (tree var) +evrp_range_analyzer::pop_value_range (tree var) { value_range *vr = stack.last ().second; gcc_checking_assert (var == stack.last ().first); @@ -567,7 +605,7 @@ evrp_dom_walker::cleanup (void) if (dump_file) { fprintf (dump_file, "\nValue ranges after Early VRP:\n\n"); - vr_values.dump_all_value_ranges (dump_file); + evrp_range_analyzer.vr_values.dump_all_value_ranges (dump_file); fprintf (dump_file, "\n"); } @@ -613,10 +651,6 @@ evrp_dom_walker::cleanup (void) static unsigned int execute_early_vrp () { - edge e; - edge_iterator ei; - basic_block bb; - /* Ideally this setup code would move into the ctor for the dominator walk. However, this setup can change the number of blocks which invalidates the internal arrays that are set up by the dominator @@ -625,12 +659,6 @@ execute_early_vrp () rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); scev_initialize (); calculate_dominance_info (CDI_DOMINATORS); - FOR_EACH_BB_FN (bb, cfun) - { - bb->flags &= ~BB_VISITED; - FOR_EACH_EDGE (e, ei, bb->preds) - e->flags |= EDGE_EXECUTABLE; - } /* Walk stmts in dominance order and propagate VRP. */ evrp_dom_walker walker;