| Message ID | 51BE66E8.3010401@linaro.org |
|---|---|
| State | New |
| Headers | show |
On Mon, 17 Jun 2013, Kugan wrote: > Can you please help to review this patch? Richard reviewed the original patch > and asked it to be split into two parts. Also, he wanted a review from RTL > maintainer for the RTL changes. > > Thanks, > Kugan > > On 03/06/13 11:43, Kugan wrote: > > 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 <kuganv@linaro.org> > > + > > + * 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 These go to gcc/ChangeLog and thus do not need the gcc/ prefix. +/* 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; +}; this way you waste a lot of padding, so please move the two bool members next to each other. +/* 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); ... @@ -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 (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); + } This looks overly complicated to me. In vrp_finalize you can simply do for (i = 0; i < num_vr_values; i++) if (vr_value[i]) { tree name = ssa_name (i); if (POINTER_TYPE_P (name)) continue; if (vr_value[i].type == VR_RANGE || vr_value[i].type == VR_ANTI_RANGE) tree_ssa_set_value_range (name, tree_to_double_int (vr_value[i].min), tree_to_double_int (vr_value[i].max), vr_value[i].type == VR_RANGE); } that is, transfer directly from the lattice. +/* 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) +{ The comment needs updating. Also this doesn't belong in tree.c but in tree-ssanames.c with a more suitable name like set_range_info (). +/* 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) no need for those, just use GTY ((tag ("0")) and "1". + /* Value range information. */ /* SSA name annotations. */ + 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. */ /* Value range information. */ + 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; why do you need to test %1.def_stmt here? Please add a way to dump the associated range information (I'm fine doing it at the time and with the same flags we dump SSA_NAME_PTR_INFO, see gimple-pretty-print.c. Sorry for taking so long to review this again. Thanks, Richard.
On 17/06/13 18:33, Richard Biener wrote: > On Mon, 17 Jun 2013, Kugan wrote: > +/* 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); > ... > @@ -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 (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); > + } > > This looks overly complicated to me. In vrp_finalize you can simply do > > for (i = 0; i < num_vr_values; i++) > if (vr_value[i]) > { > tree name = ssa_name (i); > if (POINTER_TYPE_P (name)) > continue; > if (vr_value[i].type == VR_RANGE > || vr_value[i].type == VR_ANTI_RANGE) > tree_ssa_set_value_range (name, tree_to_double_int > (vr_value[i].min), tree_to_double_int (vr_value[i].max), vr_value[i].type > == VR_RANGE); > } > Thanks Richard for taking time to review it. I was doing something like what you are suggesting earlier but noticed some problems and that’s the reason why I changed. For example, for the following testcase from the test suite, unsigned long l = (unsigned long)-2; unsigned short s; int main () { long t = l + 1; s = l; if (s != (unsigned short) -2) abort (); exit (0); } with the following gimple stmts main () { short unsigned int s.1; long unsigned int l.0; ;; basic block 2, loop depth 0 ;; pred: ENTRY l.0_2 = l; s.1_3 = (short unsigned int) l.0_2; s = s.1_3; if (s.1_3 != 65534) goto <bb 3>; else goto <bb 4>; ;; succ: 3 ;; 4 ;; basic block 3, loop depth 0 ;; pred: 2 abort (); ;; succ: ;; basic block 4, loop depth 0 ;; pred: 2 exit (0); ;; succ: } has the following value range. l.0_2: VARYING s.1_3: [0, +INF] From zero/sign extension point of view, the variable s.1_3 is expected to have a value that will overflow (or varying) as this is what is assigned to a smaller variable. extract_range_from_assignment initially calculates the value range as VARYING but later changed to [0, +INF] by extract_range_basic. What I need here is the value that will be assigned from the rhs expression and not the value that we will have with proper assignment. I understand that the above code of mine needs to be changed but not convinced about the best way to do that. I can possibly re-factor extract_range_from_assignment to give me this information with an additional argument. Could you kindly let me know your preference. > > /* SSA name annotations. */ > > + 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. > */ > > /* Value range information. */ > > + 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; > > why do you need to test %1.def_stmt here? I have seen some tree_ssa_name with def_stmt NULL. Thats why I added this. Is that something that should never happen. Thanks, Kugan
On Wed, Jul 3, 2013 at 2:25 PM, Kugan <kugan.vivekanandarajah@linaro.org> wrote: > On 17/06/13 18:33, Richard Biener wrote: >> >> On Mon, 17 Jun 2013, Kugan wrote: >> +/* 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); >> ... >> @@ -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 (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); >> + } >> >> This looks overly complicated to me. In vrp_finalize you can simply do >> >> for (i = 0; i < num_vr_values; i++) >> if (vr_value[i]) >> { >> tree name = ssa_name (i); >> if (POINTER_TYPE_P (name)) >> continue; >> if (vr_value[i].type == VR_RANGE >> || vr_value[i].type == VR_ANTI_RANGE) >> tree_ssa_set_value_range (name, tree_to_double_int >> (vr_value[i].min), tree_to_double_int (vr_value[i].max), vr_value[i].type >> == VR_RANGE); >> } >> > > Thanks Richard for taking time to review it. > > I was doing something like what you are suggesting earlier but noticed some > problems and that’s the reason why I changed. > > For example, for the following testcase from the test suite, > > unsigned long l = (unsigned long)-2; > unsigned short s; > > int main () { > long t = l + 1; > s = l; > if (s != (unsigned short) -2) > abort (); > exit (0); > } > > with the following gimple stmts > > main () > { > short unsigned int s.1; > long unsigned int l.0; > > ;; basic block 2, loop depth 0 > ;; pred: ENTRY > l.0_2 = l; > s.1_3 = (short unsigned int) l.0_2; > s = s.1_3; > if (s.1_3 != 65534) > goto <bb 3>; > else > goto <bb 4>; > ;; succ: 3 > ;; 4 > > ;; basic block 3, loop depth 0 > ;; pred: 2 > abort (); > ;; succ: > > ;; basic block 4, loop depth 0 > ;; pred: 2 > exit (0); > ;; succ: > > } > > > > has the following value range. > > l.0_2: VARYING > s.1_3: [0, +INF] > > > From zero/sign extension point of view, the variable s.1_3 is expected to > have a value that will overflow (or varying) as this is what is assigned to > a smaller variable. extract_range_from_assignment initially calculates the > value range as VARYING but later changed to [0, +INF] by > extract_range_basic. What I need here is the value that will be assigned > from the rhs expression and not the value that we will have with proper > assignment. I don't understand this. The relevant statement is s.1_3 = (short unsigned int) l.0_2; right? You have value-ranges for both s.1_3 and l.0_2 as above. And you clearly cannot optimize the truncation away (and if you could, you wond't need value-range information for that fact). > I understand that the above code of mine needs to be changed but not > convinced about the best way to do that. > > I can possibly re-factor extract_range_from_assignment to give me this > information with an additional argument. Could you kindly let me know your > preference. > > > >> >> /* SSA name annotations. */ >> >> + 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. >> */ >> >> /* Value range information. */ >> >> + 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; >> >> why do you need to test %1.def_stmt here? > > > > I have seen some tree_ssa_name with def_stmt NULL. Thats why I added this. > Is that something that should never happen. It should never happen - they should have a GIMPLE_NOP. +void +set_range_info (tree name, double_int min, + double_int max, bool vr_range) you have some whitespace issues here (please properly use tabs) + /* Allocate if not available. */ + if (ri == NULL) + { + ri = ggc_alloc_cleared_range_info_def (); + mark_range_info_unknown (ri); that looks superfluous to me. + SSA_NAME_RANGE_INFO (name) = ri; - /* 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 ("0"))) ptr_info_def *ptr_info; + /* Value range attributes used for zero/sign extension elimination. */ + struct GTY ((tag ("1"))) range_info_def *range_info; + } GTY ((desc ("%1.def_stmt && !POINTER_TYPE_P (TREE_TYPE ((tree)&%1))"))) vrp; please change vrp_info_type and vrp to other names - this is not vrp specific info after all, I suggest ssa_name_info_type and info. The genric bits otherwise look ok to me, the VRP bits still look wrong (see my above question) and need explanation. Thanks, Richard. > > Thanks, > Kugan
Thanks Richard for reviewing. On 02/09/13 22:15, Richard Biener wrote: > On Wed, Jul 3, 2013 at 2:25 PM, Kugan <kugan.vivekanandarajah@linaro.org> wrote: >> On 17/06/13 18:33, Richard Biener wrote: >>> >>> On Mon, 17 Jun 2013, Kugan wrote: >>> +/* 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); >>> ... >>> @@ -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 (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); >>> + } >>> >>> This looks overly complicated to me. In vrp_finalize you can simply do >>> >>> for (i = 0; i < num_vr_values; i++) >>> if (vr_value[i]) >>> { >>> tree name = ssa_name (i); >>> if (POINTER_TYPE_P (name)) >>> continue; >>> if (vr_value[i].type == VR_RANGE >>> || vr_value[i].type == VR_ANTI_RANGE) >>> tree_ssa_set_value_range (name, tree_to_double_int >>> (vr_value[i].min), tree_to_double_int (vr_value[i].max), vr_value[i].type >>> == VR_RANGE); >>> } >>> >> >> Thanks Richard for taking time to review it. >> >> I was doing something like what you are suggesting earlier but noticed some >> problems and that’s the reason why I changed. >> >> For example, for the following testcase from the test suite, >> >> unsigned long l = (unsigned long)-2; >> unsigned short s; >> >> int main () { >> long t = l + 1; >> s = l; >> if (s != (unsigned short) -2) >> abort (); >> exit (0); >> } >> >> with the following gimple stmts >> >> main () >> { >> short unsigned int s.1; >> long unsigned int l.0; >> >> ;; basic block 2, loop depth 0 >> ;; pred: ENTRY >> l.0_2 = l; >> s.1_3 = (short unsigned int) l.0_2; >> s = s.1_3; >> if (s.1_3 != 65534) >> goto <bb 3>; >> else >> goto <bb 4>; >> ;; succ: 3 >> ;; 4 >> >> ;; basic block 3, loop depth 0 >> ;; pred: 2 >> abort (); >> ;; succ: >> >> ;; basic block 4, loop depth 0 >> ;; pred: 2 >> exit (0); >> ;; succ: >> >> } >> >> >> >> has the following value range. >> >> l.0_2: VARYING >> s.1_3: [0, +INF] >> >> >> From zero/sign extension point of view, the variable s.1_3 is expected to >> have a value that will overflow (or varying) as this is what is assigned to >> a smaller variable. extract_range_from_assignment initially calculates the >> value range as VARYING but later changed to [0, +INF] by >> extract_range_basic. What I need here is the value that will be assigned >> from the rhs expression and not the value that we will have with proper >> assignment. > > I don't understand this. The relevant statement is > > s.1_3 = (short unsigned int) l.0_2; > > right? You have value-ranges for both s.1_3 and l.0_2 as above. And > you clearly cannot optimize the truncation away (and if you could, > you wond't need value-range information for that fact). > This is true. But just by looking at the value range of s.1.3 we will only see [0 +INF], as we are transferring directly from the lattice to lhs its value range. [0, +INF] here tells us vrp_val_is_max and it is not is_positive_overflow_infinity (or varying). Thats why we need to get the value range of RHS expression which will tell us the actual range. We can then use this range and see of we can fit it to lhs type without truncation. >> I understand that the above code of mine needs to be changed but not >> convinced about the best way to do that. >> >> I can possibly re-factor extract_range_from_assignment to give me this >> information with an additional argument. Could you kindly let me know your >> preference. >> >> >> >>> >>> /* SSA name annotations. */ >>> >>> + 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. >>> */ >>> >>> /* Value range information. */ >>> >>> + 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; >>> >>> why do you need to test %1.def_stmt here? >> >> >> >> I have seen some tree_ssa_name with def_stmt NULL. Thats why I added this. >> Is that something that should never happen. > > It should never happen - they should have a GIMPLE_NOP. > I am seeing def_stmt of NULL for TREE_NOTHROW node. debug_tree dumps the following in this case: <ssa_name 0x2aaaabd89af8 nothrow var <var_decl 0x2aaaadb384c0 t>def_stmt version 11 in-free-list> > +void > +set_range_info (tree name, double_int min, > + double_int max, bool vr_range) > > you have some whitespace issues here (please properly use tabs) > I will change it. > + /* Allocate if not available. */ > + if (ri == NULL) > + { > + ri = ggc_alloc_cleared_range_info_def (); > + mark_range_info_unknown (ri); > > that looks superfluous to me. > > + SSA_NAME_RANGE_INFO (name) = ri; > > - /* 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 ("0"))) ptr_info_def *ptr_info; > + /* Value range attributes used for zero/sign extension elimination. */ > + struct GTY ((tag ("1"))) range_info_def *range_info; > + } GTY ((desc ("%1.def_stmt && !POINTER_TYPE_P (TREE_TYPE > ((tree)&%1))"))) vrp; > > please change vrp_info_type and vrp to other names - this is not vrp > specific info > after all, I suggest ssa_name_info_type and info. > I will change this too. > The genric bits otherwise look ok to me, the VRP bits still look wrong (see my > above question) and need explanation. > > Thanks, > Richard. > >> >> Thanks, >> Kugan Thanks, Kugan
On 9/3/13 2:15 PM, Kugan wrote: > Thanks Richard for reviewing. > > On 02/09/13 22:15, Richard Biener wrote: >> On Wed, Jul 3, 2013 at 2:25 PM, Kugan >> <kugan.vivekanandarajah@linaro.org> wrote: >>> On 17/06/13 18:33, Richard Biener wrote: >>>> >>>> On Mon, 17 Jun 2013, Kugan wrote: >>>> +/* 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); >>>> ... >>>> @@ -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 (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); >>>> + } >>>> >>>> This looks overly complicated to me. In vrp_finalize you can simply do >>>> >>>> for (i = 0; i < num_vr_values; i++) >>>> if (vr_value[i]) >>>> { >>>> tree name = ssa_name (i); >>>> if (POINTER_TYPE_P (name)) >>>> continue; >>>> if (vr_value[i].type == VR_RANGE >>>> || vr_value[i].type == VR_ANTI_RANGE) >>>> tree_ssa_set_value_range (name, tree_to_double_int >>>> (vr_value[i].min), tree_to_double_int (vr_value[i].max), >>>> vr_value[i].type >>>> == VR_RANGE); >>>> } >>>> >>> >>> Thanks Richard for taking time to review it. >>> >>> I was doing something like what you are suggesting earlier but >>> noticed some >>> problems and that’s the reason why I changed. >>> >>> For example, for the following testcase from the test suite, >>> >>> unsigned long l = (unsigned long)-2; >>> unsigned short s; >>> >>> int main () { >>> long t = l + 1; >>> s = l; >>> if (s != (unsigned short) -2) >>> abort (); >>> exit (0); >>> } >>> >>> with the following gimple stmts >>> >>> main () >>> { >>> short unsigned int s.1; >>> long unsigned int l.0; >>> >>> ;; basic block 2, loop depth 0 >>> ;; pred: ENTRY >>> l.0_2 = l; >>> s.1_3 = (short unsigned int) l.0_2; >>> s = s.1_3; >>> if (s.1_3 != 65534) >>> goto <bb 3>; >>> else >>> goto <bb 4>; >>> ;; succ: 3 >>> ;; 4 >>> >>> ;; basic block 3, loop depth 0 >>> ;; pred: 2 >>> abort (); >>> ;; succ: >>> >>> ;; basic block 4, loop depth 0 >>> ;; pred: 2 >>> exit (0); >>> ;; succ: >>> >>> } >>> >>> >>> >>> has the following value range. >>> >>> l.0_2: VARYING >>> s.1_3: [0, +INF] >>> >>> >>> From zero/sign extension point of view, the variable s.1_3 is >>> expected to >>> have a value that will overflow (or varying) as this is what is >>> assigned to >>> a smaller variable. extract_range_from_assignment initially >>> calculates the >>> value range as VARYING but later changed to [0, +INF] by >>> extract_range_basic. What I need here is the value that will be assigned >>> from the rhs expression and not the value that we will have with proper >>> assignment. >> >> I don't understand this. The relevant statement is >> >> s.1_3 = (short unsigned int) l.0_2; >> >> right? You have value-ranges for both s.1_3 and l.0_2 as above. And >> you clearly cannot optimize the truncation away (and if you could, >> you wond't need value-range information for that fact). >> > This is true. But just by looking at the value range of s.1.3 we will > only see [0 +INF], as we are transferring directly from the lattice to > lhs its value range. > > [0, +INF] here tells us vrp_val_is_max and it is not > is_positive_overflow_infinity (or varying). Thats why we need to get the > value range of RHS expression which will tell us the actual range. We > can then use this range and see of we can fit it to lhs type without > truncation. Well, my point is you want to look at the l.0_2 value-range for this. Storing the l.0_2 value-range for s.1_3 is wrong. >>> I understand that the above code of mine needs to be changed but not >>> convinced about the best way to do that. >>> >>> I can possibly re-factor extract_range_from_assignment to give me this >>> information with an additional argument. Could you kindly let me know >>> your >>> preference. >>> >>> >>> >>>> >>>> /* SSA name annotations. */ >>>> >>>> + 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. >>>> */ >>>> >>>> /* Value range information. */ >>>> >>>> + 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; >>>> >>>> why do you need to test %1.def_stmt here? >>> >>> >>> >>> I have seen some tree_ssa_name with def_stmt NULL. Thats why I added >>> this. >>> Is that something that should never happen. >> >> It should never happen - they should have a GIMPLE_NOP. >> > > I am seeing def_stmt of NULL for TREE_NOTHROW node. > debug_tree dumps the following in this case: > > <ssa_name 0x2aaaabd89af8 nothrow var <var_decl 0x2aaaadb384c0 t>def_stmt > > version 11 in-free-list> This is an invalid SSA name (in-free-list) that has been released. You shouldn't look at it at all. Richard. >> +void >> +set_range_info (tree name, double_int min, >> + double_int max, bool vr_range) >> >> you have some whitespace issues here (please properly use tabs) >> > > I will change it. > >> + /* Allocate if not available. */ >> + if (ri == NULL) >> + { >> + ri = ggc_alloc_cleared_range_info_def (); >> + mark_range_info_unknown (ri); >> >> that looks superfluous to me. >> >> + SSA_NAME_RANGE_INFO (name) = ri; >> >> - /* 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 ("0"))) ptr_info_def *ptr_info; >> + /* Value range attributes used for zero/sign extension >> elimination. */ >> + struct GTY ((tag ("1"))) range_info_def *range_info; >> + } GTY ((desc ("%1.def_stmt && !POINTER_TYPE_P (TREE_TYPE >> ((tree)&%1))"))) vrp; >> >> please change vrp_info_type and vrp to other names - this is not vrp >> specific info >> after all, I suggest ssa_name_info_type and info. >> > > I will change this too. >> The genric bits otherwise look ok to me, the VRP bits still look wrong >> (see my >> above question) and need explanation. >> >> Thanks, >> Richard. >> >>> >>> Thanks, >>> Kugan > > > Thanks, > Kugan >
On 06/09/13 16:16, Richard Biener wrote: > On 9/3/13 2:15 PM, Kugan wrote: >> Thanks Richard for reviewing. >> >> On 02/09/13 22:15, Richard Biener wrote: >>> On Wed, Jul 3, 2013 at 2:25 PM, Kugan >>> <kugan.vivekanandarajah@linaro.org> wrote: >>>> On 17/06/13 18:33, Richard Biener wrote: >>>>> >>>>> On Mon, 17 Jun 2013, Kugan wrote: >>>>> +/* 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 [snip] >>>>> >>>>> for (i = 0; i < num_vr_values; i++) >>>>> if (vr_value[i]) >>>>> { >>>>> tree name = ssa_name (i); >>>>> if (POINTER_TYPE_P (name)) >>>>> continue; >>>>> if (vr_value[i].type == VR_RANGE >>>>> || vr_value[i].type == VR_ANTI_RANGE) >>>>> tree_ssa_set_value_range (name, tree_to_double_int >>>>> (vr_value[i].min), tree_to_double_int (vr_value[i].max), >>>>> vr_value[i].type >>>>> == VR_RANGE); >>>>> } >>>>> >>>> >>>> Thanks Richard for taking time to review it. >>>> >>>> I was doing something like what you are suggesting earlier but >>>> noticed some >>>> problems and that’s the reason why I changed. >>>> >>>> For example, for the following testcase from the test suite, >>>> >>>> unsigned long l = (unsigned long)-2; >>>> unsigned short s; >>>> >>>> int main () { >>>> long t = l + 1; >>>> s = l; >>>> if (s != (unsigned short) -2) >>>> abort (); >>>> exit (0); >>>> } >>>> >>>> with the following gimple stmts >>>> >>>> main () >>>> { >>>> short unsigned int s.1; >>>> long unsigned int l.0; >>>> >>>> ;; basic block 2, loop depth 0 >>>> ;; pred: ENTRY >>>> l.0_2 = l; >>>> s.1_3 = (short unsigned int) l.0_2; >>>> s = s.1_3; >>>> if (s.1_3 != 65534) >>>> goto <bb 3>; >>>> else >>>> goto <bb 4>; >>>> ;; succ: 3 >>>> ;; 4 >>>> >>>> ;; basic block 3, loop depth 0 >>>> ;; pred: 2 >>>> abort (); >>>> ;; succ: >>>> >>>> ;; basic block 4, loop depth 0 >>>> ;; pred: 2 >>>> exit (0); >>>> ;; succ: >>>> >>>> } >>>> >>>> >>>> >>>> has the following value range. >>>> >>>> l.0_2: VARYING >>>> s.1_3: [0, +INF] >>>> >>>> >>>> From zero/sign extension point of view, the variable s.1_3 is >>>> expected to >>>> have a value that will overflow (or varying) as this is what is >>>> assigned to >>>> a smaller variable. extract_range_from_assignment initially >>>> calculates the >>>> value range as VARYING but later changed to [0, +INF] by >>>> extract_range_basic. What I need here is the value that will be assigned >>>> from the rhs expression and not the value that we will have with proper >>>> assignment. >>> >>> I don't understand this. The relevant statement is >>> >>> s.1_3 = (short unsigned int) l.0_2; >>> >>> right? You have value-ranges for both s.1_3 and l.0_2 as above. And >>> you clearly cannot optimize the truncation away (and if you could, >>> you wond't need value-range information for that fact). >>> >> This is true. But just by looking at the value range of s.1.3 we will >> only see [0 +INF], as we are transferring directly from the lattice to >> lhs its value range. >> >> [0, +INF] here tells us vrp_val_is_max and it is not >> is_positive_overflow_infinity (or varying). Thats why we need to get the >> value range of RHS expression which will tell us the actual range. We >> can then use this range and see of we can fit it to lhs type without >> truncation. > > Well, my point is you want to look at the l.0_2 value-range for this. > Storing the l.0_2 value-range for s.1_3 is wrong. > Yes, tree SSA_NAME should have it's correct value range. But, assigning rhs expression's value range is not totally wrong , it is just that it can be conservative value range (please correct me if I am wrong here) in few cases, as it can have wider range. I can use the rhs value range in the above case. We can also eliminate redundant zero/sign extensions for gimple binary and ternary stmts. In this case we will have to calculate the value range. We will have to reuse these logic in tree-vrp. Other option is to add another attribute in range_info_t to indicate if set_value_range_to_nonnegative is used in value range extraction. What is your preferred solution please. >>>> I understand that the above code of mine needs to be changed but not >>>> convinced about the best way to do that. >>>> >>>> I can possibly re-factor extract_range_from_assignment to give me this >>>> information with an additional argument. Could you kindly let me know >>>> your >>>> preference. >>>> >>>> >>>> >>>>> >>>>> /* SSA name annotations. */ >>>>> >>>>> + 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. >>>>> */ >>>>> >>>>> /* Value range information. */ >>>>> >>>>> + 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; >>>>> >>>>> why do you need to test %1.def_stmt here? >>>> >>>> >>>> >>>> I have seen some tree_ssa_name with def_stmt NULL. Thats why I added >>>> this. >>>> Is that something that should never happen. >>> >>> It should never happen - they should have a GIMPLE_NOP. >>> >> >> I am seeing def_stmt of NULL for TREE_NOTHROW node. >> debug_tree dumps the following in this case: >> >> <ssa_name 0x2aaaabd89af8 nothrow var <var_decl 0x2aaaadb384c0 t>def_stmt >> >> version 11 in-free-list> > > This is an invalid SSA name (in-free-list) that has been released. You > shouldn't look at it at all. This is actually happening in garbage collection. If i remove the check, I get the following: make[2]: *** [_mulsc3.o] Error 1 0x97755f crash_signal /home/kugan/work/sources/gcc-fsf/test/gcc/toplev.c:335 0x55f7d1 gt_ggc_mx_lang_tree_node(void*) ./gt-c-c-decl.h:531 0x802e36 gt_ggc_mx<tree_node*> /home/kugan/work/sources/gcc-fsf/test/gcc/vec.h:1152 0x802e36 gt_ggc_mx_vec_tree_va_gc_(void*) /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1205 0x8081ed gt_ggc_mx_gimple_df(void*) /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1066 0x80825f gt_ggc_mx_function /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1280 0x80825f gt_ggc_mx_function(void*) /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1272 0x55f692 gt_ggc_mx_lang_tree_node(void*) ./gt-c-c-decl.h:389 0x807dd5 gt_ggc_mx_symtab_node_def(void*) /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:709 0x807fb0 gt_ggc_m_P15symtab_node_def4htab(void*) /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:2928 0x7b7915 ggc_mark_root_tab /home/kugan/work/sources/gcc-fsf/test/gcc/ggc-common.c:133 0x7b7c60 ggc_mark_roots() /home/kugan/work/sources/gcc-fsf/test/gcc/ggc-common.c:152 0x615669 ggc_collect() /home/kugan/work/sources/gcc-fsf/test/gcc/ggc-page.c:2077 Thanks a lot. Kugan > Richard. > >>> +void >>> +set_range_info (tree name, double_int min, >>> + double_int max, bool vr_range) >>> >>> you have some whitespace issues here (please properly use tabs) >>> >> >> I will change it. >> >>> + /* Allocate if not available. */ >>> + if (ri == NULL) >>> + { >>> + ri = ggc_alloc_cleared_range_info_def (); >>> + mark_range_info_unknown (ri); >>> >>> that looks superfluous to me. >>> >>> + SSA_NAME_RANGE_INFO (name) = ri; >>> >>> - /* 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 ("0"))) ptr_info_def *ptr_info; >>> + /* Value range attributes used for zero/sign extension >>> elimination. */ >>> + struct GTY ((tag ("1"))) range_info_def *range_info; >>> + } GTY ((desc ("%1.def_stmt && !POINTER_TYPE_P (TREE_TYPE >>> ((tree)&%1))"))) vrp; >>> >>> please change vrp_info_type and vrp to other names - this is not vrp >>> specific info >>> after all, I suggest ssa_name_info_type and info. >>> >> >> I will change this too. >>> The genric bits otherwise look ok to me, the VRP bits still look wrong >>> (see my >>> above question) and need explanation. >>> >>> Thanks, >>> Richard. >>> >>>> >>>> Thanks, >>>> Kugan >> >> >> Thanks, >> Kugan >> >
On Mon, Sep 9, 2013 at 1:09 AM, Kugan <kugan.vivekanandarajah@linaro.org> wrote: > > On 06/09/13 16:16, Richard Biener wrote: >> >> On 9/3/13 2:15 PM, Kugan wrote: >>> >>> Thanks Richard for reviewing. >>> >>> On 02/09/13 22:15, Richard Biener wrote: >>>> >>>> On Wed, Jul 3, 2013 at 2:25 PM, Kugan >>>> <kugan.vivekanandarajah@linaro.org> wrote: >>>>> >>>>> On 17/06/13 18:33, Richard Biener wrote: >>>>>> >>>>>> >>>>>> On Mon, 17 Jun 2013, Kugan wrote: >>>>>> +/* 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 > > > [snip] > > >>>>>> >>>>>> for (i = 0; i < num_vr_values; i++) >>>>>> if (vr_value[i]) >>>>>> { >>>>>> tree name = ssa_name (i); >>>>>> if (POINTER_TYPE_P (name)) >>>>>> continue; >>>>>> if (vr_value[i].type == VR_RANGE >>>>>> || vr_value[i].type == VR_ANTI_RANGE) >>>>>> tree_ssa_set_value_range (name, tree_to_double_int >>>>>> (vr_value[i].min), tree_to_double_int (vr_value[i].max), >>>>>> vr_value[i].type >>>>>> == VR_RANGE); >>>>>> } >>>>>> >>>>> >>>>> Thanks Richard for taking time to review it. >>>>> >>>>> I was doing something like what you are suggesting earlier but >>>>> noticed some >>>>> problems and that’s the reason why I changed. >>>>> >>>>> For example, for the following testcase from the test suite, >>>>> >>>>> unsigned long l = (unsigned long)-2; >>>>> unsigned short s; >>>>> >>>>> int main () { >>>>> long t = l + 1; >>>>> s = l; >>>>> if (s != (unsigned short) -2) >>>>> abort (); >>>>> exit (0); >>>>> } >>>>> >>>>> with the following gimple stmts >>>>> >>>>> main () >>>>> { >>>>> short unsigned int s.1; >>>>> long unsigned int l.0; >>>>> >>>>> ;; basic block 2, loop depth 0 >>>>> ;; pred: ENTRY >>>>> l.0_2 = l; >>>>> s.1_3 = (short unsigned int) l.0_2; >>>>> s = s.1_3; >>>>> if (s.1_3 != 65534) >>>>> goto <bb 3>; >>>>> else >>>>> goto <bb 4>; >>>>> ;; succ: 3 >>>>> ;; 4 >>>>> >>>>> ;; basic block 3, loop depth 0 >>>>> ;; pred: 2 >>>>> abort (); >>>>> ;; succ: >>>>> >>>>> ;; basic block 4, loop depth 0 >>>>> ;; pred: 2 >>>>> exit (0); >>>>> ;; succ: >>>>> >>>>> } >>>>> >>>>> >>>>> >>>>> has the following value range. >>>>> >>>>> l.0_2: VARYING >>>>> s.1_3: [0, +INF] >>>>> >>>>> >>>>> From zero/sign extension point of view, the variable s.1_3 is >>>>> expected to >>>>> have a value that will overflow (or varying) as this is what is >>>>> assigned to >>>>> a smaller variable. extract_range_from_assignment initially >>>>> calculates the >>>>> value range as VARYING but later changed to [0, +INF] by >>>>> extract_range_basic. What I need here is the value that will be >>>>> assigned >>>>> from the rhs expression and not the value that we will have with proper >>>>> assignment. >>>> >>>> >>>> I don't understand this. The relevant statement is >>>> >>>> s.1_3 = (short unsigned int) l.0_2; >>>> >>>> right? You have value-ranges for both s.1_3 and l.0_2 as above. And >>>> you clearly cannot optimize the truncation away (and if you could, >>>> you wond't need value-range information for that fact). >>>> >>> This is true. But just by looking at the value range of s.1.3 we will >>> only see [0 +INF], as we are transferring directly from the lattice to >>> lhs its value range. >>> >>> [0, +INF] here tells us vrp_val_is_max and it is not >>> is_positive_overflow_infinity (or varying). Thats why we need to get the >>> value range of RHS expression which will tell us the actual range. We >>> can then use this range and see of we can fit it to lhs type without >>> truncation. >> >> >> Well, my point is you want to look at the l.0_2 value-range for this. >> Storing the l.0_2 value-range for s.1_3 is wrong. >> > > Yes, tree SSA_NAME should have it's correct value range. But, assigning rhs > expression's value range is not totally wrong , it is just that it can be > conservative value range (please correct me if I am wrong here) in few > cases, as it can have wider range. If it's a sign-changing conversion it can be surely wrong. > I can use the rhs value range in the above case. We can also eliminate > redundant zero/sign extensions for gimple binary and ternary stmts. In this > case we will have to calculate the value range. We will have to reuse these > logic in tree-vrp. I fail to see the issue given no concrete example. > Other option is to add another attribute in range_info_t to indicate if > set_value_range_to_nonnegative is used in value range extraction. Why should the result of this not be accurately represented in the lattice? > What is your preferred solution please. I don't know because I do not understand the problem at hand. >>>>> I understand that the above code of mine needs to be changed but not >>>>> convinced about the best way to do that. >>>>> >>>>> I can possibly re-factor extract_range_from_assignment to give me this >>>>> information with an additional argument. Could you kindly let me know >>>>> your >>>>> preference. >>>>> >>>>> >>>>> >>>>>> >>>>>> /* SSA name annotations. */ >>>>>> >>>>>> + 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. >>>>>> */ >>>>>> >>>>>> /* Value range information. */ >>>>>> >>>>>> + 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; >>>>>> >>>>>> why do you need to test %1.def_stmt here? >>>>> >>>>> >>>>> >>>>> >>>>> I have seen some tree_ssa_name with def_stmt NULL. Thats why I added >>>>> this. >>>>> Is that something that should never happen. >>>> >>>> >>>> It should never happen - they should have a GIMPLE_NOP. >>>> >>> >>> I am seeing def_stmt of NULL for TREE_NOTHROW node. >>> debug_tree dumps the following in this case: >>> >>> <ssa_name 0x2aaaabd89af8 nothrow var <var_decl 0x2aaaadb384c0 t>def_stmt >>> >>> version 11 in-free-list> >> >> >> This is an invalid SSA name (in-free-list) that has been released. You >> shouldn't look at it at all. > > > This is actually happening in garbage collection. If i remove the check, I > get the following: Ah, ok. Well, that shows that the field is not properly zeroed at SSA name release time. Or that the garbage collector visits the ptr_info (your .vrp) even if it is NULL. You can look at the gtype-desc.c code and the way the callers are wrapped via gtype-desc.h. I suspect that the right answer is to instead do GTY ((desc (%1.ptr_info && ...))) that is, make sure the pointer is not NULL. Or push the union into the pointer target instead. Do others have a better solution? The issue is that the descriptor for the GT machinery is not valid if the "field" (either of the pointers in the union) is NULL. But then it wouldn't matter anyway. The GTY machinery doesn't seem to handle this special-case (all-pointers in the union). Richard. > make[2]: *** [_mulsc3.o] Error 1 > 0x97755f crash_signal > /home/kugan/work/sources/gcc-fsf/test/gcc/toplev.c:335 > 0x55f7d1 gt_ggc_mx_lang_tree_node(void*) > ./gt-c-c-decl.h:531 > 0x802e36 gt_ggc_mx<tree_node*> > /home/kugan/work/sources/gcc-fsf/test/gcc/vec.h:1152 > 0x802e36 gt_ggc_mx_vec_tree_va_gc_(void*) > > /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1205 > 0x8081ed gt_ggc_mx_gimple_df(void*) > > /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1066 > 0x80825f gt_ggc_mx_function > > /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1280 > 0x80825f gt_ggc_mx_function(void*) > > /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1272 > 0x55f692 gt_ggc_mx_lang_tree_node(void*) > ./gt-c-c-decl.h:389 > 0x807dd5 gt_ggc_mx_symtab_node_def(void*) > > /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:709 > 0x807fb0 gt_ggc_m_P15symtab_node_def4htab(void*) > > /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:2928 > 0x7b7915 ggc_mark_root_tab > /home/kugan/work/sources/gcc-fsf/test/gcc/ggc-common.c:133 > 0x7b7c60 ggc_mark_roots() > /home/kugan/work/sources/gcc-fsf/test/gcc/ggc-common.c:152 > 0x615669 ggc_collect() > /home/kugan/work/sources/gcc-fsf/test/gcc/ggc-page.c:2077 > > > > > Thanks a lot. > > Kugan > > >> Richard. >> >>>> +void >>>> +set_range_info (tree name, double_int min, >>>> + double_int max, bool vr_range) >>>> >>>> you have some whitespace issues here (please properly use tabs) >>>> >>> >>> I will change it. >>> >>>> + /* Allocate if not available. */ >>>> + if (ri == NULL) >>>> + { >>>> + ri = ggc_alloc_cleared_range_info_def (); >>>> + mark_range_info_unknown (ri); >>>> >>>> that looks superfluous to me. >>>> >>>> + SSA_NAME_RANGE_INFO (name) = ri; >>>> >>>> - /* 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 ("0"))) ptr_info_def *ptr_info; >>>> + /* Value range attributes used for zero/sign extension >>>> elimination. */ >>>> + struct GTY ((tag ("1"))) range_info_def *range_info; >>>> + } GTY ((desc ("%1.def_stmt && !POINTER_TYPE_P (TREE_TYPE >>>> ((tree)&%1))"))) vrp; >>>> >>>> please change vrp_info_type and vrp to other names - this is not vrp >>>> specific info >>>> after all, I suggest ssa_name_info_type and info. >>>> >>> >>> I will change this too. >>>> >>>> The genric bits otherwise look ok to me, the VRP bits still look wrong >>>> (see my >>>> above question) and need explanation. >>>> >>>> Thanks, >>>> Richard. >>>> >>>>> >>>>> Thanks, >>>>> Kugan >>> >>> >>> >>> Thanks, >>> Kugan >>> >> >
On 09/09/13 19:01, Richard Biener wrote: > On Mon, Sep 9, 2013 at 1:09 AM, Kugan <kugan.vivekanandarajah@linaro.org> wrote: >> >> On 06/09/13 16:16, Richard Biener wrote: >>> >>> On 9/3/13 2:15 PM, Kugan wrote: >>>> >>>> Thanks Richard for reviewing. >>>> >>>> On 02/09/13 22:15, Richard Biener wrote: >>>>> >>>>> On Wed, Jul 3, 2013 at 2:25 PM, Kugan >>>>> <kugan.vivekanandarajah@linaro.org> wrote: >>>>>> >>>>>> On 17/06/13 18:33, Richard Biener wrote: >>>>>>> >>>>>>> >>>>>>> On Mon, 17 Jun 2013, Kugan wrote: >>>>>>> +/* 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 >> >> >> [snip] >> >> >>>>>>> >>>>>>> for (i = 0; i < num_vr_values; i++) >>>>>>> if (vr_value[i]) >>>>>>> { >>>>>>> tree name = ssa_name (i); >>>>>>> if (POINTER_TYPE_P (name)) >>>>>>> continue; >>>>>>> if (vr_value[i].type == VR_RANGE >>>>>>> || vr_value[i].type == VR_ANTI_RANGE) >>>>>>> tree_ssa_set_value_range (name, tree_to_double_int >>>>>>> (vr_value[i].min), tree_to_double_int (vr_value[i].max), >>>>>>> vr_value[i].type >>>>>>> == VR_RANGE); >>>>>>> } >>>>>>> >>>>>> >>>>>> Thanks Richard for taking time to review it. >>>>>> >>>>>> I was doing something like what you are suggesting earlier but >>>>>> noticed some >>>>>> problems and that’s the reason why I changed. >>>>>> >>>>>> For example, for the following testcase from the test suite, >>>>>> >>>>>> unsigned long l = (unsigned long)-2; >>>>>> unsigned short s; >>>>>> >>>>>> int main () { >>>>>> long t = l + 1; >>>>>> s = l; >>>>>> if (s != (unsigned short) -2) >>>>>> abort (); >>>>>> exit (0); >>>>>> } >>>>>> >>>>>> with the following gimple stmts >>>>>> >>>>>> main () >>>>>> { >>>>>> short unsigned int s.1; >>>>>> long unsigned int l.0; >>>>>> >>>>>> ;; basic block 2, loop depth 0 >>>>>> ;; pred: ENTRY >>>>>> l.0_2 = l; >>>>>> s.1_3 = (short unsigned int) l.0_2; >>>>>> s = s.1_3; >>>>>> if (s.1_3 != 65534) >>>>>> goto <bb 3>; >>>>>> else >>>>>> goto <bb 4>; >>>>>> ;; succ: 3 >>>>>> ;; 4 >>>>>> >>>>>> ;; basic block 3, loop depth 0 >>>>>> ;; pred: 2 >>>>>> abort (); >>>>>> ;; succ: >>>>>> >>>>>> ;; basic block 4, loop depth 0 >>>>>> ;; pred: 2 >>>>>> exit (0); >>>>>> ;; succ: >>>>>> >>>>>> } >>>>>> >>>>>> >>>>>> >>>>>> has the following value range. >>>>>> >>>>>> l.0_2: VARYING >>>>>> s.1_3: [0, +INF] >>>>>> >>>>>> >>>>>> From zero/sign extension point of view, the variable s.1_3 is >>>>>> expected to >>>>>> have a value that will overflow (or varying) as this is what is >>>>>> assigned to >>>>>> a smaller variable. extract_range_from_assignment initially >>>>>> calculates the >>>>>> value range as VARYING but later changed to [0, +INF] by >>>>>> extract_range_basic. What I need here is the value that will be >>>>>> assigned >>>>>> from the rhs expression and not the value that we will have with proper >>>>>> assignment. >>>>> >>>>> >>>>> I don't understand this. The relevant statement is >>>>> >>>>> s.1_3 = (short unsigned int) l.0_2; >>>>> >>>>> right? You have value-ranges for both s.1_3 and l.0_2 as above. And >>>>> you clearly cannot optimize the truncation away (and if you could, >>>>> you wond't need value-range information for that fact). >>>>> >>>> This is true. But just by looking at the value range of s.1.3 we will >>>> only see [0 +INF], as we are transferring directly from the lattice to >>>> lhs its value range. >>>> >>>> [0, +INF] here tells us vrp_val_is_max and it is not >>>> is_positive_overflow_infinity (or varying). Thats why we need to get the >>>> value range of RHS expression which will tell us the actual range. We >>>> can then use this range and see of we can fit it to lhs type without >>>> truncation. >>> >>> >>> Well, my point is you want to look at the l.0_2 value-range for this. >>> Storing the l.0_2 value-range for s.1_3 is wrong. >>> >> >> Yes, tree SSA_NAME should have it's correct value range. But, assigning rhs >> expression's value range is not totally wrong , it is just that it can be >> conservative value range (please correct me if I am wrong here) in few >> cases, as it can have wider range. > > If it's a sign-changing conversion it can be surely wrong. > It is not sign-changing conversion. Rather, when we have rhs expression value which is VR_VARYING it is set to [0, +INF] i.e, in extract_range_from_assignment, if the value range is VR_VARYING, follwing is done if (vr->type == VR_VARYING) extract_range_basic (vr, stmt); In extract_range_basic (when the value range is varying), when the following code executes, it changes VR_VARYING to [0, +INF], if (INTEGRAL_TYPE_P (type) && gimple_stmt_nonnegative_warnv_p (stmt, &sop)) set_value_range_to_nonnegative (vr, type, sop || stmt_overflow_infinity (stmt)); This will happen only when we have VR_VARYING for the rhs expression. This is wrong from zero/sign extension elimination point of view as we cant rely on this converted value range. Currently I am leaving this as varying so that we can decide whether to eliminate the zero/sign extension. This is not completely wrong. unsigned short s; s.1_3 = (short unsigned int) l.0_2; l.0_2: VARYING s.1_3: [0, +INF] Similarly (extracted form a testcase) unsigned char _4; unsigned char _2; unsigned char _5; _5 = _4 + _2; value range extracted for expression (_4 + _2) extract_range_from_binary_expr is VARYING and _5 has value range [0 +INF] or [0, 255] after set_value_range_to_nonnegative is done. >> I can use the rhs value range in the above case. We can also eliminate >> redundant zero/sign extensions for gimple binary and ternary stmts. In this >> case we will have to calculate the value range. We will have to reuse these >> logic in tree-vrp. > > I fail to see the issue given no concrete example. > I hope I have explained it better this time. >> Other option is to add another attribute in range_info_t to indicate if >> set_value_range_to_nonnegative is used in value range extraction. > > Why should the result of this not be accurately represented in the lattice? > >> What is your preferred solution please. > > I don't know because I do not understand the problem at hand. > Could you please suggest the preferred way now. >>>>>> I understand that the above code of mine needs to be changed but not >>>>>> convinced about the best way to do that. >>>>>> >>>>>> I can possibly re-factor extract_range_from_assignment to give me this >>>>>> information with an additional argument. Could you kindly let me know >>>>>> your >>>>>> preference. >>>>>> >>>>>> >>>>>> >>>>>>> >>>>>>> /* SSA name annotations. */ >>>>>>> >>>>>>> + 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. >>>>>>> */ >>>>>>> >>>>>>> /* Value range information. */ >>>>>>> >>>>>>> + 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; >>>>>>> >>>>>>> why do you need to test %1.def_stmt here? >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> I have seen some tree_ssa_name with def_stmt NULL. Thats why I added >>>>>> this. >>>>>> Is that something that should never happen. >>>>> >>>>> >>>>> It should never happen - they should have a GIMPLE_NOP. >>>>> >>>> >>>> I am seeing def_stmt of NULL for TREE_NOTHROW node. >>>> debug_tree dumps the following in this case: >>>> >>>> <ssa_name 0x2aaaabd89af8 nothrow var <var_decl 0x2aaaadb384c0 t>def_stmt >>>> >>>> version 11 in-free-list> >>> >>> >>> This is an invalid SSA name (in-free-list) that has been released. You >>> shouldn't look at it at all. >> >> >> This is actually happening in garbage collection. If i remove the check, I >> get the following: > > Ah, ok. Well, that shows that the field is not properly zeroed at SSA name > release time. Or that the garbage collector visits the ptr_info (your .vrp) > even if it is NULL. You can look at the gtype-desc.c code and the > way the callers are wrapped via gtype-desc.h. > > I suspect that the right answer is to instead do > > GTY ((desc (%1.ptr_info && ...))) > > that is, make sure the pointer is not NULL. Or push the union into the > pointer target instead. > > Do others have a better solution? The issue is that the descriptor for > the GT machinery is not valid if the "field" (either of the pointers in the > union) is NULL. But then it wouldn't matter anyway. The GTY machinery > doesn't seem to handle this special-case (all-pointers in the union). > > Richard. > >> make[2]: *** [_mulsc3.o] Error 1 >> 0x97755f crash_signal >> /home/kugan/work/sources/gcc-fsf/test/gcc/toplev.c:335 >> 0x55f7d1 gt_ggc_mx_lang_tree_node(void*) >> ./gt-c-c-decl.h:531 >> 0x802e36 gt_ggc_mx<tree_node*> >> /home/kugan/work/sources/gcc-fsf/test/gcc/vec.h:1152 >> 0x802e36 gt_ggc_mx_vec_tree_va_gc_(void*) >> >> /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1205 >> 0x8081ed gt_ggc_mx_gimple_df(void*) >> >> /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1066 >> 0x80825f gt_ggc_mx_function >> >> /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1280 >> 0x80825f gt_ggc_mx_function(void*) >> >> /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1272 >> 0x55f692 gt_ggc_mx_lang_tree_node(void*) >> ./gt-c-c-decl.h:389 >> 0x807dd5 gt_ggc_mx_symtab_node_def(void*) >> >> /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:709 >> 0x807fb0 gt_ggc_m_P15symtab_node_def4htab(void*) >> >> /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:2928 >> 0x7b7915 ggc_mark_root_tab >> /home/kugan/work/sources/gcc-fsf/test/gcc/ggc-common.c:133 >> 0x7b7c60 ggc_mark_roots() >> /home/kugan/work/sources/gcc-fsf/test/gcc/ggc-common.c:152 >> 0x615669 ggc_collect() >> /home/kugan/work/sources/gcc-fsf/test/gcc/ggc-page.c:2077 >> >> >> >> >> Thanks a lot. >> >> Kugan >> >> >>> Richard. >>> >>>>> +void >>>>> +set_range_info (tree name, double_int min, >>>>> + double_int max, bool vr_range) >>>>> >>>>> you have some whitespace issues here (please properly use tabs) >>>>> >>>> >>>> I will change it. >>>> >>>>> + /* Allocate if not available. */ >>>>> + if (ri == NULL) >>>>> + { >>>>> + ri = ggc_alloc_cleared_range_info_def (); >>>>> + mark_range_info_unknown (ri); >>>>> >>>>> that looks superfluous to me. >>>>> >>>>> + SSA_NAME_RANGE_INFO (name) = ri; >>>>> >>>>> - /* 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 ("0"))) ptr_info_def *ptr_info; >>>>> + /* Value range attributes used for zero/sign extension >>>>> elimination. */ >>>>> + struct GTY ((tag ("1"))) range_info_def *range_info; >>>>> + } GTY ((desc ("%1.def_stmt && !POINTER_TYPE_P (TREE_TYPE >>>>> ((tree)&%1))"))) vrp; >>>>> >>>>> please change vrp_info_type and vrp to other names - this is not vrp >>>>> specific info >>>>> after all, I suggest ssa_name_info_type and info. >>>>> >>>> >>>> I will change this too. >>>>> >>>>> The genric bits otherwise look ok to me, the VRP bits still look wrong >>>>> (see my >>>>> above question) and need explanation. >>>>> >>>>> Thanks, >>>>> Richard. >>>>> >>>>>> >>>>>> Thanks, >>>>>> Kugan >>>> >>>> >>>> >>>> Thanks, >>>> Kugan >>>> >>> >>
On Tue, 10 Sep 2013, Kugan wrote: > On 09/09/13 19:01, Richard Biener wrote: > > On Mon, Sep 9, 2013 at 1:09 AM, Kugan <kugan.vivekanandarajah@linaro.org> > > wrote: > > > > > > On 06/09/13 16:16, Richard Biener wrote: > > > > > > > > On 9/3/13 2:15 PM, Kugan wrote: > > > > > > > > > > Thanks Richard for reviewing. > > > > > > > > > > On 02/09/13 22:15, Richard Biener wrote: > > > > > > > > > > > > On Wed, Jul 3, 2013 at 2:25 PM, Kugan > > > > > > <kugan.vivekanandarajah@linaro.org> wrote: > > > > > > > > > > > > > > On 17/06/13 18:33, Richard Biener wrote: > > > > > > > > > > > > > > > > > > > > > > > > On Mon, 17 Jun 2013, Kugan wrote: > > > > > > > > +/* 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 > > > > > > > > > [snip] > > > > > > > > > > > > > > > > > > > > > > for (i = 0; i < num_vr_values; i++) > > > > > > > > if (vr_value[i]) > > > > > > > > { > > > > > > > > tree name = ssa_name (i); > > > > > > > > if (POINTER_TYPE_P (name)) > > > > > > > > continue; > > > > > > > > if (vr_value[i].type == VR_RANGE > > > > > > > > || vr_value[i].type == VR_ANTI_RANGE) > > > > > > > > tree_ssa_set_value_range (name, tree_to_double_int > > > > > > > > (vr_value[i].min), tree_to_double_int (vr_value[i].max), > > > > > > > > vr_value[i].type > > > > > > > > == VR_RANGE); > > > > > > > > } > > > > > > > > > > > > > > > > > > > > > > Thanks Richard for taking time to review it. > > > > > > > > > > > > > > I was doing something like what you are suggesting earlier but > > > > > > > noticed some > > > > > > > problems and that?s the reason why I changed. > > > > > > > > > > > > > > For example, for the following testcase from the test suite, > > > > > > > > > > > > > > unsigned long l = (unsigned long)-2; > > > > > > > unsigned short s; > > > > > > > > > > > > > > int main () { > > > > > > > long t = l + 1; > > > > > > > s = l; > > > > > > > if (s != (unsigned short) -2) > > > > > > > abort (); > > > > > > > exit (0); > > > > > > > } > > > > > > > > > > > > > > with the following gimple stmts > > > > > > > > > > > > > > main () > > > > > > > { > > > > > > > short unsigned int s.1; > > > > > > > long unsigned int l.0; > > > > > > > > > > > > > > ;; basic block 2, loop depth 0 > > > > > > > ;; pred: ENTRY > > > > > > > l.0_2 = l; > > > > > > > s.1_3 = (short unsigned int) l.0_2; > > > > > > > s = s.1_3; > > > > > > > if (s.1_3 != 65534) > > > > > > > goto <bb 3>; > > > > > > > else > > > > > > > goto <bb 4>; > > > > > > > ;; succ: 3 > > > > > > > ;; 4 > > > > > > > > > > > > > > ;; basic block 3, loop depth 0 > > > > > > > ;; pred: 2 > > > > > > > abort (); > > > > > > > ;; succ: > > > > > > > > > > > > > > ;; basic block 4, loop depth 0 > > > > > > > ;; pred: 2 > > > > > > > exit (0); > > > > > > > ;; succ: > > > > > > > > > > > > > > } > > > > > > > > > > > > > > > > > > > > > > > > > > > > has the following value range. > > > > > > > > > > > > > > l.0_2: VARYING > > > > > > > s.1_3: [0, +INF] > > > > > > > > > > > > > > > > > > > > > From zero/sign extension point of view, the variable s.1_3 is > > > > > > > expected to > > > > > > > have a value that will overflow (or varying) as this is what is > > > > > > > assigned to > > > > > > > a smaller variable. extract_range_from_assignment initially > > > > > > > calculates the > > > > > > > value range as VARYING but later changed to [0, +INF] by > > > > > > > extract_range_basic. What I need here is the value that will be > > > > > > > assigned > > > > > > > from the rhs expression and not the value that we will have with > > > > > > > proper > > > > > > > assignment. > > > > > > > > > > > > > > > > > > I don't understand this. The relevant statement is > > > > > > > > > > > > s.1_3 = (short unsigned int) l.0_2; > > > > > > > > > > > > right? You have value-ranges for both s.1_3 and l.0_2 as above. > > > > > > And > > > > > > you clearly cannot optimize the truncation away (and if you could, > > > > > > you wond't need value-range information for that fact). > > > > > > > > > > > This is true. But just by looking at the value range of s.1.3 we will > > > > > only see [0 +INF], as we are transferring directly from the lattice to > > > > > lhs its value range. > > > > > > > > > > [0, +INF] here tells us vrp_val_is_max and it is not > > > > > is_positive_overflow_infinity (or varying). Thats why we need to get > > > > > the > > > > > value range of RHS expression which will tell us the actual range. We > > > > > can then use this range and see of we can fit it to lhs type without > > > > > truncation. > > > > > > > > > > > > Well, my point is you want to look at the l.0_2 value-range for this. > > > > Storing the l.0_2 value-range for s.1_3 is wrong. > > > > > > > > > > Yes, tree SSA_NAME should have it's correct value range. But, assigning > > > rhs > > > expression's value range is not totally wrong , it is just that it can be > > > conservative value range (please correct me if I am wrong here) in few > > > cases, as it can have wider range. > > > > If it's a sign-changing conversion it can be surely wrong. > > > > It is not sign-changing conversion. Rather, when we have rhs expression value > which is VR_VARYING it is set to [0, +INF] > > > i.e, in extract_range_from_assignment, if the value range is VR_VARYING, > follwing is done > if (vr->type == VR_VARYING) > extract_range_basic (vr, stmt); > > In extract_range_basic (when the value range is varying), when the following > code executes, it changes VR_VARYING to [0, +INF], > > if (INTEGRAL_TYPE_P (type) > && gimple_stmt_nonnegative_warnv_p (stmt, &sop)) > set_value_range_to_nonnegative (vr, type, > sop || stmt_overflow_infinity (stmt)); > > This will happen only when we have VR_VARYING for the rhs expression. This is > wrong from zero/sign extension elimination point of view as we cant rely on > this converted value range. > > > Currently I am leaving this as varying so that we can decide whether to > eliminate the zero/sign extension. This is not completely wrong. > > unsigned short s; > s.1_3 = (short unsigned int) l.0_2; > l.0_2: VARYING > s.1_3: [0, +INF] Note that [0, +INF] is the same as VARYING and [-INF, +INF] and VARYING for l.0_2 is the same as [-INF, +INF]. > Similarly (extracted form a testcase) > > unsigned char _4; > unsigned char _2; > unsigned char _5; > > _5 = _4 + _2; > value range extracted for expression (_4 + _2) extract_range_from_binary_expr > is VARYING and > _5 has value range [0 +INF] or [0, 255] after set_value_range_to_nonnegative > is done. See above. > > > > I can use the rhs value range in the above case. We can also eliminate > > > redundant zero/sign extensions for gimple binary and ternary stmts. In > > > this > > > case we will have to calculate the value range. We will have to reuse > > > these > > > logic in tree-vrp. > > > > I fail to see the issue given no concrete example. > > > > I hope I have explained it better this time. Not really. What's the desired value-range and what's the value-range that you get from the lattice? > > > Other option is to add another attribute in range_info_t to indicate if > > > set_value_range_to_nonnegative is used in value range extraction. > > > > Why should the result of this not be accurately represented in the lattice? > > > > > What is your preferred solution please. > > > > I don't know because I do not understand the problem at hand. > > > > Could you please suggest the preferred way now. Use the value-range from the lattice. Richard. > > I suspect that the right answer is to instead do > > > > GTY ((desc (%1.ptr_info && ...))) > > > > that is, make sure the pointer is not NULL. Or push the union into the > > pointer target instead. > > > > Do others have a better solution? The issue is that the descriptor for > > the GT machinery is not valid if the "field" (either of the pointers in the > > union) is NULL. But then it wouldn't matter anyway. The GTY machinery > > doesn't seem to handle this special-case (all-pointers in the union). Micha just suggested union vrp_info_type { /* Pointer attributes used for alias analysis. */ struct GTY ((tag ("0"))) ptr_info_def *ptr_info; /* Value range attributes used for zero/sign extension elimination. */ struct GTY ((tag ("1"))) range_info_def *range_info; } GTY ((desc ("%1.typed.type ? !POINTER_TYPE_P (TREE_TYPE ((tree)&%1)) : 2"))) vrp that is, if TREE_TYPE is NULL (released SSA names), do not walk either. Richard. > > Richard. > > > > > make[2]: *** [_mulsc3.o] Error 1 > > > 0x97755f crash_signal > > > /home/kugan/work/sources/gcc-fsf/test/gcc/toplev.c:335 > > > 0x55f7d1 gt_ggc_mx_lang_tree_node(void*) > > > ./gt-c-c-decl.h:531 > > > 0x802e36 gt_ggc_mx<tree_node*> > > > /home/kugan/work/sources/gcc-fsf/test/gcc/vec.h:1152 > > > 0x802e36 gt_ggc_mx_vec_tree_va_gc_(void*) > > > > > > /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1205 > > > 0x8081ed gt_ggc_mx_gimple_df(void*) > > > > > > /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1066 > > > 0x80825f gt_ggc_mx_function > > > > > > /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1280 > > > 0x80825f gt_ggc_mx_function(void*) > > > > > > /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1272 > > > 0x55f692 gt_ggc_mx_lang_tree_node(void*) > > > ./gt-c-c-decl.h:389 > > > 0x807dd5 gt_ggc_mx_symtab_node_def(void*) > > > > > > /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:709 > > > 0x807fb0 gt_ggc_m_P15symtab_node_def4htab(void*) > > > > > > /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:2928 > > > 0x7b7915 ggc_mark_root_tab > > > /home/kugan/work/sources/gcc-fsf/test/gcc/ggc-common.c:133 > > > 0x7b7c60 ggc_mark_roots() > > > /home/kugan/work/sources/gcc-fsf/test/gcc/ggc-common.c:152 > > > 0x615669 ggc_collect() > > > /home/kugan/work/sources/gcc-fsf/test/gcc/ggc-page.c:2077 > > > > > > > > > > > > > > > Thanks a lot. > > > > > > Kugan > > > > > > > > > > Richard. > > > > > > > > > > +void > > > > > > +set_range_info (tree name, double_int min, > > > > > > + double_int max, bool vr_range) > > > > > > > > > > > > you have some whitespace issues here (please properly use tabs) > > > > > > > > > > > > > > > > I will change it. > > > > > > > > > > > + /* Allocate if not available. */ > > > > > > + if (ri == NULL) > > > > > > + { > > > > > > + ri = ggc_alloc_cleared_range_info_def (); > > > > > > + mark_range_info_unknown (ri); > > > > > > > > > > > > that looks superfluous to me. > > > > > > > > > > > > + SSA_NAME_RANGE_INFO (name) = ri; > > > > > > > > > > > > - /* 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 ("0"))) ptr_info_def *ptr_info; > > > > > > + /* Value range attributes used for zero/sign extension > > > > > > elimination. */ > > > > > > + struct GTY ((tag ("1"))) range_info_def *range_info; > > > > > > + } GTY ((desc ("%1.def_stmt && !POINTER_TYPE_P (TREE_TYPE > > > > > > ((tree)&%1))"))) vrp; > > > > > > > > > > > > please change vrp_info_type and vrp to other names - this is not vrp > > > > > > specific info > > > > > > after all, I suggest ssa_name_info_type and info. > > > > > > > > > > > > > > > > I will change this too. > > > > > > > > > > > > The genric bits otherwise look ok to me, the VRP bits still look > > > > > > wrong > > > > > > (see my > > > > > > above question) and need explanation. > > > > > > > > > > > > Thanks, > > > > > > Richard. > > > > > > > > > > > > > > > > > > > > Thanks, > > > > > > > Kugan > > > > > > > > > > > > > > > > > > > > Thanks, > > > > > Kugan > > > > > > > > > > > > > >
On Tue, Sep 10, 2013 at 03:17:50PM +0200, Richard Biener wrote: > > unsigned short s; > > s.1_3 = (short unsigned int) l.0_2; > > l.0_2: VARYING > > s.1_3: [0, +INF] > > Note that [0, +INF] is the same as VARYING and [-INF, +INF] and VARYING for > l.0_2 is the same as [-INF, +INF]. Yeah, I don't see much value in differentiating between VR_VARYING and VR_RANGE [TYPE_MIN_VALUE, TYPE_MAX_VALUE] (perhaps a question is what to do for types with precisions different from TYPE_MODE's bitsize, if we should store for VARYING/UNDEFINED a range of all possible values in the mode). Unsigned type will be always >= 0, even if it is VARYING or UNDEFINED. What is the valid bit good for? Is it meant just for integrals with > 2*HOST_BITS_PER_WIDE_INT precision, which we can't represent in double_int? I'd say we just don't want to keep track on the value ranges for those. And, do we need to distinguish between VR_RANGE and VR_ANTI_RANGE? I mean, can't we always store the range in VR_RANGE format? Instead of -[3,7] we'd store [8,2] and define that if the min double_int is bigger than max double_int, then it is [min,+infinity] merged with [-infinity,max] range (i.e. -[max+1,min-1])? > Micha just suggested > > union vrp_info_type { > /* Pointer attributes used for alias analysis. */ > struct GTY ((tag ("0"))) ptr_info_def *ptr_info; > /* Value range attributes used for zero/sign extension elimination. > */ > struct GTY ((tag ("1"))) range_info_def *range_info; > } GTY ((desc ("%1.typed.type ? !POINTER_TYPE_P (TREE_TYPE Why not TREE_TYPE(&%1) here and why the (tree) cast? Jakub
On 10/09/13 22:47, Richard Biener wrote: > On Tue, 10 Sep 2013, Kugan wrote: > >> On 09/09/13 19:01, Richard Biener wrote: >>> On Mon, Sep 9, 2013 at 1:09 AM, Kugan <kugan.vivekanandarajah@linaro.org> >>> wrote: >>>> >>>> On 06/09/13 16:16, Richard Biener wrote: >>>>> >>>>> On 9/3/13 2:15 PM, Kugan wrote: >>>>>> >>>>>> Thanks Richard for reviewing. >>>>>> >>>>>> On 02/09/13 22:15, Richard Biener wrote: >>>>>>> >>>>>>> On Wed, Jul 3, 2013 at 2:25 PM, Kugan >>>>>>> <kugan.vivekanandarajah@linaro.org> wrote: >>>>>>>> >>>>>>>> On 17/06/13 18:33, Richard Biener wrote: >>>>>>>>> >>>>>>>>> >>>>>>>>> On Mon, 17 Jun 2013, Kugan wrote: >>>>>>>>> +/* 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 >>>> >>>> >>>> [snip] >>>> >>>> >>>>>>>>> >>>>>>>>> for (i = 0; i < num_vr_values; i++) >>>>>>>>> if (vr_value[i]) >>>>>>>>> { >>>>>>>>> tree name = ssa_name (i); >>>>>>>>> if (POINTER_TYPE_P (name)) >>>>>>>>> continue; >>>>>>>>> if (vr_value[i].type == VR_RANGE >>>>>>>>> || vr_value[i].type == VR_ANTI_RANGE) >>>>>>>>> tree_ssa_set_value_range (name, tree_to_double_int >>>>>>>>> (vr_value[i].min), tree_to_double_int (vr_value[i].max), >>>>>>>>> vr_value[i].type >>>>>>>>> == VR_RANGE); >>>>>>>>> } >>>>>>>>> >>>>>>>> >>>>>>>> Thanks Richard for taking time to review it. >>>>>>>> >>>>>>>> I was doing something like what you are suggesting earlier but >>>>>>>> noticed some >>>>>>>> problems and that?s the reason why I changed. >>>>>>>> >>>>>>>> For example, for the following testcase from the test suite, >>>>>>>> >>>>>>>> unsigned long l = (unsigned long)-2; >>>>>>>> unsigned short s; >>>>>>>> >>>>>>>> int main () { >>>>>>>> long t = l + 1; >>>>>>>> s = l; >>>>>>>> if (s != (unsigned short) -2) >>>>>>>> abort (); >>>>>>>> exit (0); >>>>>>>> } >>>>>>>> >>>>>>>> with the following gimple stmts >>>>>>>> >>>>>>>> main () >>>>>>>> { >>>>>>>> short unsigned int s.1; >>>>>>>> long unsigned int l.0; >>>>>>>> >>>>>>>> ;; basic block 2, loop depth 0 >>>>>>>> ;; pred: ENTRY >>>>>>>> l.0_2 = l; >>>>>>>> s.1_3 = (short unsigned int) l.0_2; >>>>>>>> s = s.1_3; >>>>>>>> if (s.1_3 != 65534) >>>>>>>> goto <bb 3>; >>>>>>>> else >>>>>>>> goto <bb 4>; >>>>>>>> ;; succ: 3 >>>>>>>> ;; 4 >>>>>>>> >>>>>>>> ;; basic block 3, loop depth 0 >>>>>>>> ;; pred: 2 >>>>>>>> abort (); >>>>>>>> ;; succ: >>>>>>>> >>>>>>>> ;; basic block 4, loop depth 0 >>>>>>>> ;; pred: 2 >>>>>>>> exit (0); >>>>>>>> ;; succ: >>>>>>>> >>>>>>>> } >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> has the following value range. >>>>>>>> >>>>>>>> l.0_2: VARYING >>>>>>>> s.1_3: [0, +INF] >>>>>>>> >>>>>>>> >>>>>>>> From zero/sign extension point of view, the variable s.1_3 is >>>>>>>> expected to >>>>>>>> have a value that will overflow (or varying) as this is what is >>>>>>>> assigned to >>>>>>>> a smaller variable. extract_range_from_assignment initially >>>>>>>> calculates the >>>>>>>> value range as VARYING but later changed to [0, +INF] by >>>>>>>> extract_range_basic. What I need here is the value that will be >>>>>>>> assigned >>>>>>>> from the rhs expression and not the value that we will have with >>>>>>>> proper >>>>>>>> assignment. >>>>>>> >>>>>>> >>>>>>> I don't understand this. The relevant statement is >>>>>>> >>>>>>> s.1_3 = (short unsigned int) l.0_2; >>>>>>> >>>>>>> right? You have value-ranges for both s.1_3 and l.0_2 as above. >>>>>>> And >>>>>>> you clearly cannot optimize the truncation away (and if you could, >>>>>>> you wond't need value-range information for that fact). >>>>>>> >>>>>> This is true. But just by looking at the value range of s.1.3 we will >>>>>> only see [0 +INF], as we are transferring directly from the lattice to >>>>>> lhs its value range. >>>>>> >>>>>> [0, +INF] here tells us vrp_val_is_max and it is not >>>>>> is_positive_overflow_infinity (or varying). Thats why we need to get >>>>>> the >>>>>> value range of RHS expression which will tell us the actual range. We >>>>>> can then use this range and see of we can fit it to lhs type without >>>>>> truncation. >>>>> >>>>> >>>>> Well, my point is you want to look at the l.0_2 value-range for this. >>>>> Storing the l.0_2 value-range for s.1_3 is wrong. >>>>> >>>> >>>> Yes, tree SSA_NAME should have it's correct value range. But, assigning >>>> rhs >>>> expression's value range is not totally wrong , it is just that it can be >>>> conservative value range (please correct me if I am wrong here) in few >>>> cases, as it can have wider range. >>> >>> If it's a sign-changing conversion it can be surely wrong. >>> >> >> It is not sign-changing conversion. Rather, when we have rhs expression value >> which is VR_VARYING it is set to [0, +INF] >> >> >> i.e, in extract_range_from_assignment, if the value range is VR_VARYING, >> follwing is done >> if (vr->type == VR_VARYING) >> extract_range_basic (vr, stmt); >> >> In extract_range_basic (when the value range is varying), when the following >> code executes, it changes VR_VARYING to [0, +INF], >> >> if (INTEGRAL_TYPE_P (type) >> && gimple_stmt_nonnegative_warnv_p (stmt, &sop)) >> set_value_range_to_nonnegative (vr, type, >> sop || stmt_overflow_infinity (stmt)); >> >> This will happen only when we have VR_VARYING for the rhs expression. This is >> wrong from zero/sign extension elimination point of view as we cant rely on >> this converted value range. >> >> >> Currently I am leaving this as varying so that we can decide whether to >> eliminate the zero/sign extension. This is not completely wrong. >> >> unsigned short s; >> s.1_3 = (short unsigned int) l.0_2; >> l.0_2: VARYING >> s.1_3: [0, +INF] > > Note that [0, +INF] is the same as VARYING and [-INF, +INF] and VARYING for > l.0_2 is the same as [-INF, +INF]. > I get it now. I will all the above as varying. >> Similarly (extracted form a testcase) >> >> unsigned char _4; >> unsigned char _2; >> unsigned char _5; >> >> _5 = _4 + _2; >> value range extracted for expression (_4 + _2) extract_range_from_binary_expr >> is VARYING and >> _5 has value range [0 +INF] or [0, 255] after set_value_range_to_nonnegative >> is done. > > See above. > >> >>>> I can use the rhs value range in the above case. We can also eliminate >>>> redundant zero/sign extensions for gimple binary and ternary stmts. In >>>> this >>>> case we will have to calculate the value range. We will have to reuse >>>> these >>>> logic in tree-vrp. >>> >>> I fail to see the issue given no concrete example. >>> >> >> I hope I have explained it better this time. > > Not really. What's the desired value-range and what's the value-range > that you get from the lattice? > >>>> Other option is to add another attribute in range_info_t to indicate if >>>> set_value_range_to_nonnegative is used in value range extraction. >>> >>> Why should the result of this not be accurately represented in the lattice? >>> >>>> What is your preferred solution please. >>> >>> I don't know because I do not understand the problem at hand. >>> >> >> Could you please suggest the preferred way now. > > Use the value-range from the lattice. I will do that. > > Richard. > >>> I suspect that the right answer is to instead do >>> >>> GTY ((desc (%1.ptr_info && ...))) >>> >>> that is, make sure the pointer is not NULL. Or push the union into the >>> pointer target instead. >>> >>> Do others have a better solution? The issue is that the descriptor for >>> the GT machinery is not valid if the "field" (either of the pointers in the >>> union) is NULL. But then it wouldn't matter anyway. The GTY machinery >>> doesn't seem to handle this special-case (all-pointers in the union). > > Micha just suggested > > union vrp_info_type { > /* Pointer attributes used for alias analysis. */ > struct GTY ((tag ("0"))) ptr_info_def *ptr_info; > /* Value range attributes used for zero/sign extension elimination. > */ > struct GTY ((tag ("1"))) range_info_def *range_info; > } GTY ((desc ("%1.typed.type ? !POINTER_TYPE_P (TREE_TYPE > ((tree)&%1)) : 2"))) vrp > Thanks. I will change it. Thanks, Kugan > that is, if TREE_TYPE is NULL (released SSA names), do not walk > either. > > Richard. > >>> Richard. >>> >>>> make[2]: *** [_mulsc3.o] Error 1 >>>> 0x97755f crash_signal >>>> /home/kugan/work/sources/gcc-fsf/test/gcc/toplev.c:335 >>>> 0x55f7d1 gt_ggc_mx_lang_tree_node(void*) >>>> ./gt-c-c-decl.h:531 >>>> 0x802e36 gt_ggc_mx<tree_node*> >>>> /home/kugan/work/sources/gcc-fsf/test/gcc/vec.h:1152 >>>> 0x802e36 gt_ggc_mx_vec_tree_va_gc_(void*) >>>> >>>> /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1205 >>>> 0x8081ed gt_ggc_mx_gimple_df(void*) >>>> >>>> /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1066 >>>> 0x80825f gt_ggc_mx_function >>>> >>>> /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1280 >>>> 0x80825f gt_ggc_mx_function(void*) >>>> >>>> /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1272 >>>> 0x55f692 gt_ggc_mx_lang_tree_node(void*) >>>> ./gt-c-c-decl.h:389 >>>> 0x807dd5 gt_ggc_mx_symtab_node_def(void*) >>>> >>>> /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:709 >>>> 0x807fb0 gt_ggc_m_P15symtab_node_def4htab(void*) >>>> >>>> /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:2928 >>>> 0x7b7915 ggc_mark_root_tab >>>> /home/kugan/work/sources/gcc-fsf/test/gcc/ggc-common.c:133 >>>> 0x7b7c60 ggc_mark_roots() >>>> /home/kugan/work/sources/gcc-fsf/test/gcc/ggc-common.c:152 >>>> 0x615669 ggc_collect() >>>> /home/kugan/work/sources/gcc-fsf/test/gcc/ggc-page.c:2077 >>>> >>>> >>>> >>>> >>>> Thanks a lot. >>>> >>>> Kugan >>>> >>>> >>>>> Richard. >>>>> >>>>>>> +void >>>>>>> +set_range_info (tree name, double_int min, >>>>>>> + double_int max, bool vr_range) >>>>>>> >>>>>>> you have some whitespace issues here (please properly use tabs) >>>>>>> >>>>>> >>>>>> I will change it. >>>>>> >>>>>>> + /* Allocate if not available. */ >>>>>>> + if (ri == NULL) >>>>>>> + { >>>>>>> + ri = ggc_alloc_cleared_range_info_def (); >>>>>>> + mark_range_info_unknown (ri); >>>>>>> >>>>>>> that looks superfluous to me. >>>>>>> >>>>>>> + SSA_NAME_RANGE_INFO (name) = ri; >>>>>>> >>>>>>> - /* 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 ("0"))) ptr_info_def *ptr_info; >>>>>>> + /* Value range attributes used for zero/sign extension >>>>>>> elimination. */ >>>>>>> + struct GTY ((tag ("1"))) range_info_def *range_info; >>>>>>> + } GTY ((desc ("%1.def_stmt && !POINTER_TYPE_P (TREE_TYPE >>>>>>> ((tree)&%1))"))) vrp; >>>>>>> >>>>>>> please change vrp_info_type and vrp to other names - this is not vrp >>>>>>> specific info >>>>>>> after all, I suggest ssa_name_info_type and info. >>>>>>> >>>>>> >>>>>> I will change this too. >>>>>>> >>>>>>> The genric bits otherwise look ok to me, the VRP bits still look >>>>>>> wrong >>>>>>> (see my >>>>>>> above question) and need explanation. >>>>>>> >>>>>>> Thanks, >>>>>>> Richard. >>>>>>> >>>>>>>> >>>>>>>> Thanks, >>>>>>>> Kugan >>>>>> >>>>>> >>>>>> >>>>>> Thanks, >>>>>> Kugan >>>>>> >>>>> >>>> >> >> >
Thanks Jakub for the review. On 10/09/13 23:10, Jakub Jelinek wrote: > On Tue, Sep 10, 2013 at 03:17:50PM +0200, Richard Biener wrote: >>> unsigned short s; >>> s.1_3 = (short unsigned int) l.0_2; >>> l.0_2: VARYING >>> s.1_3: [0, +INF] >> >> Note that [0, +INF] is the same as VARYING and [-INF, +INF] and VARYING for >> l.0_2 is the same as [-INF, +INF]. > > Yeah, I don't see much value in differentiating between VR_VARYING and > VR_RANGE [TYPE_MIN_VALUE, TYPE_MAX_VALUE] (perhaps a question is what to do > for types with precisions different from TYPE_MODE's bitsize, if we should > store for VARYING/UNDEFINED a range of all possible values in the mode). > Unsigned type will be always >= 0, even if it is VARYING or UNDEFINED. > What is the valid bit good for? Is it meant just for integrals with > > 2*HOST_BITS_PER_WIDE_INT precision, which we can't represent in double_int? > I'd say we just don't want to keep track on the value ranges for those. Ok, I will remove the valid. > And, do we need to distinguish between VR_RANGE and VR_ANTI_RANGE? > I mean, can't we always store the range in VR_RANGE format? Instead of > -[3,7] we'd store [8,2] and define that if the min double_int is bigger than > max double_int, then it is [min,+infinity] merged with [-infinity,max] range > (i.e. -[max+1,min-1])? > Ok, I will change this too. Thanks, Kugan >> Micha just suggested >> >> union vrp_info_type { >> /* Pointer attributes used for alias analysis. */ >> struct GTY ((tag ("0"))) ptr_info_def *ptr_info; >> /* Value range attributes used for zero/sign extension elimination. >> */ >> struct GTY ((tag ("1"))) range_info_def *range_info; >> } GTY ((desc ("%1.typed.type ? !POINTER_TYPE_P (TREE_TYPE > > Why not TREE_TYPE(&%1) here and why the (tree) cast? > > Jakub >
On Wed, 11 Sep 2013, Kugan wrote: > Thanks Jakub for the review. > > On 10/09/13 23:10, Jakub Jelinek wrote: > > On Tue, Sep 10, 2013 at 03:17:50PM +0200, Richard Biener wrote: > > > > unsigned short s; > > > > s.1_3 = (short unsigned int) l.0_2; > > > > l.0_2: VARYING > > > > s.1_3: [0, +INF] > > > > > > Note that [0, +INF] is the same as VARYING and [-INF, +INF] and VARYING > > > for > > > l.0_2 is the same as [-INF, +INF]. > > > > Yeah, I don't see much value in differentiating between VR_VARYING and > > VR_RANGE [TYPE_MIN_VALUE, TYPE_MAX_VALUE] (perhaps a question is what to do > > for types with precisions different from TYPE_MODE's bitsize, if we should > > store for VARYING/UNDEFINED a range of all possible values in the mode). > > Unsigned type will be always >= 0, even if it is VARYING or UNDEFINED. > > What is the valid bit good for? Is it meant just for integrals with > > > 2*HOST_BITS_PER_WIDE_INT precision, which we can't represent in double_int? > > I'd say we just don't want to keep track on the value ranges for those. > > Ok, I will remove the valid. > > > And, do we need to distinguish between VR_RANGE and VR_ANTI_RANGE? > > I mean, can't we always store the range in VR_RANGE format? Instead of > > -[3,7] we'd store [8,2] and define that if the min double_int is bigger than > > max double_int, then it is [min,+infinity] merged with [-infinity,max] range > > (i.e. -[max+1,min-1])? > > > > Ok, I will change this too. Make sure to add a predicate that can tell whether its an anti-range then. Richard.
On Wed, Sep 11, 2013 at 11:02:30AM +0200, Richard Biener wrote: > Make sure to add a predicate that can tell whether its an anti-range > then. Or perhaps extraction routine, that given an SSA_NAME will give you a triplet, { enum value_range_type vr_type; double_int min, max; } For non-integral SSA_NAMEs, or SSA_NAMEs with NULL RANGE_INFO (should include integral types with > 2 * HOST_BITS_PER_WIDE_INT precision) will give you VR_VARYING, for the case where min <= max VR_RANGE and otherwise decode the max > min range into VR_ANTI_RANGE with adjusted min/max? Then the min/max encoding of anti range would be just a more compact way of encoding it to lower memory usage. Jakub
On Wed, 11 Sep 2013, Jakub Jelinek wrote: > On Wed, Sep 11, 2013 at 11:02:30AM +0200, Richard Biener wrote: > > Make sure to add a predicate that can tell whether its an anti-range > > then. > > Or perhaps extraction routine, that given an SSA_NAME will give you > a triplet, > { enum value_range_type vr_type; double_int min, max; } > For non-integral SSA_NAMEs, or SSA_NAMEs with NULL RANGE_INFO > (should include integral types with > 2 * HOST_BITS_PER_WIDE_INT > precision) will give you VR_VARYING, for the case where > min <= max VR_RANGE and otherwise decode the max > min range > into VR_ANTI_RANGE with adjusted min/max? > > Then the min/max encoding of anti range would be just a more compact > way of encoding it to lower memory usage. Yeah, that also works. Richard.
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;