Patchwork Make scev instantiation call compute_overall_effect_of_inner_loop

login
register
mail settings
Submitter Sebastian Pop
Date June 8, 2010, 9:23 p.m.
Message ID <AANLkTilkMtVXw_Pfmx272I8tAVJq6adGYaIKYuzd62r0@mail.gmail.com>
Download mbox | patch
Permalink /patch/55036/
State New
Headers show

Comments

Sebastian Pop - June 8, 2010, 9:23 p.m.
On Tue, Jun 8, 2010 at 14:11, Sebastian Pop <sebpop@gmail.com> wrote:
> Hi,
>
> I remarked that in add_conditions_to_domain, we are adding the exit
> condition of a loop to the basic blocks following the loop.
> Why do we need to do this?
>
> The example I am looking at is a bit more complicated than this,
> but here is an abstraction that shows the problem:
>
> loop
>  bb0:
>    i_0 = phi (0, i_1)
>    i_1 = i_0 + 1
>    if (i_0 < 1000)
>      goto bb1
>    else
>      goto bb2
>
>  bb1:
>     goto bb0
> end_loop
>
> bb2:
>  S;
>
> We want to add the condition "i_0 >= 1000" to the domain of bb2, and
> this fails in my case as the scev analysis is not able to compute the
> overall effect of the inner loop on i_0.  In the end I wrote a patch
> that makes scev return the right answer, and not surprisingly, in the
> simple example above, we insert a useless constraint: 1000 >= 1000.

So here is that other patch that makes the instantiation of the SCEVs
call compute_overall_effect_of_inner_loop when the instantiation
should happen in an outer loop than where the SSA_NAME was defined.

Regstrap in progress on amd64-linux.  Ok for trunk?

Thanks,
Sebastian
Sebastian Pop - June 8, 2010, 11:48 p.m.
On Tue, Jun 8, 2010 at 16:23, Sebastian Pop <sebpop@gmail.com> wrote:
> On Tue, Jun 8, 2010 at 14:11, Sebastian Pop <sebpop@gmail.com> wrote:
>> Hi,
>>
>> I remarked that in add_conditions_to_domain, we are adding the exit
>> condition of a loop to the basic blocks following the loop.
>> Why do we need to do this?
>>
>> The example I am looking at is a bit more complicated than this,
>> but here is an abstraction that shows the problem:
>>
>> loop
>>  bb0:
>>    i_0 = phi (0, i_1)
>>    i_1 = i_0 + 1
>>    if (i_0 < 1000)
>>      goto bb1
>>    else
>>      goto bb2
>>
>>  bb1:
>>     goto bb0
>> end_loop
>>
>> bb2:
>>  S;
>>
>> We want to add the condition "i_0 >= 1000" to the domain of bb2, and
>> this fails in my case as the scev analysis is not able to compute the
>> overall effect of the inner loop on i_0.  In the end I wrote a patch
>> that makes scev return the right answer, and not surprisingly, in the
>> simple example above, we insert a useless constraint: 1000 >= 1000.
>
> So here is that other patch that makes the instantiation of the SCEVs
> call compute_overall_effect_of_inner_loop when the instantiation
> should happen in an outer loop than where the SSA_NAME was defined.
>
> Regstrap in progress on amd64-linux.  Ok for trunk?

Passed regstrap.
Richard Guenther - June 9, 2010, 9:58 a.m.
On Tue, 8 Jun 2010, Sebastian Pop wrote:

> On Tue, Jun 8, 2010 at 16:23, Sebastian Pop <sebpop@gmail.com> wrote:
> > On Tue, Jun 8, 2010 at 14:11, Sebastian Pop <sebpop@gmail.com> wrote:
> >> Hi,
> >>
> >> I remarked that in add_conditions_to_domain, we are adding the exit
> >> condition of a loop to the basic blocks following the loop.
> >> Why do we need to do this?
> >>
> >> The example I am looking at is a bit more complicated than this,
> >> but here is an abstraction that shows the problem:
> >>
> >> loop
> >>  bb0:
> >>    i_0 = phi (0, i_1)
> >>    i_1 = i_0 + 1
> >>    if (i_0 < 1000)
> >>      goto bb1
> >>    else
> >>      goto bb2
> >>
> >>  bb1:
> >>     goto bb0
> >> end_loop
> >>
> >> bb2:
> >>  S;
> >>
> >> We want to add the condition "i_0 >= 1000" to the domain of bb2, and
> >> this fails in my case as the scev analysis is not able to compute the
> >> overall effect of the inner loop on i_0.  In the end I wrote a patch
> >> that makes scev return the right answer, and not surprisingly, in the
> >> simple example above, we insert a useless constraint: 1000 >= 1000.
> >
> > So here is that other patch that makes the instantiation of the SCEVs
> > call compute_overall_effect_of_inner_loop when the instantiation
> > should happen in an outer loop than where the SSA_NAME was defined.
> >
> > Regstrap in progress on amd64-linux.  Ok for trunk?
> 
> Passed regstrap.

Ok.

Thanks,
Richard.
Sebastian Pop - June 9, 2010, 11:40 p.m.
On Wed, Jun 9, 2010 at 04:58, Richard Guenther <rguenther@suse.de> wrote:
> On Tue, 8 Jun 2010, Sebastian Pop wrote:
>
>> On Tue, Jun 8, 2010 at 16:23, Sebastian Pop <sebpop@gmail.com> wrote:
>> > On Tue, Jun 8, 2010 at 14:11, Sebastian Pop <sebpop@gmail.com> wrote:
>> >> Hi,
>> >>
>> >> I remarked that in add_conditions_to_domain, we are adding the exit
>> >> condition of a loop to the basic blocks following the loop.
>> >> Why do we need to do this?
>> >>
>> >> The example I am looking at is a bit more complicated than this,
>> >> but here is an abstraction that shows the problem:
>> >>
>> >> loop
>> >>  bb0:
>> >>    i_0 = phi (0, i_1)
>> >>    i_1 = i_0 + 1
>> >>    if (i_0 < 1000)
>> >>      goto bb1
>> >>    else
>> >>      goto bb2
>> >>
>> >>  bb1:
>> >>     goto bb0
>> >> end_loop
>> >>
>> >> bb2:
>> >>  S;
>> >>
>> >> We want to add the condition "i_0 >= 1000" to the domain of bb2, and
>> >> this fails in my case as the scev analysis is not able to compute the
>> >> overall effect of the inner loop on i_0.  In the end I wrote a patch
>> >> that makes scev return the right answer, and not surprisingly, in the
>> >> simple example above, we insert a useless constraint: 1000 >= 1000.
>> >
>> > So here is that other patch that makes the instantiation of the SCEVs
>> > call compute_overall_effect_of_inner_loop when the instantiation
>> > should happen in an outer loop than where the SSA_NAME was defined.
>> >
>> > Regstrap in progress on amd64-linux.  Ok for trunk?
>>
>> Passed regstrap.
>
> Ok.
>

Committed on trunk r160510.

Patch

From c7a2e1b80c1e1d3c1eb32000b6a70ce4c4f75ed8 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Tue, 8 Jun 2010 13:21:56 -0500
Subject: [PATCH] Call compute_overall_effect_of_inner_loop from instantiate_scev_name.

	* tree-scalar-evolution.c (instantiate_scev_name): Do not fail
	the scev analysis when the variable is not used outside the loop
	in a close phi node: call compute_overall_effect_of_inner_loop.
---
 gcc/tree-scalar-evolution.c |   16 +++++++++++++---
 1 files changed, 13 insertions(+), 3 deletions(-)

diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
index bf564d8..5dce6af 100644
--- a/gcc/tree-scalar-evolution.c
+++ b/gcc/tree-scalar-evolution.c
@@ -2172,9 +2172,19 @@  instantiate_scev_name (basic_block instantiate_below,
       else
 	res = chrec;
 
-      if (res == NULL_TREE
-	  || !dominated_by_p (CDI_DOMINATORS, instantiate_below,
-			      gimple_bb (SSA_NAME_DEF_STMT (res))))
+      /* When ther is no loop_closed_phi_def, it means that the
+	 variable is not used after the loop: try to still compute the
+	 value of the variable when exiting the loop.  */
+      if (res == NULL_TREE)
+	{
+	  loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
+	  res = analyze_scalar_evolution (loop, chrec);
+	  res = compute_overall_effect_of_inner_loop (loop, res);
+	  res = instantiate_scev_r (instantiate_below, evolution_loop, res,
+				    fold_conversions, cache, size_expr);
+	}
+      else if (!dominated_by_p (CDI_DOMINATORS, instantiate_below,
+				gimple_bb (SSA_NAME_DEF_STMT (res))))
 	res = chrec_dont_know;
     }
 
-- 
1.7.0.4