Metal

metal.py

# metal.py
# 
# METAL, by Dave Beazley
# dabeaz.com

# One of the main roles of a compiler is taking high-level programs
# such as what you might write in C or Python and reducing them to
# instructions that can execute on actual hardware.
#
# This file implements a very tiny CPU in the form of a Python
# program.  Although simulated, this CPU mimics the behavior of a real
# CPU.  There are registers for performing simple mathematical
# calculations, memory operations for loading/storing values, control
# flow instructions for branching and gotos, and a few I/O ports for
# performing output.
#
# See the end of this file for some exercises.
#
# The CPU has 8 registers (R0, R1, ..., R7) that hold 32-bit unsigned
# integer values.  Register R0 is hardwired to always contains the
# value 0. Register R7 is initialized to the highest valid memory
# address. A special register PC holds the index of the next
# instruction that will execute.
#
# The memory of the machine consists of 65536 memory slots, each of
# which can hold an integer value.  Special LOAD/STORE instructions
# access the memory.  Instructions are stored separately.  All memory
# addresses from 0-65535 may be used.
#
# The machine has two I/O ports. Writing to memory address 65535
# (0xFFFF) prints a 32-bit integer value.  Writing to memory address
# 65534 (0xFFFE) prints a single character.  The symbolic constant
# IO_OUT contains the value 65535.  The symbolic constant IO_CHAR
# contains the value 65534.  Both can be used when writing code.
#
# The machine understands the following instructions--which are
# encoded as tuples:
#
#   ('ADD', 'Ra', 'Rb', 'Rd')       ; Rd = Ra + Rb
#   ('SUB', 'Ra', 'Rb', 'Rd')       ; Rd = Ra - Rb
#   ('MUL', 'Ra', 'Rb', 'Rd')       ; Rd = Ra * Rb
#   ('DIV', 'Ra', 'Rb', 'Rd')       ; Rd = Ra * Rb
#   ('INC', 'Ra')                   ; Ra = Ra + 1
#   ('DEC', 'Ra')                   ; Ra = Ra - 1
#   ('AND', 'Ra', 'Rb', 'Rd')       ; Rd = Ra & Rb (bitwise-and)
#   ('OR', 'Ra', 'Rb', 'Rd')        ; Rd = Ra | Rb (bitwise-or)
#   ('XOR', 'Ra', 'Rb', 'Rd')       ; Rd = Ra ^ Rb (bitwise-xor)
#   ('SHL', 'Ra', nbits, 'Rd')      ; Rd = Ra << nbits (left shift)
#   ('SHR', 'Ra', nbits, 'Rd')      ; Rd = Ra >> nbits (right shift)
#   ('CMP', 'op', 'Ra', 'Rb', 'Rd') ; Rd = (Ra op Rb) (compare)
#   ('CONST', value, 'Rd')          ; Rd = value
#   ('LOAD', 'Rs', 'Rd', offset)    ; Rd = MEMORY[Rs + offset]
#   ('STORE', 'Rs', 'Rd', offset)   ; MEMORY[Rd + offset] = Rs
#   ('JMP', 'Rd', offset)           ; PC = Rd + offset
#   ('BZ', 'Rt', offset)            ; if Rt == 0: PC = PC + offset
#   ('HALT,)                        ; Halts machine
#
# In the the above instructions 'Rx' means some register number such
# as 'R0', 'R1', etc.  The 'PC' register may also be used as a
# register.  All memory instructions take their address from register
# plus an integer offset that's encoded as part of the instruction.

IO_OUT = 65535
CHAR_OUT = 65534
MASK = 0xffffffff

class Metal:
    def run(self, instructions):
        '''
        Run a program. memory is a Python list containing the program
        instructions and other data.  Upon startup, all registers
        are initialized to 0.  R7 is initialized with the highest valid
        memory index (len(memory) - 1).
        '''
        self.registers = { f'R{d}':0 for d in range(8) }
        self.registers['PC'] = 0
        self.instructions = instructions
        self.memory = [0] * 65536
        self.registers['R7'] = len(self.memory) - 2
        self.running = True
        while self.running:
            op, *args = self.instructions[self.registers['PC']]
            # Uncomment to debug what's happening
            # print(self.registers['PC'], op, args)
            # print(self.registers)
            # print("=============================")
            self.registers['PC'] += 1
            getattr(self, op)(*args)
            self.registers['R0'] = 0    # R0 is always 0 (even if you change it)
        return

    def ADD(self, ra, rb, rd):
        self.registers[rd] = (self.registers[ra] + self.registers[rb]) & MASK

    def SUB(self, ra, rb, rd):
        self.registers[rd] = (self.registers[ra] - self.registers[rb]) & MASK

    def MUL(self, ra, rb, rd):
        self.registers[rd] = (self.registers[ra] * self.registers[rb]) & MASK        

    def DIV(self, ra, rb, rd):
        self.registers[rd] = (self.registers[ra] // self.registers[rb]) & MASK        
        
    def INC(self, ra):
        self.registers[ra] = (self.registers[ra] + 1) & MASK

    def DEC(self, ra):
        self.registers[ra] = (self.registers[ra] - 1) & MASK

    def AND(self, ra, rb, rd):
        self.registers[rd] = (self.registers[ra] & self.registers[rb]) & MASK

    def OR(self, ra, rb, rd):
        self.registers[rd] = (self.registers[ra] | self.registers[rb]) & MASK

    def XOR(self, ra, rb, rd):
        self.registers[rd] = (self.registers[ra] ^ self.registers[rb]) & MASK

    def SHL(self, ra, nbits, rd):
        self.registers[rd] = (self.registers[ra] << nbits) & MASK

    def SHR(self, ra, nbits, rd):
        self.registers[rd] = (self.registers[ra] >> nbits) & MASK
        
    def CMP(self, op, ra, rb, rd):
        if op == '==':
            self.registers[rd] = int(self.registers[ra] == self.registers[rb])
        elif op == '!=':
            self.registers[rd] = int(self.registers[ra] != self.registers[rb])
        elif op == '<':
            self.registers[rd] = int(self.registers[ra] < self.registers[rb])
        elif op == '>':
            self.registers[rd] = int(self.registers[ra] > self.registers[rb])
        elif op == '<=':
            self.registers[rd] = int(self.registers[ra] <= self.registers[rb])
        elif op == '>=':
            self.registers[rd] = int(self.registers[ra] >= self.registers[rb])
        else:
            raise RuntimeError(f'Bad comparison {op}. Must be ==, !=, <, >, <=, >=')
            
    def CONST(self, value, rd):
        self.registers[rd] = value & MASK

    def LOAD(self, rs, rd, offset):
        self.registers[rd] = (self.memory[self.registers[rs]+offset]) & MASK

    def STORE(self, rs, rd, offset):
        addr = self.registers[rd]+offset
        self.memory[self.registers[rd]+offset] = self.registers[rs]
        if addr == IO_OUT:
            print(self.registers[rs])
        elif addr == CHAR_OUT:
            print(chr(self.registers[rs]), end='')

    def JMP(self, rd, offset):
        self.registers['PC'] = self.registers[rd] + offset

    def BZ(self, rt, offset):
        if not self.registers[rt]:
            self.registers['PC'] += offset

    def HALT(self):
        self.running = False