I have used flex and bison in order to make a lexical analyzer and a parser for an EBNF grammar. This work is done! I mean, when i put a file with a program I write, I can see if the program has mistakes. If it doesn't, I can see the whole program in my screen based on the grammar i have used. I have no problem in this.
Now, I want to use loop handling and loop unrolling. Which part should I change? The lexical analyzer? The parser? Or the main after the parser? And how?
Introduction
As we don't have sight of a piece of your code to see how you are handling a loop in the parser and outputting code, and an example of a specific loop that you might want unrolled it is difficult to give any more detailed advice than that already given. There are unlikely to be any more experienced compiler writers or teachers anywhere on the globe than those already reading your question! So we will need to explore other ways to explain how to solve a problem like this.
It often happens that people can't post examples of their code because they started with a significant code base provided as part of a class exercise or from an open source repository, and they do not fully understand how it works to be able to find appropriate code fragments to post. Let's imagine that you had the complete source of a working compiler for a real language and wanted to add some loop optimisations to that existing, working compiler, you might then say, as you did, "what source, how can I show some source?" (because in actuality it is many tens of thousands of lines of code).
An Example Compiler
In the absence of some code to reference the alternative is to create one, as an exemplar, to explain the problem and solution. This is often how it is done in compiler text books or compiler classes. I will use a similar simple example to demonstrate how such optimisations can be achieved using the tools flex and bison.
First, we need to define the language of the example. To keep within the reasonable size constraints of a SO answer the language must be very simple. I will use simple assignments of expressions as the only statement form in my language. The variables in this language will be single letters and the constants will be positive integers. The only expression operator is plus (
+
). An example program in my language might be:The output code generated by the compiler will be simple assembler for a single accumulator machine with four instructions,
LDA
,STO
,ADD
andSTP
. The code generated for the above statements would be:Where
LDA
loads a value or variable into the accumulator,ADD
adds a variable or value to the accumulator,STO
stores the accumulator back to a variable.STP
is "stop" for the end-of-program.The flex program
The language shown above will need the tokens for ID and NUMBER and should also skip whitespace. The following will suffice:
The bison program
To parse the language and generate some code from the bison actions we can achieve this by the following bison program:
Optimisation
Now we have a working compiler for a language in a few lines of code we can start to demonstrate how the process of adding code optimisation might work. As has already been said by the esteemed @Chris Dodd:
This compiler works by emitting code incrementally after parsing part of the input. As each statement is recognised the bison action (within the
{...}
clause) is invoked to generate code. If this is to be transformed into more optimal code it is this code that has to be changed to generate the desired optimisation. To be able to achieve effective optimisation we need a clear understanding of what language features are to be optimised and what the optimal transformation should be.Constant Folding
A common optimisation (or code transformation) that can be done in a compiler is constant folding. In constant folding the compiler replaces expressions made entirely of numbers by the result. For example consider the following:
An optimisation would be to treat this as:
Thus the addition of
1 + 2
was made by the compiler and not put into the generated code to occur at run time. We would expect the following output to result:Improved Code Generator
We can implement the improved code by looking for the explicit case where we have a
NUMBER
on both sides ofexpression '+' operand
. To do this we have to delay taking any action onexpression : operand
to permit the value to be propagated onwards. As the value for anexpression
might not have been evaluated we have to potentially do that on assignment and addition, which makes for a slight explosion ofif
statements. We only need to change the actions for the rulesstatement
andexpression
however, which are as shown below:If you build the resultant compiler, you will see that it does indeed generate better code and perform the constant folding transformation.
Loop Unrolling
The transformation that you specifically asked about in your question was that of loop unrolling. In loop unrolling the compiler will look for some specific integer expression values in the loop start and end conditions to determine if the unrolled code transformation should be performed. The compiler can will then generate two possible code alternative sequences for loops, the unrolled and standard looping code. We can demonstrate this concept in this example mini-compiler by using integer increments.
If we imagine that the machine code has an
INC
instruction which increments the accumulator by one and is faster that performing anADD #1
instruction, we can further improve the compiler by looking for that specific case. This involves evaluating integer constant expressions and comparing to a specific value to decide if an alternative code sequence should be used - just as in loop unrolling. For example:should result in:
Final Code Generator
To change the code generated for
n + 1
we only need to recode part of theexpression
semantics and just test that when not folding constants wether the constant to be used would be1
(which is negated in this example). The resultant code becomes:Summary
In this mini-tutorial we have defined a whole language, a complete machine code, written a lexer, a compiler, a code generator and an optimiser. It has briefly demonstrated the process of code generation and indicated (albeit generally) how code transformation and optimisation could be performed. It should enable similar improvements to be made in other (as yet unseen) compilers, and has addressed the issue of identifying loop unrolling conditions and generating specific improvements for that case.
It should also have made it clear, how difficult it is to answer questions without specific examples of some program code to refer to.