I have built my own parser that, for now at least, will only deal with statements similar to,
return a * b * c * (d + e) / f
What I will see while walking along the Abstract Syntax Tree (AST) that it generates looks like this
(in the exact order that I see it, and in a hopefully descriptive pseudo-language):
RETURN_STMT
BO(left: a, right: BO, op: *)
BO(left: BO, right: f, op: /)
BO(left: BO, right: PE, op: *)
BO(left: b, right: c, op: *)
PE(BO)
BO(left: d, right: e, op: +)
where BO is an abbreviation for Binary Operator, and PE stands for Parenthesis Expression.
I have now moved to building my compiler that will be able to take the AST above, and run it in my custom hardware that I have also generated.
A little info on the hardware: A VHDL like language that contains a set of basic components like multiplyers, dividers, adders, etc. It could look like this (again in hopefully descriptive pseudo-code):
reg a, b, c, d, e, f
int i <- 0
b <- buffer[4] // a simple FIFO queue
... // some initialization
m1 <- MUL(a, b, if: i == 0) // 2 cycles
m2 <- ADD(d, e, if: i == 0){i++} // 1 cycle
m3 <- MUL(c, m2, if: i == 1){i++} // 2 cycles
m4 <- MUL(m1, m3, if: i == 2){i++, b.put(m4)} // 2 cycles
m4 <- DIV(b.get(), f, if: i == 3){i++} // 6 cycles
The if specifier will decide when (in each cycle) the operation will fire. In this way I can have my hardware execute operations in parallel.
If we imagine an infinite amount of streaming a, b, c, d, e, f values, then we need to contend with the delays, in cycles, for each operator. If in the case that a MUL operations requires 2 cycles, and a DIV requires 6, then I will have performed 3 multiplications before I get the chance to finish one division. Hence I can store the intermediate values in a buffer that will ensure (in the streaming scenario discussed here) that nothing will get lost.
In practice this is what my compiler will have to generate if I want to tie my custom c-like language with my custom (emulated for now) hardware.
A number of issues arrise:
I can reuse hardware components, but what is the minimum amount of components (MUL, DIV, etc) that I need?
What would the minimum size of the required buffers be?
Given the output of my (recursive) walk algorithm originally shown above, how can I create an optimized series of basic operations, while at the same time respecting the hardware delay requirements?