From patchwork Mon Jun 3 02:13:47 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kugan Vivekanandarajah X-Patchwork-Id: 17428 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-gg0-f198.google.com (mail-gg0-f198.google.com [209.85.161.198]) by ip-10-151-82-157.ec2.internal (Postfix) with ESMTPS id 11D9625DF1 for ; Mon, 3 Jun 2013 02:13:56 +0000 (UTC) Received: by mail-gg0-f198.google.com with SMTP id p1sf4138810ggn.9 for ; Sun, 02 Jun 2013 19:13:55 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=x-beenthere:x-forwarded-to:x-forwarded-for:delivered-to:message-id :date:from:user-agent:mime-version:to:cc:subject:x-gm-message-state :x-original-sender:x-original-authentication-results:precedence :mailing-list:list-id:x-google-group-id:list-post:list-help :list-archive:list-unsubscribe:content-type; bh=GjCnV2bsMITzH3/In+xL09BBCLTmONvXffZCyxUHvyg=; b=p0/TS2l7RGOC280nu8TiVlE74wztrX4tvMqqvCY5idHkWlqYn+EHA7r+PTNGEOFae/ eMhFjuj1CTQ7SXAPlmu1F+P6MY0PSbq3KkJdzQT2+HjhY+/6dyIqn+iQe7y0yF3NTTF2 454/ZIdE058a8ZWkHzIbjkTMTGsVnZUk8szuJBdaskRs92Mdn/b9yIBKTtrqW4FqJJd+ WLjUQX9YIH8XJ7DHudv9xgqr5hKodEkLiN+qgRxS0FPBjkx4rB22i5WR32t4x+cZLz5Q jk1vvih3WFAcEhYzA7FQNuOJ4+uCsW4qYpoa9Gq55d+KCTup+TTw0uvffOTlViBQvBt2 WMgA== X-Received: by 10.236.189.241 with SMTP id c77mr12186014yhn.17.1370225635641; Sun, 02 Jun 2013 19:13:55 -0700 (PDT) X-BeenThere: patchwork-forward@linaro.org Received: by 10.49.74.234 with SMTP id x10ls1806040qev.14.gmail; Sun, 02 Jun 2013 19:13:55 -0700 (PDT) X-Received: by 10.220.105.9 with SMTP id r9mr16057599vco.60.1370225635368; Sun, 02 Jun 2013 19:13:55 -0700 (PDT) Received: from mail-vb0-x235.google.com (mail-vb0-x235.google.com [2607:f8b0:400c:c02::235]) by mx.google.com with ESMTPS id sz6si393866vdc.23.2013.06.02.19.13.55 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sun, 02 Jun 2013 19:13:55 -0700 (PDT) Received-SPF: neutral (google.com: 2607:f8b0:400c:c02::235 is neither permitted nor denied by best guess record for domain of patch+caf_=patchwork-forward=linaro.org@linaro.org) client-ip=2607:f8b0:400c:c02::235; Received: by mail-vb0-f53.google.com with SMTP id p13so2221975vbe.26 for ; Sun, 02 Jun 2013 19:13:55 -0700 (PDT) X-Received: by 10.52.53.36 with SMTP id y4mr13386122vdo.51.1370225634988; Sun, 02 Jun 2013 19:13:54 -0700 (PDT) X-Forwarded-To: patchwork-forward@linaro.org X-Forwarded-For: patch@linaro.org patchwork-forward@linaro.org Delivered-To: patches@linaro.org Received: by 10.221.10.206 with SMTP id pb14csp61367vcb; Sun, 2 Jun 2013 19:13:54 -0700 (PDT) X-Received: by 10.68.217.197 with SMTP id pa5mr21740766pbc.127.1370225633718; Sun, 02 Jun 2013 19:13:53 -0700 (PDT) Received: from mail-pd0-f173.google.com (mail-pd0-f173.google.com [209.85.192.173]) by mx.google.com with ESMTPS id ye10si38988335pab.67.2013.06.02.19.13.53 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sun, 02 Jun 2013 19:13:53 -0700 (PDT) Received-SPF: neutral (google.com: 209.85.192.173 is neither permitted nor denied by best guess record for domain of kugan.vivekanandarajah@linaro.org) client-ip=209.85.192.173; Received: by mail-pd0-f173.google.com with SMTP id v14so4942202pde.4 for ; Sun, 02 Jun 2013 19:13:53 -0700 (PDT) X-Received: by 10.66.118.104 with SMTP id kl8mr21975029pab.182.1370225633035; Sun, 02 Jun 2013 19:13:53 -0700 (PDT) Received: from [192.168.1.4] (27-33-114-215.tpgi.com.au. [27.33.114.215]) by mx.google.com with ESMTPSA id qi1sm60658437pac.21.2013.06.02.19.13.49 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sun, 02 Jun 2013 19:13:52 -0700 (PDT) Message-ID: <51ABFBDB.6040205@linaro.org> Date: Mon, 03 Jun 2013 11:43:47 +0930 From: Kugan User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130510 Thunderbird/17.0.6 MIME-Version: 1.0 To: "gcc-patches@gcc.gnu.org" , patches@linaro.org CC: Richard Biener , rdsandiford@googlemail.com, ramana.radhakrishnan@arm.com, Richard Earnshaw Subject: [PATCH][1 of 2] Add value range info to SSA_NAME for zero sign extension elimination in RTL X-Gm-Message-State: ALoCoQkdRav4tJpf0+92rwd7fDRDLoUhcTFw5ZaqRivD3kWRfVZ9m1+pGHiV//cBmQfrCEFygBUh X-Original-Sender: kugan.vivekanandarajah@linaro.org X-Original-Authentication-Results: mx.google.com; spf=neutral (google.com: 2607:f8b0:400c:c02::235 is neither permitted nor denied by best guess record for domain of patch+caf_=patchwork-forward=linaro.org@linaro.org) smtp.mail=patch+caf_=patchwork-forward=linaro.org@linaro.org Precedence: list Mailing-list: list patchwork-forward@linaro.org; contact patchwork-forward+owners@linaro.org List-ID: X-Google-Group-Id: 836684582541 List-Post: , List-Help: , List-Archive: List-Unsubscribe: , Hi, This patch adds value range information to tree SSA_NAME during Value Range Propagation (VRP) pass in preparation to removes some of the redundant sign/zero extensions during RTL expansion. This is based on the original patch posted in http://gcc.gnu.org/ml/gcc-patches/2013-05/msg00610.html and addresses the review comments of Richard Biener. Tested on X86_64 and ARM. I would like review comments on this. Thanks, Kugan +2013-06-03 Kugan Vivekanandarajah + + * gcc/gcc/tree-flow.h: Declared structure range_info_def and function + definition for mark_range_info_unknown. + * gcc/tree-ssa-alias.c (dump_alias_info) : Check pointer type + * gcc/tree-ssanames.c (make_ssa_name_fn) : Check pointer type in + initialize. + * (mark_range_info_unknown) : New function. + * (duplicate_ssa_name_range_info) : Likewise. + * (duplicate_ssa_name_fn) : Check pointer type and call correct + duplicate function. + * gcc/tree-vrp.c (extract_exp_value_range): New function. + * (simplify_stmt_using_ranges): Call extract_exp_value_range and + tree_ssa_set_value_range. + * gcc/tree.c (tree_ssa_set_value_range): New function. + * gcc/tree.h (SSA_NAME_PTR_INFO) : changed to access via union + * gcc/tree.h (SSA_NAME_RANGE_INFO) : New macro + diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index 24fcfbf..dd4e2f5 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -147,6 +147,19 @@ struct GTY(()) ptr_info_def unsigned int misalign; }; +/* Value range information for SSA_NAMEs representing non-pointer variables. */ + +struct GTY (()) range_info_def { + /* Set to true if VR_RANGE and false if VR_ANTI_RANGE. */ + bool vr_range; + /* Minmum for value range. */ + double_int min; + /* Maximum for value range. */ + double_int max; + /* Set to true if range is valid. */ + bool valid; +}; + /* It is advantageous to avoid things like life analysis for variables which do not need PHI nodes. This enum describes whether or not a particular @@ -532,6 +545,7 @@ extern void replace_ssa_name_symbol (tree, tree); extern bool get_ptr_info_alignment (struct ptr_info_def *, unsigned int *, unsigned int *); extern void mark_ptr_info_alignment_unknown (struct ptr_info_def *); +extern void mark_range_info_unknown (struct range_info_def *); extern void set_ptr_info_alignment (struct ptr_info_def *, unsigned int, unsigned int); extern void adjust_ptr_info_misalignment (struct ptr_info_def *, diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c index 2ecd139..8ccecb5 100644 --- a/gcc/tree-ssa-alias.c +++ b/gcc/tree-ssa-alias.c @@ -404,6 +404,7 @@ dump_alias_info (FILE *file) struct ptr_info_def *pi; if (ptr == NULL_TREE + || !POINTER_TYPE_P (TREE_TYPE (ptr)) || SSA_NAME_IN_FREE_LIST (ptr)) continue; diff --git a/gcc/tree-ssanames.c b/gcc/tree-ssanames.c index 0a405ce..420ae00 100644 --- a/gcc/tree-ssanames.c +++ b/gcc/tree-ssanames.c @@ -151,7 +151,11 @@ make_ssa_name_fn (struct function *fn, tree var, gimple stmt) SET_SSA_NAME_VAR_OR_IDENTIFIER (t, var); } SSA_NAME_DEF_STMT (t) = stmt; - SSA_NAME_PTR_INFO (t) = NULL; + if (POINTER_TYPE_P (TREE_TYPE (t))) + SSA_NAME_PTR_INFO (t) = NULL; + else + SSA_NAME_RANGE_INFO (t) = NULL; + SSA_NAME_IN_FREE_LIST (t) = 0; SSA_NAME_IS_DEFAULT_DEF (t) = 0; imm = &(SSA_NAME_IMM_USE_NODE (t)); @@ -266,6 +270,14 @@ mark_ptr_info_alignment_unknown (struct ptr_info_def *pi) pi->misalign = 0; } +/* Set the range described by RI has invalid values. */ + +void +mark_range_info_unknown (struct range_info_def *ri) +{ + ri->valid = false; +} + /* Store the the power-of-two byte alignment and the deviation from that alignment of pointer described by PI to ALIOGN and MISALIGN respectively. */ @@ -359,6 +371,26 @@ duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info) SSA_NAME_PTR_INFO (name) = new_ptr_info; } +/* Creates a duplicate of the range_info_def at RANGE_INFO for use by + the SSA name NAME. */ +void +duplicate_ssa_name_range_info (tree name, struct range_info_def *range_info) +{ + struct range_info_def *new_range_info; + + gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); + gcc_assert (!SSA_NAME_RANGE_INFO (name)); + + if (!range_info) + return; + + new_range_info = ggc_alloc_range_info_def (); + *new_range_info = *range_info; + + SSA_NAME_RANGE_INFO (name) = new_range_info; +} + + /* Creates a duplicate of a ssa name NAME tobe defined by statement STMT in function FN. */ @@ -367,10 +399,20 @@ tree duplicate_ssa_name_fn (struct function *fn, tree name, gimple stmt) { tree new_name = copy_ssa_name_fn (fn, name, stmt); - struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name); + if (POINTER_TYPE_P (TREE_TYPE (name))) + { + struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name); + + if (old_ptr_info) + duplicate_ssa_name_ptr_info (new_name, old_ptr_info); + } + else + { + struct range_info_def *old_range_info = SSA_NAME_RANGE_INFO (name); - if (old_ptr_info) - duplicate_ssa_name_ptr_info (new_name, old_ptr_info); + if (old_range_info) + duplicate_ssa_name_range_info (new_name, old_range_info); + } return new_name; } diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index ec7ef8f..36ec5fa 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -8950,6 +8950,62 @@ simplify_float_conversion_using_ranges (gimple_stmt_iterator *gsi, gimple stmt) return true; } +/* Extract the value range of assigned exprassion for GIMPLE_ASSIGN stmt. + If the extracted value range is valid, return true else return + false. */ +static bool +extract_exp_value_range (gimple stmt, value_range_t *vr) +{ + gcc_assert (is_gimple_assign (stmt)); + tree rhs1 = gimple_assign_rhs1 (stmt); + tree lhs = gimple_assign_lhs (stmt); + enum tree_code rhs_code = gimple_assign_rhs_code (stmt); + + /* Skip if the lhs is not integeral. */ + if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs)) + || CONSTANT_CLASS_P (lhs)) + return false; + + if (TREE_CODE_CLASS (rhs_code) == tcc_unary) + { + /* Get the value range for the expression. */ + if ((rhs_code == NOP_EXPR || rhs_code == CONVERT_EXPR) + && (TREE_CODE (rhs1) == SSA_NAME)) + { + value_range_t *temp = get_value_range (rhs1); + *vr = *temp; + } + else + extract_range_from_unary_expr (vr, + gimple_assign_rhs_code (stmt), + TREE_TYPE (rhs1), rhs1); + } + /* Process binary assign stmt. */ + else if (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) + == tcc_binary) + { + tree rhs2 = gimple_assign_rhs2 (stmt); + gcc_assert (rhs1); + gcc_assert (rhs2); + + /* Get the value range for the expression. */ + extract_range_from_binary_expr (vr, + gimple_assign_rhs_code (stmt), + TREE_TYPE (rhs1), rhs1, rhs2); + } + + /* Is the laue range valid. */ + if ((vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE) + && !is_overflow_infinity (vr->min) + && !is_overflow_infinity (vr->max) + && (TREE_CODE (vr->min) == INTEGER_CST) + && (TREE_CODE (vr->max) == INTEGER_CST)) + return true; + else + return false; +} + + /* Simplify STMT using ranges if possible. */ static bool @@ -8960,6 +9016,23 @@ simplify_stmt_using_ranges (gimple_stmt_iterator *gsi) { enum tree_code rhs_code = gimple_assign_rhs_code (stmt); tree rhs1 = gimple_assign_rhs1 (stmt); + tree lhs = gimple_assign_lhs (stmt); + + /* Set value range information for ssa. */ + if (!POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt))) + && (TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME) + && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt))) + && !SSA_NAME_RANGE_INFO (lhs)) + { + value_range_t vr = VR_INITIALIZER; + + /* If value range is valid, set that. */ + if (extract_exp_value_range (stmt, &vr)) + tree_ssa_set_value_range (lhs, + tree_to_double_int (vr.min), + tree_to_double_int (vr.max), + vr.type == VR_RANGE); + } switch (rhs_code) { diff --git a/gcc/tree.c b/gcc/tree.c index 6c71025..bf8c816 100644 --- a/gcc/tree.c +++ b/gcc/tree.c @@ -270,6 +270,31 @@ const char * const omp_clause_code_name[] = }; +/* Set zero/sign extension redundant for ssa def stmt. */ + +void +tree_ssa_set_value_range (tree ssa, double_int min, + double_int max, bool vr_range) +{ + gcc_assert (!POINTER_TYPE_P (TREE_TYPE (ssa))); + gcc_assert (TREE_CODE (ssa) == SSA_NAME); + range_info_def *ri = SSA_NAME_RANGE_INFO (ssa); + + /* Allocate if not available. */ + if (ri == NULL) + { + ri = ggc_alloc_cleared_range_info_def (); + mark_range_info_unknown (ri); + SSA_NAME_RANGE_INFO (ssa) = ri; + } + + /* Set the values. */ + ri->valid = true; + ri->min = min; + ri->max = max; + ri->vr_range = vr_range; +} + /* Return the tree node structure used by tree code CODE. */ static inline enum tree_node_structure_enum diff --git a/gcc/tree.h b/gcc/tree.h index 1d2b252..7629de8 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -1950,10 +1950,19 @@ struct GTY(()) tree_exp { /* Attributes for SSA_NAMEs for pointer-type variables. */ #define SSA_NAME_PTR_INFO(N) \ - SSA_NAME_CHECK (N)->ssa_name.ptr_info + SSA_NAME_CHECK (N)->ssa_name.vrp.ptr_info + +/* Value range info Attributes for SSA_NAMEs of non pointer-type variables. */ +#define SSA_NAME_RANGE_INFO(N) \ + SSA_NAME_CHECK (N)->ssa_name.vrp.range_info + +/* Sets the value range extreacted from VRP into ssa. */ +void tree_ssa_set_value_range (tree ssa, double_int min, + double_int max, bool vr_range); /* Defined in tree-flow.h. */ struct ptr_info_def; +struct range_info_def; /* Immediate use linking structure. This structure is used for maintaining a doubly linked list of uses of an SSA_NAME. */ @@ -1969,6 +1978,12 @@ typedef struct GTY(()) ssa_use_operand_d { tree *GTY((skip(""))) use; } ssa_use_operand_t; + +/* The garbage collector needs to know the interpretation of the + value range info in the tree_ssa_name. */ +#define TREE_SSA_PTR_INFO (0) +#define TREE_SSA_RANGE_INFO (1) + /* Return the immediate_use information for an SSA_NAME. */ #define SSA_NAME_IMM_USE_NODE(NODE) SSA_NAME_CHECK (NODE)->ssa_name.imm_uses @@ -1981,8 +1996,13 @@ struct GTY(()) tree_ssa_name { /* Statement that defines this SSA name. */ gimple def_stmt; - /* Pointer attributes used for alias analysis. */ - struct ptr_info_def *ptr_info; + /* Value range information. */ + union vrp_info_type { + /* Pointer attributes used for alias analysis. */ + struct GTY ((tag ("TREE_SSA_PTR_INFO"))) ptr_info_def *ptr_info; + /* Value range attributes used for zero/sign extension elimination. */ + struct GTY ((tag ("TREE_SSA_RANGE_INFO"))) range_info_def *range_info; + } GTY ((desc ("%1.def_stmt && !POINTER_TYPE_P (TREE_TYPE ((tree)&%1))"))) vrp; /* Immediate uses list for this SSA_NAME. */ struct ssa_use_operand_d imm_uses;