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