Parsed: smalltests/SimpleProcessor.bsv KB_package ("SimpleProcessor",[],[], [KB_typedefEnum (["R0"; "R1"; "R2"; "R3"],"RegNum",["Bits"]); KB_typedefSynonym (KB_typedef ("InstructionAddressWidth",[]),KB_typeNat "5"); KB_typedefSynonym (KB_typedef ("InstructionAddress",[]), KB_typeIde ("UInt",[KB_typeIde ("InstructionAddressWidth",[])])); KB_varDeclAssign (KB_typeIde ("Integer",[]),"imemSize",[], KB_functionCall (KB_id "exp", [KB_intLiteral "2"; KB_functionCall (KB_id "valueof",[KB_constantAlias "InstructionAddressWidth"])])); KB_typedefSynonym (KB_typedef ("Value",[]),KB_typeIde ("Bit",[KB_typeNat "32"])); KB_typedefTaggedUnion ([], [KB_unionSubStruct ([KB_structMember (KB_typeIde ("RegNum",[]),"rd"); KB_structMember (KB_typeIde ("Value",[]),"v")],"MovI"); KB_unionMember (Some (KB_typeIde ("InstructionAddress",[])),"Br"); KB_unionSubStruct ([KB_structMember (KB_typeIde ("RegNum",[]),"rs"); KB_structMember (KB_typeIde ("InstructionAddress",[]),"dest")],"Brz"); KB_unionSubStruct ([KB_structMember (KB_typeIde ("RegNum",[]),"rd"); KB_structMember (KB_typeIde ("RegNum",[]),"rs1"); KB_structMember (KB_typeIde ("RegNum",[]),"rs2")],"Gt"); KB_unionSubStruct ([KB_structMember (KB_typeIde ("RegNum",[]),"rd"); KB_structMember (KB_typeIde ("RegNum",[]),"rs1"); KB_structMember (KB_typeIde ("RegNum",[]),"rs2")],"Minus"); KB_unionMember (Some (KB_typeIde ("RegNum",[])),"Output"); KB_unionMember (null,"Halt")],"Instruction",["Bits"]); KB_interface (KB_typedef ("SimpleProcessor",[]), [KB_methodProto ([],KB_typeIde ("Action",[]),"loadInstruction", [KB_methodProtoFormal (KB_typeIde ("InstructionAddress",[]),"ia"); KB_methodProtoFormal (KB_typeIde ("Instruction",[]),"instr")],[]); KB_methodProto ([],KB_typeIde ("Action",[]),"start",[],[]); KB_methodProto ([],KB_typeIde ("Bool",[]),"halted",[],[])],null); KB_attribute ([KB_attr_spec ("synthesize",null)], KB_moduleDef ("mkSimpleProcessor",[],Some (KB_typeIde ("SimpleProcessor",[])),[],[], [KB_varDecl (KB_typeIde ("Reg",[KB_typeIde ("Instruction",[])]),"imem", [KB_id "imemSize"]); KB_for (KB_varDeclAssign (KB_typeIde ("Integer",[]),"j",[],KB_intLiteral "0"), KB_diadic (KB_bop V_dltd,KB_id "j",KB_id "imemSize"), KB_varAssign (KB_id "j",KB_diadic (KB_op V_plus,KB_id "j",KB_intLiteral "1")), KB_varDeclDo (null,KB_bit_insert (KB_id "imem",KB_id "j"),KB_id "mkRegU")); KB_varDeclDo (Some (KB_typeIde ("Reg",[KB_typeIde ("InstructionAddress",[])])), KB_id "pc",KB_functionCall (KB_id "mkReg",[KB_intLiteral "0"])); KB_varDecl (KB_typeIde ("Reg",[KB_typeIde ("Value",[])]),"regs", [KB_id "regFileSize"]); KB_for (KB_varDeclAssign (KB_typeIde ("Integer",[]),"j",[],KB_intLiteral "0"), KB_diadic (KB_bop V_dltd,KB_id "j",KB_id "regFileSize"), KB_varAssign (KB_id "j",KB_diadic (KB_op V_plus,KB_id "j",KB_intLiteral "1")), KB_varDeclDo (null,KB_bit_insert (KB_id "regs",KB_id "j"),KB_id "mkRegU")); KB_varDeclDo (Some (KB_typeIde ("Reg",[KB_typeIde ("Bool",[])])),KB_id "running", KB_functionCall (KB_id "mkReg",[KB_systemFunction ("False",[])])); KB_varDeclDo (Some (KB_typeIde ("Reg",[KB_typeIde ("UInt",[KB_typeNat "32"])])), KB_id "cycle",KB_functionCall (KB_id "mkReg",[KB_intLiteral "0"])); KB_rule ([],"fetchAndExecute",Some (KB_id "running"), [KB_letBinding ("instr",KB_bitSelect (KB_id "imem",[KB_id "pc"])); KB_case (KB_id "instr", [(KB_taggedUnion ("MovI", Some (KB_spi [("rd", KB_dot (KB_id "rd")); ("v", KB_dot (KB_id "v"))])), KB_block (null, [KB_regWrite (KB_id "pc", KB_diadic (KB_op V_plus,KB_id "pc",KB_intLiteral "1")); KB_regWrite (KB_bit_insert (KB_id "regs", KB_functionCall (KB_id "pack",[KB_id "rd"])), KB_id "v")],null)); (KB_taggedUnion ("Br",Some (KB_patternVar "d")), KB_regWrite (KB_id "pc",KB_id "d")); (KB_taggedUnion ("Brz", Some (KB_spi [("rs", KB_dot (KB_id "rs")); ("dest", KB_dot (KB_id "d"))])), KB_if (KB_diadic (KB_bop V_deqd, KB_bitSelect (KB_id "regs", [KB_functionCall (KB_id "pack",[KB_id "rs"])]), KB_intLiteral "0"),KB_regWrite (KB_id "pc",KB_id "d"), Some (KB_regWrite (KB_id "pc", KB_diadic (KB_op V_plus,KB_id "pc",KB_intLiteral "1"))))); (KB_taggedUnion ("Gt", Some (KB_spi [("rd", KB_dot (KB_id "rd")); ("rs1", KB_dot (KB_id "rs1")); ("rs2", KB_dot (KB_id "rs2"))])), KB_block (null, [KB_varDeclAssign (KB_typeIde ("Bool",[]),"b",[], KB_diadic (KB_bop V_dgtd, KB_bitSelect (KB_id "regs", [KB_functionCall (KB_id "pack",[KB_id "rs1"])]), KB_bitSelect (KB_id "regs", [KB_functionCall (KB_id "pack",[KB_id "rs2"])]))); KB_varDeclAssign (KB_typeIde ("Value",[]),"bv",[], KB_functionCall (KB_id "extend", [KB_functionCall (KB_id "pack",[KB_id "b"])])); KB_regWrite (KB_bit_insert (KB_id "regs", KB_functionCall (KB_id "pack",[KB_id "rd"])), KB_id "bv"); KB_regWrite (KB_id "pc", KB_diadic (KB_op V_plus,KB_id "pc",KB_intLiteral "1"))], null)); (KB_taggedUnion ("Minus", Some (KB_spi [("rd", KB_dot (KB_id "rd")); ("rs1", KB_dot (KB_id "rs1")); ("rs2", KB_dot (KB_id "rs2"))])), KB_block (null, [KB_regWrite (KB_bit_insert (KB_id "regs", KB_functionCall (KB_id "pack",[KB_id "rd"])), KB_diadic (KB_op V_minus, KB_bitSelect (KB_id "regs", [KB_functionCall (KB_id "pack",[KB_id "rs1"])]), KB_bitSelect (KB_id "regs", [KB_functionCall (KB_id "pack",[KB_id "rs2"])]))); KB_regWrite (KB_id "pc", KB_diadic (KB_op V_plus,KB_id "pc",KB_intLiteral "1"))], null)); (KB_taggedUnion ("Output",Some (KB_patternVar "rs")), KB_block (null, [KB_functionCall (KB_id "$display", [KB_stringLiteral "%0d: output regs[%d] = %0d"; KB_id "cycle"; KB_id "rs"; KB_bitSelect (KB_id "regs", [KB_functionCall (KB_id "pack",[KB_id "rs"])])]); KB_regWrite (KB_id "pc", KB_diadic (KB_op V_plus,KB_id "pc",KB_intLiteral "1"))], null)); (KB_taggedUnion ("Halt",null), KB_block (null, [KB_functionCall (KB_id "$display", [KB_stringLiteral "%0d: Halt at pc"; KB_id "cycle"; KB_id "pc"]); KB_regWrite (KB_id "running",KB_systemFunction ("False",[]))],null)); (KB_caseDefault, KB_block (null, [KB_functionCall (KB_id "$display", [KB_stringLiteral "%0d: Illegal instruction at pc %0d: %0h"; KB_id "cycle"; KB_id "pc"; KB_id "instr"]); KB_regWrite (KB_id "running",KB_systemFunction ("False",[]))],null))]); KB_regWrite (KB_id "cycle", KB_diadic (KB_op V_plus,KB_id "cycle",KB_intLiteral "1"))], null); KB_methodDef (Some (KB_typeIde ("Action",[])),"loadInstruction", [KB_methodFormal (Some (KB_typeIde ("InstructionAddress",[])),"ia"); KB_methodFormal (Some (KB_typeIde ("Instruction",[])),"instr")], Some (KB_monadic ("!",KB_id "running")), [KB_regWrite (KB_bit_insert (KB_id "imem",KB_id "ia"),KB_id "instr")],null); KB_methodDef (Some (KB_typeIde ("Action",[])),"start",[],null, [KB_regWrite (KB_id "cycle",KB_intLiteral "0"); KB_regWrite (KB_id "pc",KB_intLiteral "0"); KB_regWrite (KB_id "running",KB_systemFunction ("True",[]))],null); KB_methodDef (Some (KB_typeIde ("Bool",[])),"halted",[],null, [KB_returnStmt (KB_monadic ("!",KB_id "running"))],null)], Some "mkSimpleProcessor"))],Some "SimpleProcessor") // Copyright 2008 Bluespec, Inc. All rights reserved. // ================================================================ // Small Example Suite: Example 9a // Simple Processor model, illustrating the use of enums, tagged unions, // structs, arrays of registers, and pattern-matching. // ================================================================ // The entire program is given on the next few lines. // The rest of the file is commentary on this program. package SimpleProcessor; // ---------------------------------------------------------------- // A small instruction set // ---- Names of the four registers in the register file typedef enum {R0, R1, R2, R3} RegNum deriving (Bits); //Integer regFileSize = exp (2, valueof (SizeOf#(RegNum))); // ---- Instruction addresses for a 32-location instruction memory typedef 5 InstructionAddressWidth; typedef UInt#(InstructionAddressWidth) InstructionAddress; Integer imemSize = exp (2, valueof(InstructionAddressWidth)); // ---- Values stored in registers typedef Bit#(32) Value; // ---- Instructions typedef union tagged { struct { RegNum rd; Value v; } MovI; // Move Immediate InstructionAddress Br; // Branch Unconditionally struct { RegNum rs; InstructionAddress dest; } Brz; // Branch if zero struct { RegNum rd; RegNum rs1; RegNum rs2; } Gt; // rd <= (rs1 > rs2) struct { RegNum rd; RegNum rs1; RegNum rs2; } Minus; // rd <= (rs1 - rs2) RegNum Output; void Halt; } Instruction deriving (Bits); // ---------------------------------------------------------------- // The processor model interface SimpleProcessor; method Action loadInstruction (InstructionAddress ia, Instruction instr); method Action start (); // Begin instruction execution at pc 0 method Bool halted (); endinterface (* synthesize *) module mkSimpleProcessor (SimpleProcessor); // ---- Instruction memory (modeled here using an array of registers) Reg#(Instruction) imem[imemSize]; for (Integer j = 0; j < imemSize; j = j + 1) imem [j] <- mkRegU; Reg#(InstructionAddress) pc <- mkReg (0); // The program counter // ---- The register file (modeled here using an array of registers) Reg#(Value) regs[regFileSize]; // The register file for (Integer j = 0; j < regFileSize; j = j + 1) regs [j] <- mkRegU; // ---- Status Reg#(Bool) running <- mkReg (False); Reg#(UInt#(32)) cycle <- mkReg (0); // ---------------- // RULES rule fetchAndExecute (running); let instr = imem [pc]; case (instr) matches tagged MovI { rd: .rd, v: .v } : begin pc <= pc + 1; regs[pack(rd)] <= v; end tagged Br .d : pc <= d; tagged Brz { rs: .rs, dest: .d } : if (regs[pack(rs)] == 0) pc <= d; else pc <= pc + 1; tagged Gt { rd:.rd, rs1:.rs1, rs2:.rs2 } : begin Bool b = (regs[pack(rs1)] > regs[pack(rs2)]); Value bv = extend (pack (b)); regs[pack(rd)] <= bv; pc <= pc + 1; end tagged Minus { rd:.rd, rs1:.rs1, rs2:.rs2 } : begin regs[pack(rd)] <= regs[pack(rs1)] - regs[pack(rs2)]; pc <= pc + 1; end tagged Output .rs : begin $display ("%0d: output regs[%d] = %0d", cycle, rs, regs[pack(rs)]); pc <= pc + 1; end tagged Halt : begin $display ("%0d: Halt at pc", cycle, pc); running <= False; end default: begin $display ("%0d: Illegal instruction at pc %0d: %0h", cycle, pc, instr); running <= False; end endcase cycle <= cycle + 1; endrule // ---------------- // METHODS method Action loadInstruction (InstructionAddress ia, Instruction instr) if (! running); imem [ia] <= instr; endmethod method Action start (); cycle <= 0; pc <= 0; running <= True; endmethod method Bool halted (); return (! running); endmethod endmodule: mkSimpleProcessor endpackage: SimpleProcessor /* ================================================================ * ================================================================ * ================================================================ Commentary (rest of this file) The model is very readable because the type system allows us to work with readable, symbolic names throughout, instead of getting bogged down with details about the bit fields in an instruction encoding. ---------------- The following statement: typedef enum {R0, R1, R2, R3} RegNum deriving (Bits); defines four symbolic names for the registers in a four-register register file. The 'deriving(Bits)' tells the compiler to pick a default bit representation (here 0, 1, 2, and 3, but we will never have to be aware of these details in the code that follows). The statement: Integer regFileSize = exp (2, valueof (SizeOf#(RegNum))); calculates the size of the register file (here, 4). 'SizeOf#(RegNum)' evaluates to the numeric type 2, because that is the number of bits needed to represent a RegNum. 'valueof (2)' converts this numeric type '2' into the ordinary Integer 2. Finally, 'exp (2, 2)' computes 2 raised to the power 2, yielding 4. Thus, if tomorrow we decided to double the size of the register file, e.g.: typedef enum {R0, R1, R2, R3, R4, R5, R6, R7} RegNum the system will automatically recompute 'regFileSize' to be 8. ---------------- The next set of statements: typedef 5 InstructionAddressWidth; typedef UInt#(InstructionAddressWidth) InstructionAddress; Integer imemSize = exp (2, valueof(InstructionAddressWidth)); defines instructions to be 5 bits wide, defines the 'InstructionAddress' type to be a synonym for an unsigned integer of width 5, and finally computes the instruction memory size to be exp(2,5) yielding 32. ---------------- Our simple processor computes with 32-bit values: typedef Bit#(32) Value; ---------------- The next statement: typedef union tagged { ... } Instruction deriving (Bits); defines the data structure representing an 'Instruction'. This is a 'tagged union' type, and the declaration can be read in English as follows: An Instruction is either a 'MovI' kind (Move Immediate), in which case it contains a struct with two members rd of type RegNum and v of type Value, or it is a 'Br' kind (Branch Unconditionally), in which case it contains an InstructionAddress or it is a 'Brz' kind (Branch on Zero) in which case it contains a struct with two members rs of type RegNum and dest of type InstructionAddress ... and so on ... or it is a 'Halt' kind in which case it contains nothing (void). Notice that we do not get bogged down into details of how these members are laid out in memory, i.e., the bit representations (we will revisit this question later). The 'deriving (Bits)' tells the compiler to pick a default bit representation. Given an Instruction, we will directly use the symbolic names 'MovI', 'Br', 'Brz', ... and so on to test what kind of instruction it is. Therefore, these are also called 'tags', and hence the name 'tagged union'. In the bit representation, there will be bits that permit the system to decode which kind of instruction we have. ---------------- The next phrase: interface SimpleProcessor; ... declares the simple interface to our processor. The 'loadInstruction' method allows us to load instructions into the processor's instruction memory. The 'start' method commands the processor to begin executing instructions in its instruction memory, starting at pc 0. The 'halted' method allows the environment to query whether the processor is currently executing a program or not. ---------------- In module 'mkSimpleProcessor', the lines: Reg#(Instruction) imem[imemSize]; for (Integer j = 0; j < imemSize; j = j + 1) imem [j] <- mkRegU; declare an array of registers. The array size is 'imemSize'. The for-loop initializes each element of the array using the 'mkRegU' module, i.e., an uninitialized register. ---------------- An equally good alternative style for this would be: import Vector::*; // near the top of the file ... Vector#(TExp#(InstructionAddressWidth), Reg#(Instruction)) imem <- replicateM (mkRegU); i.e., we declare 'imem' to be a Vector of size TExp#(InstructionAddressWidth) containing 'Reg#(Instruction)'s, and we initialize the Vector using 'replicateM' applied to 'mkRegU'. We use the '<-' assignment, and the 'replicateM' because 'mkRegU' is a side-effecting operation that instantiates a register and returns a register interface. Other than the fact that '[]' arrays take an Integer size and are usually initialized in for-loops, whereas a 'Vector' takes a numeric type for its size and is often initialized using 'replicate' or 'replicateM', choosing one style over the other is mostly a matter of stylistic preference. Both '[]' arrays and 'Vector's are indexed in the same way, using square bracket notation, as seen later in the code. ---------------- The next statement allocates the register for our PC (Program Counter), which just contains an instruction address: Reg#(InstructionAddress) pc <- mkReg (0); // The program counter ---------------- The next set of statements: Reg#(Value) regs[regFileSize]; // The register file for (Integer j = 0; j < regFileSize; j = j + 1) regs [j] <- mkRegU; allocates an array of registers for the register file, just like the instruction memory. Here, too, a Vector could have been used. In such an array (or Vector) of registers, there is no hardware significance to the array itself--the array is just a notational convenience for us to talk about the aggregate, and to name individual members of the aggregate using indexing. However, given that it just represents a collection of registers, note that like any other collection of registers there is no a priori constraint on how many registers we read and write every cycle--it's just a matter of building the appropriate muxing and decode logic. However, in real life, when we build register files, we try to limit the complexity of this muxing and decode logic by restricting the number of 'ports' of a register file, i.e., we place a constraint on how many registers can be read or written in the same cycle. The BSV library provides a primitive called 'RegFile' that is indeed constrained in this way, and provides a more realistic register file. However, this simple example does not use that. ---------------- The simple processor has a single rule that encapsulates fetching and executing an instruction (whenever it is 'running'): rule fetchAndExecute (running); let instr = imem [pc]; case (instr) matches tagged MovI { rd: .rd, v: .v } : begin regs[pack(rd)] <= v; pc <= pc + 1; end tagged Br .d : pc <= d; ... endcase ... endrule We fetch an instruction 'instr' from 'imem[pc]'. The 'case (instr) matches ... endcase' phrase is called a 'pattern-matching' case statement. For example, the first two arms of the case statement can be read in English as follows: If 'instr' is of the 'MovI' kind, its contents is a struct with members 'rd' and 'v' (of type RegNum and Value, respectively); let us bind these members to the variables 'rd' and 'v' respectively, and then let us assign v to the rd'th register and increment pc by 1 If 'instr' is of the 'Br' kind, its contents is of type 'InstructionAddress'; let us bind it to the variable 'd', and then let us assign 'd' to 'pc' and so on. In each case arm, the phrase before the ':' can be seen as a 'pattern' that is to be matched against 'instr'. If the pattern successfully matches, it also binds certain contents of 'instr' to certain variables. If the pattern is successfully matched, the case arm is selected, and we execute the right-hand side (after the ':') using the variables bound during the pattern-match. As you will see, this pattern-matching notation dramatically improves readability; we are not groveling in the details of selecting certain bit-fields out of 'instr', an activity that normally is extremely tedious, error-prone, and unmaintainable. ---------------- Once you understand the pattern-matching, the right-hand sides of each case arm are practically self-explanatory. Our one remaining comment is about why we use 'pack' in 'regs[pack(...)]' expressions. The reason is that variables like 'rd', 'rs1', 'rs2' etc. are of type 'RegNum', whereas arrays are indexed by numeric types such as integers, bits, and so on. By applying 'pack', we convert a 'RegNum' type into a 'Bits#()' type, which is legal as an index. ---------------- Finally, we define the methods, which are pretty self-explanatory. ---------------- SUMMARY - The use of - enums, tagged unions, structs, and arrays - automatic computations of parameters such as regFileSize, imemSize, - 'deriving (Bits)' to provide default bit representations, - pattern-matching, - and static type-checking of all the above make this code remarkably readable (even 'obvious') and maintainable. The whole simple-processor model fits in about 130 lines of clear source code. * ================================================================ */