Re: [tree-ssa]: Loop normalization pass

[Pop Sébastian <pop at gauvain dot u-strasbg dot fr>]

On Wed, Jan 15, 2003 at 12:35:29PM -0500, Diego Novillo wrote:
> On Wed, 15 Jan 2003, Daniel Berlin wrote:
> > Diego:
> > > 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.
> > 
> Eh?  Dependence analysis is precisely why we find IVs.  I meant
> doing loop normalization using the information gathered by the
> induction variable pass.
> 

Open64 does exactly what Diego proposed: 
- IV detection,
- reduction to a single IV per loop,
- loop normalization

Here is a comment from be/opt/opt_ivr.h

//   Once all IVs are identified, we can then merge them by replacing
//   those secondary IVs with the primary IV.  Since this is done
//   befor the global copy propagation, we can place a initialization
//   at the beginning of the loop body with a specific equation.  We
//   use the triple (var, var_init, var_step ) to represent an
//   induction variable.  If variable i and j are recognized as IV,
//   (i, init_i, step_i) and (j, init_j, step_j).  We can convert j
//   to be function of i.  The function is:
//   j = init_j + (step_j/step_i)// (i - init_i)
//   The major factor is really (step_j/step_i).  If it is 1, j
//   becomes i + init_j - init_i.  If (init_j - init_i) is less than
//   32K, there is not any register requirement.  If (step_j/step_i)
//   is not a constant, we then need a register for its value.  We
//   probably end up using another register for
//   (step_j/step_i)*init_i.  With all these register consideration,
//   CG would definition want to have some control over the IV
//   conversion.
//
// Note: IV recognition is using copy propagation to do the real code
//       replacement.  Similarly, the Loop Normalization use the same
//       approach.  It is important to coordinate these two
//       transformation.  Currently, we do the IV recognition first.