[otbn,dv] Add support for "giant loops" to RIG
These are loops that have an end address above the top of IMEM.
They'll never actually complete, so we generate a sequence of
instructions that *does* complete to go inside them.
Signed-off-by: Rupert Swarbrick <rswarbrick@lowrisc.org>
diff --git a/hw/ip/otbn/dv/rig/rig/configs/base.yml b/hw/ip/otbn/dv/rig/rig/configs/base.yml
index a42c545..533bc3c 100644
--- a/hw/ip/otbn/dv/rig/rig/configs/base.yml
+++ b/hw/ip/otbn/dv/rig/rig/configs/base.yml
@@ -13,4 +13,5 @@
# Generators that end the program
ECall: 1
BadInsn: 1
+ BadGiantLoop: 1
BadZeroLoop: 1
diff --git a/hw/ip/otbn/dv/rig/rig/gens/bad_giant_loop.py b/hw/ip/otbn/dv/rig/rig/gens/bad_giant_loop.py
new file mode 100644
index 0000000..c8cdf58
--- /dev/null
+++ b/hw/ip/otbn/dv/rig/rig/gens/bad_giant_loop.py
@@ -0,0 +1,103 @@
+# 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 Optional
+
+from shared.insn_yaml import InsnsFile
+
+from .loop import Loop
+from ..config import Config
+from ..model import Model
+from ..program import ProgInsn, Program
+from ..snippet import LoopSnippet
+from ..snippet_gen import GenCont, GenRet
+
+
+class BadGiantLoop(Loop):
+ '''A generator for loops with end addresses that don't lie in memory
+
+ This generator has "ends_program = True", but doesn't end the program in
+ itself. Instead, it sets up a loop with an endpoint that doesn't fit in
+ memory (so the loop body will never actually terminate) and then generates
+ a sequence for the rest of the program, to go inside the body. OTBN will
+ complete its operation without popping the loop off the stack.
+
+ '''
+
+ ends_program = True
+
+ def __init__(self, cfg: Config, insns_file: InsnsFile) -> None:
+ super().__init__(cfg, insns_file)
+
+ def gen(self,
+ cont: GenCont,
+ model: Model,
+ program: Program) -> Optional[GenRet]:
+
+ # We need space for at least 2 instructions here: one for the loop head
+ # instruction and one for the minimal body (which might contain an
+ # ECALL, for example)
+ space_here = program.get_insn_space_at(model.pc)
+ if space_here < 2:
+ return None
+
+ # Similarly, the smallest possible loop will take 2 instructions
+ if program.space < 2:
+ return None
+
+ # And we don't want to overflow the loop stack
+ if model.loop_depth == Model.max_loop_depth:
+ return None
+
+ insn = self._pick_loop_insn()
+ iters_op_type = insn.operands[0].op_type
+ bodysize_op_type = insn.operands[1].op_type
+
+ bodysize_range = bodysize_op_type.get_op_val_range(model.pc)
+ assert bodysize_range is not None
+
+ bodysize_min, bodysize_max = bodysize_range
+
+ # Adjust bodysize_min to make sure we pick an end address that's larger
+ # than IMEM (and check that we can represent the result).
+ bodysize_min = max(bodysize_min, (program.imem_size - model.pc) // 4)
+ if bodysize_max < bodysize_min:
+ return None
+
+ # Pick bodysize, preferring the endpoints
+ x = random.random()
+ if x < 0.4:
+ bodysize = bodysize_min
+ elif x < 0.8:
+ bodysize = bodysize_max
+ else:
+ bodysize = random.randint(bodysize_min, bodysize_max)
+
+ enc_bodysize = bodysize_op_type.op_val_to_enc_val(bodysize, model.pc)
+ assert enc_bodysize is not None
+
+ # Now pick the number of iterations (not that the number actually
+ # matters)
+ iters = self._pick_iterations(iters_op_type, bodysize, model)
+ if iters is None:
+ return None
+
+ iters_opval, num_iters = iters
+ hd_addr = model.pc
+ hd_insn = ProgInsn(insn, [iters_opval, enc_bodysize], None)
+
+ body_model = self._setup_body(hd_insn, model, program)
+
+ # At this point, all the "loop related work" is done: we've entered the
+ # loop body (from which we can never leave). Now call the continuation
+ # with a flag to say that we'd like the generation to complete.
+ body_snippet, end_model = cont(body_model, program, True)
+
+ # Because we passed end=True to cont, the snippet from the continuation
+ # is not None.
+ assert body_snippet is not None
+
+ loop_snippet = LoopSnippet(hd_addr, hd_insn, body_snippet)
+ return (loop_snippet, True, end_model)
diff --git a/hw/ip/otbn/dv/rig/rig/gens/loop.py b/hw/ip/otbn/dv/rig/rig/gens/loop.py
index c4d066d..4382069 100644
--- a/hw/ip/otbn/dv/rig/rig/gens/loop.py
+++ b/hw/ip/otbn/dv/rig/rig/gens/loop.py
@@ -415,6 +415,21 @@
is_loopi = random.random() < self.loopi_prob
return self.loopi if is_loopi else self.loop
+ def _setup_body(self,
+ hd_insn: ProgInsn,
+ model: Model,
+ program: Program) -> Model:
+ '''Set up a Model for use in body; insert hd_insn into program'''
+ body_model = model.copy()
+ body_model.update_for_insn(hd_insn)
+ body_model.pc += 4
+ body_model.loop_depth += 1
+ assert body_model.loop_depth <= Model.max_loop_depth
+
+ program.add_insns(model.pc, [hd_insn])
+
+ return body_model
+
def _gen_pieces(self,
cont: GenCont,
model: Model,
@@ -465,13 +480,7 @@
hd_insn = ProgInsn(insn, [iter_opval, enc_bodysize], None)
body_program = program.copy()
- body_program.add_insns(model.pc, [hd_insn])
-
- body_model = model.copy()
- body_model.update_for_insn(hd_insn)
- body_model.pc += 4
- body_model.loop_depth += 1
- assert body_model.loop_depth <= Model.max_loop_depth
+ body_model = self._setup_body(hd_insn, model, body_program)
# Constrain fuel in body_model: subtract one (for the first instruction
# after the loop) and then divide by the number of iterations. When we
diff --git a/hw/ip/otbn/dv/rig/rig/snippet_gen.py b/hw/ip/otbn/dv/rig/rig/snippet_gen.py
index 754e8a2..0089106 100644
--- a/hw/ip/otbn/dv/rig/rig/snippet_gen.py
+++ b/hw/ip/otbn/dv/rig/rig/snippet_gen.py
@@ -19,10 +19,10 @@
# The return type of a single generator. This is a tuple (snippet, done,
# model). snippet is a generated snippet. done is true if the processor has
-# just executed an ECALL instruction. model is a Model object representing the
-# state of the processor after executing the code in the snippet(s). The PC of
-# the model will be the next instruction to be executed unless done is true, in
-# which case it still points at the ECALL.
+# just executed an instruction that causes it to stop. model is a Model object
+# representing the state of the processor after executing the code in the
+# snippet(s). The PC of the model will be the next instruction to be executed
+# unless done is true, in which case it still points at the final instruction.
GenRet = Tuple[Snippet, bool, Model]
# An "internal" return type for generators that never cause termination.
@@ -35,7 +35,8 @@
# A continuation type that allows a generator to recursively generate some more
# stuff. If the boolean argument is true, the continuation will try to generate
-# a snippet that causes OTBN to stop.
+# a snippet that causes OTBN to stop. In this case, the Snippet term in the
+# GensRet will not be None.
GenCont = Callable[[Model, Program, bool], GensRet]
diff --git a/hw/ip/otbn/dv/rig/rig/snippet_gens.py b/hw/ip/otbn/dv/rig/rig/snippet_gens.py
index 8639ceb..fb04799 100644
--- a/hw/ip/otbn/dv/rig/rig/snippet_gens.py
+++ b/hw/ip/otbn/dv/rig/rig/snippet_gens.py
@@ -21,6 +21,7 @@
from .gens.straight_line_insn import StraightLineInsn
from .gens.bad_insn import BadInsn
+from .gens.bad_giant_loop import BadGiantLoop
from .gens.bad_zero_loop import BadZeroLoop
@@ -35,6 +36,7 @@
ECall,
BadInsn,
+ BadGiantLoop,
BadZeroLoop
]
@@ -216,6 +218,8 @@
'''
snippets, next_model = self._gens(model, program, end)
+ # If end was True, there must be at least one instruction
+ assert snippets or not end
snippet = Snippet.merge_list(snippets) if snippets else None
return (snippet, next_model)
