Virtual Machines (eBook)

Copyright Page 
4 
Preface 6
Acknowledgements 8
Table of Contents 
9 
1 Introduction 
14 
1.1 Introduction 14
1.2 Interpreters 16
1.3 Landin's SEeD Machine 16
1.4 The Organisation of this Book 18
1.5 Omissions 20
2 VMs for Portability: BCPL 
24 
2.1 Introduction 24
2.2 BCPL the Language 25
2.3 VM Operations 28
2.4 The OeODE Machine 30
2.5 OCODE Instructions and their Implementation 
31 
2.5.1 Expression Instructions 31
2.5.2 Load and Store Instructions 33
2.5.3 Instructions Relating to Routines 33
2.5 .4 Control Instructions 35
2.5.5 Directives 36
2.6 The Intcode/Cintcode Machine 
37 
3 The Java Virtual Machine 
40 
3.1 Introduction 40
3.2 JVM Organisation: An Overview 41
3.2.1 The stack 42
3.2.2 Method areas 43
3.2.3 The PC register 
44 
3.2.4 Other structures 45
3.3 Class Files 45
3.4 Object Representation at Runtime 53
3.5 Initialisation 55
3.6 Object Deletion 57
3.7 JVM Termination 58
3.8 Exception Handling 58
3.9 Instructions 59
3.9.1 Data-manipulation instructions 61
3.9.2 Control instructions 64
3.9.3 Stack-manipulating instructions 67
3.9.4 Support for object orientation 
69 
3.9.5 Synchronisation 72
3.10 Concluding Remarks 72
4 DIY VMs 
73 
4.1 Introduction 73
4.2 ALEX 74
4.2.1 Language Overview 74
4.2.2 What the Virtual Machine Must Support 77
4.2.3 Virtual Machine-Storage Structures 78
4.2.4 Virtual Machine-Registers 80
4.2 .5 Virtual Machine-Instruction Set 82
4.2.6 An Example 91
4.2.7 Implementation 93
4.2.8 Extensions 97
4.2.9 Alternatives 100
4.2.10 Specification 105
4.3 Issues 108
4.3.1 Indirect and Relative Jumps 109
4.3.2 More Data Types 110
4.3.3 Higher-Order Routines 118
4.3.4 Primitive Routines 118
4.4 Concluding Remarks 119
5 More Stack-Based VMs 
121 
5.1 Introduction 121
5.2 A Simple Object-Oriented Language 122
5.2.1 Language Overview 122
5.2 .2 Virtual Machine-Storage Structures 123
5.2.3 Virtual Machine-Registers 125
5.2.4 Virtual Machine-Instruction Set 125
5.2.5 Extensions 128
5.2.6 Alternatives 128
5.3 A Parallel Language 129
5.3.1 Language Overview 129
5.3.2 Virtual Machine-Storage Structures 131
5.3.3 Virtual Machine-Registers 133
5.3.4 Virtual Machine-Instruction Set 134
5.3.5 Implementation 136
5.3.6 Extensions 138
5.3.7 Alternatives 140
5.3.8 Issues 141
5.4 Concluding Remarks 141
5.4.1 Some Optimisations 141
5.4.2 Combining the Languages 142
6 Case Study: An Event-Driven Language 
143 
6.1 Introduction 143
6.2 The Structure of Rules 145
6.3 Events 148
6.4 Execution Cycle 148
6.5 Interpretation Rules 150
6.6 VM Specification 153
6.6.1 States and Notational Conventions 154
6.6.2 Infra-Rule Transitions 157
6.6.3 Extra-Rule Transitions 160
6.6.4 VM-Only Transitions 162
6.6.5 Introspective Operations 163
6.7 Rule Equivalences 165
6.8 Concluding Remarks 166
7 Register-Based Machines 
168 
7.1 Introduction 168
7.2 The Register-Transfer Model 169
7.3 Register Machine Organisation 172
7.4 Parrot-General Organisation 176
7.5 Parrot Instruction Set 179
7.5.1 Control instructions 180
7.5.2 Data management instructions 180
7.5.3 Register and stack operations 181
7.6 DIY Register-Based Virtual Machine 182
7.6.1 Informal Design 183
7.6.2 Extensions 187
7.6.3 Transition Rules 188
7.7 Translating ALEXVM into RTM 194
7.8 Example Code 197
7.9 Correctness of the Translation 197
7.10 More Natural Compilation 207
7.11 Extensions 211
8 Implementation Techniques 
212 
8.1 Stack-Based Machines 213
8.1.1 Direct Implementation 213
8.1.2 Translation 214
8.1.3 Threaded Code 218
8.2 Register Machines 220
8.2.1 Register sets 221
8.2.2 Addressing 221
8.2.3 Translation to Another VM 223
8.3 Using Transitions 223
8.4 Concluding Remarks 224
9 Open Issues 
226 
9.1 Security 226
9.2 New Languages 227
9.3 Typed Instruction Sets and Intermediate Codes 227
9.4 High-Level Instructions 229
9.5 Additivity and Replacement 229
9.6 Compiler Correctness 229
9.7 Dynamic Code Insertion 230
9.8 Instrumentation 231
9.9 Including more Information about Source Code 232
9.10 Integration with Databases 233
9.11 Increased Inter-Operability 233
9.12 Code Mobility 234
9.13 Small Platforms 235
9.14 Real-Time VMs 237
9.15 Code Morphing 238
9.16 Greater Optimisation 238
9.17 Operating System Constructs 239
9.18 Virtual Machines for more General Portability 240
9.19 Distributed VMs 240
9.20 Objects and VMs 240
9.21 Virtual VMs 241
9.22 By Way of a Conclusion 242
A Compiling ALEX 
243 
A.1 Introduction 
243 
A.2 Notational Conventions 243
A.3 Compilation Rules 245
B Harrison Machine Compilation Rules 
251 
B.1 Introduction 251
B.2 Compilation Rules 251
C Harrison Machine Instruction Set 
266 
References 269
Index 272

"7 Register-Based Machines (S. 157-158)

7.1 Introduction

The virt ual machines described so far have all had th e same property: they use at least one stack and a collection of special-purpose regist ers. This has been taken as the way to const ruct virtu al machines. It is certainly a relatively quick and easy way to do it and it is a target machine for which it is particularly easy to generate code. There are, however, alternatives, the primary being that based on the Register- Transfer Model (RTM) . This is the model upon which most hardware processors are based.

There have been many machine simulato rs over the years and there are programming environments , particularly for real-time and embedded systems, that allow programs for one processor to be executed using a simulated processor. However, t he use of the RTM for virt ual machines is relat ively new; the largest implementation to date (2004) is the Parrot virt ual machine for Perl6. This chapte r is concerned with this alternative organisation for virt ual machines.

Section 7.2 is concerned with the arguments surrounding registerbased machines, both pro and con. Section 7.3 contains a description of one way to organise a regist er-based virt ual machine. Since the only really public register-based virtual machine of any st rength is t hat for Parrot , Section 7.4 is a description of Parrot s general organisation , while Section 7.5 contains a description of Parrots instruction set (the description is only partial because th e published documentation is, as yet , incomplete- th e best way to understand t he Parrot VM is to read its code). In Section 7.6, a DIY register machine is presented.

In Section 7.7, it is shown how the two-stack code for the simple ALEX programming language can be converte d (macro processed, in essence) into code for the DIY register-t ran sfer machine. The following section contains examples of such translat ions using a simple function. The correct ness of the translat ion from two-stack to register-machine code is the subject of Section 7.9 In Section 7.10 a more natural compilation of ALEX to register-machine code is presented. In the last section, Section 7.11 some extensions to the register machine are considered. 7.2 The Register-Transfer Model Almost all work on abstract machines has concentrated on stack-based architectures.

The SECD machine is the classic of this form, of course. The Pascal-S , Pascal P4, UCSD Pascal, Smalltalk and Java abstract machines are also stack-based. One good reason for constructing stack-based machines is that expressions can be directly evaluated on the stack . Stacks are also used to represent scope, thus making procedures and block structures easy to implement. Stacks are required to implement recursion , a feature of ISWIM, Algol60 and most modern programming languages . Stack-based architectures are good for compiler writers, therefore."