The polyhedral representation enabled by the Graphite project is currently limited to Static Control Parts (SCoPs). This page gives some directions on how to extend the representation for complete code. Not only the representation is essential, but also the ability to generate efficient code.

This page is in progress of being converted from the following document: PolyhedralModelExtensions.pdf

The basis

Non-manifest expressions

The iteration domains in the polyhedral model are polyhedra (hence the name): they are defined by a set of equations where each equation is an affine function of domain dimensions. Such a constraint can only be generated for loops where the bounds are statically known (as a function of outer loop iterators). Such a loop is called manifest. In addition, array index expressions are represented as affine mappings of the domain dimensions to the array dimensions. These limitations can be overcome by extending the model to non-manifest, non-affine expressions.

We'll call the non-manifest, non-affine sub-expression the data-dependent part.

Representation of non-manifest or non-affine expressions

Data-dependent index expressions

Most analyses (e.g. dependence analysis) can either project away the parameters, or exploit equality between parameters.

Data-dependent conditions

Equivalent to if-conversion [AKPW83].

In code generation, generate conditions for data-dependent constraints as soon as all loops on which the data-dependent parts depend have been generated.

Data-dependent loop bounds

No issues for modelling, it's even possible to leave out the bound completely. The problem is in code generation: you don't want to generate loops without upper bound (i.e. endless loops).

If range propagation yields worst-case bounds for the control variable, these can be used as loop bounds when generating code. However, could lead to many empty iterations.

Technique proposed in [Gei97]:

While loops

A while loop is any loop for which no controlling iterator can be found, i.e. it contains no induction variable or none of the induction variables appear in the exit condition.

[Gei97] again proposes a technique for while loops. It involves generating an artificial iterator which starts at zero. Its upper bound depends on itself: it is updated inside the loop. This creates a loop carried dependence, which is preferably modelled by explicitly adding a dependence rather than extracting it from an extra statement.

Irregular control flow

Irregular control flow mainly appears due to breaks, gotos and short-circuit operators in the loop control expressions. [EH94] proposes control flow restructuring, which can convert any control flow into a tree of nested loops. It involves the creation of additional variables, but these are anyway already present in the three-address SSA representation. It also adds many conditions to the code. However, the extra conditions don't need to be added explicitly, they are only used to construct the polyhedral constraints.

During code generation these extra conditions do appear. It should be possible to remove them through a combination of common subexpression elimination and control-flow optimizations.

Non-array data

Array accesses are represented by index mappings. Pointers are already converted into iterator-dependent expressions [VEG01].

We can distinguish between array data, scalar data and aliased data.

Accesses to array data which are not through index expressions are represented by data-dependent (sub)expressions.

Data layout transformations are difficult for non-array data, because also the declaration has to be modified. ArnoutVandecappelle therefore thinks it is better not to perform data layout transformations inside the polyhedral model, but on some other representation.


Loop transformations are sometimes unnecessarily constrained by reduction operators. This can be overcome during the dependency analysis: if an assignment is a reduction (i.e. of the form  a = a op b; , where op is an associative operator like + and there is no risk of overflow), the corresponding loop-carried dependence can be removed and replaced directly by a dependence to the final result. However, the code generator must also take this into account.

Efficient polyhedral representation

With all these extensions, the polyhedral model will grow very large. An efficient representation is therefore required.


J. R. Allen, Ken Kennedy, Carrie Porterfield, and Joe Warren. Conversion of control dependence to data dependence. In POPL '83: Proceedings of the 10th ACM SIGACT- SIGPLAN symposium on Principles of programming languages, pages 177- 189, New York, NY, USA, 1983. ACM.
Eddy De Greef, Francky Catthoor, and Hugo De Man. Memory size reduction through storage order optimization for embedded parallel multimedia applications. Parallel Computing, special issue on "Parallel Processing in Multi-media" (ed. A.Krikelis), Elsevier, 23(12), December 1997.
Ana M. Erosa and Laurie J. Hendren. Taming Control Flow: A Structured Approach to Eliminating GOTO Statements. In Proc. 1994 Intnl. Conf. on Computer Languages (ICCL), pages 229- 240, May 1994.
Max Geigl. Parallelization of loop nests with general bounds in the polyhedron model. Master's thesis, University Passau, Germany, March 1997.
Sylvain Girbal, Nicolas Vasilache, Cédric Bastoul, Albert Cohen, David Parello, Marc Sigler, and Olivier Temam. Semi- automatic composition of loop transformations for deep parallelism and memory hierarchies. Int. J. Parallel Program. , 34(3):261- 317, 2006.
W. Harrison. Compiler analysis of the value ranges for variables. IEEE Trans. Software Eng., SE-3:243- 250, May 1977.
Chris J. Newburn, Derek B. Noonburg, and John Paul Shen. A PDG-based tool and its use in analyzing program control dependences. In PACT '94: Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques, pages 157- 168, Amsterdam, The Netherlands, The Netherlands, 1994. North- Holland Publishing Co.
Preeti Ranjan Panda, Hiroshi Nakamura, Nikil D. Dutt, and Alexandru Nicolau. Augmenting loop tiling with data alignment for improved cache performance. IEEE Trans. Comput. , 48(2):142- 149, 1999.
Sebastian Pop, Georges-André Silber, Albert Cohen, Cédric Bastoul, Sylvain Girbal, and Nicolas Vasilache. Graphite: Polyhedral analyses and optimizations for gcc. In GNU Compilers Collection Developers Summit , Ottawa, Canada, June 28- 30 2006.
W. Pugh and D. Wonnacott. Nonlinear array dependence analysis. In B. K. Szymanski and B. Sinharoy, editors, Languages, Compilers and Run-Time Systems for Scalable Computers, pages 1-14. Kluwer Academic Publishers, Boston, 1995.
Fabien Quilleré, Sanjay Rajopadhye, and Doran Wilde. Generation of efficient nested loops from polyhedra. Int. J. Parallel Program. , 28(5):469- 498, 2000.
B. Ramakrishna Rau. Data flow and dependence analysis for instruction level parallelism. In Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing , pages 236- 250, London, UK, 1992. Springer- Verlag.
Sven Verdoolaege, Maurice Bruynooghe, Gerda Janssens, and Francky Catthoor. Multi- dimensional incremental loop fusion for data locality. In Proc. Int. Conf. on Application- specific Systems, Architectures and Processors (ASAP), pages 17- 27, The Hague, The Netherlands, June 2003.
Nicolas Vasilache, Albert Cohen, and Louis-Noël Pouchet. Automatic correction of loop transformations. In Proc. 16th Intnl. Conf. on Parallel Architecture and Compilation Techniques (PACT 2007) , pages 292- 304, Brasov, Romania, 15- 19 September 2007.
Robert A. Van Engelen and Kyle A. Gallivan. An efficient algorithm for pointer- to- array access conversion for compiling and optimizing DSP applications. In Innovative Architecture for Future Generation High- Performance Processors and Systems, pages 80- 89, Maui, Hawaii, 2001.
Peter Vanbroekhoven, Gerda Janssens, Maurice Bruynooghe, Henk Corporaal, and Francky Catthoor. Advanced copy propagation for arrays. In Proceedings of the 2003 ACM SIGPLAN Conference on Languages, Compilers and Tools for Embedded Systems (LCTES'03), pages 24- 33. ACM SIGPLAN, ACM Press, 2003.
Peter Vanbroekhoven, Gerda Janssens, Maurice Bruynooghe, and Francky Catthoor. A practical dynamic single assignment transformation. ACM Transactions on Design Automation of Electronic Systems, accepted 2007.

None: PolyhedralModelExtensions (last edited 2008-06-04 15:08:49 by c-76-111-171-34)