The low level GIMPLE does no longer contain loop syntactic structures. Once the control flow graph is constructed, the loop expressions are lowered into labels and gotos. Consequently, the natural loops are detected on the CFG.


For sending information from the middle-end level to the back-end, structures that contain the information have to be persistent. It is already the case for the control flow graph that sends the edge frequencies to the back-end. Another example is the data dependence analysis, that can be difficultly performed at the RTL level. The data dependence graph is currently built and used only at the tree level, but important optimizers in the back-end, such as the modulo scheduler, are restricted because of the lack of accurate information that can be gathered only at the tree level.

Maybe one of the difficulties that we have to face comes from the fact that the loops structure was considered as, and still is at the moment, a secondary representation. The construction of the loops structure is considered cheap enough for being rebuilt instead of being updated at the end of an aggressive loop optimization. Despite the fact that it is cheap to recompute the loops, the amount of information that we are attaching to this structure is important and much more costly to recompute. This brings the main argument for the persistence of the loops structure. Basically the loops structure will become a primary intermediate representation at the moment when the informations that it carries to the back-end will become of critical importance to the performance of some optimizers.

The primary informations that we would like to send to the back-end are:

  1. the [data dependence graph||Data Dependence Analysis]

  2. is this a parallel_loop?

  3. the number_of_iterations

In the future, other informations could be analyzed once at the tree level, then attached to the loops structure for later uses. Another example of information that could be transferred to the back-end is the parallel loop constructs coming from a front-end.

Implementation details:

The primary task is to ensure that all the transformation passes respect the loops structure: that is, destructive optimizations have to update the loops structure and keep it alive, if an optimization modifies the loops structure, in the same time, it has to modify the attached information. Another important point in the implementation is to minimize the overhead due to the synchronization of the loop transforms and the attached data.

None: loops_structure (last edited 2008-01-10 19:39:00 by localhost)