Re: [lno] some cleanups for scev

[Sebastian Pop <sebastian dot pop at cri dot ensmp dot fr>]

On Thu, Apr 15, 2004 at 06:12:22PM +0200, Zdenek Dvorak wrote:
> Hello,
> 
> > > > @@ -2330,9 +2291,36 @@ follow_ssa_edge_inner_loop_phi (struct l
> > > >  				tree *evolution_of_loop)
> > > >  {
> > > >    struct loop *loop = loop_of_stmt (loop_phi_node);
> > > > -  tree ev = compute_overall_effect_of_inner_loop (loop,
> > > > -						  PHI_RESULT (loop_phi_node));
> > > > +  tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
> > > > +
> > > > +  /* Sometimes, the inner loop is too difficult to analyze, and the
> > > > +     result of the analysis is a symbolic parameter.  */
> > > > +  if (ev == PHI_RESULT (loop_phi_node))
> > > 
> > > note that I have removed whole "symbolic parameter" stuff, as it made us
> > > produce really weird results (what should have been the purpose of it)?
> > 
> > When you have:
> > 
> > "a = f ()"
> > "a = phi (unknown, unknown)"
> > 
> > it is still possible to keep the result under a symbolic form: "a".
> > This mechanism was used in older versions of the analyzer, so it could
> > be a little dusty.
> 
> I still do not understand.  We want the result to be chrec_top in this
> case, don't we?  I.e. we want to know that we cannot say anything sane
> about value of a.
> 


  /* Sometimes, the inner loop is too difficult to analyze, and the
     result of the analysis is a symbolic parameter.  */
  if (ev == PHI_RESULT (loop_phi_node))
    {
      bool res = false;
      int i;

      for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
	{
	  tree arg = PHI_ARG_DEF (loop_phi_node, i);
	  basic_block bb;

	  /* Follow the edges that exit the inner loop.  */
	  bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
	  if (!flow_bb_inside_loop_p (loop, bb))
	    res = res || follow_ssa_edge_in_rhs (outer_loop, arg, halting_phi,
						 evolution_of_loop);
	}

      /* If the path crosses this loop-phi, give up.  */
      if (res == true)
	*evolution_of_loop = chrec_top;

      return res;
    }

When the result of the analyzer for the inner loop is symbolic, we
still have to end the search algorithm and ensure that the analyzed
loop phi node is not on the path that we're searching.  If it is on
this path, then the evolution is chrec_top, otherwise (when res is
false) keep searching the path (and return false).



> Perhaps you could write a more complete example, so that it can be seen
> what you have in mind?
> 

Yes, here it goes:


Example1:

loop_1 
  a = phi (3, c)
  d = foo ()
  c = a + d
endloop_1

I still want to have a -> {3, +, d}


Example2:

loop_2
  d = phi (3, h)
  loop_3
    e = phi (4, f)
    f = foo ()
  endloop_3
  h = d + e
endloop_2

I still want that after having determined that the evolution of "e"
cannot be analyzed further: e -> e be able to determine that e is not
on the path from d to d, and determine that the evolution of d is: 
d -> {3, +, e} even if e cannot be further instantiated.

On the contrary, in the following I want to return chrec_top for d:

loop_2
  d = phi (3, h)
  loop_3
    e = phi (d, f)
    f = foo ()
  endloop_3
  h = e + 7
endloop_2

In this case the path from d to itself runs as follows: d -> h -> e -> d 
and in this case, you want to answer chrec_top after the analysis of the 
inner loop phi e.

> > > So this case never triggers.
> > > 
> > 
> > I don't think so.  
> 
> as I said, I removed this mechanism completely recently, so indeed it
> cannot.
> 

Maybe you should have not removed it completely?