<div>Hi Oscar, </div><div><br></div><div>Thank you for your reply. Unfortunately my stack instruction set contains instructions, that it's impossible to predict how much stack space would they require (Unwind/Eval instructions from G-Machine code). Therefore I doubt that I would be able to implement it using compile-time stack only (and I believe that this is what you're suggesting). I think I have to implement some sort of run-time stack and my question was what is the best way to do this. Now I know that subsequent alloca's doesn't allocate contiguous area of memory on the stack, so I believe that the only way to go would be to allocate stack items consisting of 2 elements:</div>

<div> - the pointer to the previous stack cell</div><div> - actual value of the cell</div><div><br></div><div>Do you see any better way of doing that?</div><div><br></div><div>Kind regards</div><br><div class="gmail_quote">

On Mon, Jul 25, 2011 at 6:58 PM, Óscar Fuentes <span dir="ltr"><<a href="mailto:ofv@wanadoo.es">ofv@wanadoo.es</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

The following message is a courtesy copy of an article<br>
that has been posted to gmane.comp.compilers.llvm.devel as well.<br>
<div><div></div><div class="h5"><br>
Piotr Kaleta <<a href="mailto:piotrek.kaleta@gmail.com">piotrek.kaleta@gmail.com</a>> writes:<br>
<br>
> I'm translating the source of stack-based virtual machine into LLVM IR and<br>
> my plan is to implement  the stack in LLVM IR (using alloca/load/store) in<br>
> order to emulate the VM's stack and then use the optimization phase<br>
> "mem2reg". Therefore I'm going to have a stack pointer that points to the<br>
> top of my stack. I'm curious whether I will have to implement that in a<br>
> linked-list fashion, i.e. each stack node would contain the pointer to the<br>
> previous node as well as the current value of the top of the stack or maybe<br>
> alloca instruction works in a way that the subsequent calls to it allocates<br>
> the contiguous memory area and I could get rid of the "pointer to previous<br>
> thing" and only count the number of calls to alloca instruction.<br>
><br>
> Another thing is that there might be a better (less expensive or easier) way<br>
> of doing the whole stack -> SSA transformation which I didn't came up with,<br>
> but someone else did?<br>
<br>
</div></div>My compiler also emits instructions for a virtual stack-based<br>
machine. The LLVM backend is implemented as a translator from those<br>
instructions to LLVM IR.<br>
<br>
In principle, creating an alloca for every value that is pushed into the<br>
stack would work: when the VM should push a value to the stack, you<br>
create the alloca and store the value into it; then you load the alloca<br>
when the virtual machine should pop the value from the stack. You don't<br>
need linked lists, just a stack (!) data structure that emulates the<br>
state of the VM, where you push and pop alloca's as the VM does with the<br>
real values. In essence, your translator would work like an interpreter<br>
over the VM instructions that, instead of working with real data, works<br>
with the alloca's where the real values will be stored when the LLVM<br>
code is executed. Apart from that, you don't need to care about the<br>
alloca's anymore.<br>
<br>
The above method should work but has the inconvenience of generating<br>
lots of alloca/store/load instructions. That's is fine if you don't care<br>
too much about compilation time or readability of the unoptimized LLVM<br>
IR code. My translator uses general LLVM values instead of just allocas,<br>
so code like this:<br>
<br>
a := (b + c) * d<br>
<br>
that would translate to this with the alloca method:<br>
<br>
(b, c and d are values already on the stack)<br>
<br>
# pop the alloca for b<br>
# pop the alloca for c<br>
# generate LLVM load (for b)<br>
# generate LLVM load (for c)<br>
# generate LLVM instruction for b + c<br>
# create LLVM alloca for result (let's call it T)<br>
# push the alloca<br>
# generate the LLVM store for T into the alloca<br>
# pop the alloca for T<br>
# pop the alloca for d<br>
# generate LLVM load (for T)<br>
# generate LLVM load (for d)<br>
# generate LLVM instruction for T * d<br>
# create LLVM alloca for result (let's call it U)<br>
# push the alloca<br>
# generate the LLVM store for U into the alloca<br>
# pop<br>
# generate LLVM load for U<br>
# generate LLVM store for U into memory reserved for variable `a'<br>
<br>
And with the general LLVM instruction method:<br>
<br>
# pop (for b)<br>
# pop (for c)<br>
# generate LLVM instruction for (b + c)<br>
# push the resulting LLVM instruction<br>
# pop (for the previous result)<br>
# pop (for d)<br>
# generate LLVM instruction for T * d<br>
# generate LLVM instruction for storing the previous result into the<br>
  memory reserver for variable `a'<br>
<br>
If any `b', `c', `d' are variables, you need to detect that and generate<br>
the corresponding `load'. Note that `push' and `pop' are operations on<br>
the stack of your translator, not LLVM instructions.<br>
<br>
The key here is to realize that any LLVM instruction that yields a value<br>
(imul, add, etc) *is* a LLVM Value object, the same as the result of a<br>
`load' instruction.<br>
<br>
HTH.<br>
</blockquote></div><br><br clear="all"><br>-- <br>Piotr Kaleta<br>