-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmachine-details.txt
386 lines (320 loc) · 14.8 KB
/
machine-details.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
The Abstract Machine.
This document describes the abstract computer that the
Winzig compiler generates code for. The abstract machine is
designed for convenient code generation from Pascal-like
languages. It is modeled after (actually a subset of) the
abstract Dream machine, designed by Frank DeRemer. It is a
stack machine with no addressable registers. There are no
instructions such as "load register n with ...".
The machine also lacks many of the common complications
that actual processors usually have: branch instructions are
not limited to a certain range, but can instead reach any-
where in the code. All instructions are in the same format,
not two or three different formats, as in some (IBM)
machines.
The machine has three separate and distinct memo-
ries. When a program is loaded into memory for execution,
various base and limit registers are set to perform range
checking and to facilitate addressing and stack computations
at run time. The general layout of the machine is depicted
in figure 1.
REGISTER ABREV. CODE MEMORY
+-------------------+
| //////////// |
Code Base CBR ----------> +-------------------+
| |
| CODE |
| |
Code Limit CLR ----------> +-------------------+
| //////////// |
+-------------------+
DATA MEMORY
+-------------------+
| //////////// |
Global Base GBR ----------> +-------------------+
| |
| Globals |
| |
Global Limit GLR ----------> +-------------------+
| |
| Prior |
| Stack |
| Frames: |
| |
| Locals + Temps |
| |
+-------------------+
Local Base LBR ----------> +-------------------+
| |
| Top Frame: |
| |
| Locals + Temps |
| |
Stack Top STR ----------> +-------------------+
| |
| Available but |
| currently unused |
| |
Stack Limit SLR ----------> +-------------------+
RETURN MEMORY
+-------------------+
| //////////// |
Return Base RBR ----------> +-------------------+
| |
| RETURN |
| ADDRESSES |
| |
Return Top RTR ----------> +-------------------+
| //////////// |
Return Limit RLR ----------> +-------------------+
Figure 1. Registers and memory layout.
The program cannot branch out of its code area because
every instruction address is ascertained to be inclusively
between the contents of the code base register (CBR), and
the contents of the code limit register (CLR). The code
memory is considered to be read-only. Neither code nor
return addresses can be modified or copied because all
fetches and stores are restricted to be inclusively between
the global base register (GBR) and the stack top register
(STR). In other words, dangerous mucking around with self
modifying code is impossible. An overal limit on the amount
of memory available is set by the Stack Limit Register
(SLR). This is provided because a physical realization of
the machine can only have a finite amount of memory (DeRemer
still plans to have this machine put on a chip sometime).
For now, the interpreter provided to play the role of the
machine will have virtual memory, i.e. its SLR will have the
value "infinity".
All addressing of local and global variables in
instructions is indicated relative to either the GBR or the
LBR. Thus "LLV i" (Load Local Value i) means "push on the
stack the value in the i'th word of the local frame". Here
"i" can be viewed as an offset from the LBR. The push car-
ried out by this operation will, of course, adjust the stack
top register (STR) accordingly. Another example is "SGV i"
(Store Global Value i), which means "pop the top value of
the stack and store it in the i'th global word". Again, the
STR is adjusted, and "i" is the offset from the GBR. Yet
another example is "LIT i" (Literal i), which means "push i
on the stack".
For the sake of simplicity, execution of the program
(once loaded) is assumed to begin at the instruction desig-
nated by the CBR. Hence we assume that the loader loads the
program at that location. Instructions have an optional
label, the instruction mnemonic, and up to two operands.
For example, consider the following program:
program copy:
{ Echo-prints the first ten numbers on the input }
var count: integer;
begin
count := 1
while (count <= 10) do
begin
output (read)
count := count + 1
end
end copy.
The machine code is shown below. The comments are not pro-
duced by the code generator, obviously.
LIT 0 # Storage for "count".
LIT 1 # Assign 1
SGV 0 # to count.
L2 LGV 0 # Load "count"
LIT 10 # Load 10.
BOP BLE # Pop them, compare them. Push T/F result.
COND L3 L4 # Pop stack. If true, go to L3, else L4.
L3 SOS INPUT # OS Service Call. Read, push on stack.
SOS OUTPUT # OS Service Call. Pop stack, print.
SOS OUTPUTL # Print a "line feed".
LGV 0 # Load "count".
LIT 1 # Load 1.
BOP BPLUS # Add them. Push result on stack.
SGV 0 # Pop stack, store value in "count".
GOTO L2 # Go back to L2.
L4 HALT # Come here when done. Stop.
To understand the execution in utter detail, which
you must do soon to succeed in COP-5641/4640, you should
read the following program, which defines the interpreter of
these instructions, and then draw some pictures of the
machine as the execution proceeds, hand simulating each
step. Then you should write another source program or two,
hand translate them into machine code, and hand simulate
their execution.
algorithm Machine_Interpreter
var I: Initial_Abstract_Instruction
loop Process_the_Instruction
I <- I + 1
pool
where Process_the_Instruction means # Lf: Local Frame
case (Decode(I)) of # Gf: Global Frame
NOP : # Do nothing.
HALT : halt # Stop.
LIT v : Push v on Lf # Literal v.
LLV i : Push (Lf i) on Lf # Load Local Value i.
LGV i : Push (Gf i) on Lf # Load Global Value i.
SLV i : Lf i <- Pop Lf # Store Local Value i.
SGV i : Gf i <- Pop Lf # Store Global Value i.
LLA i : Push (Local_Address i) on Lf # Load Local Address i.
LGA i : Push (Global_Address i) on Lf # Load Global Address i.
UOP i : const X = Pop Lf # Unary Operation i.
Push (Unop(i,X)) on Lf
BOP i : const Xr,Xl = Pop Lf, Pop Lf # Binary Operation i.
Push (Binop(i,Xl,Xr)) on Lf
POP n : Pop n off Lf # Pop n values.
DUP : Push (Top Lf ) on Lf # DUPlicate top of stack.
SWAP : const One,Two = Pop Lf, Pop Lf # SWAP top two values.
Push One on Lf
Push Two on Lf
CALL n : Push I on Return_Stack # Save current instruction.
I <- Pop Lf # Entry point.
Open_Frame n # Bump LBR (see below).
repeat # back to top of loop.
RTN n : const Start = Depth Lf - n # Return top n values
if Start > 0 then # to caller
for j=0 to n-1 do # Move values to bottom of
LF j <- Lf (Start+j) # frame.
Pop Start off Lf # Get rid of the rest.
fi
I <- Pop Return_Stack # Branch to return address.
Close_Frame i # Un-bump (De-bump?) LBR
where I is CALL i # (see below).
GOTO L : I <- L # branch to L
repeat # Back to top of loop.
COND L M: I <- if Pop Lf = True # Pop Stack. If value is:
then L # true, go to L
else M # false, go to M.
fi
repeat # Back to top of loop.
CODE F : Push F on Lf # Push entry point.
SOS i : Operating_System i # May change Lf.
endcase
where
Unop(i,X) means
case i of
UNOT : not(X)
UNEG : -(X)
USUCC : X+1
UPRED : X-1
endcase
and Binop(i,Xl,Xr) means
case i of
BAND : Xl and Xr
BOR : Xl or Xr
BPLUS : Xl + Xr
BMINUS : Xl - Xr
BMULT : Xl * Xr
BDIV : Xl div Xr
BMOD : Xl mod Xr
BEQ : Xl = Xr
BNE : Xl <> Xr
BLE : Xl <= Xr
BGE : Xl >= Xr
BLT : Xl < Xr
BGT : Xl > Xr
endcase
and Operating_System i means
case i of
TRACEX : Trace_Execution <- not TraceExecution
DUMPMEM: Dump_Memory
INPUT : readln(i)
Push i on Lf
INPUTC : readln(ch)
Push Ord(ch) on Lf
OUTPUT : write (Pop Lf)
OUTPUTC: write (Chr(Pop(Lf)))
OUTPUTL: writeln
EOF : if eof(input)
then Push True on Lf
else Push False on Lf
endcase
and Push v on Lf means Inc_STR 1
Data_Memory(STR) <- v
and Top Lf means Data_Memory(STR)
and Pop Lf means Data_Memoty(STR)
Dec_STR 1
and Pop n off Lf means Dec_STR n
and Depth Lf means STR - LBR + 1
and Open_Frame i means LBR <- LBR + i
and Close_Frame i means LBR <- LBR - i
and Lf i means Data_Memory (GBR + Local_Address i)
and Gf i means Data_Memory (GBR + Global_Address i)
and Inc_STR i means STR <- STR + i
and Dec_STR i means STR <- STR - i
and Local_Address i means LBR + i - GBR
and Global_Address i means i
and Push I on
Return_Stack means RTR <- RTR + 1
Return_Stack (RTR) <- I
and Pop
Return_Stack means Return_Stack (RTR)
RTR <- RTR - 1
end Machine_Interpreter
To aid in understanding the machine, here is a sample
program.
program fact:
var m:integer;
function fact (n:integer):integer
begin
if n>0 then
fact := n * fact (n-1)
else fact := 1;
m := m + 1
end;
begin
m := 0;
output ( fact(read) , m)
end fact.
Here is the Abstract Machine Code for the factorial
program. You should hand-simulate its execution.
LIT 0
GOTO L1
L2 LLV 1
LIT 0
BOP BGT
COND L3 L4
L3 LLV 1
LIT 0
LLV 1
LIT 1
BOP BMINUS
CODE L2
CALL 3
BOP BMULT
SLV 0
GOTO L5
L4 LIT 1
SLV 0
NOP
L5 LGV 0
LIT 1
BOP BPLUS
SGV 0
LLV 0
RTN 1
L1 LIT 0
SGV 0
LIT 0
SOS INPUT
CODE L2
CALL 1
SOS OUTPUT
LGV 0
SOS OUTPUT
SOS OUTPUTL
HALT
SOS INPUT
CODE L2
CALL 1
SOS OUTPUT
LGV 0
SOS OUTPUT
SOS OUTPUTL
HALT
SOS INPUT
CODE L2
CALL 1
SOS OUTPUT
LGV 0
SOS OUTPUT
SOS OUTPUTL
HALT