Treegraph-based Instruction Scheduling for Stack-based Virtual Machines

Jiin Park, Jinhyung Park, Wonjoon Song, Songwook Yoon, Bernd Burgstaller, Bernhard Scholz

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Pages (from-to)33-45
Number of pages13
JournalElectronic Notes in Theoretical Computer Science
Issue number1
Publication statusPublished - 2011 Dec 2

Bibliographical note

Funding Information:
1 Authors contributed equally. 2 Research partially supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MEST) (No. 2010-0005234), and the OKAWA Foundation Research Grant (2009). 3 Research partially supported by the Australian Research Council through ARC DP grant DP1096445.

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Treegraph-based Instruction Scheduling for Stack-based Virtual Machines'. Together they form a unique fingerprint.

Cite this