The P-machine: In this assignment, you will implement a virtual machine (VM) known as the P-machine (PMO). The P-machine is a stack machine with two memory stores: the "stack," which is organized as a stack and contains the data to be used by the PMO CPU, and the "text", which contains the instructions for the VM. The PMO CPU has four registers to handle the stack and text segments: The registers are named base pointer (BP), stack pointer (SP). program counter (PC) and instruction register (IR). They will be explained in detail later on in this document. The machine also has a register file (RF) with eight (8) registers (0-7). The Instruction Set Architecture (ISA) of the PM/0 has 24 instructions and the instruction format is as follows: "OPRL M E RE Each instruction contains four components (OP RL M) that are separated by one space. OP is the operation code. R refers to a register L indicates the lexicographical level or a register in arithmetic and relational instructions. M depending of the operators it indicates: - A number (instructions: LIT, INC). - A program address instructions: JMP, JPC, CAL). - A data address instructions: LOD, STO) - A register in arithmetic and logic instructions. (e.g. ADD R[1] R[2]. R[3]) The list of instructions for the ISA can be found in Appendix A and B. P-Machine Cycles The PM/O instruction cycle is carried out in two steps. This means that it executes two steps for each instruction. The first step is the Fetch Cycle, where the actual instruction is fetched from the "text" memory store and place in the instruction register. The second step is the Execute Cycle, where the instruction that was fetched is executed using the "stack" memory store and the register file (RF). This does not mean the instruction is stored in the "stack." Fetch Cycle: In the Fetch Cycle, an instruction is fetched from the "text" store and placed in the IR register (IR code[PC]). Afterwards, the program counter is incremented by 1 to point to the next instruction to be executed (PC PC +1). . Execute Cycle: In the Execute Cycle, the instruction that was fetched is executed by the VM. The OP component that is stored in the IR register (IR OP) indicates the operation to be executed. For example, if IR OP is the instruction ADD (IR. OP = 12), then R,L,M components of the instruction in IR (IRR IRL, IR M) are used as registers numbers to execute the instruction ADD (IRR IRL + IR M) PMI/O Initial/Default Values: Initial values for PM/O CPU registers: SP=0; BP = 1; PC = 0: IR = 0; Initial "stack" store values are all zero: stack[1] =0, stack[2] =0, stack:[3] =0.....stack[39] = 0. All registers in the register file have initial value zero (RO = 0, RI=0. R3 = 0...R7=0. Constant Values: MAX_STACK_HEIGHT is 40 MAX_CODE_LENGTH is 200 MAX LEXI_LEVELS is 3 Assignment Instructions and Guidelines: 1. The VM must be written in C and must run on Eustis a) A readme document indicating how to compile and run the VM b) The source code of your PM 0 VM. 1. The output of a test program running in the virtual machine. Please provide a copy of the initial state of the stack and the state of stack after the execution of each instruction. Please see the example in Appendix C. Appendix A Instruction Set Architecture (ISA) There are 13 arithmetic/logical operations that manipulate the data within the register file. These operations will be explain after the 11 basic instructions of PM/0. ISA: 01 - LIT R, 0, M Loads a constant value (literal) M into Register R 02 - RTN 0,0,0 Returns from a subroutine and restore the caller environment 03 - LOD R, L, M Load value into a selected register from the stack location at offset M from L lexicographical levels down STO R, LM CAL 0, L, M Store value from a selected register in the stack location at offset M from L lexicographical levels down Call procedure at code index M (generates new Activation Record and pc M) Allocate M locals (increment sp by M). First four are Functional Value, Static Link (SL), Dynamic Link (DL). and Return Address (RA) INC 0,0,M - JMP 0, 0, M. Jump to instruction M Jump to instruction M if R=0 JPC R, O, M SIO R,0,1 Write a register to the screen SIO R. 0,2 Read in input from the user and store it in a register 11 - SIO 0,0,3 End of program (program stops running) Appendix B ISA Pseudo Code 01 - LIT R,0 M R[ D M; ESTE 02 - RTN 0,0,0 sp bp pc bp - 1; stack[sp +3]: stack[sp + 4], 03 - LOD R, L, M R[i] stack base(L., bp) +M]: stack base(L, bp) + M) R[i]: 04 - STO R, L, M 05 - CAL 0,LM stack[sp + 1] + 0; stack[sp +2] + base(L, bp): stack[sp +3] + bp: stack sp + 4] : bp sp + 1; pc M /* space to return value /* static link (SL) /* dynamic link (DL) / return address (RA) 06 - INC 0,0, M 07 - JMP 0,0,M 08 - JPC R, 0, M sp + sp+M: pcM: if Ra=0 then { p M ; } 09 - SIO R, 0,1 print([1]). 10 - SIO 11 - SIO R, 0,2 R. 0,3 read(R[i]) Set Halt flag to one; (End of program) 12 - NEG (R[i] 13 - ADD (R[A] 14 - SUB (R[i] 15 - MUL (R[i] 16 - DIV (R ) 17 - ODD (R[i 18 - MOD (R[i] 19 - EQL (R[i] 20 - NEO (R[i] 21 - LSS (R[i] R[i]) RG] - R[k]) RG) - R[k]) RG) * R[k]) RO] R[k]) Rimod 2) or ordfodd(R[i]) RG) mod R[k]) R[ R[k]) RG) IR[k]) R[] R[k]) 22 - LEO ( RURG] =R[k]) 23 - GTR (R[B] R[] > R[k]) 24 - GEQ (R[i] + RG] >=R[k]) NOTE: The result of a logical operation such as (A > B) is defined as 1 if the condition was met and 0 otherwise. NOTE: in all arithmetic or relational instructions, "I refers to operand R, "J" refers to operand L, and "k" refers to operand M. For example, if we have the instruction ADD 7 8 9 (12789), we have to interpret this ast R[7] R[8] + R[9] Another example: if we have instruction LIT 5 09 (1 509), we have to interpret this as: R[5] 9 Appendix C Example of Execution This example shows how to print the stack after the execution of each instruction. The following PL/O program, once compiled, will be translated into a sequence code for the virtual machine PM/0 as shown below in the INPUT FILE FFERTE ocedure sub; FRETE const n=8 intih: procedure sub, const k = 7; intih: begin len; i=1: hek end begin 133; h:=9 call sub end. INPUT FILE For every line, there must be 4 integers representing OP, R. L and M. we recommend using the following structure for your instructions: 700 10 7002 6006 1008 4004 1001 4014 1007 4005 2000 6006 1003 4004 1009 4005 5002 11003 struct int op/* opcode int 1: R int m: int m; instruction: OUTPUT FILE 1) Print out the program in interpreted assembly language with line numbers: Line OP RLM O imp0 0 10 1 jmp 0 0 2 2 inc006 3 lit 008 sto 00.4 5 lit001 6 sto 0 1 4 7 lit 0 0 7 8 sto 0 0 5 9 tn 0 0 0 10 inc006 11 lit 0 0 3 12 sto 004 13 lit 009 14 sto 005 15 cal 002 16 sio 003 2) Print out the execution of the program in the virtual machine, showing the stack and registers pc. bp. and pcbp . registers Initial values 0 0 0 0 0 0 0 0 0 Stack: 0000000000000000000000000000000000000000 pcbp 10 0 Sp. 0 registers 0 0 0 0 0 0 0 0 O jmp 0 0 10 Stack 11 1 6 0 0 0 0 0 0 0 0 10 inc 0.06 Stack: 000000 11 lit 0 0 3 Stack: 000000 12 sto 0 0 4 Stack: 0 0 0 0 30 12 1 6 300ooooo 13 1 6 3 0 0 0 0 0 0 0 13 lit 0 0 9 Stack: 0 0 0 0 30 14 16 9ooooooo . 15 1 6 900 0 0 0 0 0 14 sto 0 0 5 Stack: 000039 na teraz 6 900 000 15 cal 0 0 2 Stack: 000039 12 900 0 0 0 0 0 2 inc0 0 6 3 Stack: 0 0 0 0 3 91011 1600 12 8 0 0 0 0 0 0 0 3 lit 008 Stack: 0000391011 1600 4 sto 00 4 5 8 0 0 0 0 0 0 0 Stack: 000039101116.80 5. lit 0016 7 12 10 0 0 0 0 0 0 Stack: 00003910111680 6 sto 0 14 7.7 12 1000 0 0 0 0 Stack: 00001901116 80 7 lit 007 8 7 12 700 0 0 0 0 0 Stack: 000019011 16 8 0 8 sto 0 0 5 9 7 12 700 0 0 0 0 0 Stack: 000019011 16 8 7 16 16 70oooooo Stack: 000019 16 sio 003 17 16 7000oooo. Stack: 000019 NOTE: It is necessary to separate each Activation Record with a bar", Appendix D Helpful Tips This function will be helpful to find a variable in a different Activation Record some L levels down: Find base L levels down int base(1, base) // stand for L in the instruction format mat af int bl; //find base L levels down bl = base; while ( 10) bl = stack[b] + 1); return bl; For example in the instruction: STO R, L, M . you can do stack[base(u L bp) + [IRM -RFCIRR) to store the content of register into the stack L levels down from the current AR. RF stand for register file The P-machine: In this assignment, you will implement a virtual machine (VM) known as the P-machine (PMO). The P-machine is a stack machine with two memory stores: the "stack," which is organized as a stack and contains the data to be used by the PMO CPU, and the "text", which contains the instructions for the VM. The PMO CPU has four registers to handle the stack and text segments: The registers are named base pointer (BP), stack pointer (SP). program counter (PC) and instruction register (IR). They will be explained in detail later on in this document. The machine also has a register file (RF) with eight (8) registers (0-7). The Instruction Set Architecture (ISA) of the PM/0 has 24 instructions and the instruction format is as follows: "OPRL M E RE Each instruction contains four components (OP RL M) that are separated by one space. OP is the operation code. R refers to a register L indicates the lexicographical level or a register in arithmetic and relational instructions. M depending of the operators it indicates: - A number (instructions: LIT, INC). - A program address instructions: JMP, JPC, CAL). - A data address instructions: LOD, STO) - A register in arithmetic and logic instructions. (e.g. ADD R[1] R[2]. R[3]) The list of instructions for the ISA can be found in Appendix A and B. P-Machine Cycles The PM/O instruction cycle is carried out in two steps. This means that it executes two steps for each instruction. The first step is the Fetch Cycle, where the actual instruction is fetched from the "text" memory store and place in the instruction register. The second step is the Execute Cycle, where the instruction that was fetched is executed using the "stack" memory store and the register file (RF). This does not mean the instruction is stored in the "stack." Fetch Cycle: In the Fetch Cycle, an instruction is fetched from the "text" store and placed in the IR register (IR code[PC]). Afterwards, the program counter is incremented by 1 to point to the next instruction to be executed (PC PC +1). . Execute Cycle: In the Execute Cycle, the instruction that was fetched is executed by the VM. The OP component that is stored in the IR register (IR OP) indicates the operation to be executed. For example, if IR OP is the instruction ADD (IR. OP = 12), then R,L,M components of the instruction in IR (IRR IRL, IR M) are used as registers numbers to execute the instruction ADD (IRR IRL + IR M) PMI/O Initial/Default Values: Initial values for PM/O CPU registers: SP=0; BP = 1; PC = 0: IR = 0; Initial "stack" store values are all zero: stack[1] =0, stack[2] =0, stack:[3] =0.....stack[39] = 0. All registers in the register file have initial value zero (RO = 0, RI=0. R3 = 0...R7=0. Constant Values: MAX_STACK_HEIGHT is 40 MAX_CODE_LENGTH is 200 MAX LEXI_LEVELS is 3 Assignment Instructions and Guidelines: 1. The VM must be written in C and must run on Eustis a) A readme document indicating how to compile and run the VM b) The source code of your PM 0 VM. 1. The output of a test program running in the virtual machine. Please provide a copy of the initial state of the stack and the state of stack after the execution of each instruction. Please see the example in Appendix C. Appendix A Instruction Set Architecture (ISA) There are 13 arithmetic/logical operations that manipulate the data within the register file. These operations will be explain after the 11 basic instructions of PM/0. ISA: 01 - LIT R, 0, M Loads a constant value (literal) M into Register R 02 - RTN 0,0,0 Returns from a subroutine and restore the caller environment 03 - LOD R, L, M Load value into a selected register from the stack location at offset M from L lexicographical levels down STO R, LM CAL 0, L, M Store value from a selected register in the stack location at offset M from L lexicographical levels down Call procedure at code index M (generates new Activation Record and pc M) Allocate M locals (increment sp by M). First four are Functional Value, Static Link (SL), Dynamic Link (DL). and Return Address (RA) INC 0,0,M - JMP 0, 0, M. Jump to instruction M Jump to instruction M if R=0 JPC R, O, M SIO R,0,1 Write a register to the screen SIO R. 0,2 Read in input from the user and store it in a register 11 - SIO 0,0,3 End of program (program stops running) Appendix B ISA Pseudo Code 01 - LIT R,0 M R[ D M; ESTE 02 - RTN 0,0,0 sp bp pc bp - 1; stack[sp +3]: stack[sp + 4], 03 - LOD R, L, M R[i] stack base(L., bp) +M]: stack base(L, bp) + M) R[i]: 04 - STO R, L, M 05 - CAL 0,LM stack[sp + 1] + 0; stack[sp +2] + base(L, bp): stack[sp +3] + bp: stack sp + 4] : bp sp + 1; pc M /* space to return value /* static link (SL) /* dynamic link (DL) / return address (RA) 06 - INC 0,0, M 07 - JMP 0,0,M 08 - JPC R, 0, M sp + sp+M: pcM: if Ra=0 then { p M ; } 09 - SIO R, 0,1 print([1]). 10 - SIO 11 - SIO R, 0,2 R. 0,3 read(R[i]) Set Halt flag to one; (End of program) 12 - NEG (R[i] 13 - ADD (R[A] 14 - SUB (R[i] 15 - MUL (R[i] 16 - DIV (R ) 17 - ODD (R[i 18 - MOD (R[i] 19 - EQL (R[i] 20 - NEO (R[i] 21 - LSS (R[i] R[i]) RG] - R[k]) RG) - R[k]) RG) * R[k]) RO] R[k]) Rimod 2) or ordfodd(R[i]) RG) mod R[k]) R[ R[k]) RG) IR[k]) R[] R[k]) 22 - LEO ( RURG] =R[k]) 23 - GTR (R[B] R[] > R[k]) 24 - GEQ (R[i] + RG] >=R[k]) NOTE: The result of a logical operation such as (A > B) is defined as 1 if the condition was met and 0 otherwise. NOTE: in all arithmetic or relational instructions, "I refers to operand R, "J" refers to operand L, and "k" refers to operand M. For example, if we have the instruction ADD 7 8 9 (12789), we have to interpret this ast R[7] R[8] + R[9] Another example: if we have instruction LIT 5 09 (1 509), we have to interpret this as: R[5] 9 Appendix C Example of Execution This example shows how to print the stack after the execution of each instruction. The following PL/O program, once compiled, will be translated into a sequence code for the virtual machine PM/0 as shown below in the INPUT FILE FFERTE ocedure sub; FRETE const n=8 intih: procedure sub, const k = 7; intih: begin len; i=1: hek end begin 133; h:=9 call sub end. INPUT FILE For every line, there must be 4 integers representing OP, R. L and M. we recommend using the following structure for your instructions: 700 10 7002 6006 1008 4004 1001 4014 1007 4005 2000 6006 1003 4004 1009 4005 5002 11003 struct int op/* opcode int 1: R int m: int m; instruction: OUTPUT FILE 1) Print out the program in interpreted assembly language with line numbers: Line OP RLM O imp0 0 10 1 jmp 0 0 2 2 inc006 3 lit 008 sto 00.4 5 lit001 6 sto 0 1 4 7 lit 0 0 7 8 sto 0 0 5 9 tn 0 0 0 10 inc006 11 lit 0 0 3 12 sto 004 13 lit 009 14 sto 005 15 cal 002 16 sio 003 2) Print out the execution of the program in the virtual machine, showing the stack and registers pc. bp. and pcbp . registers Initial values 0 0 0 0 0 0 0 0 0 Stack: 0000000000000000000000000000000000000000 pcbp 10 0 Sp. 0 registers 0 0 0 0 0 0 0 0 O jmp 0 0 10 Stack 11 1 6 0 0 0 0 0 0 0 0 10 inc 0.06 Stack: 000000 11 lit 0 0 3 Stack: 000000 12 sto 0 0 4 Stack: 0 0 0 0 30 12 1 6 300ooooo 13 1 6 3 0 0 0 0 0 0 0 13 lit 0 0 9 Stack: 0 0 0 0 30 14 16 9ooooooo . 15 1 6 900 0 0 0 0 0 14 sto 0 0 5 Stack: 000039 na teraz 6 900 000 15 cal 0 0 2 Stack: 000039 12 900 0 0 0 0 0 2 inc0 0 6 3 Stack: 0 0 0 0 3 91011 1600 12 8 0 0 0 0 0 0 0 3 lit 008 Stack: 0000391011 1600 4 sto 00 4 5 8 0 0 0 0 0 0 0 Stack: 000039101116.80 5. lit 0016 7 12 10 0 0 0 0 0 0 Stack: 00003910111680 6 sto 0 14 7.7 12 1000 0 0 0 0 Stack: 00001901116 80 7 lit 007 8 7 12 700 0 0 0 0 0 Stack: 000019011 16 8 0 8 sto 0 0 5 9 7 12 700 0 0 0 0 0 Stack: 000019011 16 8 7 16 16 70oooooo Stack: 000019 16 sio 003 17 16 7000oooo. Stack: 000019 NOTE: It is necessary to separate each Activation Record with a bar", Appendix D Helpful Tips This function will be helpful to find a variable in a different Activation Record some L levels down: Find base L levels down int base(1, base) // stand for L in the instruction format mat af int bl; //find base L levels down bl = base; while ( 10) bl = stack[b] + 1); return bl; For example in the instruction: STO R, L, M . you can do stack[base(u L bp) + [IRM -RFCIRR) to store the content of register into the stack L levels down from the current AR. RF stand for register file
