• LoopOptTasks

Loop Optimization related tasks

This page is a TODO list for tasks related to loop optimizations, based on my notes from a discussion at GCC Summit 2006. At each task I list the person who proposed the task (and who should be contacted in case you want to start working on it), my rough estimate on the time necessary to finish it (short = hours, long = weeks or months, medium = something in between), and a short description of the project.

The list was updated after GCC Summit 2007. Here is the summary of the Loop-Optimizations BOF that took place at the 2007 GCC summit.

In progress:

• Preserving loop structures during optimizations (Zdenek Dvorak, medium): In order to remember and reuse loop-related information, as well as to be able to mix loop optimization passes with the non-loop related passes, all optimizers should be able to preserve loop structures. This includes making loop structures safe for garbage collection, and teaching some of the optimizers (jump threading and others) not to destroy loops. This project is about to be merged to 4.3.

• Graphite (Sebastian Pop, long): A framework for high-level loop optimizations, see the paper in the GCC Summit proceedings.

• Unstructured memory references (Zdenek Dvorak, medium): Express all memory references using a flat representation (base object and a vector of indices), in order to make work of high-level loop optimizations easier. See http://gcc.gnu.org/ml/gcc/2007-04/msg00096.html for more details.

• Omega dependency tester applications (Sebastian Pop, short): Make Omega the default dependency tester. Use the Omega framework for loopnest local reuse analysis.
• Loop Skewing (Jan Sjodin): Implement loop skewing for the benefit of vectorization.

TODO:

• Cache modeling, whole program reuse analysis (Daniel Berlin, Zdenek Dvorak, long): Develop the infrastructure necessary for describing the structure of the data caches of the processor, and for evaluation of the effects of various loop optimizations on their performance.
• Rewrite IVOPTs (Zdenek Dvorak, long): IVOPTs is a pass that performs the common induction variable optimizations; in some cases, it is quite slow and sensitive to the information provided by machine description, as well as hard to extend. It should be rewritten into several simpler passes, dedicated to the separate induction variable optimizations (possibly sharing some of the analyses and data structures).

• Loop header copying/invariant motion/unswitching improvements (Zdenek Dvorak & Richard Guenther, medium): See http://gcc.gnu.org/PR23855.

• Using VRP in # of iterations analysis (Zdenek Dvorak, short): To eliminate the assumptions in # of iterations analysis, we scan the conditions that precede the loop. This is not entirely reliable, as these conditions may be eliminated by a preceding VRP pass (or other optimization). The value ranges obtained by VRP should be saved and used instead (or in addition) to this. Knowledge of the value ranges may also be useful on other places (overflow analysis, non-loop optimizations).

• Not flattening Fortran arrays (Zdenek Dvorak, long): In gfortran, a(i,j) is currently translated as <code>a[offset + step * j + i]</code>, which makes data dependence analysis impossible. This representation should be changed to <code>a[i][j]</code> (using the possibility to store the step and offset in ARRAY_REF). The changes necessary in the gfortran frontend are however nontrivial.

• Pragmas for loop optimizations (Zdenek Dvorak, medium): Some compilers use pragmas to receive hints regarding (lack of) data dependences, suggested unrolling factor, etc. Implement this for gcc.
• Updating loop-related information (Zdenek Dvorak, medium): The cached results of # of iterations analysis, scev and data dependence analysis are thrown away after almost every change in the code. Make us update this information, or at least remove just the affected parts of it.

• Merge scev testcases (Daniel Berlin & Sebastian Pop, short): There are many testcases for scev in the lno-branch, many of them should still be valid (not all the functionality present in lno-branch was merged to mainline). Find and update these testcases, and add them to the testsuite in mainline.

• Use profiling information for loop optimizations (Richard Guenther, long): See the paper in the GCC Summit proceedings.

• Versioning & unrolling for nested loops (Richard Guenther & Zdenek Dvorak, short): Make loop versioning and loop unrolling of non-innermost loops work.

• Canonicalization (Zdenek Dvorak & Sebastian Pop, medium): Add initial pass(es) that would make structure of loops and their induction variable more friendly for high-level loop optimizers, and evaluate the effects.