| # Copyright lowRISC contributors. |
| # Licensed under the Apache License, Version 2.0, see LICENSE for details. |
| # SPDX-License-Identifier: Apache-2.0 |
| |
| import random |
| from typing import Dict, List, Optional, Tuple |
| |
| from shared.insn_yaml import Insn |
| from shared.operand import ImmOperandType, RegOperandType, OperandType |
| |
| from .program import ProgInsn |
| |
| |
| class KnownMem: |
| '''A representation of what memory/CSRs have architectural values''' |
| def __init__(self, top_addr: int): |
| assert top_addr > 0 |
| |
| self.top_addr = top_addr |
| # A list of pairs of addresses. If the pair (lo, hi) is in the list |
| # then each byte in the address range {lo..hi - 1} has a known value. |
| self.known_ranges = [] # type: List[Tuple[int, int]] |
| |
| def touch_range(self, base: int, width: int) -> None: |
| '''Mark {base .. base+width} as known''' |
| assert 0 <= width |
| assert 0 <= base <= self.top_addr - width |
| for off in range(width): |
| self.touch_idx(base + off) |
| |
| def touch_idx(self, idx: int) -> None: |
| '''Mark idx as known''' |
| assert 0 <= idx < self.top_addr |
| |
| # Find the index of the last range that starts below us, if there is |
| # one, and the index of the first range that starts above us, if there |
| # is one. |
| last_idx_below = None |
| first_idx_above = None |
| for idx, (lo, hi) in enumerate(self.known_ranges): |
| if lo <= idx: |
| last_idx_below = idx |
| continue |
| |
| first_idx_above = idx |
| break |
| |
| # Are we below all other ranges? |
| if last_idx_below is None: |
| # Are we one address below the next range above? In which case, we |
| # need to shuffle it back one. |
| if first_idx_above is not None: |
| lo, hi = self.known_ranges[first_idx_above] |
| assert idx < lo |
| if idx == lo - 1: |
| self.known_ranges[first_idx_above] = (lo - 1, hi) |
| return |
| |
| # Otherwise, we're disjoint. Add a one-element range at the start. |
| self.known_ranges = [(idx, idx + 1)] + self.known_ranges |
| return |
| |
| # If not, are we inside a range? In that case, there's nothing to do. |
| left_lo, left_hi = self.known_ranges[last_idx_below] |
| if idx < left_hi: |
| return |
| |
| left = (self.known_ranges[:last_idx_below - 1] |
| if last_idx_below > 0 else []) |
| |
| # Are we just above it? |
| if idx == left_hi: |
| # If there is no range above, we can just extend the last range by one. |
| if first_idx_above is None: |
| self.known_ranges = left + [(left_lo, left_hi + 1)] |
| return |
| |
| # Otherwise, does this new address glue two ranges together? |
| assert first_idx_above == last_idx_below + 1 |
| right_lo, right_hi = self.known_ranges[first_idx_above] |
| assert idx < right_lo |
| |
| if idx == right_lo - 1: |
| self.known_ranges = (left + [(left_lo, right_hi)] + |
| self.known_ranges[first_idx_above + 1:]) |
| return |
| |
| # Otherwise, we still extend the range by one (but have to put the |
| # right hand list back too). |
| self.known_ranges = (left + [(left_lo, left_hi + 1)] + |
| self.known_ranges[first_idx_above:]) |
| return |
| |
| # We are miles above the left range. If there is no range above, we can |
| # just append a new 1-element range. |
| left_inc = self.known_ranges[:first_idx_above] |
| if first_idx_above is None: |
| self.known_ranges.append((idx, idx + 1)) |
| return |
| |
| # Otherwise, are we just below the next range? |
| assert first_idx_above == last_idx_below + 1 |
| right_lo, right_hi = self.known_ranges[first_idx_above] |
| assert idx < right_lo |
| |
| if idx == right_lo - 1: |
| self.known_ranges = (left_inc + [(right_lo - 1, right_hi)] + |
| self.known_ranges[first_idx_above + 1:]) |
| return |
| |
| # If not, we just insert a 1-element range in between |
| self.known_ranges = (left_inc + [(idx, idx + 1)] + |
| self.known_ranges[first_idx_above:]) |
| return |
| |
| def pick_lsu_target(self, |
| loads_value: bool, |
| min_addr: int, |
| max_addr: int) -> Optional[int]: |
| '''Try to pick an address in range [min_addr, max_addr] |
| |
| If loads_value is true, the memory needs a known value at that |
| address. |
| |
| ''' |
| assert min_addr <= max_addr |
| |
| if min_addr >= self.top_addr or max_addr < 0: |
| return None |
| |
| min_addr = max(0, min_addr) |
| max_addr = min(max_addr, self.top_addr - 1) |
| |
| if not loads_value: |
| # If we're not loading something, we can pick any old address in |
| # the range. |
| return int(random.randrange(min_addr, max_addr + 1)) |
| |
| # If we are loading something, we need to be more careful. Collect up |
| # the known ranges that have an intersection with the range in |
| # question. Note that the (lo, hi) pairs are exclusive, but |
| # min_addr/max_addr is inclusive, so we need a +1 every so often. |
| ranges = [] |
| weights = [] |
| for lo, hi in self.known_ranges: |
| lo = max(lo, min_addr) |
| hi = min(hi, max_addr + 1) |
| if lo >= hi: |
| continue |
| ranges.append((lo, hi)) |
| weights.append(hi - lo) |
| |
| # If there are no ranges that intersect, give up. |
| if not ranges: |
| return None |
| |
| # Otherwise, pick a range with weight equal to the number of elements |
| # in the range (so we'll get a uniform sampling on valid addresses) and |
| # then pick from the range. |
| lo, hi = random.choices(ranges, weights=weights)[0] |
| return random.randrange(lo, hi) |
| |
| |
| class Model: |
| '''An abstract model of the processor and memories |
| |
| This definitely doesn't try to act as a simulator. Rather, it tracks what |
| registers and locations in memory are guaranteed have defined values after |
| following the instruction stream to this point. |
| |
| ''' |
| def __init__(self, dmem_size: int, reset_addr: int) -> None: |
| self.dmem_size = dmem_size |
| |
| # Known values for registers. This is a dictionary mapping register |
| # type to a dictionary of known registers of that type. The register |
| # type is a string matching the formats in RegOperandType.TYPE_FMTS. |
| # The value for a type is another dictionary, mapping register index to |
| # an Optional[int]. If the value is a number, the register value is |
| # known to currently equal that number. If it is None, the register |
| # value is unknown (but the register does have an architectural value). |
| self._known_regs = {} # type: Dict[str, Dict[int, Optional[int]]] |
| |
| # Set x0 (the zeros register) |
| self._known_regs['gpr'] = {0: 0} |
| |
| # Known values for memory, keyed by memory type ('dmem', 'csr', 'wsr'). |
| self._known_mem = { |
| 'dmem': KnownMem(dmem_size), |
| # TODO: How many CSRs/WSRs? Is that written down somewhere we can |
| # extract? |
| 'csr': KnownMem(4096), |
| 'wsr': KnownMem(4096) |
| } |
| |
| # The current PC (the address of the next instruction that needs |
| # generating) |
| self.pc = reset_addr |
| |
| def write_reg(self, reg_type: str, idx: int, value: Optional[int]) -> None: |
| '''Mark a register as having an architectural value |
| |
| If value is not None, it is the actual value that the register has. |
| Writes to the zeros register x0 are ignored. |
| |
| ''' |
| if reg_type == 'gpr' and idx == 0: |
| return |
| |
| self._known_regs.setdefault(reg_type, {})[idx] = value |
| |
| def get_reg(self, reg_type: str, idx: int) -> Optional[int]: |
| '''Get a register value, if known.''' |
| return self._known_regs.setdefault(reg_type, {}).get(idx) |
| |
| def touch_mem(self, mem_type: str, base: int, width: int) -> None: |
| '''Mark {base .. base+width} as known for given memory type''' |
| assert mem_type in self._known_mem |
| self._known_mem[mem_type].touch_range(base, width) |
| |
| def pick_operand_value(self, op_type: OperandType) -> Optional[int]: |
| '''Pick a random value for an operand |
| |
| The result will always be non-negative: if the operand is a signed |
| immediate, this is encoded as 2s complement. |
| |
| ''' |
| if isinstance(op_type, RegOperandType): |
| return self.pick_reg_operand_value(op_type) |
| |
| if isinstance(op_type, ImmOperandType): |
| rng = op_type.get_range() |
| if rng is None: |
| # If we don't know the width, the only immediate that we *know* |
| # is valid is 0. |
| return 0 |
| |
| lo, hi = rng |
| value = random.randrange(lo, hi + 1) |
| return op_type.encode_val(value) |
| |
| raise NotImplementedError('Unknown operand type in ' |
| 'Model.pick_operand_value') |
| |
| def pick_reg_operand_value(self, op_type: RegOperandType) -> Optional[int]: |
| '''Pick a random value for a register operand |
| |
| Returns None if there's no valid value possible.''' |
| if op_type.is_src(): |
| # This operand needs an architectural value. Pick a register |
| # from the indices in _known_regs[op_type.reg_type]. |
| known_regs = self._known_regs.get(op_type.reg_type) |
| if not known_regs: |
| return None |
| |
| return random.choice(list(known_regs)) |
| |
| # This operand isn't treated as a source. Pick any register! |
| assert op_type.width is not None |
| return random.getrandbits(op_type.width) |
| |
| def regs_with_known_vals(self, reg_type: str) -> List[Tuple[int, int]]: |
| '''Find registers whose values are known |
| |
| Returns a list of pairs (idx, value) where idx is the register index |
| and value is its value. |
| |
| ''' |
| ret = [] |
| known_regs = self._known_regs.get(reg_type) |
| if known_regs is not None: |
| for reg_idx, reg_val in known_regs.items(): |
| if reg_val is not None: |
| ret.append((reg_idx, reg_val)) |
| return ret |
| |
| def pick_lsu_target(self, |
| mem_type: str, |
| loads_value: bool, |
| known_regs: Dict[str, List[Tuple[int, int]]], |
| imm_min: int, |
| imm_max: int, |
| byte_width: int) -> Optional[Tuple[int, |
| int, |
| Dict[str, int]]]: |
| '''Try to pick an address for an LSU operation. |
| |
| mem_type is the type of memory (which must a key of self._known_mem). |
| If loads_value, this address needs to have an architecturally defined |
| value. |
| |
| known_regs is a map from operand name to a list of pairs (idx, value) |
| with index and known value for this register operand. Any immediate |
| operand will have a value in the range [imm_min, imm_max]. byte_width |
| is the number of contiguous addresses that the LSU operation touches. |
| |
| Returns None if we can't find an address. Otherwise, returns a tuple |
| (addr, imm_val, reg_vals) where addr is the target address, imm_val is |
| the value of any immediate operand and reg_vals is a map from operand |
| name to the index picked for that register operand. |
| |
| ''' |
| assert mem_type in self._known_mem |
| assert imm_min <= imm_max |
| |
| # A "general" solution to this needs constraint solving, but we expect |
| # [imm_min, imm_max] to cover most of the address space most of the |
| # time. So we'll do something much simpler: pick a value for each |
| # register, then pick a target address that can be reached from the |
| # "sum so far" plus the range of the immediate. |
| reg_indices = {} |
| reg_sum = 0 |
| |
| for name, indices in known_regs.items(): |
| # If there are no known indices for this operand, give up now. |
| if not indices: |
| return None |
| |
| # Otherwise, pick an index and value |
| idx, value = random.choice(indices) |
| reg_sum += value |
| reg_indices[name] = idx |
| |
| # TODO: This is a bit pessimistic, because it doesn't allow things like |
| # the register sum coming to -1 (module 2^32) and adding an |
| # immediate 1 to get a valid address. |
| min_addr = reg_sum + imm_min |
| max_addr = reg_sum + imm_max |
| known_mem = self._known_mem[mem_type] |
| |
| addr = known_mem.pick_lsu_target(loads_value, min_addr, max_addr) |
| |
| # If there was no address we could use, give up. |
| if addr is None: |
| return None |
| |
| return (addr, addr - reg_sum, reg_indices) |
| |
| def update_for_lui(self, insn: Insn, op_vals: List[int]) -> None: |
| '''Update model state after a LUI |
| |
| A lui instruction looks like "lui x1, 80000" or similar. This operation |
| is easy to understand, so we can actually update the model registers |
| appropriately. |
| |
| ''' |
| assert insn.mnemonic == 'lui' |
| assert len(insn.operands) == len(op_vals) |
| |
| exp_shape = (len(insn.operands) == 2 and |
| isinstance(insn.operands[0].op_type, RegOperandType) and |
| insn.operands[0].op_type.reg_type == 'gpr' and |
| insn.operands[0].op_type.is_dest() and |
| isinstance(insn.operands[1].op_type, ImmOperandType) and |
| not insn.operands[1].op_type.signed) |
| if not exp_shape: |
| raise RuntimeError('LUI instruction read from insns.yml is ' |
| 'not the shape expected by ' |
| 'Model.update_for_lui.') |
| |
| assert op_vals[1] >= 0 |
| self.write_reg('gpr', op_vals[0], op_vals[1]) |
| |
| def update_for_addi(self, insn: Insn, op_vals: List[int]) -> None: |
| '''Update model state after an ADDI |
| |
| If the source register happens to have a known value, we can do the |
| addition and store the known result. |
| |
| ''' |
| assert insn.mnemonic == 'addi' |
| assert len(insn.operands) == len(op_vals) |
| |
| exp_shape = (len(insn.operands) == 3 and |
| isinstance(insn.operands[0].op_type, RegOperandType) and |
| insn.operands[0].op_type.reg_type == 'gpr' and |
| insn.operands[0].op_type.is_dest() and |
| isinstance(insn.operands[1].op_type, RegOperandType) and |
| insn.operands[1].op_type.reg_type == 'gpr' and |
| not insn.operands[1].op_type.is_dest() and |
| isinstance(insn.operands[2].op_type, ImmOperandType) and |
| insn.operands[2].op_type.signed) |
| if not exp_shape: |
| raise RuntimeError('ADDI instruction read from insns.yml is ' |
| 'not the shape expected by ' |
| 'Model.update_for_addi.') |
| |
| src_val = self.get_reg('gpr', op_vals[1]) |
| if src_val is None: |
| return |
| |
| value = src_val + op_vals[2] |
| if value < 0: |
| value += 1 << 32 |
| assert value >= 0 |
| if value >> 32: |
| value -= 1 << 32 |
| assert (value >> 32) == 0 |
| |
| self.write_reg('gpr', op_vals[0], value) |
| |
| def update_for_insn(self, prog_insn: ProgInsn) -> None: |
| # Mark any destination operand as having an architectural value |
| insn = prog_insn.insn |
| assert len(insn.operands) == len(prog_insn.operands) |
| for operand, op_val in zip(insn.operands, prog_insn.operands): |
| op_type = operand.op_type |
| if isinstance(op_type, RegOperandType): |
| if op_type.is_dest: |
| self.write_reg(op_type.reg_type, op_val, None) |
| |
| # If this is a sufficiently simple operation that we understand the |
| # result, actually set the destination register with a value. |
| # Currently, we just support lui and addi |
| if insn.mnemonic == 'lui': |
| self.update_for_lui(insn, prog_insn.operands) |
| elif insn.mnemonic == 'addi': |
| self.update_for_addi(insn, prog_insn.operands) |
| |
| # If this is an LSU operation, we've either loaded a value (in which |
| # case, the memory hopefully had a value already) or we've stored |
| # something. In either case, we mark the memory as having a value now. |
| if prog_insn.lsu_info is not None: |
| assert insn.lsu is not None |
| mem_type, addr = prog_insn.lsu_info |
| self.touch_mem(mem_type, addr, insn.lsu.idx_width) |
