Re: loop heuristics tweeks

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello.

> > > Zdenek: I've noticed that you've integrated loop peeling and unrolling into
> > > simple loop unrollers.  This looks like neat idea.  What i am worried about
> > > is whether it is required for correctness?
> > 
> > If you speak about the changes in my last patch, yes, it is requiered for
> > correctness (it ensures that we may remove exits from unrolled loop except for
> > first (last) copy).
> 
> So if I unserdtand it correctly, we now have stand alone loop peeling and
> stand alone loop unrolling code handling generic loops (for peeling only
> innermost loops?)

I think it is a bit confused (at least from what you said :-). This is what is
done (in this order):

loop peeling
  -- loops whose headers are cold are skipped
  -- loops that are not innermost are skipped
  -- maximum number of peelings is counted based on loops size
  -- too big loops are skipped
  -- loops that roll more than this number on average are skipped
  -- number of peelings is set to number of iterations
        /* IMHO these two steps should be only done if profile is available */
  /* -- than I had check if the loop is simple, that you removed.
       You should probably return it back (together with check that the loop
       iterates constant number of times, that I had not there) -- we are able
       to peel such loops more efficiently (removing unused exit edges); maybe
       later optimizations will do it anyway, but why to wait with it till
       then?  
  */
  -- loop is peeled

loop unrolling
  -- cold loops are skipped
  -- maximum number of unrollings is counted based on loops size
  -- too big loops are skipped
  -- if loop is simple then
       {
        if number of iterations is known
          -- if it is small enough, we peel the loop completely and remove
             exit edges
          -- otherwise we peel several iterations so that number of iterations
             of the loop body mod number of unrollings is
                0 if exit check may be on beginning of loop body
                n.of unrollings - 1 if exit check may be on end of loop body
              /* So that exit edge is not in the middle of loop body. */
             and unroll the loop, while removing exit edges from other than
             mentioned copies
        if we can count number of iterations in runtime
          -- we peel n.of unrollings iterations (-1) of the loop and add the
             code to ensure that number of iterations of loop body modulo
             n. of unrollings is 0, resp. n.of unrollings - 1 /* as above */
             and unroll the loop while removing unused exit edges.
       }
     else
       -- if it rolls less then twice the number of unrollings and profile
          is available (so we know it reliably), we skip the loop
       -- loop is unrolled stupidly

Is that more clear now?

Zdenek