Patent Description:
Different inventions have been identified that propose solutions to facilitate the tracing of instructions.

<CIT>, "System and method for tracing program execution within a processor before and after a triggering event", enables the starting and interrupting of the tracing of instructions, using a trace processor that works in parallel with the processor that executes the instructions themselves. The trace processor, after detecting the start time of the trace by means of a specific instruction, stores in a shared memory information relating to the entire sequence of execution of instructions until the moment at which it detects the stop instruction of the trace. So, to enable and disable the trace it inserts a specific instruction into the executable code.

Commercial tools such as RapiTime (<NPL>), use certain techniques in order to characterize critical systems in the field of avionics, automotive, or space systems. To achieve this, they use the instrumentation of the code, entering instructions that trigger the trace at the previously selected points analysing the source files. The instrumentation, however, has its disadvantages in the overload introduced in the execution time due to the instructions inserted, and the consequent increase in the space occupied by the executable code.

With respect to <CIT>, "Systems and methods for a real time embedded trace", the main difference is that the system traces the jump instructions autonomously.

As described above, the identification of the execution time of previously selected instructions is being used in critical systems and enables the tracing of code blocks to evaluate their execution time in the worst case, taking into account that the transition between some of these blocks, such as that corresponding to an else block and the subsequent block, do not imply a jump in the execution; they would therefore not be detected by the solution presented by <CIT>.

As for <CIT>, "System and method for tracing program execution within a superscalar processor", it presents an improvement with respect to <CIT>, enabling working with superscalar processors that work at high frequencies, above <NUM>. To do this, it uses an encoding of the information that it is desired to trace that enables a reduction in the space required to store it in the trace buffer that is provided as an output. As in this patent, blocks of instructions are traced to analyse the execution thereof, but defining a more flexible way to trigger the trace and using a trace encoding that enables a saving in terms of the information stored and the number of pins used. This patent, therefore, does not prevent the overload of the use of code instrumentation techniques that affect the entire system, as is the case with the invention claimed, but aims to optimize a tracing mechanism, not based on the instrumentation, but on the detection of events that conform to predefined conditions.

<CIT> describes a microprocessor implements an instruction tracing mechanism that saves the state of the microprocessor without special hardware. Prior to the execution of a traced instruction, a trace microcode routine is implemented that saves the state of the microprocessor to external memory. The state information saved by the trace microcode routine varies depending upon the amount of data needed by the end user. After the state of the processor has been saved, the trace instruction is executed. State information that changed during the execution of the trace instruction is saved to memory prior to a subsequent instruction. This patent proposes a trace method that is not selective as it does not allow to determine which instructions to trace and which not to trace, nor does it allow to execute different trace instructions in parallel with the program instructions.

Finally, there is a patent entitled "A METHOD AND DEVICE FOR THE PARALLEL PROCESSING OF PROGRAM INSTRUCTIONS AND TRACE INSTRUCTIONS", patent <CIT>, which differs significantly from the new invention filed. Although the issue they intend to solve is the same, in <CIT>, the instrumentation of the code is facilitated by adding a specific trace instruction to the set of instructions of the processor, and a processor design capable of simultaneously decoding and executing an effective instruction and a trace instruction, preventing the execution time overload, but being intrusive with respect to the location of the code and to the total space it occupies, since it requires the modification thereof for the insertion of the trace instructions.

It is therefore concluded that many of the existing systems for tracing instructions enable specific trace triggering events to be programmed, to collect trace information limited to a certain interval prior to and/or subsequent to such an event. These methods, however, suffer from some rigidity in that the number of blocks that can be traced in each execution is always limited, and these are not well adapted to the code instrumentation techniques that are used in the characterization of worst-case execution time in critical systems, such as that used by the aforementioned RapiTime tool.

The above-mentioned applications all disclose methods for tracing microprocessor instructions.

The invention is defined in the appended independent claims.

In a first aspect of the invention a method is disclosed for generating the content of ar auxiliary memory which, being aligned with the memory that stores the instructions of a program, is intended to store the information that enables the tracing of a set of instructions selected from said program. This method consists of a three-step procedure: <NUM>) From the pre-processed source files (that is, with all macros expanded) of a program, the source code statements to be traced and the type of trace for each statement are selected. <NUM>) After selection, the object files with debugging information for that program are used to automatically locate the relative memory address where the instruction corresponding to the execution of each statement selected is stored. <NUM>) Finally, using the symbol localisation file, and the information obtained in the two previous steps, the content of the auxiliary memory aligned with the program memory is generated. This content places in the absolute positions, which have been calculated on the basis of the symbol location file and of the relative memory addresses obtained in step <NUM>), the code of the type of trace chosen for each statement in step <NUM>), the memory thus being configured with the information that enables the tracing of the statements selected. The second aspect of the invention is a configurable processing device capable of working in two modes called "TRACE" and "NOMINAL".

In "NOMINAL" mode the device reads and interprets the content of the auxiliary memory as error detection and correction codes associated with the instructions stored in the program memory, correcting the instructions in the event that the fault is recoverable, or generating an exception in the event that it is not.

In "TRACE" mode, the device is able to read and interpret the trace codes stored in the auxiliary memory, execute them in parallel with the instructions aligned to each code, finally resulting in the generation of trace information in an output register, this information also being sufficient to unequivocally identify the instruction traced.

The invention is directly applicable to those architectures that use error detection and correction modules such as EDAC modules, although any architecture can be the object of the invention by enabling access to an auxiliary memory aligned with the program memory, so that with each word in the program memory, the word in the auxiliary memory that has the same displacement is also captured.

The processing device configurable in "TRACE" mode and in "NOMINAL" mode, comprises:.

wherein the data path controller is configured to determine, based on its own state and on the value of the inputs into said controller, the value of the outputs that are sent to the multiplexers of the data path in such a way that, in "TRACE" mode, a trace instruction is executed synchronously with the program instruction that has been read simultaneously, said execution being made effective during the final stage of the trace pipeline.

In one embodiment of the invention, the processing device detects the insertion of a bubble into the program instruction decoding step, which leads the data path controller to establish a path that in the next cycle loads a "<NUM>" as an inoperative trace instruction in the trace instruction decoding step, this trace instruction becoming inoperative in parallel with the bubble entered into the program instruction decoding step.

In one embodiment of the invention, the processing device detects the insertion into the next cycle of a bubble in step <NUM> of the program instruction pipeline, which leads the data path controller to establish a path that in the next cycle loads a "<NUM>" as an inoperative trace instruction into step <NUM> of the trace instructions, this trace instruction becoming inoperative in parallel with the bubble inserted in step <NUM> of the program instructions.

In one embodiment of the invention, the processing device detects the entering into the next cycle of a bubble in step <NUM> of the program instruction pipeline, which leads the data path controller to establish a path that in the next cycle loads a "<NUM>" as an inoperative trace instruction into step <NUM> of the trace instructions, this trace instruction becoming inoperative in parallel with the bubble inserted in step <NUM> of the program instructions.

In one embodiment of the invention, the processing device uses a field from an internal control register to determine the configuration of its "TRACE" or "NOMINAL" working mode. In another embodiment of the invention, the processing device uses the value assigned to an external signal of the device to configure the "TRACE" or "NOMINAL" working mode.

A third aspect of the invention discloses a processor comprising a device for the searching, decoding and processing in parallel, and synchronously, of program instructions and trace instructions according to any one of the preceding embodiments for the first aspect of the invention.

In the present device, a shared memory is not used, and the trace mechanism is based on the execution of trace codes stored in words in an auxiliary memory, and not on the execution by the processor itself of an instruction that activates and deactivates the trace. The method of the invention proposed enables the independent control of the trace of each executable code instruction, since the trace codes are inserted into words that are aligned with the executable code instructions from which it is desired to obtain a point trace. The method of the invention proposed defines a three-step procedure, which employs the source code, the object code, and the symbol localization file of a program, to locate the positions of the auxiliary memory words in which to insert the trace information, without altering the executable code. The device proposed in this invention processes the trace information in parallel with the aligned instruction it is intended to trace, which results in the writing, in an output register, of a unique identifying word of the instruction executed. An analysis hardware captures the identification word, so that the specific time at which the instruction traced was executed is recorded. Thus, the present invention does not establish intervals of instructions to be traced, but, by selectively monitoring the trace of instructions located in any part of the code, enables the obtaining of the the worst-case execution time of each of the system functions.

In the invention presented herein, the instructions traced are defined by a method that selectively enables the insertion of the trace information into an auxiliary memory, and in a position aligned to the instruction that we wish to trace. The device presented herein processes the trace information in parallel and synchronously with the instruction it is intended to trace.

The invention defines a method that, on the basis of the source code, the object code, and the symbol localization file of a program, and once the points of the source code to be traced have been selected, determines the content of an auxiliary memory, aligned with the memory that stores the code, so that the instructions to be traced are marked. The invention, therefore, does not modify the array of instructions of the processor and does not require the insertion of trace instructions into the code, so including trace codes does not alter the executable code of the program to be traced. In addition, the invention proposes the configuration of the processing device in two modes, one called TRACE, where the information in the auxiliary memory is interpreted as trace codes that are executed in parallel, and the other, called NOMINAL, which uses the auxiliary memory to contain error detection and correction codes.

Since the application of code instrumentation using current processors introduces an overload at the time of execution, the invention presented, intended to eliminate these overloads, provides an improvement with a specific objective included in this area. The invention prevents the increase in the space occupied by the executable code, since the code is not implemented to mark the instructions to be traced and the need to add new operation codes to the processor.

To complement the description of the invention and for the purpose of aiding the better understanding of the characteristics thereof, a set of drawings is attached as an integral part of said description wherein, by way of illustration and not limitation, the following has been represented:.

The embodiment of the invention will be based on the implementation of the method described in <FIG>, which enables the obtaining of the content of an auxiliary memory, formed by trace codes and no-operation codes, which enables the selective tracing of a program stored in a program memory aligned with the auxiliary memory, as well as the construction of a device, described in <FIG>, with two operating modes, called "TRACE" and "NOMINAL", and which in its "TRACE" mode is able to search, decode and execute the trace codes in parallel with the program instructions, without introducing any overload in the execution time of the program, while in "NOMINAL" mode the device is able to interpret each word of the auxiliary memory aligned with an instruction in the program memory, such as a detection and correction code for errors in the storage of that instruction.

The method and the device in its "TRACE" mode can be used to perform a hybrid analysis of programs. This analysis combines the static analysis of the program code with information obtained during the execution of this program on the deployment platform, with the aim of inferring program properties, such as the "worst case execution" time of each of the program functions. The static analysis determines which statements must be traced and, using the selective program instruction tracing method described in the invention, the content of the auxiliary memory containing the trace codes corresponding to the instructions selected for the tracing is obtained.

The selective program instruction tracing method consists of a three-step procedure (<NUM>, <NUM>, <NUM>). To execute this procedure, the pre-processed source files (<NUM>) of the program, their object files with debugging information (<NUM>), and the symbol localisation file (<NUM>) obtained during the linking (<NUM>) intended to generate the executable file (<NUM>) are required. The process makes it possible to obtain the content of an auxiliary memory (<NUM>), consisting of trace codes (<NUM>) and no-operation codes (<NUM>), aligned with the content of the program memory (<NUM>) where the instructions to be traced are located.

The first step of the procedure (<NUM>) consists of the selection of the statements that will be traced on the pre-processed source files of the program (<NUM>), the elements that characterize each statement (<NUM>) selected being: the name of the source file (<NUM>), the line number (<NUM>) of the statement within that file, and the type of trace (<NUM>) that it is intended to perform. The procedure enables different types of trace, with the basic type being that which only traces the time of execution of the statement, while the other non-basic types enable the tracing of different elements of the internal state of the processor, such as, for example, the specific content of a register.

The second step of the procedure (<NUM>) consists of using the object files with program debugging information (<NUM>) to automatically identify, for each statement (<NUM>) selected in the first step (<NUM>), the relative address (<NUM>) of the instruction to be traced (<NUM>) that completes the execution of said statement.

The third and final step of the procedure (<NUM>) uses, for each statement (<NUM>) selected in the first step (<NUM>), the elements that characterize said selection, these being: the file name (<NUM>), line number (<NUM>) and trace type (<NUM>). The information provided by these elements, together with the relative address (<NUM>), within the object file, of the instruction to be traced (<NUM>) identified in the second step (<NUM>), is used to perform a search on the symbol localisation file (<NUM>), and thus, to be able to automatically obtain the content of an auxiliary memory (<NUM>) that locates the trace codes (<NUM>) of each statement (<NUM>) selected in the first step (<NUM>), the displacement (<NUM>) of each trace code (<NUM>) within the content of the auxiliary memory (<NUM>) being the same as that of the instruction to be traced (<NUM>), identified in the second step of the procedure (<NUM>), within the content of the program memory (<NUM>). Those positions of the auxiliary memory that have the same displacement as the instructions that have not been selected for the trace are completed with no-operation (NOP) codes (<NUM>), thus obtaining a content of the auxiliary memory (<NUM>) that maintains the trace codes (<NUM>) of the statements selected for the trace (<NUM>) aligned with the instructions to be traced (<NUM>) that complete those statements, which are part of the content of the program memory (<NUM>).

The device proposed in the invention consists of an internal structure that enables the searching, decoding and execution of program instructions and trace instructions in parallel, so that the trace of the instructions of a program is not intrusive either in the execution time or in the location of the program in the program memory, since it is an auxiliary memory that is used to locate the trace codes. In this way, the storage address, the sequence and the execution time of the program instructions under analysis are not modified by the introduction of the traces.

The main elements of the structure of the device proposed are as follows: a search step (<NUM>), which is formed by an instruction address calculation module (<NUM>) and a main search step module (<NUM>); a decoding step (<NUM>), which has a program instruction decoding module (<NUM>) and a trace instruction decoding module (<NUM>); a pipeline for the program instructions (<NUM>); a specific pipeline for the trace instructions (<NUM>); an output register (<NUM>), which receives the trace information obtained upon execution of the trace instructions; a data path, formed by an array of multiplexers (<NUM>,<NUM>,<NUM>,<NUM>,<NUM>); a device data path controller (<NUM>) which determines, on the basis of its state and of the value of its inputs (<NUM>), the value of the outputs (<NUM>) controlled by both the multiplexers (<NUM>,<NUM>,<NUM>,<NUM>,<NUM>) of the different steps, and the load signals in registers associated with the different steps (<NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>), and also the output register (<NUM>). Both the inputs (<NUM>) and the outputs (<NUM>) are represented graphically in <FIG>, next to the label assigned for each signal.

The processing device uses the search step (<NUM>) to simultaneously load a program instruction (<NUM>) from the program memory (<NUM>) and a code (<NUM>) from the auxiliary memory (<NUM>), the code being aligned with the instruction; meaning that it has the same displacement within the auxiliary memory (<NUM>) as the program instruction (<NUM>) within the program memory (<NUM>).

The processing device, in its NOMINAL mode, interprets the code (<NUM>) within the main module of the search step (<NUM>) as an error detection and correction code, such that the program instruction (<NUM>) read from the program memory (<NUM>) can be corrected in the event of a recoverable error, and it is supplied error-free in the next cycle as a valid program instruction (<NUM>) to the program instruction decoder (<NUM>) in the decoding step (<NUM>). In the event that the error is not recoverable, the main module (<NUM>) of the search step (<NUM>) will trigger a signal (<NUM>) that will be interpreted by the processor as an exception.

The processing device, in its "TRACE" mode, combines the code (<NUM>) read from the auxiliary memory (<NUM>) with the address (<NUM>) corresponding to the program instruction (<NUM>) read from the program memory (<NUM>), in order to construct a trace instruction (<NUM>) which in subsequent cycles is decoded and executed in parallel with the program instruction (<NUM>).

In the "TRACE" mode of the processing device, the program instruction decoding module (<NUM>), corresponding to the decoding step (<NUM>), decodes the program instruction (<NUM>) and, in parallel, the trace instruction decoding module (<NUM>) decodes the trace instruction (<NUM>), the trace code whereof was stored in the auxiliary memory (<NUM>) in a position aligned with that of the program instruction (<NUM>) in the program memory (<NUM>).

In the "TRACE" mode of the processing device, the path controller (<NUM>) uses the values of the "STANDBY" (<NUM>), "BUBBLE_E2" (<NUM>), "BUBBLE_E3" (<NUM>), "BUBBLE_E4" (<NUM>), "BUBBLE_E5" (<NUM>) signals to determine the path to be followed by the trace instructions toward the subsequent steps. The controller configures the multiplexers (<NUM>, <NUM>, <NUM>, and <NUM>) of the path to ensure that a trace instruction is executed synchronously with the aligned program instruction, said execution being effective during the final stage (<NUM>) of the trace pipeline (<NUM>), wherein it is verified that the "TE5_DIR_ES_0" (<NUM>) signal is deactivated, in which case the "LD_TR_OUT" signal is activated (<NUM>) and the trace information is directed toward the output register (<NUM>).

The trace information stored in the output register (<NUM>) of the device may be analysed by supporting hardware and a logic analyser, such that it is possible to capture the execution time of the program instructions traced, as well as the result of the execution of the trace instruction corresponding to the "TR" field (<NUM>) of the trace information. The trace information uniquely identifies the program instruction traced thanks to the DIRI field (<NUM>) that was assigned at the search step to the value of the address (<NUM>) of the program instruction (<NUM>) read.

In the "TRACE" mode of the processing device, the data path controller (<NUM>) will monitor the "BUBBLE_E2" signal (<NUM>) to detect the insertion of a bubble into the instruction decoding module (<NUM>) of the decoding step (<NUM>), and will set the "SEL_TE2" signal (<NUM>) at the same value as the "BUBBLE_E2" signal (<NUM>), such that in the event of insertion of the bubble, the multiplexer (<NUM>) inputting to the trace instruction decoding module (<NUM>) of the decoding step (<NUM>) routes a <NUM> as input to the trace instruction decoding module (<NUM>); and otherwise, what is routed is the trace instruction formed by the code (<NUM>) and the address of the instruction to be traced (<NUM>), originating from the main module (<NUM>) of the previous search step (<NUM>).

In the "TRACE" mode of the processing device, the data path controller (<NUM>) will monitor the "BUBBLE_E3" signal (<NUM>) to detect the insertion of a bubble in step <NUM> (<NUM>) of the instruction pipeline (<NUM>), and will set the "SEL_TE3" signal (<NUM>) at the same value as the "BUBBLE_E3" signal (<NUM>) so that, in the event of the insertion of the bubble, the multiplexer (<NUM>) inputting to step <NUM> (<NUM>) of the trace pipeline (<NUM>) routes a <NUM> as input to that step (<NUM>); and otherwise, what is routed is the trace instruction (<NUM>) from the previous decoding step (<NUM>).

In the "TRACE" mode of the processing device, the data path controller (<NUM>) will monitor the "BUBBLE_E4" signal (<NUM>) to detect the insertion of a bubble in step <NUM> (<NUM>) of the instruction pipeline (<NUM>) and will set the "SEL_TE4" signal (<NUM>) at the same value as the "BUBBLE_E4" signal (<NUM>) so that, in the event of the insertion of the bubble, the multiplexer (<NUM>) inputting to step <NUM> (<NUM>) of the trace pipeline (<NUM>) routes a <NUM> as input to that step (<NUM>); and otherwise, what is routed to step <NUM> (<NUM>) is the output from the previous step (<NUM>).

In the "TRACE" mode of the processing device, the data path controller (<NUM>) will monitor the "BUBBLE_E5" signal (<NUM>) to detect the insertion of a bubble in step <NUM> (<NUM>) of the instruction pipeline (<NUM>) and will set the "SEL_TE5" signal (<NUM>) at the same value as the "BUBBLE_E5" signal (<NUM>) so that in the event of the insertion of the bubble, the multiplexer (<NUM>) inputting to step <NUM> (<NUM>) of the trace pipeline (<NUM>) routes a <NUM> to the DIRI field (<NUM>) of that step (<NUM>); and otherwise, what is routed to step <NUM> (<NUM>) is the output from the previous step (<NUM>).

The processing device, regardless of whether it is configured in "TRACE" mode, or in "NOMINAL" mode, in the event of a jump instruction being made effective in one step of the instruction pipeline (<NUM>), will insert a bubble in the next cycle, both in that step and in the previous steps of the instruction pipeline (<NUM>), and will set the "SEL_DIR" signal (<NUM>) at <NUM>, so that the address calculation module (<NUM>) takes the value of the effective jump address located in NEXT_PC (<NUM>).

The processing device, regardless of whether it is configured in "TRACE" mode or in "NOMINAL" mode, in the event that its search step (<NUM>) detects that the instruction addressed in the program memory (<NUM>), whose address is provided by the "DIR" register (<NUM>), is not available in a single cycle and one or more standby cycles are required to complete the reading, will activate the "STANDBY" signal for as many cycles as standby cycles are required for the reading; each standby cycle requiring the insertion of a bubble in the decoding step (<NUM>).

The preferred physical embodiment will have on the one hand a "Software" part, corresponding to the program that performs the method of obtaining the content of the auxiliary memory described in <FIG>, and another "Hardware/Firmware" part, implementing the described functionality of the processing device portrayed in <FIG>, based on a model description of a standard processor architecture that uses an auxiliary memory module for the detection and correction of errors on which the aforementioned modifications will be made, which basically affect the possibility of working in two modes; one called "NOMINAL", which interprets the content of the auxiliary memory as error detection and correction codes, and another, called "TRACE" which, by modifying the design of the search and decoding steps, and incorporating the trace pipeline, enables the searching, decoding and execution of the program instructions in parallel with the trace codes stored in the auxiliary memory, calculated by the "Software" that implements the method of obtaining the content of the auxiliary memory described in <FIG>. These model descriptions of architectures will enable the generation of the details of manufacture of the device, which can be realized on a programmable device such as an FPGA (Field Programmable Gate Array) or on an Application Specific Integrated Circuit (ASIC).

There are different realization options. All of them are based on the VHDL model of an "IP Core" of a segmented processor, such as ARM, LEON or RISC-V, on which the implementation of the pipeline structure of the device will be modified to include the functionality described in this patent. The objective is to generate a new "IP Core", which can be manufactured on FPGA or ASIC.

Claim 1:
A method for the selective tracing of program instructions which, given a program for which pre-processed source files (<NUM>), object files with debugging information (<NUM>), and a symbol localisation file (<NUM>) generated during the linking (<NUM>) are provided, comprises the following steps (<NUM>, <NUM>, <NUM>):
<NUM>. selecting the statements to be traced on the pre-processed source files of the program (<NUM>), the elements that characterize each statement being: the name of the source file (<NUM>), the line number (<NUM>) of the statement within that file, and the type of trace (<NUM>); basic if it only traces the time of execution of the statement, or non-basic if it also traces the value of some element of the internal state of the processor, which is intended to be performed;
<NUM>. automatically identifying, for each statement (<NUM>) selected, the relative address (<NUM>) of the instruction to be traced (<NUM>) that completes the execution of said statement, using the object files with program debugging information (<NUM>);
<NUM>. automatically obtaining the content of an auxiliary memory (<NUM>), comprising trace codes (<NUM>) and no-operation codes (<NUM>), using the elements that characterize each statement (<NUM>) selected, the relative address (<NUM>) identified within the object file of the instruction to be traced that corresponds to the statement (<NUM>) selected, and the information from the symbol localisation file (<NUM>) obtained during the linking (<NUM>) of the object files of the program (<NUM>) that generates the executable file (<NUM>); in order to obtain, for each statement (<NUM>) selected, the trace code (<NUM>) and its displacement within the auxiliary memory storing the same, the trace codes (<NUM>) being aligned with the instructions to be traced (<NUM>) in the content of the program memory (<NUM>); where aligned means that the displacement (<NUM>) of each trace code (<NUM>) within the content of the auxiliary memory (<NUM>) is the same as that of the instruction to be traced (<NUM>) within the content of the program memory (<NUM>), and those positions of the auxiliary memory that have the same displacement as the program instructions that have not been selected for tracing are completed with NOP no-operation codes (<NUM>).