4

I'm writing a compiler that compiles to C. This means that most of the time I piggyback on top of C for optimisations and generating code for multiple platforms.

Right now I can think of a few reasons why it might be beneficial:

  • I can perform specific optimisations for my language
  • It will be easier to translate the simplified SSA into C than it would be to handle all the edge cases in translating my semi-complex language to C
  • It will make certain analysis on the code easier

I can think of a few drawbacks:

  • The compiler is slower as I'll have to generate SSA IR

But is it worth it?

My main question is that will C be able to optimise code translated from an SSA IR well or better?

I imagine that the code the SSA form translates to will have labels and jumps everywhere. It wont use C constructs like for loops or if statements, etc. Will C find this easier or harder to optimise?

I'm keen on doing this purely to learn more about the SSA form, as well as if I eventually generate code for LLVM, it will be a bit easier.

Bonus question: is there a different IR I can look into that may be more suited to the problem at hand?

  • 6
    You need to define your terms. What is SSA? Social Security Administration? What is IR? Infrared? Don't just assume that people know what you're talking about. – Robert Harvey Nov 28 '16 at 20:39
  • 7
    @RobertHarvey Good point. But if they don't know what I'm talking about then I'm not sure if they are the audience I have in mind for my question. – flooblebit Nov 28 '16 at 20:54
  • 2
    Kinda thought you'd say that. Keep in mind that this is a website that is supposed to have broad applicability; questions and answers should be useful to others, not just to the chosen few. Also, note that we don't necessarily have to be PhD's in the subject matter to help you. – Robert Harvey Nov 28 '16 at 20:56
  • 5
    @RobertHarvey You have a valid point here, in general, but in this specific case he's right. Compiler work can be very specialized. Heck, I maintain a production-grade compiler and I do understand the terms being used here, and I'm still not qualified to answer this question, because it doesn't use SSA or a LLVM-style codegen, so it's outside of my realm of experience. – Mason Wheeler Nov 28 '16 at 20:59
  • 1
    In any case, I don't think specialized knowledge is necessarily needed here. Not all of us know what IR means at first blush, but those of us who have done a minimal study of compilers know what an expression tree is, which is a form of IR. The description of SSA at Wikipedia is strongly suggestive of immutable design, which doesn't require a compiler expert to understand either. ("each variable is assigned exactly once, and every variable is defined before it is used. Existing variables in the original IR are split into versions") – Robert Harvey Nov 28 '16 at 21:45
2

It's somewhat difficult to answer this definitively without knowing more about the language you are writing. However, it's probably helpful to think about what kind of code transformations you're expecting to perform between the type checking and the code gen. If you're planning some optimisation passes or some form of sophisticated memory or lock analysis, then it may well be worth it.

By the same token it's hard to say whether an intermediate representation would help or hinder the C optimisations. It's probably fair to say that if you use a low level IR, like LLVM's, you may well lose type information which in turn could limit the analyses the C compiler can work with.

For inspiration I would recommend you look at the recent work on Rust's MIR or Swift's SIL which are both high level IRs that retain type information. Interestingly they both lower to LLVM's IR for optimisation and code gen. The discussions cover the performance cost, and both went through the expense of re-factoring to include the high level IR. They had different reasons for the inclusion but both, effectively, include sophisticated analysis passes that they considered justified the cost. YMMV of course.

| improve this answer | |
1

On the optimisations side of your question, the answer is no. The C compiler's optimisations won't be targetted at C code that looks like SSA. It will be targetted at code that looks like C code.

Furthermore, the SSA form can express things at a level that C cannot; LLVM IR can express more than C. It can have invariants (or variants) that C can't - for instance, different aliasing rules.

At absolute best, the C compiler will optimize equally well as the LLVM compiler.

| improve this answer | |
  • 1
    I think the first part of this answer is a little un-necessary and not particularly constructive. – flooblebit Nov 28 '16 at 21:55
  • @flooblebit: I removed the obnoxious parts. – Robert Harvey Nov 28 '16 at 22:06
  • 1
    None of this is that simple, and certainly in the context of IRs, C is a high-level language. A C compiler given "SSAed" input can still potentially output better code even if it does use LLVM for code generation. If it doesn't use an LLVM back-end, there's even less of a reason to think it would be inferior to directly targeting LLVM performance-wise. Most compilers can handle non-idiomatic code quite well because they tend to produce it themselves during optimizations, and either way this assumes that the "non-SSA" output is idiomatic which is unlikely. – Derek Elkins left SE Nov 29 '16 at 3:26
1

It sounds like SSA is an extra step in your case, and I wonder if you've considered whether the possible optimization is worth worrying about.

Will your language sometimes be used to write functions/procedures that will do heavy computation that doesn't call lower-level functions? If so, then compiler-level optimization is a valid concern.

I only ask because sometimes people are concerned about optimization in code where the instruction pointer seldom is, because it's in lower-level functions, or because it isn't called that often.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.