| # 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, Sequence, Tuple |
| |
| from shared.insn_yaml import InsnsFile |
| from shared.operand import ImmOperandType, RegOperandType |
| |
| from .jump import Jump |
| from ..program import ProgInsn, Program |
| from ..model import Model |
| from ..snippet import BranchSnippet, ProgSnippet |
| from ..snippet_gen import GenCont, GenRet, SnippetGen |
| |
| |
| class Branch(SnippetGen): |
| '''A generator that makes a snippet with a BEQ or BNE branch''' |
| def __init__(self, insns_file: InsnsFile) -> None: |
| self.jump_gen = Jump(insns_file) |
| self.beq = self._get_named_insn(insns_file, 'beq') |
| self.bne = self._get_named_insn(insns_file, 'bne') |
| |
| # beq and bne expect operands: grs1, grs2, offset |
| for insn in [self.beq, self.bne]: |
| if not (len(insn.operands) == 3 and |
| isinstance(insn.operands[0].op_type, RegOperandType) and |
| insn.operands[0].op_type.reg_type == 'gpr' and |
| not 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): |
| raise RuntimeError('{} instruction from instructions file is not ' |
| 'the shape expected by the Branch generator.' |
| .format(insn.mnemonic)) |
| |
| _FloatRng = Tuple[float, float] |
| _WeightedFloatRng = Tuple[float, _FloatRng] |
| |
| @staticmethod |
| def pick_from_weighted_ranges(r: Sequence[_WeightedFloatRng]) -> float: |
| ff0, ff1 = random.choices([rng for _, rng in r], |
| weights=[w for w, _ in r])[0] |
| return random.uniform(ff0, ff1) |
| |
| def _pick_tgt_addr(self, |
| pc: int, |
| off_min: int, |
| off_max: int, |
| program: Program) -> Optional[int]: |
| '''Pick the target address for a branch''' |
| # Make sure we can cover the case where we branch conditionally to |
| # PC+4, which is probably quite unlikely otherwise, by giving at 1% |
| # chance. |
| # |
| # We'll need at least 4 instructions' space for a proper branch: the |
| # branch instruction, the fall-through instruction, the branch target |
| # (which will jump back if necessary), and an eventual ECALL) |
| if program.get_insn_space_left() < 4: |
| fall_thru = True |
| else: |
| fall_thru = random.random() < 0.01 |
| |
| return (pc + 4 if fall_thru else |
| program.pick_branch_target(pc, 1, off_min, off_max)) |
| |
| def gen(self, |
| cont: GenCont, |
| model: Model, |
| program: Program) -> Optional[GenRet]: |
| |
| if model.fuel <= 1: |
| # The shortest possible branch sequence (branch to PC + 4) takes an |
| # instruction and needs at least one instruction afterwards for the |
| # ECALL, so don't generate anything if fuel is less than 2. |
| return None |
| |
| # Return None if this is the last instruction in the current gap |
| # because we need to either jump or do an ECALL to avoid getting stuck |
| # (just like the StraightLineInsn generator) |
| if program.get_insn_space_at(model.pc) <= 1: |
| return None |
| |
| # Decide whether to generate BEQ or BNE. In the future, we'll load |
| # this weighting from somewhere else. |
| beq_weight = 1.0 |
| bne_weight = 1.0 |
| sum_weights = beq_weight + bne_weight |
| is_beq = random.random() < beq_weight / sum_weights |
| |
| insn = self.beq if is_beq else self.bne |
| grs1_op, grs2_op, off_op = insn.operands |
| |
| assert isinstance(off_op.op_type, ImmOperandType) |
| |
| # Calculate the range of target addresses we can encode (this includes |
| # any PC-relative adjustment) |
| off_rng = off_op.op_type.get_op_val_range(model.pc) |
| assert off_rng is not None |
| off_min, off_max = off_rng |
| |
| # Pick the source GPRs that we're comparing. |
| assert isinstance(grs1_op.op_type, RegOperandType) |
| assert isinstance(grs2_op.op_type, RegOperandType) |
| grs1 = model.pick_reg_operand_value(grs1_op.op_type) |
| grs2 = model.pick_reg_operand_value(grs2_op.op_type) |
| if grs1 is None or grs2 is None: |
| return None |
| |
| tgt_addr = self._pick_tgt_addr(model.pc, off_min, off_max, program) |
| if tgt_addr is None: |
| return None |
| |
| assert off_min <= tgt_addr <= off_max |
| |
| off_enc = off_op.op_type.op_val_to_enc_val(tgt_addr, model.pc) |
| assert off_enc is not None |
| |
| branch_insn = ProgInsn(insn, [grs1, grs2, off_enc], None) |
| |
| if tgt_addr == model.pc + 4: |
| # If tgt_addr equals model.pc + 4, this actually behaves like a |
| # straight-line instruction! Add the branch instruction, update the |
| # model, and return. |
| psnip = ProgSnippet(model.pc, [branch_insn]) |
| psnip.insert_into_program(program) |
| model.update_for_insn(branch_insn) |
| model.pc += 4 |
| return (psnip, model) |
| |
| # Decide how much of our remaining fuel to give the code below the |
| # branch. Each side gets the same amount because only one side appears |
| # in the instruction stream. |
| fuel_frac_ranges = [(1, (0, 0.1)), |
| (10, (0.1, 0.5)), |
| (1, (0.5, 1.0))] |
| fuel_frac = self.pick_from_weighted_ranges(fuel_frac_ranges) |
| assert 0 <= fuel_frac <= 1 |
| branch_fuel = max(1, int(0.5 + fuel_frac * model.fuel)) |
| |
| # Similarly, decide how much of our remaining space to give the code |
| # below the branch. Unlike with the fuel, we halve the result for each |
| # side (since each side of the branch consumes instruction space) |
| space_frac_ranges = fuel_frac_ranges |
| space_frac = self.pick_from_weighted_ranges(space_frac_ranges) |
| assert 0 <= space_frac <= 1 |
| # Subtract 2: one for the branch instruction and one for an eventual |
| # ECALL. We checked earlier we had at least 4 instructions' space left, |
| # so there should always be at least 2 instructions' space left |
| # afterwards. |
| max_space_for_branches = program.get_insn_space_left() - 2 |
| assert max_space_for_branches >= 2 |
| branch_space = max(1, int(space_frac * (max_space_for_branches / 2))) |
| assert 2 * branch_space <= max_space_for_branches |
| |
| # Make an updated copy of program that includes the branch instruction. |
| # Similarly, take a copy of the model and update it as if we've fallen |
| # through the branch instruction. Note that we can't just modify |
| # program or model here because generation might fail. |
| # |
| # Insert a bogus instruction at tgt_addr into prog0. This represents |
| # the first instruction on the other side of the branch: we need to do |
| # this to avoid both sides of the branch trying to put an instruction |
| # there. |
| prog0 = program.copy() |
| prog0.add_insns(model.pc, [branch_insn]) |
| model0 = model.copy() |
| model0.update_for_insn(branch_insn) |
| |
| model0.pc += 4 |
| prog0.add_insns(tgt_addr, [branch_insn]) |
| |
| model0.fuel = branch_fuel |
| prog0.constrain_space(branch_space) |
| |
| ret0 = cont(model0, prog0) |
| if ret0 is None: |
| return None |
| |
| snippet0, model0 = ret0 |
| |
| # We successfully generated the fall-through branch. Now we want to |
| # generate the other side. Make another copy of program and insert the |
| # instructions from snippet0 into it. Add the bogus instruction at |
| # model.pc, as above. Also add a bogus instruction at model0.pc: this |
| # represents "the next thing" that happens at the end of the first |
| # branch, and we mustn't allow snippet1 to use that space. |
| prog1 = program.copy() |
| snippet0.insert_into_program(prog1) |
| prog1.add_insns(model.pc, [branch_insn]) |
| prog1.add_insns(model0.pc, [branch_insn]) |
| |
| model1 = model.copy() |
| model1.update_for_insn(branch_insn) |
| model1.pc = tgt_addr |
| |
| prog1.constrain_space(branch_space) |
| model1.fuel = branch_fuel |
| |
| ret1 = cont(model1, prog1) |
| if ret1 is None: |
| return None |
| |
| snippet1, model1 = ret1 |
| |
| # We've managed to generate both sides of the branch. All that's left |
| # to do is fix up the execution paths to converge again. To do this, we |
| # need to add a jump to one side or the other. (Alternatively, we could |
| # jump from both to another address, but this shouldn't provide any |
| # extra coverage, so there's not much point) |
| if random.random() < 0.5: |
| # Add the jump to go from branch 0 to branch 1 |
| jump_ret = self.jump_gen.gen_tgt(model0, prog0, model1.pc) |
| if jump_ret is None: |
| return None |
| |
| jmp_snippet, model0 = jump_ret |
| snippet0 = snippet0.merge(jmp_snippet) |
| else: |
| # Add the jump to go from branch 1 to branch 0 |
| jump_ret = self.jump_gen.gen_tgt(model1, prog1, model0.pc) |
| if jump_ret is None: |
| return None |
| |
| jmp_snippet, model1 = jump_ret |
| snippet1 = snippet1.merge(jmp_snippet) |
| |
| assert model0.pc == model1.pc |
| model0.merge(model1) |
| |
| snippet = BranchSnippet(model.pc, branch_insn, snippet0, snippet1) |
| snippet.insert_into_program(program) |
| return (snippet, model0) |
