(* CSC 123 Abstract Machine Implementation Assignment (version 7E9) Abstract Machine AM16 is a simple computer with 64K RAM. Word size is 32 bits (4 bytes), so there are only 16K memory addresses. The machine's CPU contains four general purpose registers, ax, bx, cx and dx, special purpose register sp and bp (top of stack and stack base), an program counter register pc. The CPU's arithmetic logic unit (ALU) is limited to integer operations add, sub, imul and idiv. AM16 Instruction Set add src dst # add ax bx, add 4 bx sub src dst # only src can be immediate imul src dst idiv src dst push src # push ax, push 5 pop dst # pop ax mov src dst jmp inst # unconditional jump to instruction number jnz inst # jump if cx register is not zero jz inst # jump if cx=0 jn inst # jump if cx<0 call inst # push sp, then jump ret # pc = sp nop # does nothing, but it has a role The semantics of an instruction such as (sub ax bx) is bx -= ax: the second operand is also the destination operand. There is an exception with the integer division instruction: (idiv ax cx) will leave the quotient in cx and remainder in dx. If the destination register is dx, the remainder is discarded. Instruction operands can be immediate (3), register (ax), or memory ([3] or [ax]). However, AM16 is a RISC architecture. This means that memory operands are only allowed in the mov instruction for loading and saving to memory: mov [ax] bx # load from memory address in ax into bx mov ax [bx] # store ax into memory at address bx. mov [ax] [bx] # NOT ALLOWED IN RISC MACHINES. Memory operands are also allowed to be immediate (move [16] ax). The jump instructions set the pc register to the instruction number. When implementing these instructions, be aware that pc is automatically incremented by 1 in the executeProg function found below. The call instruction should push the current value of the pc register on the stack, then jump to the indicated instruction number The ret instruction pops the stack into the pc register. For example, the following program calculates 6! mov 6 cx mov 1 ax imul cx ax sub 1 cx jnz 2 push ax # push result on stack AM16 programs should always leave the final result on top of the stack. This program implements A FRAGMENT OF AM16 in F#, including assembler. Your assignment would be to complete the implementation. *) open System open System.Collections.Generic open Microsoft.FSharp.Math open System.Text.RegularExpressions type operand = Imm of int | Reg of string | Mem of operand;; // Mem is limited to Mem(Reg_) or M(Imm _). type instruction = | ALU of (string*operand*operand) // includes "add", "sub", "imul", "idiv" | PUSH of operand | POP of operand | MOV of operand*operand | JMP of int | JNZ of int | JZ of int | JN of int | CALL of int | RET | NOP // an operation such as 'add ax bx' is represented internally as // ALU("add",Reg("ax"),Reg("bx")). This is the "abstract syntax" of AM16. // A program is represented by a list of such instructions ////////////////////// Machine Simulation ////////////////////// let RAM:int[] = Array.zeroCreate (16*1024); // simulates memory let mutable sp = 0 // top of stack register // sp points to next available slot on stack, so 0 means empty stack. let mutable pc = 0 // program counter register let mutable fault = false // halts machine on true let REGS = Dictionary();; // simulate general registers REGS["ax"] <- 0 REGS["bx"] <- 0 REGS["cx"] <- 0 REGS["dx"] <- 0 REGS["bp"] <- 0 // core dump prints current snapshot of registers plus top portion of stack. let coredump() = fault <- true printfn "MACHINE FAULT, CORE DUMPED!" printfn "ax=%d, bx=%d, cx=%d, dx=%d" (REGS["ax"]) (REGS["bx"]) (REGS["cx"]) (REGS["dx"]) printfn "sp=%d, top portion of stack:\n" sp let mutable i = sp-1 while (i>=0 && i>sp-8) do printfn "%d" (RAM[i]) i <- i-1;; let load_operand = function // returns integer | Imm(n) -> n | Reg("sp") -> sp | Reg(r) -> REGS[r] | _ -> 0 let execute inst = match inst with | ALU("add",a,Reg(b)) -> REGS[b] <- REGS[b] + (load_operand a) | ALU("sub",a,Reg(b)) -> REGS[b] <- REGS[b] - (load_operand a) | ALU("imul",a,Reg(b)) -> REGS[b] <- REGS[b] * (load_operand a) | PUSH(x) when sp // push immediate, as in push 3 RAM[sp] <- (load_operand x) sp <- sp+1 | POP(Reg(r)) when sp>0 -> // pop into register r sp <- sp - 1 REGS[r] <- RAM[sp] | NOP -> () // does nothing | x -> Console.WriteLine("Illegal Instruction "+string(x)); coredump(); //Execute a program as a list of operations. Note how pc is incremented //so any jump instruction must be written carefully. let executeProg trace (program:instruction list) = pc <- 0 sp <- 0 while (not fault) && pc0 then printfn " tos=%d" (RAM[sp-1]) else printfn "" //executeprog ///////////////////////////// ASSEMBLER/SIMULATION ///////////////////////// //////////////// Don't need to touch this part // translate a string into an operand let rec translate_operand (x:string) = try Imm(int(x)) // try-with block exception handling with | exce -> let len = x.Length if x[0]='[' && x[len-1]=']' then Mem(translate_operand (x.Substring(1,len-2))) else Reg(x) // translate a string token array into an AM16 instruction let translate_instruction ary = match ary with | [| "push"; x |] -> PUSH(translate_operand x) | [| "pop"; x |] -> POP(translate_operand x) | [| "mov"; x; y |] -> MOV(translate_operand x, translate_operand y) | [| "jmp"; x |] -> JMP(int x) | [| "jnz"; x |] -> JNZ(int x) | [| "jz"; x |] -> JZ(int x) | [| "jn"; x |] -> JN(int x) | [| "call"; x |] -> CALL(int x) | [| op; x; y |] -> ALU(op, translate_operand x, translate_operand y) | [| "ret" |] -> RET | [| "nop" |] -> NOP | _ -> raise(Exception("Unrecognized instruction"));; let assemble inst = translate_instruction (Regex.Split(inst,"\s"));; //let i1 = assemble "add ax bx"; sample let assemble inst = translate_instruction (Regex.Split(inst,"\s"));; let readprogram() = let mutable line = "" let vec = ResizeArray(); while line<>null do line <- Console.ReadLine() if line<>null && line.Length>0 && line[0]<>'#' then vec.Add(assemble line) let rec inner i ax = if i=0 then (vec[0]::ax) else inner (i-1) (vec[i]::ax) inner (vec.Count-1) [] executeProg true (readprogram()) // run program with trace // run with dotnet fsi am16asn.fsx < test1.m16 (* YOUR ASSIGNMENT 1. Write a 'prettyinst' function that translates an instruction in abstract syntax to a string in concrete syntax: for example, Push(Reg("ax")) should translate to "push ax". Uncomment the call the prettyinst in the executeProg function. 2. Complete the definition of the `execute` function to cover all cases. All instructions with valid operands must be accounted for. 3. Test your program with the various .m16 programs included. *)