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.
  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 """
  29     CPU:   Fetch   <- log file
  30             |
  31            Decode  <- works out read/write regs
  32             |
  33            Issue   <- checks read-regs, sets write-regs
  34             |
  35            Execute  -> stages (countdown) clears write-regs
  36
  37 """
  38
  39 from collections import namedtuple
  40 import io
  41 import unittest
  42
  43 # trace file entries are lists of these.
  44 Hazards = namedtuple("Hazards", ["action", "target", "ident", "offs", "elwid"])
  45
  46 # key: readport, writeport (per clock cycle)
  47 HazardProfiles = {
  48     "GPR": (4, 1),  # GPR allows 4 reads 1 write possible in 1 cycle...
  49     "FPR": (3, 1),
  50     "CR" : (2, 1),  # Condition Register (32-bit)
  51     "CRf": (3, 3),  # Condition Register Fields (4-bit each)
  52     "XER": (1, 1),
  53     "MSR": (1, 1),
  54     "FPSCR": (1, 1),
  55     "PC": (1, 1),    # Program Counter
  56     "SPRf" : (4, 3), # Fast SPR (actually STATE regfile in TestIssuer)
  57     "SPRs" : (1, 1), # Slow SPR
  58 }
  59
  60
  61 def read_file(fname):
  62     """reads a trace file in the format "[r:FILE:regnum:offset:width]* # insn"
  63     """
  64     is_file = hasattr(fname, "write")
  65     if not is_file:
  66         fname = open(fname, "r")
  67     res = []
  68     for line in fname.readlines():
  69         (specs, insn) = map(str.strip, line.strip().split("#"))
  70         line = [insn]
  71         for spec in specs.split(" "):
  72             line.append(Hazards._make(spec.split(":")))
  73         res.append(line)
  74     if not is_file:
  75         fname.close()
  76     return res
  77
  78
  79 class RegisterWrite:
  80     """
  81     RegisterWrite: contains the set of Read-after-Write Hazards.
  82     Anything in this set must be a STALL at Decode phase because the
  83     answer has still not popped out the end of a pipeline
  84     """
  85     def __init__(self):
  86         self.storage = set()
  87
  88     def expect_write(self, regs):
  89         return self.storage.update(regs)
  90
  91     def write_expected(self, regs):
  92         return (len(self.storage.intersection(regs)) != 0)
  93
  94     def retire_write(self, regs):
  95         return self.storage.difference_update(regs)
  96
  97
  98 class Execute:
  99     """
 100     Execute Pipeline: keeps a countdown-sorted list of instructions
 101     to expect at a future cycle (tick).  Anything at zero is processed
 102     by assuming it is completed, and wishes to write to the regfile.
 103     However there are only a limited number of regfile write ports,
 104     so they must be handled a few at a time.  under these circumstances
 105     STALL condition is returned, and the "processor" must *NOT* tick().
 106     """
 107     def __init__(self, cpu):
 108         self.stages = []
 109         self.cpu = cpu
 110
 111     def add_stage(self, cycles_away, stage):
 112         while cycles_away > len(self.stages):
 113             self.stages.append([])
 114         self.stages[cycles_away].append(stage)
 115
 116     def add_instruction(self, insn, writeregs):
 117         self.add_stage(2, {'insn': insn, 'writes': writeregs})
 118
 119     def tick(self):
 120         self.stages.pop(0) # tick drops anything at time "zero"
 121
 122     def process_instructions(self, stall):
 123         instructions = self.stages[0] # get list of instructions
 124         to_write = set()              # need to know total writes
 125         for instruction in instructions:
 126             to_write.update(instruction['writes'])
 127         # see if all writes can be done, otherwise stall
 128         writes_possible = self.cpu.writes_possible(to_write)
 129         if writes_possible != to_write:
 130             stall = True
 131         # retire the writes that are possible in this cycle (regfile writes)
 132         self.cpu.regs.retire_write(writes_possible)
 133         # and now go through the instructions, removing those regs written
 134         for instruction in instructions:
 135             instruction['writes'].difference_update(writes_possible)
 136         return stall
 137
 138
 139 class Fetch:
 140     """
 141     Fetch: reads the next log-entry and puts it into the queue.
 142     """
 143     def __init__(self, cpu):
 144         self.stages = [None] # only ever going to be 1 long but hey
 145         self.cpu = cpu
 146
 147     def tick(self):
 148         self.stages[0] = None
 149
 150     def process_instructions(self, stall):
 151         if stall: return stall
 152         insn = self.stages[0] # get current instruction
 153         if insn is not None:
 154             self.cpu.decode.add_instructions(insn) # pass on instruction
 155         # read from log file, write into self.stages[0]
 156         # XXX TODO
 157         return stall
 158
 159
 160 class Decode:
 161     """
 162     Decode: performs a "decode" of the instruction. identifies and records
 163     read/write regs. the reads/writes possible should likely not all be here,
 164     perhaps split across "Issue"?
 165     """
 166     def __init__(self, cpu):
 167         self.stages = [None] # only ever going to be 1 long but hey
 168         self.cpu = cpu
 169
 170     def add_instruction(self, insn):
 171         # get the read and write regs
 172         writeregs = get_input_regs(insn)
 173         readregs = get_output_regs(insn)
 174         assert self.stages[0] is None # must be empty (tick or stall)
 175         self.stages[0] = (insn, writeregs, readregs)
 176
 177     def tick(self):
 178         self.stages[0] = None
 179
 180     def process_instructions(self, stall):
 181         if stall: return stall
 182         # get current instruction
 183         insn, writeregs, readregs = self.stages[0]
 184         # check that the readregs are all available
 185         reads_possible = self.cpu.reads_possible(readregs)
 186         stall = reads_possible != readregs
 187         # perform the "reads" that are possible in this cycle
 188         readregs.difference_update(reads_possible)
 189         # and "Reserves" the writes
 190         self.cpu.expect_write(writeregs)
 191         # now pass the instruction on to Issue
 192         self.cpu.issue.add_instruction(insn, writeregs)
 193         return stall
 194
 195
 196 class Issue:
 197     """
 198     Issue phase: if not stalled will place the instruction into execute.
 199     TODO: move the reading and writing of regs here.
 200     """
 201     def __init__(self, cpu):
 202         self.stages = [None] # only ever going to be 1 long but hey
 203         self.cpu = cpu
 204
 205     def add_instruction(self, insn, writeregs):
 206         # get the read and write regs
 207         assert self.stages[0] is None # must be empty (tick or stall)
 208         self.stages[0] = (insn, writeregs)
 209
 210     def tick(self):
 211         self.stages[0] = None
 212
 213     def process_instructions(self, stall):
 214         if stall: return stall
 215         self.cpu.execute.add_instructions(self.stages[0])
 216         return stall
 217
 218
 219 class CPU:
 220     """
 221     CPU: contains Fetch, Decode, Issue and Execute pipelines, and regs.
 222     Reads "instructions" from a file, starts putting them into a pipeline,
 223     and monitors hazards.  first version looks only for register hazards.
 224     """
 225     def __init__(self):
 226         self.regs = RegisterWrite()
 227         self.fetch = Fetch(self)
 228         self.decode = Decode(self)
 229         self.issue = Issue(self)
 230         self.exe = Execute(self)
 231         self.stall = False
 232
 233     def reads_possible(self, regs):
 234         # TODO: subdivide this down by GPR FPR CR-field.
 235         # currently assumes total of 3 regs are readable at one time
 236         possible = set()
 237         r = regs.copy()
 238         while len(possible) < 3 and len(r) > 0:
 239             possible.add(r.pop())
 240         return possible
 241
 242     def writess_possible(self, regs):
 243         # TODO: subdivide this down by GPR FPR CR-field.
 244         # currently assumes total of 1 reg is possible regardless of what it is
 245         possible = set()
 246         r = regs.copy()
 247         while len(possible) < 1 and len(r) > 0:
 248             possible.add(r.pop())
 249         return possible
 250
 251     def process_instructions(self):
 252         stall = self.stall
 253         stall = self.fetch.process_instructions(stall)
 254         stall = self.decode.process_instructions(stall)
 255         stall = self.issue.process_instructions(stall)
 256         stall = self.exe.process_instructions(stall)
 257         self.stall = stall
 258         if not stall:
 259             self.fetch.tick()
 260             self.decode.tick()
 261             self.issue.tick()
 262             self.exe.tick()
 263
 264
 265 class TestTrace(unittest.TestCase):
 266
 267     def test_trace(self): # TODO, assert this is valid
 268         lines = (
 269             "r:GPR:0:0:64 w:GPR:1:0:64              # addi 1, 0, 0x0010",
 270             "r:GPR:0:0:64 w:GPR:2:0:64              # addi 2, 0, 0x1234",
 271             "r:GPR:1:0:64 r:GPR:2:0:64              # stw 2, 0(1)",
 272             "r:GPR:1:0:64 w:GPR:3:0:64              # lwz 3, 0(1)",
 273             "r:GPR:3:0:64 r:GPR:2:0:64 w:GPR:1:0:64 # add 1, 3, 2",
 274             "r:GPR:0:0:64 w:GPR:3:0:64              # addi 3, 0, 0x1234",
 275             "r:GPR:0:0:64 w:GPR:2:0:64              # addi 2, 0, 0x4321",
 276             "r:GPR:3:0:64 r:GPR:2:0:64 w:GPR:1:0:64 # add  1, 3, 2",
 277         )
 278         f = io.StringIO("\n".join(lines))
 279         lines = read_file(f)
 280         for trace in lines:
 281             print(trace)
 282
 283
 284 if __name__ == "__main__":
 285     unittest.main()