Re: [tree-ssa]: Loop normalization pass

[Daniel Berlin <dberlin at dberlin dot org>]

On Wednesday, January 15, 2003, at 11:52  AM, Diego Novillo wrote:

> On Tue, 14 Jan 2003, Daniel Berlin wrote:
>
> > Normalizes loops to start at 1 (or would we rather 0), and have a 
> > stride
> > of 1.
> For C, I would rather normalize at 0.  For Fortran, I think 1
> would make more sense.  But I don't know how g95 generates array
> references.  Maybe a runtime argument?
I'll just normalize to zero, given what Steven said.

> If we implement an induction variable finder a-la Wolfe's "Beyond
> Induction Variables", maybe wouldn't need this pre-pass?
No, although wolfe has strong feelings on not doing loop normalization 
(on the other hand, every commercial compiler i know of does it)
It's more for dependence analysis than it is for induction variable 
finding.

> > It currently doesn't create the new statements in GIMPLE form, mainly
> > because it's pointless at the moment, since the SSA needs to be 
> > rebuilt
> > anyway.  Once we have an SSA form we can update easily, i'll create 
> > GIMPLE
> > statements and update it.
> Why?
Because it's pointless at the moment.

> SSA and GIMPLE are not related.  I don't see why you're not
> generating GIMPLE statements.  At worst, you could generate
> arbitrary code and re-run the gimplifier.
Yes, I know.
But without copy and constant propagation, it just makes things worse.
To build the best GIMPLE statements without copy prop requires checking 
which of the pieces turned out to be constant as we build it.

If you really want me to run simplify_stmt on the end expressions, i 
will, but it's silly until we can chain passes together anyway.

> > Bootstrapped with -O2 -fno-tree-ccp -ftree-loop on 
> > powerpc-apple-darwin6.3.
> Why no CCP?  It should work.
No it won't, we won't have refs for the new loop counter variable, and 
CCP is run *after* loop normalization right now.
If you want me to switch them around, i'll bootstrap with ccp.

> > Index: tree-loop.c
> > ===================================================================
> > RCS file: tree-loop.c
> > diff -N tree-loop.c
> > --- /dev/null	1 Jan 1970 00:00:00 -0000
> > +++ tree-loop.c	14 Jan 2003 15:33:39 -0000
> > @@ -0,0 +1,570 @@
> > +/* Loop optimizations for trees
> > +   Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc.
> > +   Contributed by Daniel Berlin <dan@dberlin.org>
> > +
> > +This file is part of GNU CC.
> > +
> Old copyright notice.  Use one that refers to GCC, not GNU CC.
> Also, some lines are a bit too long and they wrap beyond 80
> columns.
Sure.

> > +/* Count number of times lc is incremented. */
> > +static int
> > +count_lc_increments (lc, loop_start_bb)
> > +     tree_ref lc;
> > +     basic_block loop_start_bb;
> > +{
> > +  int defs = 0;
> > +  basic_block bb;
> > +  FOR_BB_BETWEEN (bb, loop_start_bb, latch_block (loop_start_bb), 
> > next_bb)
> > +  {
> > +    ref_list_iterator rli;
> > +    rli = rli_start (bb_refs (bb));
> > +    for (; !rli_after_end (rli); rli_step (&rli))
> Hmm, I'm in the process of rewriting large chunks of the
> infrastructure.  It should reduce memory usage.  It also moves
> much of the dataflow information into the statements.  bb_refs()
> is gone as is most of the tree_ref stuff.  I should be done any
> day now (FLW).
I know.

> > +/**
> > +   @brief Find the loop counter initialization statement.
> > +   @param lc Loop counter.
> > +   @param lc_rphi Phi reached from conditional used to exit loop  
> > (i.e. in i >
> I've found doxygen markers more annoying than helpful.  Besides,
> if the rest of the compiler doesn't use them, it's difficult to
> justify the effort of keeping them up-to-date.  I think that just
> delimiting comments with /** */ should be enough for our
> purposes.
Okey.

> > +static tree_ref
> > +find_lc_init_in_phi (lc, lc_rphi, loop_start_bb)
> > +     tree_ref lc ATTRIBUTE_UNUSED;
> > +     tree_ref lc_rphi;
> > +     basic_block loop_start_bb;
> > +{
> > +  /* The initialization statement, after GIMPLEification, comes
> > +     immediately before the loop.  So it must be in one of the
> > +     immediate predecessors of the loop_expr's basic block*/
> >                                                         ^^^^^
> Formatting.
Fixed.

> > +static void
> > +normalize_loops  (fn)
> > +     tree fn ATTRIBUTE_UNUSED;
> > +{
> > +  basic_block bb;
> > +
> > +  FOR_EACH_BB (bb)
> > +  {
> > +    if (bb->flags &  BB_LOOP_CONTROL_EXPR)
> > +      {
> > +	gimple_stmt_iterator gsi;
> > +	gsi = gsi_start_bb (bb);
> > +	for (; !gsi_end_bb (gsi); gsi_step_bb (&gsi))
> > +         {
> Why do you need this for() statement?  If you check for
> bb->flags & (BB_LOOP_CONTROL_EXPR | BB_COMPOUND_ENTRY), you
> should get the entry block to a loop such that its first
> statement is a LOOP_EXPR.
I wasn't clear on what combination of flags would give it to me, so i 
did it the hard way.
I'll modify it to check the right flags.

> Another thing you could do is use flow_loops_find in cfgloop.c.
> You can then go through all the loops that start with LOOP_EXPR
> statements.  Granted, this might be faster since tree CFGs are so
> structured, but flow_loops_find computes other data that you
> might find useful for other things.
No, it doesn't work, canonicalize_shared_headers segfaults us.
I've tried it.
> > +           tree stmt = gsi_stmt (gsi);
> > +           if (TREE_CODE (stmt) == LOOP_EXPR)
> > +             {
> > +               gimple_stmt_iterator gsi2;
> > +               gsi2 = gsi_start (&LOOP_EXPR_BODY (stmt));
> > +               for (; !gsi_end (gsi2); gsi_step (&gsi2))
> > +                 {
> > +                   tree stmt2 = gsi_stmt (gsi2);
> > +                   if (stmt2 && TREE_CODE (stmt2) == COND_EXPR)
> > +                     if (TREE_CODE (COND_EXPR_THEN (stmt2)) == 
> > GOTO_EXPR)
> > +                       {
> > +                         normalize_loop (stmt, stmt2);
> This looks wrong.  stmt2 could be a GOTO_EXPR to a statement
> inside the loop.
Only if loop norm is run after an optimization that can move 
conditional statements, or inserts ifs and gotos.
Otherwise, the *first* cond/goto will be the exit.
Always.
I have a "break" in the line after normalize_loop now, so that it only 
does it for the first one we see.
This is, however, a pre-pass, so i don't really think we need to make 
it amazingly general and able to run at any time.

>  It would be safer to use the loop structure
> here.  Not all LOOP_EXPRs are for() loops.
In fact, none of them are.
All LOOP_EXPRS are while loops.
I'm also not going to use the loop structure until i need to, as i'm 
not up for fixing the tree/rtl difference in 
canonicalize_shared_headers right now.
It would also be much slower, with no real benefit.