Tool for loop transformations

Hi everyone!

I would like to create a tool which would "simulate" several loop transformations. It should serve as a part of my bachelor thesis.

Typical usage of that tool would be this:
Mark a loop in a source (probably C/C++) file and specify desired transformation in a predefined way (for example a special comment or something). -> Run the tool on that "crafted" source file. -> Watch the result (which should be in an input language or possibly in LLVM IR).

I know that LLVM can do some of the loop transformations but as far as I know it decides itself what transformation (if any) will be done. Or am I mistaken? Is it possible to specify which loop is supposed to be transformed and how? Is it easily possible to get the (above mentioned) mark through the compiler frontend so it would appear in the LLVM IR as well? Then maybe I could write my own pass and use the `opt` command to run it on the .ll file and watch it before and after the pass. Am I mistaken? Is there a better way?

Do you understand what I want to achieve? Is LLVM suitable for my needs? What should I read? Where should I start? What would you advise me?

Thanks for all your answers and ideas.

Have you thought of implementing OpenMP? That would be a great addition to LLVM.

Hello Tomas,

I’m a little bit new here too, but I guess I could try to help you. First, let me see if I get your project straight: you are writing a tool that should (let’s say) help students to identify what does a loop seems like after a chosen transformation. Is that the case? If so, your first objective would be isolating a loop transformation and avoid other transformations to mess up with the transformed loop, right?

Well, as far as I know, every analysis and transformation in LLVM is a Pass. If you want to see which passes and the order that they were called, you could pass --debug-pass=Structure when using opt, and the PassManager will print the call list for you.

If you want only one transformation to be called, you could disable in opt all analysis and transformations (I guess -o0 is the default), and enable only the ones that you are interested in (something like -transform1 -transform2 etc.). Keep in mind that the transformations could need different types of analysis (that will be also printed by the PassManager), and, sometimes, should be interesting for a transformation the combination of it with another transformations that only will clean up the code (such as dead code elimination, for example). For a list of all passes available in LLVM, please check http://llvm.org/docs/Passes.html.

I advise you to have a read in http://llvm.org/docs/WritingAnLLVMPass.html too, to get a better idea of how the passes work.

Hope I could help,

Renato, sorry for repost, I forgot to Cc the mailing list...

Hello Tomas,

Hi!

I’m a little bit new here too, but I guess I could try to help you. First, let me see if I get your project straight: you are writing a tool that should (let’s say) help students to identify what does a loop seems like after a chosen transformation. Is that the case? If so, your first objective would be isolating a loop transformation and avoid other transformations to mess up with the transformed loop, right?

Yes, I think you got me right.

Well, as far as I know, every analysis and transformation in LLVM is a Pass. If you want to see which passes and the order that they were called, you could pass --debug-pass=Structure when using opt, and the PassManager will print the call list for you.

I have already found out that opt can help me but thanks anyway. I think this could be my approach:

  • Think up how to mark the loop which is wanted to be transformed and how to get that mark through the compiler frontend from the source to the IR. I guess I could use #pragma or implement new attribute for that.
  • Then I have to store that mark in the IR form. I could probably use IR metadata for that but I have to look at them more to find out if this could suit my needs.
  • And finally I have to implement new pass which will search the given IR for specified mark and transform the marked loop accordingly.

If any of you think my vision is wrong or you have better ideas feel free to express your opinions.

If you want only one transformation to be called, you could disable in opt all analysis and transformations (I guess -o0 is the default), and enable only the ones that you are interested in (something like -transform1 -transform2 etc.). Keep in mind that the transformations could need different types of analysis (that will be also printed by the PassManager), and, sometimes, should be interesting for a transformation the combination of it with another transformations that only will clean up the code (such as dead code elimination, for example). For a list of all passes available in LLVM, please check http://llvm.org/docs/Passes.html.

I advise you to have a read in http://llvm.org/docs/WritingAnLLVMPass.html too, to get a better idea of how the passes work.

Hope I could help,

Thanks for your feedback! I will definitely look at those links.