# US 2021/0081297 A1 · Trace-data processing device

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0081297 A1
- Document ID: US20210081297A1
- Status: Published application
- Kind: A1
- Application number: 17/017,963
- Filed: 2020-09-11
- Published: 2021-03-18
- Earliest claimed: 2019-09-13
- Assignees: Accemic Technologies GmbH
- Applicants: Accemic Technologies GmbH
- Inventors: Alexander WEISS; Alexander LANGE
- Web page: https://patentgrep.com/patent/US20210081297A1

## CPC

- G06F 11/3476: {Data logging (G06F11/14, G06F11/2205 take precedence)}
- G06F 9/30065: {Loop control instructions; iterative instructions, e.g. LOOP, REPEAT}
- G06F 9/323: {for indirect branch instructions}
- G06F 11/2733: {Test interface between tester and unit under test}
- G06F 11/323: {Visualisation of programs or trace data}
- G06F 11/3636: {by tracing the execution of the program}
- G06F 11/3648: {using additional hardware}
- G06F 11/3676: {for coverage analysis}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A trace-data-processing device for reconstructing an execution flow of a program performed by a source device under test or under observation, herein DUT, using at least one source-specific trace-data stream is disclosed. The trace-data-processing device comprises a trace-data-processing unit, which is configured to identify in the trace-data stream at least one instruction-synchronization message and branch messages. Moreover, the trace-data-processing device is configured to generate runtime-information data indicative of an at least partial reconstruction of the execution flow, using the identified trace messages, a pre-defined branch identifier allocated to each branch instruction address in the program that is associated with a direct branch instruction and pre-stored reconstruction information stored in a reconstruction memory.

## Claims

### Claim 1

A trace-data-processing device for reconstructing an execution flow of a program performed by a source device under test or under observation, herein DUT, using at least one source-specific trace-data stream, wherein the trace-data-processing device comprises a trace-data-processing unit, which is configured
to identify in the trace-data stream
at least one instruction-synchronization message indicative of an instruction address of an instruction executed by the DUT, and
branch messages comprising information about an execution of a branch instruction by the DUT; and
to generate runtime-information data indicative of an at least partial reconstruction of the execution flow, using
the identified at least one instruction-synchronization message and the identified branch messages,
a pre-defined branch identifier allocated to each branch instruction address in the program that is associated with a direct branch instruction, wherein the branch identifiers are in an order corresponding to an execution direction of the program, and using
pre-stored reconstruction information stored in a reconstruction memory, which includes
(i) address-allocation information that allocates a next branch identifier to each instruction address of the program, wherein the next branch identifier is that branch identifier whose branch instruction address is closest, in the execution direction, to an instruction address under consideration, or directly at the instruction address under consideration; and
(ii) branch-identifier-allocation information that allocates to each branch identifier a subsequent branch identifier, wherein the subsequent branch identifier is that branch identifier whose branch instruction address is closest, in the execution direction, to a jump-in address associated with a branch instruction of a branch identifier under consideration, or is directly at the jump-in address; and wherein the trace-data-processing unit is configured
upon identification of the synchronization message, to store as an intermediate runtime information that next branch identifier which corresponds to the instruction address comprised by the synchronization message according to the address-allocation information; and
upon identification of a given branch message that indicates that a direct branch instruction was executed,
(i) to include into the runtime information data the branch identifier stored as the intermediate runtime information, and
(ii) to subsequently overwrite the intermediate runtime information with that subsequent branch identifier which is allocated to the stored branch identifier according to the branch-identifier-allocation information; and
upon identification of a given branch message that indicates that a branch instruction was not executed, to update the intermediate runtime information by adding a predetermined increment to the value of the intermediate runtime information.

### Claim 2 (depends on 1)

The trace-data-processing device of claim 1, wherein the trace-data-processing unit is configured to generate runtime-information data using the pre-defined branch identifiers, wherein a predefined branch identifier is also allocated to each of those branch instruction addresses in the program that are associated with an indirect branch instruction; and wherein the trace-data-processing unit is additionally configured,
upon identification of a branch message that indicates that an indirect branch instruction was executed,
(i) to include into the runtime information data the branch identifier stored as the intermediate runtime information, and
(ii) to subsequently overwrite the intermediate runtime information with that next branch identifier which is allocated to the jump-in address indicated by the branch message according to the address allocation.

### Claim 3 (depends on 1)

The trace-data-processing device of claim 1, wherein the trace-data-processing unit is configured, upon reception of a branch message that indicates that a branch instruction was not executed, to include into the runtime information data the branch identifier stored as the intermediate runtime information.

### Claim 4 (depends on 1)

The trace-data-processing device of claim 1, wherein the trace-data-processing unit is configured, upon reception of a branch message, to include into the runtime information a time information associated with the processing of the branch message by the trace-data-processing unit.

### Claim 5 (depends on 1)

The trace-data-processing device of claim 1, wherein the trace-data-processing unit is configured to output the jump-in address of the branch instruction of the stored branch identifier, upon reception of a branch message indicating that a branch instruction was executed.

### Claim 6 (depends on 1)

The trace-data-processing device of claim 1, wherein
the branch-identifier-allocation information includes marks for distinguishing those of the branch identifiers which are to be included into the runtime information data from those of the branch identifiers which are not to be included into the runtime information data; and wherein
the trace-data-processing unit is configured, upon identification of a branch message that indicates execution or non-execution of a branch instruction, to include into the runtime information data only those branch identifiers stored in the intermediate runtime information that are marked for inclusion into the runtime information data.

### Claim 7

The trace-data-processing unit, wherein the branch-identifier-allocation information additionally allocates to a branch identifier under consideration
for each sequence of a set of sequences of execution information elements indicative of execution or non-execution of corresponding direct branch instructions, the sequences starting from the branch identifier under consideration and ending at a respective final branch identifier, wherein
the set includes at least those sequences, up to a given length, whose first and last execution information element in the sequence indicate execution of the corresponding branch instruction,
a series branch identifier, which is that branch identifier whose branch instruction address is closest to, in the execution direction, or directly at the jump-in address of the final branch identifier; and wherein
the trace-data-processing unit is configured, upon identification of a sequence of branch messages indicative of execution or non-execution of direct branch instructions, to include into the runtime information, using the branch-identifier-allocation information those branch identifiers whose direct branch instructions were executed by the DUT.

### Claim 8 (depends on 1)

The trace-data-processing device of claim 1, wherein the trace-data-processing unit is configured to generate the runtime-information data additionally using
in the program whose execution is to be monitored by the trace-data-processing unit; wherein
the address-allocation information additionally allocates a next TOP identifier to each instruction address, wherein the next TOP identifier is that TOP identifier, if any, whose instruction address is located closest to or directly at an instruction address under consideration and whose instruction address is located in an interval between the instruction address under consideration and a branch instruction address located closest to the instruction address under consideration, in the execution direction; and
the branch-identifier-allocation information additionally allocates to each branch identifier a first subsequent TOP identifier, which is that TOP identifier, if any, whose instruction address is located closest to or directly at a branch instruction address of a branch identifier under consideration and whose instruction address is located in an interval between the branch instruction address of the branch identifier under consideration and a branch instruction address located closest to the branch instruction address of the branch identifier under consideration, in the execution direction; and
the branch-identifier-allocation information additionally allocates to each branch identifier a second subsequent TOP identifier, which is that TOP identifier, if any, whose instruction address is located closest to or directly at a jump-in address of a branch identifier under consideration and whose instruction address is located in an interval between the jump-in address of the branch identifier under consideration and a branch instruction address located closest to the jump-in address of the branch identifier under consideration, in the execution direction; and
the pre-stored reconstruction information additionally includes
IOP-allocation information that indicates for a given TOP identifier any following TOP identifier, whose instruction address is located in an interval between the instruction address of the TOP identifier under consideration and a branch instruction address located closest to the instruction address of the TOP identifier under consideration, in the execution direction; and wherein
the trace-data-processing unit is configured
upon identification of an instruction-synchronization message, to determine, using the address-allocation information and the TOP-allocation information, those TOP identifiers, if any, whose associated instructions are to be executed by the DUT before execution or non-execution of a next branch instruction in the program execution flow, and to include the determined TOP identifiers into the intermediate runtime information; and
upon reception of a branch message indicating execution or non-execution of a direct branch instruction, to include into the runtime information data any TOP identifier comprised in the intermediate runtime information and to determine, using the branch-identifier allocation and the TOP allocation, those TOP identifiers, if any, whose associated instructions are to be executed by the DUT before execution or non-execution of a next branch instruction in the program execution flow, and to include the determined TOP identifiers into the intermediate runtime information.

### Claim 9 (depends on 7)

The trace-data-processing device of claim 7, wherein the branch-identifier allocation information additionally allocates to a branch identifier under consideration
for sets of sequences of execution information elements indicative of execution or non-execution of a corresponding direct branch instructions, starting from the branch identifier under consideration and ending at a respective final branch identifier,
a series TOP identifier, which is that TOP identifier whose instruction address,
(i) in case of execution of the branch instruction of the final branch identifier, is located closest to, in the execution direction, or directly at a jump-in address of the branch instruction of the final branch identifier, and is located in an interval between the jump-in address and a branch instruction address located closest to the jump-in address of the final branch identifier in the execution direction; and
(ii) in case of non-execution of the branch instruction of the final branch identifier, is located closest to in the execution direction or directly at the branch instruction address of the final branch identifier, and is located in an interval between the branch instruction address of the final branch identifier and a branch instruction address located closest to the branch instruction address of the final branch identifier in the execution direction; and wherein
the trace-data-processing unit is configured, upon identification of a sequence of branch messages indicative of execution or non-execution of direct branch instructions, to include into the runtime information, using the branch-identifier allocation and the IOP-identifier allocation, those IOP identifiers whose instructions were executed by the DUT.

### Claim 10 (depends on 2)

The trace-data-processing device of claim 2, wherein the data-trace-processing unit is additionally configured,
upon reception of a branch message indicating execution or non-execution of an indirect branch instruction, to determine, using the branch-identifier-allocation information and the IOP-allocation information, those IOP identifiers, if any, whose associated instructions were executed by the DUT, and to include the determined IOP identifiers into the runtime information data.

### Claim 11 (depends on 1)

The trace-data-processing device of claim 1, wherein
the values of the branch identifiers are integers, wherein the values of branch identifiers of neighboring branch instructions differ by 1; and
the value of the predetermined increment is 1.

### Claim 12 (depends on 1)

The trace-data-processing device of claim 1, wherein the trace-data-processing device comprises a token-generation unit, which is configured to generate and output a token comprising at least a part of the runtime information data.

### Claim 13 (depends on 1)

A trace-data-processing device of claim 1, wherein the trace-data-processing unit is configured
to identify within the trace-data stream any two consecutive sequences of direct branch messages that
(i) comprise an identical sequence of branch messages, referred to as loop-message sequence, indicative of execution or non-execution of direct branch instructions and that
(ii) produce an identical sequence of branch identifiers, referred to as loop-identifier sequence; and
upon identification of a loop-message sequence, to store the corresponding loop-identifier sequence; and
to determine the sequence of branch identifiers of any loop-messages that consecutively follow the two identified loop-message sequences using the stored loop-identifier sequence.

### Claim 14

A trace-data-processing method for reconstructing an execution flow of a program per-formed by a source device under test or under observation, herein DUT, using at least one source-specific trace-data stream, the method comprising
identifying in the trace-data stream
at least one instruction-synchronization message indicative of an instruction address of an instruction executed by the DUT, and
branch messages comprising information about an execution of a branch instruction by the DUT;
generating runtime-information data indicative of an at least partial reconstruction of the execution flow, using
the identified at least one instruction-synchronization message and the identified branch messages,
a pre-defined branch identifier allocated to each branch instruction address in the program that is associated with a direct branch instruction, wherein the branch identifiers are in an order corresponding to an execution direction of the program, and using
pre-stored reconstruction information stored in a reconstruction memory, which includes
(i) address-allocation information that allocates a next branch identifier to each instruction address of the program, wherein the next branch identifier is that branch identifier whose branch instruction address is closest, in the execution direction, to an instruction address under consideration, or directly at the instruction address under consideration; and
(ii) branch-identifier-allocation information that allocates to each branch identifier a sub-sequent branch identifier, wherein the subsequent branch identifier is that branch identifier whose branch instruction address is closest, in the execution direction, to a jump-in address associated with a branch instruction of a branch identifier under consideration, or is directly at the jump-in address;
wherein generating the runtime-information data comprises
upon identification of the synchronization message, storing as an intermediate runtime information that next branch identifier which corresponds to the instruction address comprised by the synchronization message according to the address-allocation information; and
upon identification of a given branch message that indicates that a direct branch instruction was executed,
(i) including into the runtime information data the branch identifier stored as the intermediate runtime information, and
(ii) subsequently overwriting the intermediate runtime information with that subsequent branch identifier which is allocated to the stored branch identifier according to the branch-identifier-allocation information; and
upon identification of a given branch message that indicates that a branch instruction was not executed, updating the intermediate runtime information by adding a predetermined increment to the value of the intermediate runtime information.

### Claim 15 (depends on 14)

A computer program comprising instructions which, when the program is executed by a computer, cause the computer to carry out the steps of the method of claim 14.
