There are a number of questions on how to convert SSA representation to stack machines, but I'm interested in the inverse.
Question
Consider a stack-based VM with conditional/unconditional jumps, where each opcode has a fixed number of stack elements it consumes and produces.
Are there tools/approaches in the LLVM framework to reconstruct an SSA form from the bytecode output. This would be essentially a form of disassembly.
There are no tools in LLVM itself, but it's just s SMoP. I've done it. Parts of it were difficult but so's anything. I'll answer instead of comment to ramble a bit about the most difficult part.
Stacks are typically typeless; the value that is on the top of the stack has a type, but "top of stack" does not. An LLVM Value always has a type, and those two systems collide when the code contains loops. Consider this code:
int a = b();
while(a<10)
a++;
a has a type and all values of it will be int (perhaps i32 in LLVM IR). When the first line pushes the return value from b() onto the stack, the top of stack acquires type int. You can probably envision how those lines look on your stack machine. It ought to be translated to IR rather like this:
entry:
%a1 = call @b();
br label %b1
b1:
%stack.0.b1 = phi i32 [%entry, %a1], [%b1, %a2]
%a2 = add i32 1, %stack.0.b1
%done = icmp ult i32 %stack.0.b1, 10
br i1 %done, label %b1, label %b2
b2:
(Sorry about the syntax errors, I haven't written much IR by hand.)
You probably see that each instruction except the phi can be generated from a single instruction in your stack language. Perhaps an instruction in your stack language leads to more than one IR instruction, or leads to no IR instructions, e.g. dup or push-constant-zero, which merely modify the stack.
The phi is different, it represents the stack at that point.
The stack on entry to block b1 is computed from the stack at the end of each of entry and b1. You can generate a phi node for each value on the stack at the start of each basic block; the challenge is that the type of each phi node depends on the types on the stack at the end of the preceding blocks. In this case the stack at the end of entry has one entry, a1 and at the ened of b1 is has one, a2. Therefore the type of stack.0.b1 depends on that of a2, which in turn depends on stack.0.b1. You'll need to think hard about that, particularly if your language includes implicit type promotion or casting (i32 to i64, string to object, etc).
(I could have started with a ruby-like type system and code instead of c-like; I think the final problem would be the same, only your solution is different.)