Re: [RFC] Have the scalarizer generate vectorizable loops.

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

Hello,

> > > > It passed make -k check with no additional regressions.
> > > > 
> > > > Who can approve this patch ? Sebastian ? DannyB ?
> > > 
> > > I looked at the patch, and it looks fine to me, although it does look
> > > like this code is getting a bit messy.
> > > 
> > > (Personally, I think we should be using SCEV more heavily than we do
> > > now, instead of making up affine style expressions everywhere, like loop
> > > strength reduction)
> > 
> > the reason for this is that ivopts and # of iteration analysis only work
> > with affine ivs,
> >  and having to wrap and unwrap the components from
> > CHRECs would be quite cumbersome (and wasting memory). 
> 
> You are joking, right?
> 
> It ends up looking something like ComputeIterationCount* in
> http://llvm.cs.uiuc.edu/cvsweb/cvsweb.cgi/llvm/lib/Analysis/ScalarEvolution.cpp?rev=1.44&content-type=text/x-cvsweb-markup
> 
> This code looks a heck of a lot nicer than the weird mix of stuff we
> have.

you are joking, right? Not about the part that the code looks nicer, of
course.  But:

>  case Instruction::SetLT:
>      if (LHS->getType()->isInteger() && 
> 
***
>          ExitCond->getOperand(0)->getType()->isSigned()) {
***
> 
>               SCEVHandle TC = HowManyLessThans(LHS, RHS, L);
>                if (!isa<SCEVCouldNotCompute>(TC)) return TC;
>      }
>  break;

yeah, working just with signed loop control variables that do not
overflow makes life much simpler.  Or perhaps that is so that
HowManyLessThans does not have to deal with unsigned comparisons? Does
not really matter, the best part comes:

> SCEVHandle ScalarEvolutionsImpl::
> HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L) {
> ...
>   if (AddRec->isAffine()) {

****
>     // FORNOW: We only support unit strides.
>     SCEVHandle One = SCEVUnknown::getIntegerSCEV(1, RHS->getType());
>     if (AddRec->getOperand(1) != One)
>       return UnknownValue;
****

Now this makes things really easy.  However, not for LLVM:

>     // The number of iterations for "[n,+,1] < m", is m-n.  However, we
>     // don't
>     // know that m is >= n on input to the loop.  If it is, the
>     // condition return
>     // true zero times.  What we really should return, for full
>     // generality, is
>     // SMAX(0, m-n).  Since we cannot check this, we will instead check
>     // for a
>     // canonical loop form: most do-loops will have a check that
>     // dominates the
>     // loop, that only enters the loop if [n-1]<m.  If we can find this
>     // check,
>     // we know that the SMAX will evaluate to m-n, because we know that
>     // m >= n.

Some 40 lines of code that checks for this special case follows.

If everyone agrees that it is sufficient for gcc to handle loops of very
special form, with step one, whose control variable is signed, I may
also write the # of iteration analysis into 100 lines of nice code.
Unfortunately, unlike toy compilers, we probably cannot afford this type
of simplification :-(

Zdenek