loop fusion in LLVM

Hi,

I am a student and my team is trying to identify a suitable topic for our compiler class final project. The requirement is to implement some optimization in LLVM that is not already existed, at least not in the list of standard opt that LLVM already has. We are looking at loop fusion as a potential candidate topic. Since we are all new to LLVM we would like to ask for experts’ opinions here if there already is a well known implementation of loop fusion pass existed, and if not, is there a particular reason that it is not done given such optimization is fairly standard?

Thank you.

-Qi

Hi Qi,

No, we don’t have loop fusion. The loop fusion transformation itself is easy, but the profitability and legality checks are challenging. For legality, you would need to analyze the memory that you access and figure out that it is legal to fuse the loops. For profitability you would need to predict the effect on performance. You would need to predict register pressure and resource utilization, which is difficult to do.

Thanks,
Nadav

Thanks a lot for your input. We will look more into the legality and profitability checks you’ve mentioned.

-Qi

Hi Qi,

regarding loop fusion and other high-level loop transformations,
http://polly.llvm.org may also be of help. The default scheduling optimizer we use has some heuristics for loop fusion, but it does not yet take into account register pressure.

Cheers,
Tobias

Identify some motivating cases where the performance benefits will be fairly obvious, and restrict the fusion to handle these. This will save you some work for the project and you can still extend it later. I'm thinking about cases like array contraction, or situations where one loop initializes some array, and then the next loop updates some of the elements again (overwriting previous values).

-Krzysztof