Re: unflattening fortran matrices

[Janne Blomqvist <blomqvist dot janne at gmail dot com>]

Hi,

sorry for taking so long to respond. I'm cc:ing the main gcc@ list as 
well, in case someone more knowledgeable than me wants to set the story 
straight. :)

Paul Thomas wrote:
> Before welcoming patches, perhaps you can convince the uninitiates what 
> this would do for us.  The debug side I can understand but exactly which 
> vectorization features would we miss?

Well, I'm not an expert but in general I think the problem is dependency 
analysis. To be able to do a lot of optimizations (vectorization and 
others as well) the middle end needs to be able to figure out e.g. that 
a(i,j) and a(i2, j2) are different memory addresses (for a loop body 
during any iteration of the loop or somesuch). If the array information 
is passed as such to the middle end this is easy; just check that (i != 
i2 || j != j2). This is not as easy to figure out if the middle end 
instead gets a 1D array reference with a non-trivial index expression.

Another one, e.g.

do i = 1, N
  do j = 1, M
     a(i,j) = b + c(i,j)
  end do
end do

Any Fortran user should immediately see that we're accessing a and c in 
the wrong order, but I suspect there's still plenty of code out there 
that gets it wrong. If the optimizer can figure out that there is no 
dependency, it can switch the loops or alternatively transpose the array 
by manipulating the descriptor 
(http://gcc.gnu.org/wiki/MatrixReorganization), and not only does the 
loop then vectorize, we get better memory locality as well.

Yet another one, outer loop vectorization, see 
http://gcc.gnu.org/wiki/VectorizationTasks

Another thing is that array flattening is actually a useful optimization 
(http://gcc.gnu.org/wiki/MatrixReorganization). Gfortran gets it "for 
free", but AFAICT not in a beneficial way as the benefit is in reducing 
the overhead in updating loop counters; in gfortran we still have the 
original nested loops for walking over a flattened array.

> Are they such that we could 
> forego this rebuild of gfortran by signalling the multi-dimensionality 
> of arrays to the vectorizer?

Hmm, maybe. Apparently there is some work in that direction 
(http://gcc.gnu.org/wiki/LoopOptTasks): "Index recovery (Daniel Berlin & 
Richard Guenther, medium): Recover the values of the indices of 
multidimensional arrays represented as one-dimensional arrays (often 
used in C; see also the "Not flattening Fortran arrays" task), using the 
induction variable analysis and value range information.". If that would 
work I guess it could be much less work than doing major surgery on 
gfortran?

>  Alternatively, can we pre-empt the 
> necessary vectorizer steps in the front-end; cf. Toon's talk to the gcc 
> summit?  (I haven't forgotten common factor elimination, Toon:-) ).

Yes, I've read Toon's paper. Though I think it's worth distinguishing 
between general and Fortran-specific optimizations. For the general 
optimizations, the middle-end is staffed by a bunch of clever people 
with Phd:s in compilerology working to some extent full time on gcc. 
Leveraging the efforts of these people where possible is, IMHO, the only 
sensible way. For the Fortran-specific stuff like optimizations of array 
expressions I suppose there's no particular value in pushing these 
things to the middle-end, if nobody else is going to be interested in 
maintaining them anyway.

--
Janne Blomqvist