Re: cfg merge part 17 - loop datastructure updates

[Jan Hubicka <jh at suse dot cz>]

Zdenek,
will you have time to update the patch today?
I can do that tonight, but I don't want to run into conflict.

> On Mon, May 13, 2002 at 03:02:51PM +0200, Jan Hubicka wrote:
> > +   /* In new loop representation, we store only pointers here.  */
> > +   struct loop **parray;
> 
> Well, I should hope so, since this is a pointer type.
> Aside from that, the comment is less than enlightening.
> 
> > + /* Ratio of frequencies of edges so that one of more latch edges is
> > +    considered to belong to inner loop with same header.  */
> > + #define HEAVY_EDGE_RATIO 8
> 
> 
> >     /* Check all nodes within the loop to see if there are any
> >        successors not in the loop.  Note that a node may have multiple
> >        exiting edges ?????  A node can have one jumping edge and one fallthru
> >        edge so only one of these can exit the loop.  */
> 
> The ??? comment is wrong.  A node can be a switch statement and
> lots of edges can exit the loop.  A node can throw an exception
> and have oodles of edges leaving the loop.  The code seems to
> handle the arbitrary case though.

Yes, I've missed this while pre-reviewing the patch.  It appears that
code does not rely on this anyway.

Concerning the varray, I think both sollutions are approximately at same
costs, but I may be mistaken.  Fast grepping show that there is not much
use for flow_loop_scan.

On CFG branch we do have some other loop structure analysers in
cfgloopanal.c and they works differently - do not save the results to
prepared fields of loop structure, instead they just return it.  For
isntance code to discover invariants simply have it's own structure
containing bitmap of invariant defs.

I believe it is saner API.  I think main motivation of Michael has been
the current design of loop optimizer, but with the idea of designing
loop as multiple passes (unroller, strength reduction and so on), I
think it is cleaner to not do that.

So I would suggest to not invest much energy to flow_scan_loop and
instead slowly replace it by equivaelnts in incremental patch.
> 
> Question: wouldn't it be better to use a varray for the exit_edges
> so that you don't have to test each edge twice?
> 
> > +   if (HEADER_BLOCK (ENTRY_BLOCK_PTR->succ->dest))
> > +     {
> > +       rtx insn;
> > +       edge fallthru, next_e;
> > +       basic_block bb;
> > +       /* We could not redirect edges freely here. On the other hand,
> > + 	 we know that no abnormal edge enters this block, so we can simply
> > + 	 split it into two...  */
> > +       bb = ENTRY_BLOCK_PTR->succ->dest;
> > +       insn = PREV_INSN (first_insn_after_basic_block_note (bb));
> > +       fallthru = split_block (bb, insn);
> > +  
> > +       /* And redirect all edges to second part.  */
> > +       for (e = fallthru->src->pred; e; e = next_e)
> > + 	{
> > + 	  next_e = e->pred_next;
> > + 	  if (e->src == ENTRY_BLOCK_PTR)
> > + 	    continue;
> > + 	  fallthru->src->frequency -= EDGE_FREQUENCY (e);
> > + 	  fallthru->src->count -= e->count;
> > + 	  if (fallthru->src->frequency < 0)
> > + 	    fallthru->src->frequency = 0;
> > + 	  if (fallthru->src->count < 0)
> > + 	    fallthru->src->count = 1;
> > + 	  redirect_edge_with_latch_update (e, fallthru->dest);
> > + 	}
> 
> Surely this is the same as split_edge(ENTRY_BLOCK_PTR->succ)?
> Or, if additional code needed for latch/header updates, can still
> be greatly simplified.

Hmm yes, I am doing similar trict for EXIT_BLOCK_PTR in the loop
optimizer and it works well.

Thanks!
Honza