10.1. Decoder

10.1. Decoder

Reference Python implementations of both the encoder and decoder can be found at https://github.com/riscv-non-isa/riscv-trace-spec.

10.1.1. Decoder pseudo code

# global variables
global        pc                          # Reconstructed program counter
global        last_pc                     # PC of previous instruction
global        branches = 0                # Number of branches to process
global        branch_map = 0              # Bit vector of not taken/taken (1/0) status for branches
global bool   stop_at_last_branch = FALSE # Flag to indicate reconstruction is to end at the final branch
global bool   inferred_address = FALSE    # Flag to indicate that reported address from format 0/1/2 was
                                          # not following an uninferable jump (and is therefore inferred)
global bool   start_of_trace = TRUE       # Flag indicating 1st trace packet still to be processed
global        address                     # Reconstructed address from te_inst packets
global        privilege                   # Privilege from te_inst packets
global        poss_next_epc               # Possible next exception address
global bool   pne_valid = FALSE           # Possible next exception address is valid
global        options                     # Operating mode flags (sijump onwards from support packet)
global array  return_stack                # Array holding return address stack
global        irstack_depth = 0           # Number of entries on the return address stack traced
global        irets = 0                   # Number of implicit (i.e. unreported) returns
global        popped_return_target        # Return address popped from the stack
global bool   prt_valid = FALSE           # Popped return address is valid
global array  bpred                       # Structure holding branch predictor.  Each entry is 2 bools
global bool   use_bpred = FALSE           # Use branch predictor to determine branch outcome
global array  cache                       # Array holding cache of jump target addresses
global struct discovery                   # Structure containing fields from discovery
global struct previous_te_inst            # Copy of previous te_inst packet

# Process te_inst packet.  Call each time a te_inst packet is received ##################################
function process_te_inst (te_inst)
  use_bpred = FALSE
  irets = 0
  if (te_inst.format == 3)
    if (te_inst.subformat == 3) # Support packet
      process_support(te_inst)
      return
    if (te_inst.subformat == 2) # Context packet
      return
    if (te_inst.subformat == 1) # Trap packet
      previous_te_inst = te_inst
      report_trap(te_inst)
      if (!te_inst.interrupt) # Exception
        report_epc(exception_address(te_inst))
      if (!te_inst.thaddr) # Trap only - nothing retired
        return

    inferred_address = FALSE
    pne_valid = FALSE
    address       = (te_inst.address << discovery.iaddress_lsb)
    if (te_inst.subformat == 1 or start_of_trace)
      branches    = 0
      branch_map  = 0
    if (is_branch(get_instr(address))) # 1 unprocessed branch if this instruction is a branch
      branch_map = branch_map | (te_inst.branch << branches)
      branches++
    if (te_inst.subformat == 0 and !start_of_trace and
        !(previous_te_inst.format == 3 and previous_te_inst.subformat == 1 and !previous_te_inst.thaddr))
      follow_execution_path(address, te_inst)
    else
      pc           = address
      report_pc(pc)
      last_pc      = pc # previous pc not known but ensures correct operation for is_sequential_jump()
    if (start_of_trace or !options.resync_disabled)
      irstack_depth  = 0
      return_stack[0].count = 0
      bpred_init()
    if ((start_of_trace or !options.resync_disabled or te_inst.subformat == 1) and is_call(get_instr(pc))
        push_return_stack(pc)
    privilege = te_inst.privilege
    start_of_trace = FALSE

  else # Not format 3
    if (start_of_trace) # This should not be possible!
      ERROR: Expecting trace to start with format 3
      abort
    if (includes_address(te_inst))
      if (options.full_address)
        address  = (te_inst.address << discovery.iaddress_lsb)
      else
        address += (te_inst.address << discovery.iaddress_lsb)
      stop_at_last_branch = is_branch(get_instr(address))
    else if (includes_cache_index(te_inst))
      address  = cache_lookup(te_inst.index)
      stop_at_last_branch = is_branch(get_instr(address))
    if (includes_bpred_count(te_inst))
      use_bpred = branches == 0
      stop_at_last_branch = (te_inst.branch_fmt == 0)
      branches += te_inst.branch_count + 31
      if (is_failed_bpred(te_inst))
        # Reporting branch following the number of correct predictions indicated by te_inst.branch_count
        branches++
    else if (includes_branch_map(te_inst))
      stop_at_last_branch = stop_at_last_branch or (te_inst.branches == 0)
      # Branch map will contain <= 1 branch (1 if last reported instruction was a branch)
      branch_map = branch_map | (te_inst.branch_map << branches)
      if (te_inst.branches == 0)
        branches += 31
      else
        branches += te_inst.branches

    follow_execution_path(address, te_inst)
    return

# Follow execution path to reported address ###############################################################
function follow_execution_path(address, te_inst)

  local previous_address = pc
  local bool stop_here = FALSE
  local unproc_ir = FALSE
  while (TRUE)
    if (inferred_address) # iterate again from previously reported address to find second occurrence
      stop_here = next_pc(previous_address, previous_te_inst)
      report_pc(pc)
      if (stop_here)
        inferred_address = FALSE
        irets = prt_valid ? 1 : 0
    else
      unproc_ir = unprocessed_implicit_returns(te_inst)
      stop_here = next_pc(address, te_inst)
      if (!is_call(get_instr(address)) # Set unproc_ir after popping stack but before pushing
        unproc_ir = unprocessed_implicit_returns(te_inst)
      report_pc(pc)
      if (branches == 1 and is_branch(get_instr(pc)) and stop_at_last_branch)
        # Reached final branch - stop here (do not follow to next instruction as we do not yet know
        # whether it retires)
        if (is_failed_bpred(te_inst))
          # Final branch failed prediction so set branch map accordingly
          branch_map[0] = bpred_taken(pc, te_inst)
        stop_at_last_branch = FALSE
        return
      if (stop_here)
        # Reached reported address following an uninferable discontinuity - stop here
        if (unprocessed_branches(pc))
          ERROR: unprocessed branches
          abort
        return
      if (!stop_at_last_branch and pc == address and flag_notify(te_inst) and
      !unprocessed_branches(pc) and !unproc_ir)
        # All branches and implicit returns processed, and reached reported address due to a notification,
        # not as an uninferable jump target.
        return
      if (!stop_at_last_branch and pc == address and !is_uninferable_discon(get_instr(last_pc) and
          !unprocessed_branches(pc) and !unproc_ir and !flag_updiscon(te_inst) and te_inst.format != 3))
        # All branches and implicit returns processed, and reached reported address, but not as an
        # uninferable jump target.  Stop here for now, though flag indicates this may not be final retired
        # instruction
        previous_te_inst = te_inst
        inferred_address = TRUE
        return
      if (te_inst.format == 3 and pc == address and !unprocessed_branches(pc) and
          (te_inst.privilege == privilege or is_return_from_trap(get_instr(last_pc))))
        # All branches processed, and reached reported address
        return

# Compute next PC #########################################################################################
function next_pc (address, te_inst)

  local instr   = get_instr(pc)
  local this_pc = pc
  local bool stop_here = FALSE
  local bool exception = te_inst.format == 3 and te_inst.subformat == 1

  if (is_inferrable_jump(instr))
    pc += instr.imm
  else if (is_sequential_jump(instr, last_pc)) # lui/auipc followed by jump using same register
    pc = sequential_jump_target(pc, last_pc)
  else if (is_implicit_return(address, instr, te_inst))
    pc = popped_return_target
    if (!exception)
      cache_update(pc)
      if (includes_cache_index(te_inst) and te_inst.index == get_index(pc, "cache"))
        address = pc
        stop_at_last_branch = is_branch(get_instr(address))

  else if (is_uninferable_discon(instr))
    if (stop_at_last_branch and !is_branch(address))
      ERROR: unexpected uninferable discontinuity
      abort
    else
      pc = address
      if (!exception)
        if (!flag_irreport(te_inst) or address != popped_return_target)
          # Update cache unless address is correctly predicted but reported for some other reason
          cache_update(pc)
      stop_here = TRUE
  else if (is_branch(instr))
    if (!exception)
      irets = 0
    pc += is_taken_branch(pc, te_inst) ? instr.imm : instruction_size(instr)
  else
    pc += instruction_size(instr)

  if (!exception)
    if (is_call(get_instr(pc)))
      push_return_stack(pc)
    prt_valid = FALSE
    if (is_return(get_instr(pc)) and irstack_depth > 0)
      popped_return_target = pop_return_stack()
      prt_valid = TRUE

  last_pc = this_pc

  return stop_here

# Process support packet.  Call each time a support packet is received ##################################
function process_support (te_inst)

  local bool stop_here = FALSE

  options = te_inst.options
  pne_valid = FALSE
  if (te_inst.qual_status != no_change)
    start_of_trace = TRUE # Trace ended, so get ready to start again

  if (te_inst.qual_status == ended_ntr and inferred_address)
    local previous_address = pc
    inferred_address       = FALSE
    while (TRUE)
      stop_here = next_pc(previous_address, previous_te_inst)
      report_pc(pc)
      if (stop_here)
        return

  return

# Packet includes an address (formats 0, 1, 2) ############################################################
function includes_address (te_inst)

  if (te_inst.format == 2 or
      (te_inst.format == 1 and te_inst.branches != 0) or
      (includes_bpred_count(te_inst) and te_inst.branch_fmt != 0))
    return TRUE

  return FALSE

# Packet includes branch map ##############################################################################
function includes_branch_map (te_inst)

  if (te_inst.format == 1 or (includes_cache_index(te_inst) and te_inst.branches > 0))
    return TRUE

  return FALSE

# Packet includes branch predictor count ##################################################################
function includes_bpred_count (te_inst)

  if (te_inst.format == 0 and options.branch_predictor and
      (!includes_f0sub(te_inst) or te_inst.subformat == 0))
    return TRUE

  return FALSE

# Packet includes jump target cache index #################################################################
function includes_cache_index (te_inst)

  if (te_inst.format == 0 and options.jump_target_cache and
      (!includes_f0sub(te_inst) or te_inst.subformat == (discovery.bpred_size == 0 ? 0 : 1)))
    return TRUE

  return FALSE

# Format 0 packet includes optional sub-format field ######################################################
function includes_f0sub (te_inst)

  if (te_inst.format != 0 or (f0subformats() < 2))
    return FALSE

  return TRUE

# Return the number of supported format 0 sub-formats #####################################################
function f0subformats ()

  local bpred_present          = discovery.bpred_size > 0 ? 1 : 0
  local cache_present          = discovery.cache_size > 0 ? 1 : 0

  return bpred_present + cache_present

# Determine if instruction is a branch, adjust branch count/map, and return taken status ##################
function is_taken_branch (address, te_inst)

  local      instr = get_instr(address)
  local bool taken = FALSE

  if (branches == 0)
    ERROR: cannot resolve branch
    abort
  else
    if (use_bpred)
      taken = bpred_taken(address, te_inst)
    else
      taken = !branch_map[0]
      branch_map >> 1
      use_bpred = includes_bpred_count(te_inst)
    bpred_update(address, taken)
    branches--

  return taken

# Determine if instruction is a branch ####################################################################
function is_branch (instr)

  if ((instr.opcode == BEQ)    or
      (instr.opcode == BNE)    or
      (instr.opcode == BLT)    or
      (instr.opcode == BGE)    or
      (instr.opcode == BLTU)   or
      (instr.opcode == BGEU)   or
      (instr.opcode == C.BEQZ) or
      (instr.opcode == C.BNEZ))
    return TRUE

  return FALSE

# Determine if branch prediction failed ###################################################################
function is_failed_bpred(te_inst)

  return (includes_bpred_count(te_inst) and (te_inst.branch_fmt == 0 or te_inst.branch_fmt == 3))

# Determine if instruction is an inferrable jump ##########################################################
function is_inferrable_jump (instr)

  if ((instr.opcode == JAL)   or
      (instr.opcode == C.JAL) or
      (instr.opcode == C.J)   or
      (instr.opcode == JALR and instr.rs1 == 0))
    return TRUE

  return FALSE

# Determine if instruction is an uninferable jump ########################################################
function is_uninferable_jump (instr)

  if ((instr.opcode == JALR and instr.rs1 != 0) or
      (instr.opcode == C.JALR)                  or
      (instr.opcode == C.JR))
    return TRUE

  return FALSE

# Determine if instruction is a return from trap ##########################################################
function is_return_from_trap (instr)

  if ((instr.opcode == SRET)      or
      (instr.opcode == MRET))
    return TRUE

  return FALSE

# Determine if instruction is an uninferable discontinuity ###############################################
function is_uninferable_discon (instr)

  if (is_uninferable_jump(instr) or
      is_return_from_trap (instr) or
      (instr.opcode == ECALL)     or
      (instr.opcode == EBREAK)    or
      (instr.opcode == C.EBREAK))
    return TRUE

  return FALSE

# Determine if instruction is a sequentially inferrable jump ##############################################
function is_sequential_jump (instr, prev_addr)

  if (not (is_uninferable_jump(instr) and options.sijump))
    return FALSE

  local prev_instr = get_instr(prev_addr)

  if((prev_instr.opcode == AUIPC) or
     (prev_instr.opcode == LUI)   or
     (prev_instr.opcode == C.LUI))
    return (instr.rs1 == prev_instr.rd)

  return FALSE

# Find the target of a sequentially inferrable jump #######################################################
function sequential_jump_target (addr, prev_addr)

  local instr      = get_instr(addr)
  local prev_instr = get_instr(prev_addr)
  local target     = 0

  if (prev_instr.opcode == AUIPC)
    target = prev_addr
  target += prev_instr.imm
  if (instr.opcode == JALR)
    target += instr.imm

  return target

# Determine if instruction is a call ######################################################################
# - excludes tail calls as they do not push an address onto the return stack
function is_call (instr)

  if ((instr.opcode == JALR   and instr.rd  == 1 and instr.rs1 != 5) or
      (instr.opcode == JALR   and instr.rd  == 5 and instr.rs1 != 1) or
      (instr.opcode == C.JALR and instr.rs1 != 5)                    or
      (instr.opcode == JAL    and (instr.rd == 1 or instr.rd  == 5)) or
      (instr.opcode == C.JAL)                                        or
      (instr.opcode == CMJALT))
    return TRUE

  return FALSE

# Determine if instruction is a return ####################################################################
function is_return (instr)

  if ((instr.opcode == JALR and (instr.rs1 == 1 or instr.rs1 == 5) and instr.rd != 1 and instr.rd != 5) or
      (instr.opcode == C.JR and (instr.rs1 == 1 or instr.rs1 == 5)) or
      (instr.opcode == CM.POPRET))
    return TRUE

  return FALSE

# Determine if instruction return address can be implicitly inferred ######################################
function is_implicit_return (address, instr, te_inst)

  if (!options.implicit_return) # Implicit return mode disabled
    return FALSE

  if (is_return (instr))
    if (flag_irreport(te_inst) and !unprocessed_branches(address) and te_inst.irets == irets - 1)
      return FALSE
    return prt_valid

  return FALSE

# Check whether notify is present and return flag state ###################################################
function flag_notify (te_inst)

  if (te_inst.format == 3 or !includes_address(te_inst))
    return FALSE

  return (te_inst.notify != get_preceding_bit(te_inst, "notify"))

# Check whether updiscon is present and return flag state #################################################
function flag_updiscon (te_inst)

  if (te_inst.format == 3 or !includes_address(te_inst))
    return FALSE

  return (te_inst.updiscon != get_preceding_bit(te_inst, "updiscon"))

# Check whether irreport is present and return flag state #################################################
function flag_irreport (te_inst)

  if (te_inst.format == 3 or !(includes_address(te_inst) or includes_cache_index(te_inst)))
    return FALSE

  return (te_inst.irreport != get_preceding_bit(te_inst, "irreport"))

# Check for unprocessed branches ##########################################################################
function unprocessed_branches (address)
  # Check all branches processed (except 1 if this instruction is a branch)
  return (branches != (is_branch(get_instr(address)) ? 1 : 0))

# Check for unprocessed implicit returns ##################################################################
function unprocessed_implicit_returns (te_inst)

  return (irstack_depth > 0 and flag_irreport(te_inst) and te_inst.irets > irets)

# Push address onto return stack ##########################################################################
function push_return_stack (address)

  if (!options.implicit_return) # Implicit return mode disabled
    return

  local irstack_depth_max = discovery.return_stack_size  ?
                             2**discovery.return_stack_size :
                             2**discovery.call_counter_size
  local call_counter_max  = discovery.return_stack_size  ?
                             2**discovery.call_counter_size - 1 : 0
  local instr             = get_instr(address)
  local link              = address + instruction_size(instr)

  if (irstack_depth > 0 and
      return_stack[irstack_depth-1].link  == link and
      return_stack[irstack_depth-1].count != call_counter_max)
    # Recursive call and each stack entry has an associated counter - increase count for top of stack
    return_stack[irstack_depth-1].count++
  else # Push new entry onto the stack
    if (irstack_depth == irstack_depth_max)
      # Delete oldest entry from stack to make room for new entry added below
      irstack_depth--
      for (i = 0; i < irstack_depth; i++)
        return_stack[i] = return_stack[i+1]

    return_stack[irstack_depth].link  = link
    return_stack[irstack_depth].count = 0
    irstack_depth++

  return

# Pop address from return stack ###########################################################################
function pop_return_stack ()

  local link

  link = peek_return_stack()
  if (return_stack[irstack_depth-1].count > 0)
    return_stack[irstack_depth-1].count--
  else
    irstack_depth-- # function not called if irstack_depth is 0, so no need to check for underflow

  irets++

  return link

# Return address from top of return stack #################################################################
function peek_return_stack ()

  return return_stack[irstack_depth-1].link

# Return the address of an exception ######################################################################
function exception_address (te_inst)

  local instr = get_instr(pc)
  local epc = poss_next_epc

  if (start_of_trace or is_uninferable_discon(instr))
    if (te_inst.thaddr) # This should not be possible!
      ERROR: Expecting EPC address in te_inst
      abort

    return (te_inst.address << discovery.iaddress_lsb)

  poss_next_epc = te_inst.address << discovery.iaddress_lsb
  if (pne_valid)
    pne_valid = !te_inst.thaddr
    return epc
  pne_valid = !te_inst.thaddr

  if ((instr.opcode == ECALL) or (instr.opcode == EBREAK) or (instr.opcode == C.EBREAK))
    return pc
  if (!te_inst.thaddr) # pne_valid is false.  te_inst address is EPC of current trap, not next trap
    return (te_inst.address << discovery_response.iaddress_lsb)

  next_pc(pc, te_inst)
  return pc

# Report ecause and tval (user to populate if desired) ####################################################
function report_trap (te_inst)

  return

# Report program counter value (user to populate if desired) ##############################################
function report_pc (address)

  return

# Report exception program counter value (user to populate if desired) ####################################
function report_epc (address)

  return

# Initialize branch predictor #############################################################################
function bpred_init ()

  if (discovery.bpred_size == 0)
    return

  for(i = 0; i < 2** discovery.bpred_size; i++)
    bpred[i][1] = FALSE
    bpred[i][0] = TRUE
  return

# Update Branch predictor #################################################################################
function bpred_update (address, taken)

  local index

  if (!options.branch_predictor)
    return

  # MSB is predicted next outcome, and changes after 2 failed predictions.  LSB is current outcome
  index = get_index(address, "bpred")
  if (bpred[index][1] != bpred[index][0])
    bpred[index][1] = taken
  bpred[index][0] = taken

  return

# Return the predicted branch outcome #####################################################################
function bpred_taken (address, te_inst)

  local index
  local taken

  if (!options.branch_predictor) # This should not be possible
    ERROR: Can't predict branch outcome when branch predictor disabled
    abort

  index = get_index(address, "bpred")
  taken = bpred[index][1]
  if (branches == 1 and te_inst.branch_fmt == 3)
    # Prediction failed on final branch
    taken = !taken

  return taken

# Update jump target cache ################################################################################
function cache_update (address)

  local index

  if (options.jump_target_cache)
    index = get_index(address, "cache")
    cache[index] = address

# Look up address in jump target cache ####################################################################
function cache_lookup (index)

  if (!options.jump_target_cache) # This should not be possible
    ERROR: Can't look up cache index when cache is disabled
    abort

  return cache[index]

# Extract lookup index from address #######################################################################
function get_index (address, type)

  local size

  if (type == "bpred")
    size = discovery.bpred_size
  else
    size = discovery.cache_size

  # Index into predictor is bpred_size or cache_size bits of the address, starting from iaddress_lsb
  return (address >> discovery.iaddress_lsb) & ((1 << size) - 1)