From patchwork Fri Jul 15 04:44:26 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kugan Vivekanandarajah X-Patchwork-Id: 72062 Delivered-To: patch@linaro.org Received: by 10.140.29.52 with SMTP id a49csp417518qga; Thu, 14 Jul 2016 21:44:55 -0700 (PDT) X-Received: by 10.98.192.144 with SMTP id g16mr18491696pfk.55.1468557895436; Thu, 14 Jul 2016 21:44:55 -0700 (PDT) Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id m88si3567476pfi.190.2016.07.14.21.44.55 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 14 Jul 2016 21:44:55 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-431719-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org; spf=pass (google.com: domain of gcc-patches-return-431719-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-431719-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :subject:to:references:cc:from:message-id:date:mime-version :in-reply-to:content-type; q=dns; s=default; b=yECNerxzPkb9+rTGS 7WExBeKmTfl2Kjwz0vFnalrusbJ2BVfHXZ7kJA7xfBtpAhOOXaUKbsJzzWzHfCuW pOdVFS98qioCFcQJO6y97wLL9sIPPDUnTPO9xrMFNfNUNisijaKouvqGviGYyaQT HU9rXd/YUuzheoAsfSLwpVZmK0= 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 :subject:to:references:cc:from:message-id:date:mime-version :in-reply-to:content-type; s=default; bh=Vb3JDqRjKRh+r70KzYyOEog NM8Y=; b=PG56qYR5CWl0ZWfazlVWZ658Lw+jirvq4jDFGPVeSPZxhGCMn8atYxI HLORZeF15kf/cWPra6+M9B9ZUnoZ1qDdd0gYElD5LPfDs+3hrZtocTkLwHmhqIXl HvLi+cr5f3KC1pQOZuMtBKFXe9seVQ+i5x5ejpnaFRUNNWiN0swM= Received: (qmail 103562 invoked by alias); 15 Jul 2016 04:44:37 -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 103550 invoked by uid 89); 15 Jul 2016 04:44:36 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.6 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 spammy=Minimum, NEG, inv, Traverse X-HELO: mail-wm0-f41.google.com Received: from mail-wm0-f41.google.com (HELO mail-wm0-f41.google.com) (74.125.82.41) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Fri, 15 Jul 2016 04:44:32 +0000 Received: by mail-wm0-f41.google.com with SMTP id f65so11265201wmi.0 for ; Thu, 14 Jul 2016 21:44:31 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:subject:to:references:cc:from:message-id:date :user-agent:mime-version:in-reply-to; bh=5CilPWjvQqR4QCgXmaEbV1cjXGL4vCGOfWgI+TaPolY=; b=FrOUGcFlwEeuBboSZoUJ22Ul8zidAvWcV4U21ktk2zv/FZiQxFFpv+ms23MYEFckU0 zsP1CAQ5F3zl/YYpYMbKtb3qdxzqxPHkMgKAsq91vZiyA5jjyPgofJnbB3GSI8++emjK gMhOg7fAaiLFJLqEyA4eF90LxK1yFK7RQ/rQ2tsGxyqrkXMKo3qdYThcC9yTsPgAi/+J cJYaC+fHpijPIiNKaCvjeCeVYNQ1kVwQAzBCIelXEl1X/uO+MNaraE2UTmm2asac0UYE /jcy5JhRbcBkCvM4bSRt3DOzbtCZCoxwo1YlFG1osZhUyynjU3wXK3IaT+PadjhAxRWD ydkw== X-Gm-Message-State: ALyK8tJUSyu2RaWYk5lxyXFo7KmAxhqOcaQuKDBPVbLxl+Lob60VkIsExwMPfSzNbURpL1Qa X-Received: by 10.28.167.80 with SMTP id q77mr19318431wme.62.1468557869335; Thu, 14 Jul 2016 21:44:29 -0700 (PDT) Received: from [192.168.207.67] ([62.28.188.194]) by smtp.gmail.com with ESMTPSA id b130sm1249908wmg.3.2016.07.14.21.44.28 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 14 Jul 2016 21:44:28 -0700 (PDT) Subject: [RFC][IPA-VRP] Re-factor tree-vrp to factor out common code To: "gcc-patches@gcc.gnu.org" References: <57886949.8010300@linaro.org> Cc: Richard Biener , Jan Hubicka , Martin Jambor From: kugan Message-ID: <57886A2A.4070703@linaro.org> Date: Fri, 15 Jul 2016 14:44:26 +1000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.8.0 MIME-Version: 1.0 In-Reply-To: <57886949.8010300@linaro.org> X-IsSubscribed: yes Hi, This patch re-factors common code in tree-vrp to be used in early vrp. I am not entirely sure where I should place struct value_range. For now I have placed in tree.h. Thanks, Kugan 2016-07-14 Kugan Vivekanandarajah * tree-ssanames.h (enum value_range_type): Move to tree.h. * tree-vrp.c (struct value_range): Add GTY marker and move to tree.h. (set_value_range_to_varying): Move inline function to tree-vrp.h (symbolic_range_p): Likewise. (change_value_range): New. (vrp_finalize): Add param jump_thread_p and make function global. (execute_vrp): Make function global. (extract_range_from_assert): Likewise. (stmt_interesting_for_vrp): Likewise. (vrp_initialize): Likewise. (vrp_meet): Likewise. (vrp_visit_stmt): Likewise. (vrp_visit_phi_node): Likewise. * tree-vrp.h: New file. >From ce7b251bc5a17ae04be57a7fb1db22e86adac282 Mon Sep 17 00:00:00 2001 From: Kugan Vivekanandarajah Date: Tue, 21 Jun 2016 12:42:44 +1000 Subject: [PATCH 3/6] Refactor vrp --- gcc/tree-ssanames.h | 5 --- gcc/tree-vrp.c | 93 +++++++++++++++++------------------------------------ gcc/tree-vrp.h | 65 +++++++++++++++++++++++++++++++++++++ gcc/tree.h | 31 ++++++++++++++++++ 4 files changed, 125 insertions(+), 69 deletions(-) create mode 100644 gcc/tree-vrp.h diff --git a/gcc/tree-ssanames.h b/gcc/tree-ssanames.h index c81b1a1..8e66ce6 100644 --- a/gcc/tree-ssanames.h +++ b/gcc/tree-ssanames.h @@ -62,11 +62,6 @@ struct GTY ((variable_size)) range_info_def { #define num_ssa_names (vec_safe_length (cfun->gimple_df->ssa_names)) #define ssa_name(i) ((*cfun->gimple_df->ssa_names)[(i)]) - -/* Type of value ranges. See value_range_d In tree-vrp.c for a - description of these types. */ -enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING }; - /* Sets the value range to SSA. */ extern void set_range_info (tree, enum value_range_type, const wide_int_ref &, const wide_int_ref &); diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 23c12b5..8c87c06 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -58,32 +58,7 @@ along with GCC; see the file COPYING3. If not see #include "omp-low.h" #include "target.h" #include "case-cfn-macros.h" - -/* Range of values that can be associated with an SSA_NAME after VRP - has executed. */ -struct value_range -{ - /* Lattice value represented by this range. */ - enum value_range_type type; - - /* Minimum and maximum values represented by this range. These - values should be interpreted as follows: - - - If TYPE is VR_UNDEFINED or VR_VARYING then MIN and MAX must - be NULL. - - - If TYPE == VR_RANGE then MIN holds the minimum value and - MAX holds the maximum value of the range [MIN, MAX]. - - - If TYPE == ANTI_RANGE the variable is known to NOT - take any values in the range [MIN, MAX]. */ - tree min; - tree max; - - /* Set of SSA names whose value ranges are equivalent to this one. - This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE. */ - bitmap equiv; -}; +#include "tree-vrp.h" #define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL } @@ -103,8 +78,6 @@ live_on_edge (edge e, tree name) /* Local functions. */ static int compare_values (tree val1, tree val2); static int compare_values_warnv (tree val1, tree val2, bool *); -static void vrp_meet (value_range *, value_range *); -static void vrp_intersect_ranges (value_range *, value_range *); static tree vrp_evaluate_conditional_warnv_with_ops (enum tree_code, tree, tree, bool, bool *, bool *); @@ -351,21 +324,9 @@ set_value_range_to_undefined (value_range *vr) } -/* Set value range VR to VR_VARYING. */ - -static inline void -set_value_range_to_varying (value_range *vr) -{ - vr->type = VR_VARYING; - vr->min = vr->max = NULL_TREE; - if (vr->equiv) - bitmap_clear (vr->equiv); -} - - /* Set value range VR to {T, MIN, MAX, EQUIV}. */ -static void +void set_value_range (value_range *vr, enum value_range_type t, tree min, tree max, bitmap equiv) { @@ -660,7 +621,7 @@ abs_extent_range (value_range *vr, tree min, tree max) If we have no values ranges recorded (ie, VRP is not running), then return NULL. Otherwise create an empty range if none existed for VAR. */ -static value_range * +value_range * get_value_range (const_tree var) { static const value_range vr_const_varying @@ -717,6 +678,19 @@ get_value_range (const_tree var) return vr; } +/* Update the value range VR to VAR. */ + +void change_value_range (const_tree var, value_range *vr) +{ + unsigned ver = SSA_NAME_VERSION (var); + + if (!vr_value) + return; + + if (ver < num_vr_values) + vr_value[ver] = vr; +} + /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */ static inline bool @@ -751,7 +725,7 @@ vrp_bitmap_equal_p (const_bitmap b1, const_bitmap b2) this function. Do not call update_value_range when NEW_VR is the range object associated with another SSA name. */ -static inline bool +bool update_value_range (const_tree var, value_range *new_vr) { value_range *old_vr; @@ -867,15 +841,6 @@ range_int_cst_singleton_p (value_range *vr) && tree_int_cst_equal (vr->min, vr->max)); } -/* Return true if value range VR involves at least one symbol. */ - -static inline bool -symbolic_range_p (value_range *vr) -{ - return (!is_gimple_min_invariant (vr->min) - || !is_gimple_min_invariant (vr->max)); -} - /* Return the single symbol (an SSA_NAME) contained in T if any, or NULL_TREE otherwise. We only handle additive operations and set NEG to true if the symbol is negated and INV to the invariant part, if any. */ @@ -1461,7 +1426,7 @@ op_with_boolean_value_range_p (tree op) /* Extract value range information from an ASSERT_EXPR EXPR and store it in *VR_P. */ -static void +void extract_range_from_assert (value_range *vr_p, tree expr) { tree var, cond, limit, min, max, type; @@ -4600,7 +4565,6 @@ compare_range_with_value (enum tree_code comp, value_range *vr, tree val, /* Debugging dumps. */ -void dump_value_range (FILE *, value_range *); void debug_value_range (value_range *); void dump_all_value_ranges (FILE *); void debug_all_value_ranges (void); @@ -6828,7 +6792,7 @@ remove_range_assertions (void) /* Return true if STMT is interesting for VRP. */ -static bool +bool stmt_interesting_for_vrp (gimple *stmt) { if (gimple_code (stmt) == GIMPLE_PHI) @@ -6876,7 +6840,7 @@ stmt_interesting_for_vrp (gimple *stmt) /* Initialize local data structures for VRP. */ -static void +void vrp_initialize (void) { basic_block bb; @@ -7862,7 +7826,7 @@ vrp_visit_switch_stmt (gswitch *stmt, edge *taken_edge_p) If STMT produces a varying value, return SSA_PROP_VARYING. */ -static enum ssa_prop_result +enum ssa_prop_result vrp_visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p) { tree def; @@ -8493,7 +8457,7 @@ vrp_intersect_ranges_1 (value_range *vr0, value_range *vr1) bitmap_copy (vr0->equiv, vr1->equiv); } -static void +void vrp_intersect_ranges (value_range *vr0, value_range *vr1) { if (dump_file && (dump_flags & TDF_DETAILS)) @@ -8590,7 +8554,7 @@ vrp_meet_1 (value_range *vr0, value_range *vr1) bitmap_clear (vr0->equiv); } -static void +void vrp_meet (value_range *vr0, value_range *vr1) { if (dump_file && (dump_flags & TDF_DETAILS)) @@ -8615,7 +8579,7 @@ vrp_meet (value_range *vr0, value_range *vr1) edges. If a valid value range can be derived from all the incoming value ranges, set a new range for the LHS of PHI. */ -static enum ssa_prop_result +enum ssa_prop_result vrp_visit_phi_node (gphi *phi) { size_t i; @@ -10164,8 +10128,8 @@ finalize_jump_threads (void) /* Traverse all the blocks folding conditionals with known ranges. */ -static void -vrp_finalize (bool warn_array_bounds_p) +void +vrp_finalize (bool jump_thread_p, bool warn_array_bounds_p) { size_t i; @@ -10206,7 +10170,8 @@ vrp_finalize (bool warn_array_bounds_p) /* We must identify jump threading opportunities before we release the datastructures built by VRP. */ - identify_jump_threads (); + if (jump_thread_p) + identify_jump_threads (); /* Free allocated memory. */ for (i = 0; i < num_vr_values; i++) @@ -10295,7 +10260,7 @@ execute_vrp (bool warn_array_bounds_p) vrp_initialize (); ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node); - vrp_finalize (warn_array_bounds_p); + vrp_finalize (true, warn_array_bounds_p); free_numbers_of_iterations_estimates (cfun); diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h new file mode 100644 index 0000000..bcefaa7 --- /dev/null +++ b/gcc/tree-vrp.h @@ -0,0 +1,65 @@ +/* Support routines for Value Range Propagation (VRP). + Copyright (C) Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "tree-ssa-operands.h" +#include "gimple.h" +#include "tree-ssa-propagate.h" + +#define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL } + +extern void vrp_initialize (void); +extern void vrp_finalize (bool update, bool warn_array_bounds_p); +extern void vrp_intersect_ranges (value_range *vr0, value_range *vr1); +extern void vrp_meet (value_range *vr0, value_range *vr1); +extern enum ssa_prop_result vrp_visit_stmt (gimple *stmt, + edge *taken_edge_p, + tree *output_p); +extern enum ssa_prop_result vrp_visit_phi_node (gphi *phi); +extern bool stmt_interesting_for_vrp (gimple *stmt); + +extern void extract_range_from_assert (value_range *vr_p, tree expr); +extern bool update_value_range (const_tree var, value_range *vr); +extern value_range *get_value_range (const_tree var); +extern void set_value_range (value_range *vr, enum value_range_type t, + tree min, tree max, bitmap equiv); +extern void change_value_range (const_tree var, value_range *new_vr); + +extern void dump_value_range (FILE *, value_range *); + +/* Return true if value range VR involves at least one symbol. */ + +inline bool +symbolic_range_p (value_range *vr) +{ + return (!is_gimple_min_invariant (vr->min) + || !is_gimple_min_invariant (vr->max)); +} + +/* Set value range VR to VR_VARYING. */ + +inline void +set_value_range_to_varying (value_range *vr) +{ + vr->type = VR_VARYING; + vr->min = vr->max = NULL_TREE; + if (vr->equiv) + bitmap_clear (vr->equiv); +} + diff --git a/gcc/tree.h b/gcc/tree.h index 90413fc..8fc4f4f 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -230,6 +230,37 @@ as_internal_fn (combined_fn code) #define TREE_CODE_LENGTH(CODE) tree_code_length[(int) (CODE)] +/* Type of value ranges. See value_range_d In tree-vrp.c for a + description of these types. */ +enum value_range_type { VR_UNDEFINED, VR_RANGE, + VR_ANTI_RANGE, VR_VARYING, VR_LAST }; + +/* Range of values that can be associated with an SSA_NAME after VRP + has executed. */ +struct GTY(()) value_range +{ + /* Lattice value represented by this range. */ + enum value_range_type type; + + /* Minimum and maximum values represented by this range. These + values should be interpreted as follows: + + - If TYPE is VR_UNDEFINED or VR_VARYING then MIN and MAX must + be NULL. + + - If TYPE == VR_RANGE then MIN holds the minimum value and + MAX holds the maximum value of the range [MIN, MAX]. + + - If TYPE == ANTI_RANGE the variable is known to NOT + take any values in the range [MIN, MAX]. */ + tree min; + tree max; + + /* Set of SSA names whose value ranges are equivalent to this one. + This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE. */ + bitmap equiv; +}; + /* Helper macros for math builtins. */ -- 1.9.1