| Message ID | 881b2805-15ec-ad68-96a5-e2debd2fb850@linaro.org |
|---|---|
| State | New |
| Headers | show |
On Sat, Oct 8, 2016 at 9:38 PM, kugan <kugan.vivekanandarajah@linaro.org> wrote: > Hi Richard, > > Thanks for the review. > On 07/10/16 20:11, Richard Biener wrote: >> >> On Fri, Oct 7, 2016 at 12:00 AM, kugan >> <kugan.vivekanandarajah@linaro.org> wrote: >>> >>> Hi, >>> >>> In vrp intersect_ranges, Richard recently changed it to create integer >>> value >>> ranges when it is integer singleton. >>> >>> Maybe we should do the same when the other range is a complex ranges with >>> SSA_NAME (like [x+2, +INF])? >>> >>> Attached patch tries to do this. There are cases where it will be >>> beneficial >>> as the testcase in the patch. (For this testcase to work with Early VRP, >>> we >>> need the patch posted at >>> https://gcc.gnu.org/ml/gcc-patches/2016-10/msg00413.html) >>> >>> Bootstrapped and regression tested on x86_64-linux-gnu with no new >>> regressions. >> >> >> This is not clearly a win, in fact it can completely lose an ASSERT_EXPR >> because there is no way to add its effect back as an equivalence. The >> current choice of always using the "left" keeps the ASSERT_EXPR range >> and is able to record the other range via an equivalence. > > > How about changing the order in Early VRP when we are dealing with the same > SSA_NAME in inner and outer scope. Here is a patch that does this. Is this > OK if no new regressions? I'm not sure if this is a good way forward. The failure with the testcase is that we don't extract a range for k from if (j < k) which I believe another patch from you addresses? As said the issue is with the equivalence / value-range representation so you can't do sth like /* Discover VR when condition is true. */ extract_range_for_var_from_comparison_expr (op0, code, op0, op1, &vr); if (old_vr->type == VR_RANGE || old_vr->type == VR_ANTI_RANGE) vrp_intersect_ranges (&vr, old_vr); /* If we found any usable VR, set the VR to ssa_name and create a PUSH old value in the stack with the old VR. */ if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE) { new_vr = vrp_value_range_pool.allocate (); *new_vr = vr; push_value_range (op0, new_vr); ->>> add equivalence to old_vr for new_vr. because old_vr and new_vr are the 'same' (they are associated with SSA name op0) Richard. > Thanks, > Kugan > > > > > >> My thought on this was that we need to separate "ranges" and associated >> SSA names so we can introduce new ranges w/o the need for an SSA name >> (and thus we can create an equivalence to the ASSERT_EXPR range). >> IIRC I started on this at some point but never finished it ... >> >> Richard. >> >>> Thanks, >>> Kugan >>> >>> >>> gcc/testsuite/ChangeLog: >>> >>> 2016-10-07 Kugan Vivekanandarajah <kuganv@linaro.org> >>> >>> * gcc.dg/tree-ssa/evrp6.c: New test. >>> >>> gcc/ChangeLog: >>> >>> 2016-10-07 Kugan Vivekanandarajah <kuganv@linaro.org> >>> >>> * tree-vrp.c (intersect_ranges): If we failed to handle >>> the intersection and the other range involves computation with >>> symbolic values, choose integer range if available. >>> >>> >>> >
Hi Richard, On 10/10/16 20:13, Richard Biener wrote: > On Sat, Oct 8, 2016 at 9:38 PM, kugan <kugan.vivekanandarajah@linaro.org> wrote: >> Hi Richard, >> >> Thanks for the review. >> On 07/10/16 20:11, Richard Biener wrote: >>> >>> On Fri, Oct 7, 2016 at 12:00 AM, kugan >>> <kugan.vivekanandarajah@linaro.org> wrote: >>>> >>>> Hi, >>>> >>>> In vrp intersect_ranges, Richard recently changed it to create integer >>>> value >>>> ranges when it is integer singleton. >>>> >>>> Maybe we should do the same when the other range is a complex ranges with >>>> SSA_NAME (like [x+2, +INF])? >>>> >>>> Attached patch tries to do this. There are cases where it will be >>>> beneficial >>>> as the testcase in the patch. (For this testcase to work with Early VRP, >>>> we >>>> need the patch posted at >>>> https://gcc.gnu.org/ml/gcc-patches/2016-10/msg00413.html) >>>> >>>> Bootstrapped and regression tested on x86_64-linux-gnu with no new >>>> regressions. >>> >>> >>> This is not clearly a win, in fact it can completely lose an ASSERT_EXPR >>> because there is no way to add its effect back as an equivalence. The >>> current choice of always using the "left" keeps the ASSERT_EXPR range >>> and is able to record the other range via an equivalence. >> >> >> How about changing the order in Early VRP when we are dealing with the same >> SSA_NAME in inner and outer scope. Here is a patch that does this. Is this >> OK if no new regressions? > > I'm not sure if this is a good way forward. The failure with the testcase is > that we don't extract a range for k from if (j < k) which I believe another > patch from you addresses? Yes, I have committed that. I am trying to add test cases for this and thats when I stumbled on this: For: foo (int k, int j) { <bb 2>: if (j_1(D) > 9) goto <bb 3>; else goto <bb 6>; <bb 3>: if (j_1(D) < k_2(D)) goto <bb 4>; else goto <bb 6>; <bb 4>: k_3 = k_2(D) + 1; if (k_2(D) <= 8) goto <bb 5>; else goto <bb 6>; <bb 5>: abort (); <bb 6>: return j_1(D); } Before we look at - if (j_1(D) < k_2(D)) j_1 (D) has [10, +INF] EQUIVALENCES: { j_1(D) } (1 elements) When we look at if (j_1(D) < k_2(D)) The range is [-INF, k_2(D) + -1] EQUIVALENCES: { j_1(D) } (1 elements) We intersect: [-INF, k_2(D) + -1] EQUIVALENCES: { j_1(D) } (1 elements) and [10, +INF] EQUIVALENCES: { j_1(D) } (1 elements) to [-INF, k_2(D) + -1] EQUIVALENCES: { j_1(D) } (1 elements) Due to this, in if (j_1(D) < k_2(D)) , we get pessimistic value range for k_2(D) Thanks, Kugan > As said the issue is with the equivalence / value-range representation so > you can't do sth like > > /* Discover VR when condition is true. */ > extract_range_for_var_from_comparison_expr (op0, code, op0, op1, &vr); > if (old_vr->type == VR_RANGE || old_vr->type == VR_ANTI_RANGE) > vrp_intersect_ranges (&vr, old_vr); > > /* If we found any usable VR, set the VR to ssa_name and create a > PUSH old value in the stack with the old VR. */ > if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE) > { > new_vr = vrp_value_range_pool.allocate (); > *new_vr = vr; > push_value_range (op0, new_vr); > ->>> add equivalence to old_vr for new_vr. > > because old_vr and new_vr are the 'same' (they are associated with SSA name op0) > > Richard. > >> Thanks, >> Kugan >> >> >> >> >> >>> My thought on this was that we need to separate "ranges" and associated >>> SSA names so we can introduce new ranges w/o the need for an SSA name >>> (and thus we can create an equivalence to the ASSERT_EXPR range). >>> IIRC I started on this at some point but never finished it ... >>> >>> Richard. >>> >>>> Thanks, >>>> Kugan >>>> >>>> >>>> gcc/testsuite/ChangeLog: >>>> >>>> 2016-10-07 Kugan Vivekanandarajah <kuganv@linaro.org> >>>> >>>> * gcc.dg/tree-ssa/evrp6.c: New test. >>>> >>>> gcc/ChangeLog: >>>> >>>> 2016-10-07 Kugan Vivekanandarajah <kuganv@linaro.org> >>>> >>>> * tree-vrp.c (intersect_ranges): If we failed to handle >>>> the intersection and the other range involves computation with >>>> symbolic values, choose integer range if available. >>>> >>>> >>>> >>
On Tue, Oct 11, 2016 at 2:57 AM, kugan <kugan.vivekanandarajah@linaro.org> wrote: > Hi Richard, > > > On 10/10/16 20:13, Richard Biener wrote: >> >> On Sat, Oct 8, 2016 at 9:38 PM, kugan <kugan.vivekanandarajah@linaro.org> >> wrote: >>> >>> Hi Richard, >>> >>> Thanks for the review. >>> On 07/10/16 20:11, Richard Biener wrote: >>>> >>>> >>>> On Fri, Oct 7, 2016 at 12:00 AM, kugan >>>> <kugan.vivekanandarajah@linaro.org> wrote: >>>>> >>>>> >>>>> Hi, >>>>> >>>>> In vrp intersect_ranges, Richard recently changed it to create integer >>>>> value >>>>> ranges when it is integer singleton. >>>>> >>>>> Maybe we should do the same when the other range is a complex ranges >>>>> with >>>>> SSA_NAME (like [x+2, +INF])? >>>>> >>>>> Attached patch tries to do this. There are cases where it will be >>>>> beneficial >>>>> as the testcase in the patch. (For this testcase to work with Early >>>>> VRP, >>>>> we >>>>> need the patch posted at >>>>> https://gcc.gnu.org/ml/gcc-patches/2016-10/msg00413.html) >>>>> >>>>> Bootstrapped and regression tested on x86_64-linux-gnu with no new >>>>> regressions. >>>> >>>> >>>> >>>> This is not clearly a win, in fact it can completely lose an ASSERT_EXPR >>>> because there is no way to add its effect back as an equivalence. The >>>> current choice of always using the "left" keeps the ASSERT_EXPR range >>>> and is able to record the other range via an equivalence. >>> >>> >>> >>> How about changing the order in Early VRP when we are dealing with the >>> same >>> SSA_NAME in inner and outer scope. Here is a patch that does this. Is >>> this >>> OK if no new regressions? >> >> >> I'm not sure if this is a good way forward. The failure with the testcase >> is >> that we don't extract a range for k from if (j < k) which I believe >> another >> patch from you addresses? > > > Yes, I have committed that. I am trying to add test cases for this and > thats when I stumbled on this: > > For: > foo (int k, int j) > { > <bb 2>: > if (j_1(D) > 9) > goto <bb 3>; > else > goto <bb 6>; > > <bb 3>: > if (j_1(D) < k_2(D)) > goto <bb 4>; > else > goto <bb 6>; > > <bb 4>: > k_3 = k_2(D) + 1; > if (k_2(D) <= 8) > goto <bb 5>; > else > goto <bb 6>; > > <bb 5>: > abort (); > > <bb 6>: > return j_1(D); > > } > > Before we look at - if (j_1(D) < k_2(D)) > j_1 (D) has [10, +INF] EQUIVALENCES: { j_1(D) } (1 elements) > > When we look at if (j_1(D) < k_2(D)) > The range is [-INF, k_2(D) + -1] EQUIVALENCES: { j_1(D) } (1 elements) > > We intersect: > [-INF, k_2(D) + -1] EQUIVALENCES: { j_1(D) } (1 elements) > and > [10, +INF] EQUIVALENCES: { j_1(D) } (1 elements) > > to > [-INF, k_2(D) + -1] EQUIVALENCES: { j_1(D) } (1 elements) > > Due to this, in if (j_1(D) < k_2(D)) , we get pessimistic value range for > k_2(D) Ah, but that is because when generating the range for k from j < k we use the updated range for j. That obviously doens't make too much sense. @@ -10650,7 +10661,7 @@ public: virtual void after_dom_children (basic_block); void push_value_range (const_tree var, value_range *vr); value_range *pop_value_range (const_tree var); - void try_add_new_range (tree op, tree_code code, tree limit); + value_range *try_add_new_range (tree op, tree_code code, tree limit); /* Cond_stack holds the old VR. */ auto_vec<std::pair <const_tree, value_range*> > stack; @@ -10661,7 +10672,7 @@ public: /* Add new range to OP such that (OP CODE LIMIT) is true. */ -void +value_range * evrp_dom_walker::try_add_new_range (tree op, tree_code code, tree limit) { value_range vr = VR_INITIALIZER; @@ -10678,8 +10689,9 @@ evrp_dom_walker::try_add_new_range (tree { value_range *new_vr = vrp_value_range_pool.allocate (); *new_vr = vr; - push_value_range (op, new_vr); + return new_vr; } + return NULL; } /* See if there is any new scope is entered with new VR and set that VR to @@ -10715,7 +10727,7 @@ evrp_dom_walker::before_dom_children (ba code = invert_tree_comparison (gimple_cond_code (stmt), HONOR_NANS (op0)); /* Add VR when (OP0 CODE OP1) condition is true. */ - try_add_new_range (op0, code, op1); + value_range *op0_range = try_add_new_range (op0, code, op1); /* Register ranges for y in x < y where y might have ranges that are useful. */ @@ -10728,8 +10740,13 @@ evrp_dom_walker::before_dom_children (ba &new_code, &limit)) { /* Add VR when (OP1 NEW_CODE LIMIT) condition is true. */ - try_add_new_range (op1, new_code, limit); + value_range *op1_range = try_add_new_range (op1, new_code, limit); + if (op1_range) + push_value_range (op1, op1_range); } + + if (op0_range) + push_value_range (op0, op0_range); } } seems to fix that and the issue. > Thanks, > Kugan > > > >> As said the issue is with the equivalence / value-range representation so >> you can't do sth like >> >> /* Discover VR when condition is true. */ >> extract_range_for_var_from_comparison_expr (op0, code, op0, op1, >> &vr); >> if (old_vr->type == VR_RANGE || old_vr->type == VR_ANTI_RANGE) >> vrp_intersect_ranges (&vr, old_vr); >> >> /* If we found any usable VR, set the VR to ssa_name and create >> a >> PUSH old value in the stack with the old VR. */ >> if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE) >> { >> new_vr = vrp_value_range_pool.allocate (); >> *new_vr = vr; >> push_value_range (op0, new_vr); >> ->>> add equivalence to old_vr for new_vr. >> >> because old_vr and new_vr are the 'same' (they are associated with SSA >> name op0) >> >> Richard. >> >>> Thanks, >>> Kugan >>> >>> >>> >>> >>> >>>> My thought on this was that we need to separate "ranges" and associated >>>> SSA names so we can introduce new ranges w/o the need for an SSA name >>>> (and thus we can create an equivalence to the ASSERT_EXPR range). >>>> IIRC I started on this at some point but never finished it ... >>>> >>>> Richard. >>>> >>>>> Thanks, >>>>> Kugan >>>>> >>>>> >>>>> gcc/testsuite/ChangeLog: >>>>> >>>>> 2016-10-07 Kugan Vivekanandarajah <kuganv@linaro.org> >>>>> >>>>> * gcc.dg/tree-ssa/evrp6.c: New test. >>>>> >>>>> gcc/ChangeLog: >>>>> >>>>> 2016-10-07 Kugan Vivekanandarajah <kuganv@linaro.org> >>>>> >>>>> * tree-vrp.c (intersect_ranges): If we failed to handle >>>>> the intersection and the other range involves computation with >>>>> symbolic values, choose integer range if available. >>>>> >>>>> >>>>> >>> >
From 54e92b7ddc47f6986e4dc79402d6808bb9c30c69 Mon Sep 17 00:00:00 2001 From: Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org> Date: Sat, 8 Oct 2016 15:09:09 +1100 Subject: [PATCH 4/7] Revese value range before calling interset_range --- gcc/testsuite/gcc.dg/tree-ssa/evrp6.c | 22 ++++++++++++++++++++++ gcc/tree-vrp.c | 16 +++++++++++++++- 2 files changed, 37 insertions(+), 1 deletion(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/evrp6.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/evrp6.c b/gcc/testsuite/gcc.dg/tree-ssa/evrp6.c new file mode 100644 index 0000000..35d4d74 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/evrp6.c @@ -0,0 +1,22 @@ + +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + +extern void abort (void); + +int +foo (int k, int j) +{ + if (j >= 10) + { + if (j < k) + { + k++; + if (k < 10) + abort (); + } + } + + return j; +} +/* { dg-final { scan-tree-dump "\\\[12, \\+INF" "evrp" } } */ diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 160adb5..c18c86f 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -10664,7 +10664,21 @@ evrp_dom_walker::try_add_new_range (tree op, tree_code code, tree limit) extract_range_for_var_from_comparison_expr (op, code, op, limit, &vr); if (old_vr->type == VR_RANGE || old_vr->type == VR_ANTI_RANGE) - vrp_intersect_ranges (&vr, old_vr); + { + if (range_int_cst_p (old_vr) + && !range_int_cst_p (&vr)) + { + /* intersect_range will use the left value range to keeps the + ASSERT_EXPR range and record the other range via an equivalence. + In this case, we are tracking value_ranges for same SSA_NAME in + different scope, so reverse it for better result. */ + value_range other_vr = vr; + vr = *old_vr; + vrp_intersect_ranges (&vr, &other_vr); + } + else + vrp_intersect_ranges (&vr, old_vr); + } /* If we found any usable VR, set the VR to ssa_name and create a PUSH old value in the stack with the old VR. */ if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE) -- 2.7.4