csdw@alpha.cs.ru.ac.za (Dave Williams) (03/27/91)
In an attempt to optimize a functional language, I would like to turn the stack based intermediate code into three address code. Has anyone done similar conversions? Any references would be greatly appreciated. Dave Williams (Internet: alpha.cs.ru.ac.za) -------------------------------------------
torbenm@diku.dk (Torben [gidius Mogensen) (04/02/91)
csdw@alpha.cs.ru.ac.za (Dave Williams) writes: >In an attempt to optimize a functional language, I would like to >turn the stack based intermediate code into three address code. >Has anyone done similar conversions? Any references would be >greatly appreciated. >Dave Williams (Internet: alpha.cs.ru.ac.za) >------------------------------------------- I have seen this done several times, but I can't recall any references. The basic idea is to simulate the stack at compile time: Each stack cell contains a description of what/where the contents is at run time. A description can say that the cell is a certain constant value, that the cell can be found in a specified register or memory location or that it is in fact located on a run time stack. As you generate code for a stack instruction, you generate a three address instruction that takes its arguments from where the compile time description says the corresponding stack elements are located, and puts its result in an unused register. You then update the compile time stack description to reflect the new state. As an example, assume that you have the following compile time stack description: top: R1 R0 and the following stack code sequence: loadconst(17); add; loadmemory(x); mul; sub; you would for the loadconst(17) instruction generate no code, but change the stack description: top: const(17) R1 R0 The add instruction would generate the instruction ADD R1,#17,R1 (assuming R1 is now an unused register) and update the stack description to top: R1 R0 The loadmemory(x) would generate no code but update the stack description to: top: memory(x) R1 R0 The mul instruction would generate MUL R1,x,R1 (since R1 is now unused) and update the stack description to top: R1 R0 sub will generate SUB R0,R1,R0 and the final stack description top: R0 So the entire code is: ADD R1,#17,R1 MUL R1,x,R1 SUB R0,R1,R0 This is fine as long as there are sufficient registers, but if you run out, you must spill registers to a run time stack. The best choice is usually registers that hold values far down in the stack. You generate code that pushes the register(s) to the stack, and update the descriptions of the compile time stack and used/unused registers. Another complication is what to do about function calls / jumps. If a piece of code can be called from several places, there is no single compile time stack/register description. The simplest solution is to spill everything to the stack, so that all stack elements are found on the run time stack and all registers are unused. This is somewhat inefficient, but good interprocedural optimization is hard. It is also possible to do the code generation in reverse, keeping a description of where the stack elements are _required_ to be, and generate code that ensures this. This has the advantage that the result need no always be stored in an unused register, but could be put directly into memory. On the other hand, it would require the arguments to be in fixed places, probably registers. A compromise is to use a lookahead to see where the result is needed / what the arguments are. A lookahead of just one or two instructions would find most cases where saving can be made. Hope this helps Torben Mogensen (torbenm@diku.dk)