src/openpower/cyclemodel/inorder.py

   1 #!/usr/bin/env python3
   2 # Copyright (C) 2023 Luke Kenneth Casson Leighton <lkcl@lkcl.net>
   3 # Copyright (C) 2023 Dimitry Selyutin <ghostmansd@gmail.com>
   4 # LGPLv3+
   5 # Funded by NLnet
   6 #
   7 # An In-order cycle-accurate model of a Power ISA 3.0 hardware implementation
   8 #
   9 #       This program should be entirely self-sufficient such that it may be
  10 #       published in a magazine, or in a specification, or on another website,
  11 #       or as part of an Academic Paper (please ensure Attribution/Copyright
  12 #       is retained: distribution without these Copyright Notices intact is
  13 #       prohibited).
  14 #
  15 #       It should therefore not import complex modules (regex, dataclass)
  16 #       keeping to simple techniques and simple python modules that are
  17 #       easy to understand.  readability comments are crucial.  Unit tests
  18 #       should be bare-minimum practical demonstrations but also within this
  19 #       file, and additional unit tests in separate files (listed below)
  20 #
  21 #       Duplication of code from other models in this series is perfectly
  22 #       acceptable in order to respect the self-sufficiency requirement.
  23 #
  24 # Bugs:
  25 #
  26 # * https://bugs.libre-soc.org/show_bug.cgi?id=1039
  27 #
  28 # Separate Unit tests:
  29 #
  30 # * TODO
  31 #
  32 """
  33     CPU:   Fetch   <- log file
  34             |
  35            Decode  <- works out read/write regs
  36             |
  37            Issue   <- checks read-regs, sets write-regs
  38             |
  39            Execute  -> stages (countdown) clears write-regs
  40
  41 """
  42
  43 from collections import namedtuple
  44 import io
  45 import unittest
  46 import getopt
  47 import sys
  48
  49 # trace file entries are lists of these.
  50 Hazard = namedtuple("Hazard", ["action", "target", "ident", "offs", "elwid"])
  51
  52 # key: readport, writeport (per clock cycle)
  53 HazardProfiles = {
  54     "GPR": (4, 1),  # GPR allows 4 reads 1 write possible in 1 cycle...
  55     "FPR": (3, 1),
  56     "CR" : (2, 1),  # Condition Register (32-bit)
  57     "CRf": (3, 3),  # Condition Register Fields (4-bit each)
  58     "XER": (1, 1),
  59     "MSR": (1, 1),
  60     "FPSCR": (1, 1),
  61     "PC": (1, 1),    # Program Counter
  62     "SPRf" : (4, 3), # Fast SPR (actually STATE regfile in TestIssuer)
  63     "SPRs" : (1, 1), # Slow SPR
  64 }
  65
  66
  67 def read_file(fname):
  68     """reads a trace file in the form "[{rw}:FILE:regnum:offset:width]* # insn"
  69     this function is a generator, it yields a list comprising each line:
  70     ["insn", Hazard(...), Hazard(....), ....]
  71
  72     fname may be a *file* (an object) with a function named "read",
  73     in which case the Contract is that it is the *CALLER* that must
  74     take responsibility for the file: opening, closing, seeking.
  75
  76     if fname is a string then this function will take care of reading
  77     from it and is itself responsible for closing the file handle.
  78     """
  79     is_file = hasattr(fname, "read")
  80     if not is_file:
  81         fname = open(fname, "r")
  82
  83     for line in fname.readlines():
  84         (specs, insn) = map(str.strip, line.strip().split("#"))
  85         line = [insn]
  86         for spec in specs.split(" "):
  87             line.append(Hazard._make(spec.split(":")))
  88         yield line
  89     if not is_file:
  90         fname.close()
  91
  92
  93 class RegisterWrite:
  94     """
  95     RegisterWrite: contains the set of Read-after-Write Hazards.
  96     Anything in this set must be a STALL at Decode phase because the
  97     answer has still not popped out the end of a pipeline
  98     """
  99     def __init__(self):
 100         self.storage = set()
 101
 102     def expect_write(self, regs):
 103         return self.storage.update(regs)
 104
 105     def write_expected(self, regs):
 106         return (len(self.storage.intersection(regs)) != 0)
 107
 108     def retire_write(self, regs):
 109         return self.storage.difference_update(regs)
 110
 111
 112 class Execute:
 113     """
 114     Execute Pipeline: keeps a countdown-sorted list of instructions
 115     to expect at a future cycle (tick).  Anything at zero is processed
 116     by assuming it is completed, and wishes to write to the regfile.
 117     However there are only a limited number of regfile write ports,
 118     so they must be handled a few at a time.  under these circumstances
 119     STALL condition is returned, and the "processor" must *NOT* tick().
 120     """
 121     def __init__(self, cpu):
 122         self.stages = []
 123         self.cpu = cpu
 124
 125     def add_stage(self, cycles_away, stage):
 126         while cycles_away > len(self.stages):
 127             self.stages.append([])
 128         self.stages[cycles_away].append(stage)
 129
 130     def add_instruction(self, insn, writeregs):
 131         self.add_stage(2, {'insn': insn, 'writes': writeregs})
 132
 133     def tick(self):
 134         self.stages.pop(0) # tick drops anything at time "zero"
 135
 136     def process_instructions(self, stall):
 137         instructions = self.stages[0] # get list of instructions
 138         to_write = set()              # need to know total writes
 139         for instruction in instructions:
 140             to_write.update(instruction['writes'])
 141         # see if all writes can be done, otherwise stall
 142         writes_possible = self.cpu.writes_possible(to_write)
 143         if writes_possible != to_write:
 144             stall = True
 145         # retire the writes that are possible in this cycle (regfile writes)
 146         self.cpu.regs.retire_write(writes_possible)
 147         # and now go through the instructions, removing those regs written
 148         for instruction in instructions:
 149             instruction['writes'].difference_update(writes_possible)
 150         return stall
 151
 152
 153 class Fetch:
 154     """
 155     Fetch: reads the next log-entry and puts it into the queue.
 156     """
 157     def __init__(self, cpu):
 158         self.stages = [None] # only ever going to be 1 long but hey
 159         self.cpu = cpu
 160
 161     def tick(self):
 162         self.stages[0] = None
 163
 164     def process_instructions(self, stall):
 165         if stall: return stall
 166         insn = self.stages[0] # get current instruction
 167         if insn is not None:
 168             self.cpu.decode.add_instructions(insn) # pass on instruction
 169         # read from log file, write into self.stages[0]
 170         # XXX TODO
 171         return stall
 172
 173
 174 class Decode:
 175     """
 176     Decode: performs a "decode" of the instruction. identifies and records
 177     read/write regs. the reads/writes possible should likely not all be here,
 178     perhaps split across "Issue"?
 179     """
 180     def __init__(self, cpu):
 181         self.stages = [None] # only ever going to be 1 long but hey
 182         self.cpu = cpu
 183
 184     def add_instruction(self, insn):
 185         # get the read and write regs
 186         writeregs = get_input_regs(insn)
 187         readregs = get_output_regs(insn)
 188         assert self.stages[0] is None # must be empty (tick or stall)
 189         self.stages[0] = (insn, writeregs, readregs)
 190
 191     def tick(self):
 192         self.stages[0] = None
 193
 194     def process_instructions(self, stall):
 195         if stall: return stall
 196         # get current instruction
 197         insn, writeregs, readregs = self.stages[0]
 198         # check that the readregs are all available
 199         reads_possible = self.cpu.reads_possible(readregs)
 200         stall = reads_possible != readregs
 201         # perform the "reads" that are possible in this cycle
 202         readregs.difference_update(reads_possible)
 203         # and "Reserves" the writes
 204         self.cpu.expect_write(writeregs)
 205         # now pass the instruction on to Issue
 206         self.cpu.issue.add_instruction(insn, writeregs)
 207         return stall
 208
 209
 210 class Issue:
 211     """
 212     Issue phase: if not stalled will place the instruction into execute.
 213     TODO: move the reading and writing of regs here.
 214     """
 215     def __init__(self, cpu):
 216         self.stages = [None] # only ever going to be 1 long but hey
 217         self.cpu = cpu
 218
 219     def add_instruction(self, insn, writeregs):
 220         # get the read and write regs
 221         assert self.stages[0] is None # must be empty (tick or stall)
 222         self.stages[0] = (insn, writeregs)
 223
 224     def tick(self):
 225         self.stages[0] = None
 226
 227     def process_instructions(self, stall):
 228         if stall: return stall
 229         self.cpu.execute.add_instructions(self.stages[0])
 230         return stall
 231
 232
 233 class CPU:
 234     """
 235     CPU: contains Fetch, Decode, Issue and Execute pipelines, and regs.
 236     Reads "instructions" from a file, starts putting them into a pipeline,
 237     and monitors hazards.  first version looks only for register hazards.
 238     """
 239     def __init__(self):
 240         self.regs = RegisterWrite()
 241         self.fetch = Fetch(self)
 242         self.decode = Decode(self)
 243         self.issue = Issue(self)
 244         self.exe = Execute(self)
 245         self.stall = False
 246
 247     def reads_possible(self, regs):
 248         # TODO: subdivide this down by GPR FPR CR-field.
 249         # currently assumes total of 3 regs are readable at one time
 250         possible = set()
 251         r = regs.copy()
 252         while len(possible) < 3 and len(r) > 0:
 253             possible.add(r.pop())
 254         return possible
 255
 256     def writess_possible(self, regs):
 257         # TODO: subdivide this down by GPR FPR CR-field.
 258         # currently assumes total of 1 reg is possible regardless of what it is
 259         possible = set()
 260         r = regs.copy()
 261         while len(possible) < 1 and len(r) > 0:
 262             possible.add(r.pop())
 263         return possible
 264
 265     def process_instructions(self):
 266         stall = self.stall
 267         stall = self.fetch.process_instructions(stall)
 268         stall = self.decode.process_instructions(stall)
 269         stall = self.issue.process_instructions(stall)
 270         stall = self.exe.process_instructions(stall)
 271         self.stall = stall
 272         if not stall:
 273             self.fetch.tick()
 274             self.decode.tick()
 275             self.issue.tick()
 276             self.exe.tick()
 277
 278
 279 class TestTrace(unittest.TestCase):
 280
 281     def test_trace(self): # TODO, assert this is valid
 282         lines = (
 283             "r:GPR:0:0:64 w:GPR:1:0:64              # addi 1, 0, 0x0010",
 284             "r:GPR:0:0:64 w:GPR:2:0:64              # addi 2, 0, 0x1234",
 285             "r:GPR:1:0:64 r:GPR:2:0:64              # stw 2, 0(1)",
 286             "r:GPR:1:0:64 w:GPR:3:0:64              # lwz 3, 0(1)",
 287             "r:GPR:3:0:64 r:GPR:2:0:64 w:GPR:1:0:64 # add 1, 3, 2",
 288             "r:GPR:0:0:64 w:GPR:3:0:64              # addi 3, 0, 0x1234",
 289             "r:GPR:0:0:64 w:GPR:2:0:64              # addi 2, 0, 0x4321",
 290             "r:GPR:3:0:64 r:GPR:2:0:64 w:GPR:1:0:64 # add  1, 3, 2",
 291         )
 292         f = io.StringIO("\n".join(lines))
 293         lines = read_file(f)
 294         for trace in lines:
 295             print(trace)
 296
 297 def help():
 298     print ("-t             runs unit tests")
 299     print ("-h --help      prints this message")
 300     exit(-1)
 301
 302
 303 if __name__ == "__main__":
 304     opts, args = getopt.getopt(sys.argv[1:], "thi:o:",
 305                                              ["help",])
 306
 307     # default files are stdin/stdout.
 308     in_file = sys.stdin
 309     out_file = sys.stdout
 310
 311     for opt, arg in opts:
 312         if opt in ['-h', '--help']:
 313             help()
 314         if opt in ['-t']:
 315             unittest.main(argv=[sys.argv[0]]+sys.argv[2:])
 316         if opt in ['-i']:
 317             in_file = arg
 318         if opt in ['-o']:
 319             out_file = arg
 320
 321     # TODO: run model
 322     lines = read_file(in_file)
 323     for trace in lines:
 324         out_file.write("|" + "|".join(map(str, trace)) + "|\n")