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)