P-Machine Architecture The P-machine is a stack machine that conceptually has one memory area called the process address space (PAS). The process address space is divide into two contiguous segments: the "text", which contains the instructions for the VM to execute and the "stack," which is organized as a data-stack to be used by the PM/0 CPU. Register's The PM/0 has a few built-in registers used for its execution: The registers are named: - base pointer (BP), which points to the base of the current activation record - stack pointer (SP), which points to the current top of the stack. The stack grows downwards., - program counter (PC), which points to the next instruction to be executed. - Instruction Register (IR), which store the instruction to be executed The use of these registers will be explained in detail below. The stack grows downwards. Instruction Format The Instruction Set Architecture (ISA) of the PM/0 has instructions that each have three components, which are integers (i.e., they have the C type int) named as follows. OP is the operation code. L indicates the lexicographical level (We will give more details on L below) M depending of the operators it indicates: - A number (when OP is LIT or INC). - A program address (when OP is JMP, JPC, or CAL ). - A data address (when OP is LOD, STO) - The identity of the arithmetic/relational operation associated to the OPR op-code. (e.g. OPR 02 (ADD) or OPR 04 (MUL)) The list of instructions for the ISA can be found in Appendix A and B. P-Machine Cycles The PM/0 instruction cycle conceptually does the following for each instruction: The PM/0 instruction cycle is carried out in two steps. The first step is the fetch cycle, where the instruction pointed to by the program counter (PC) is fetched from the "text" segment, placed in the instruction register (IR) and the PC is incremented to point to the next instruction in the code list. In the second step the instruction in the IR is executed using the "stack" segment. (This does not mean that the instruction is stored in the "stack segment.") Fetch Cycle: 1.- IR.OP pas[pc] IR.L pas [pc+1] IR.M pas [pc+2] (note that each instruction need 3 entries in array "TEXT". 2. (PCPC+3). Execute Cycle: The op-code (OP) component in the IR register (IR.OP) indicates the operation to be executed. For example, if IR encodes the instruction " 202 ", then the machine adds the top two elements of the stack, popping them off the stack in the process, and stores the result in the top of the stack (so in the end sp is one less than it was at the start). Note that arithmetic overflows and underflows happen as in C int arithmetic. PM/0 initial/Default Values When the PM/0 starts execution. BP==499,SP==500,andPC==0; This means that execution starts with the "text segment" element 0 . Similarly, the initial "stack" segment values are all zero (BP=499 and SP=BP+1). The figure bellow illustrate the process address space: Size Limits Initial values for PM/0 CPU registers are: BP=499SP=BP+1PC=0; Initial process address space values are all zero: pas[0]=0,pas[1]=0,pas[3]=0[n1]=0. Constant Values: ARRAY_SIZE is 500 Note: Be aware that in PM/0 the stack is growing downwards Assignment Instructions and Guidelines: 1. The VM must be written in C and must run on Eustis3. If it runs in your PC but not on Eustis, for us it does not run. 2. The input file name should be read as a command line argument at runtime, for example: S./a.out input.txt (A deduction of 5 points will be applied to submissions that do not implement this). 3. Program output should be printed to the screen, and should follow the formatting of the example in Appendix C. A deduction of 5 points will be applied to submissions that do not implement this. 4. Submit to Webcourses: a) A readme text file indicating how to compile and run the VM. b) The source code of your PM/0 VM which should be named "vm.c" c) Student names should be written in the header comment of each source code file, in the readme, and in the comments of the submission d) Do not change the ISA. Do not add instructions or combine instructions. Do not change the format of the input. If you do so, your grade will be zero. e) Include comments in your program. If you do not comments, your grade will be zero. f) Do not implement each VM instruction with a function. If you do, a penalty of - 100 will be applied to your grade. You should only have two functions: main and base (Appendix D). g) The team member(s) must be the same for all projects. In case of problems within the team. The team will be split and each member must continue working as a one-member team for all other projects. h) On late submissions: - One day late 10% off. - Two days late 20% off. - Submissions will not be accepted after two days. Resubmissions are not accepted after two days. Your latest submission is the one that will be graded. We will be using a bash script to test your programs. This means your program should follow the output guidelines listed (see Appendix C for an example). You don't need to be concerned about whitespace beyond newline characters. We use diff -w. Rubric: If you submit a program from another semester or we detect plagiarism your grade is F for this course. Using functions to implement instructions even if only one is implemented that way, means that your grade will be "zero". Pointers and handling of dynamic data structures is not allowed. If you do your grade is "zero" 100 - Does not compile 10 - Compiles 25 - Produces lines of meaningful execution before segfaulting or looping infinitely 5 - Follows IO specifications (takes command line argument for input file name and prints output to console) 10 - README.txt containing author names 5 - Fetch cycle is implemented correctly 10 - Well commented source code 5 -Arithmetic instructions are implemented correctly 5 - Read and write instructions are implemented correctly 10 - Load and store instructions are implemented correctly 10 - Call and return instructions are implemented correctly 5 -Follows formatting guidelines correctly, source code is named vm.c Appendix A Instruction Set Architecture (ISA) - (eventually we will use "stack" to refer to the stack segment in PAS) In the following tables, italicized names (such as p ) are meta-variables that refer to integers. If an instruction's field is notated as "-", then its value does not matter (we use 0 as a placeholder for such values in examples). ISA: 01 - LIT 0, M Pushes a constant value (literal) M onto the stack 02 - OPR 0,M Operation to be performed on the data at the top of the stack. (or return from function) 03 - LOD L, M Load value to top of stack from the stack location at offset M from L lexicographical levels down 04 - STO L, M Store value at top of stack in the stack location at offset M from L lexicographical levels down 05 - CAL L, M Call procedure at code index M (generates new Activation Record and PCM ) 06 - INC 0, M Allocate M memory words (increment SP by M). First four are reserved to Static Link (SL), Dynamic Link (DL), and Return Address (RA) 07 - JMP 0, M Jump to instruction M(PCM) 08 - JPC 0, M Jump to instruction M if top stack element is 0 09 - SYS 0, 1 Write the top stack element to the screen SYS 0,2 Read in input from the user and store it on top of the stack SYS 0,3 End of program (Set "eop" flag to zero) Appendix B (Arithmetic/L0gical Instructions) ISA Pseudo Code 02 - OPR 0, \# (1 pas[sp] spsp+1; 10 GEQ pas[sp +1] pas[sp +1]>= pas[sp] spsp+1; Appendix C Example of Execution This example shows how to print the stack after the execution of each instruction. INPUT FILE For every line, there must be 3 values representing OP,L and M. 7761124132817126959900000010100000000000456443341447397425052613 When the input file (program) is read in to be stored in the text segment starting at location 0 in the process address space, each instruction will need three memory locations to be stored. Therefore, the PC must be incremented by 3 in the fetch cycle. The initial CPU register values for the example in this appendix are: SP=500;BP=SP1PC=0;IR=000;(astructoralineararraycanbeusedtoimplementIR) Hint: Each instruction uses 3 array elements and each data value just uses 1 array element. OUTPUT FILE Print out the execution of the program in the virtual machine, showing the stack and pc, bp, and sp. 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: For example in the instruction: STO L, M - You can do stack [base (IR.L) + IR.M]= pas [SP] to store the content of the top of the stack into an AR in the stack, located L levels down from the current AR. Notel: we are working at the CPU level therefore the instruction format must have only 3 fields. Any program whose number of fields in the instruction format is grater than 3 will get a zero. Note2: If your program does not follow the specifications, your grade will get a zero. Note3: if any of the instructions is implemented by calling a function, your grade will be zero