Abstract | ||
---|---|---|
Given the growing interest in the JVM and Microsoft@?s CLI as programming language implementation targets, code generation techniques for efficient stack-code are required. Compiler infrastructures such as LLVM are attractive for their highly optimizing middleend. However, LLVM@?s intermediate representation is register-based, and an LLVM code generator for a stack-based virtual machine needs to bridge the fundamental differences of the register and stack-based computation models. In this paper we investigate how the semantics of a register-based IR can be mapped to stack-code. We introduce a novel program representation called treegraphs. Treegraph nodes encapsulate computations that can be represented by DFS trees. Treegraph edges manifest computations with multiple uses, which is inherently incompatible with the consuming semantics of stack-based operators. Instead of saving a multiply-used value in a temporary, our method keeps all values on the stack, which avoids costly store and load instructions. Code-generation then reduces to scheduling of treegraph nodes in the most cost-effective way. We implemented a treegraph-based instruction scheduler for the LLVM compiler infrastructure. We provide experimental results from our implementation of an LLVM backend for TinyVM, which is an embedded systems virtual machine for C. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1016/j.entcs.2011.11.004 | Electr. Notes Theor. Comput. Sci. |
Keywords | Field | DocType |
compiler infrastructure,stack-based computation model,treegraph-based instruction scheduling,stack-based virtual machines,stack-based virtual machine,stack-based operator,llvm code generator,llvm backend,treegraph node,consuming semantics,code generation technique,llvm compiler infrastructure | Distributed File System,Virtual machine,Instruction scheduling,Scheduling (computing),Computer science,Call stack,Parallel computing,Code generation,Compiler,Programming language implementation | Journal |
Volume | Issue | ISSN |
279 | 1 | 1571-0661 |
Citations | PageRank | References |
1 | 0.36 | 13 |
Authors | ||
6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jiin Park | 1 | 9 | 1.55 |
Jin-Hyung Park | 2 | 65 | 7.38 |
Wonjoon Song | 3 | 1 | 0.36 |
Songwook Yoon | 4 | 1 | 0.36 |
Bernd Burgstaller | 5 | 133 | 17.54 |
Bernhard Scholz | 6 | 104 | 10.59 |