  Optimizing compilers are mainly equipped to optimize control flow. The
optimization of data structures is left to the programmer and it is the
programmer's responsibility to design the data structures to suit the target
hardware. Very specific data structures are required to exploit certain
hardware features, such as cache line size, address alignment, vector width,
and memory hierarchy specifics. Because optimizing compilers do not target data
structures, these features are explicitly encoded in program specifications.
This leads to convoluted programs that obscure the essence of the computation
from the compiler, in turn causing compiler analysis techniques to break down
and hampering compiler optimizations from being applied.
  To solve this problem, we propose to move towards the specification of
programs without explicitly specifying the data structure. The compiler will
automatically generate actual data structures and executable code starting from
this specification. In this paper, we introduce a compiler-based framework to
support this automatic generation of data structures, allowing the compiler to
go beyond the optimization of solely control flow and also target the way data
is organized and accessed. As a case study of the effectiveness of this
framework, we present a detailed description and experimental results of the
application of the proposed techniques to automatically generate data
structures for sparse matrix computations. We show that this way sparse data
structures can be generated that were up till now only specified by hand and
that automatically instantiated routines and corresponding data structures can
be found that outperform implementations of three existing sparse algebra
libraries.
