  Polyhedral compilers can perform complex loop optimizations that improve
parallelism and cache behaviour of loops in the input program. These
transformations result in significant performance gains on modern processors
which have large compute power and deep memory hierarchies. The paper,
"Polyhedral Auto-transformation with No Integer Linear Programming", identifies
issues that adversely affect scalability of polyhedral transformation
frameworks; in particular the Pluto algorithm. The construction and solving of
a complex Integer Linear Programming (ILP) problem increases the time taken by
a polyhedral compiler significantly. The paper presents two orthogonal ideas,
which together overcome the scalability issues in the affine scheduling
problem. It first relaxes the ILP to a Linear Programming (LP) problem, thereby
solving a cheaper algorithm. To overcome the sub-optimalities that arise due to
this relaxation, the affine scheduling problem is decomposed into following
three components: (1) Fusion and dimension matching, (2) Loop scaling and
shifting, and (3) Loop skewing. This new auto-transformation framework,
pluto-lp-dfp, significantly improves the time taken by the Pluto algorithm
without sacrificing performance of the generated code. This report first
provides proofs for the theoretical claims made in the paper surrounding
relaxed LP formulation of the Pluto algorithm. The second part of the report
describes an approach to find good loop fusion (or distribution) and loop
permutations that enable tileability. This short report serves as the
supplementary material for the paper.
