News Column

Patent Issued for Tracing Speculatively Executed Instructions

July 15, 2014



By a News Reporter-Staff News Editor at Information Technology Newsweekly -- ARM Limited (Cambridge, GB) has been issued patent number 8769344, according to news reporting originating out of Alexandria, Virginia, by VerticalNews editors.

The patent's inventors are Gilkerson, Paul Anthony (Newmarket, GB); Horley, John Michael (Hauxton, GB).

This patent was filed on June 13, 2011 and was published online on July 1, 2014.

From the background information supplied by the inventors, news correspondents obtained the following quote: "The field of the invention relates to data processing and in particular to diagnostic mechanisms for monitoring data processing operations.

"There are a number of situations where it is desirable to keep track of the processing being performed by a processing circuit. For example, such information is useful during the development of data processing systems. An example of a tool that may be used to assist in such a process is a tracing tool.

"Tracing the activity of a data processing system whereby a trace stream is generated that includes data representing the step-by-step activity within the system is a highly useful tool in system development. Such tracing tools use a variety of means for tracing the program flow including embedded trace macrocells (ETM, a trademark of ARM Limited, Cambridge) which are present on the chip whose processing is being monitored.

"If the complete step by step activity of a processing system is monitored the amount of data that needs to be collected, transmitted and stored can be prohibitively large. Thus, various ways of reducing this amount of information have been devised. These include reducing the amount of trace data generated by only tracing some instructions such as branches and load/store instructions, all other 'trace-inactive' instructions being inferred from the trace of these 'trace-active' instructions and a knowledge of the instruction stream. Further reduction in the trace stream is possible by providing the ability to turn the trace on and off, so that for certain parts of the execution that are deemed trace-inactive no trace data is generated. This ability to only trace a subset of instructions is described in U.S. Pat. No. 7,707,394.

"Most processor instruction set architectures include the ability to execute instructions speculatively in order to increase processing speed. Thus, for example, branch instructions that are conditional on the state of the data processing system at the point where the branch is processed, and will execute and branch to the destination if some condition is true, and not execute and continue to the next sequential instruction if the condition is false, may be predicted as executing in a certain way, so that the subsequent instructions can be executed before it is known whether the condition is true or false. If the prediction is wrong then the speculatively executed instructions will need to be cancelled and the processor restored to the state it had before the branch was taken.

"It is not always straightforward when tracing speculatively executed instructions to keep the trace stream output consistent with the instructions that are actually committed."

Supplementing the background information on this patent, VerticalNews reporters also obtained the inventors' summary information for this patent: "Viewed from a first aspect, the present invention provides a trace unit for generating items of trace data indicative of processing activities of at least one processor executing at least one stream of instructions, said at least one stream of instructions comprising a plurality of groups of instructions, said at least one processor executing at least some of said instructions speculatively, said trace unit comprising: trace circuitry for monitoring a behaviour of said at least one processor, said trace circuitry being controlled by current trace control data; a data store for storing at least some of said trace control data associated with a corresponding one of said groups of executed instructions; said trace circuitry being configured to store said trace control data in said data store in response to detection of execution of said group of instructions; said trace circuitry being responsive to detecting said at least one processor cancelling at least one group of said speculatively executed instructions to retrieve at least some of said trace control data stored in said data store and to control said trace circuitry with said retrieved trace control data.

"The present invention recognises that tracing data processing apparatus that execute speculative instructions may result in the trace data output being difficult to understand where instructions that have been executed speculatively are later cancelled. It addresses this problem by providing for the storage of trace control data associated with each group of executed instructions within a data store, so that when speculatively executed instructions are cancelled the value of previously used trace control data can be retrieved from the data store. The trace control data that was current at the relevant point can thus be restored.

"In some embodiments said trace unit further comprises storage circuitry for storing said current trace control data for controlling said trace circuitry; wherein in response to detecting said at least one processor cancelling said at least one group of said speculatively executed instructions, said trace circuitry stores said retrieved trace control data in said storage circuitry.

"Although the trace control data can simply be a logic state that can be used to control the trace circuitry in some embodiments it is stored in storage circuitry.

"In some embodiments said trace control data is stored in said data store along with an identifier identifying said corresponding group of instructions.

"The trace control data that is stored needs to be related to the group of instructions that it pertains to in some way. This may be with an identifier, or it may be in some other way such as in the storage format.

"In some embodiments said trace circuitry is configured to retrieve said at least some of said trace control data stored in said data store for said cancelled group of instructions.

"When a group of instructions has been cancelled then relevant trace control data that was current at a start of the cancelled group of instructions should be restored to enable the trace circuitry to function correctly. In some embodiments the trace control data that was current at the start of a group is stored in the data store for that group and thus, this is retrieved. In other embodiments the trace control data current at the end of execution of a group might be stored for that group in which case the trace control data for the group immediately preceding the cancelled group would be retrieved.

"In some embodiments, said group comprises a group of instructions where if a first instruction within said group is executed all of said instructions within said group will execute.

"The instructions can be grouped in a number of ways. In some embodiments a group may consist of single instructions, although this might result in the data store for storing the trace control data being large. The instructions should be grouped in a way, so that if the first instruction within the group is executed, the whole group will be executed. In other words, no exception can occur within a group and instructions will be cancelled and committed as whole groups. A speculatively executed instruction is committed or cancelled when its fate is known, i.e. it is known whether the speculation was correct, where it is committed or not, where it is cancelled

"In some embodiments, said trace control data comprises a sticky value, said trace circuitry being responsive to said sticky value having a predetermined value to output a trace value for a subsequently executed trace-active instruction whether or not a trace enable signal has an enabled value, a trace-active instruction being an instruction triggering output of an item of trace data.

"A problem that can arise with the cancelling of speculatively executed instructions that are being traced is that where trace only outputs trace elements for trace-active instructions and implies that other instructions have been executed from the tracing of subsequent instructions, then where groups of instructions may be cancelled and where trace enable may be turned on or off at different times, if the final instruction in a group of instructions is not a trace-active instruction and if trace enable is turned off before the next instruction is traced then the diagnostic apparatus analysing the trace data will not know that this trace-inactive instruction has in fact executed. This problem is addressed by the use of a sticky value in the trace control data.

"The trace circuitry is responsive to detecting execution of a final instruction in one of said groups of instructions, where said final instruction is not a trace-active instruction triggering output of an item of trace data, to set said sticky value in said trace control data for controlling a subsequent group of instructions and to store said sticky value in said data store for a subsequent group of instructions.

"Thus, the sticky value is set for a subsequent group when a final instruction in a group is a trace-inactive instruction that does not output a trace element. Thus, the subsequent trace-active instruction to be executed outputs a trace element whether or not trace is enabled. When a trace element has been output the sticky value stored in the storage circuitry is reset. The sticky value allows the diagnostic apparatus analysing the trace data to recognise that the trace-inactive instruction did indeed execute. When a group of speculatively executed instructions are cancelled then the sticky value previously applied to the cancelled instructions is restored to the storage circuitry. Thus, as the sticky value has been stored for the subsequent group of instructions, if this group is cancelled, the sticky value is updated and the next trace-active instruction will output a trace element, so that execution of the final trace-inactive instruction in the preceding group can be implied.

"In some embodiments said trace control data comprises a previous-traced value, said trace circuitry being configured to store a value of said trace enable signal when a final instruction in a preceding group is executed as said previous-traced value for said subsequent group, said trace circuitry being responsive to detecting said processor cancelling a group of speculatively executed instructions and to said trace enable value being enabled and to said previous-traced value stored associated with said cancelled group being set, to output a trace element indicating said trace is turning on.

"A further problem that may arise with speculatively executed instructions being cancelled is that where trace is turned on, during a group of instructions that is subsequently cancelled, then any indication that may have been output that trace is turned on is lost. The previous-traced value is used to indicate where a trace on signal should be output in view of cancelled instructions. One simple way of setting the previous-traced value may be to store the trace enable value for the final instruction of a preceding group as the previous traced value for the subsequent group, thereby providing a simple way of indicating if trace was enabled or not when that group of instructions had finished executing.

"In some embodiments, said trace control data comprises an initial-traced value, said initial-traced value being set for a group of instructions in response to trace being enabled for execution of a first instruction in said group, wherein in response to detecting said processor cancelling a group of instructions and said initial-traced value being clear for said group of instructions and said previous traced value being set for said group of instructions, said trace circuitry outputs a state element indicating an execution address of said instruction executed following said cancel.

"A further problem may arise where trace is enabled during execution of a speculative group and this group is then cancelled. Where trace is enabled a state trace element may be output which indicates an execution address so that any diagnostic apparatus can understand where trace was enabled again. If these instructions are later cancelled then a problem may arise as the diagnostic apparatus will believe that execution is proceeding from the execution address output for the instructions that were cancelled. The use of the initial-traced value can help avoid this problem by triggering the output of a further state element indicating a further execution instruction address. Thus, in response to the cancellation of a group a further state element is output when initial-traced is clear for the cancelled group and previous traced is set for this group. Previous-traced being set indicates that trace was enabled when the final instruction of the previous group, in this case the group before the group that was cancelled, was executed, while initial-traced being clear indicates that it was not enabled when the first instruction of the cancelled group was executed. Thus, it may be enabled during execution of the cancelled group and a state element may have been output. Thus, an extra state element is output.

"In some embodiments, said trace control data comprises a traced interesting value, said traced interesting value being set for a group in response to a trace element being output for said group and being clear for a group where no trace element is output for said group.

"A further trace control value that embodiments of the present invention can use is a traced interesting value. This is used to indicate where trace elements are output for a group and where no trace elements are output for a group. It can be used to determine if a group that is committed was not traced and thus a commit count value in the trace output should not imply that it was. It can also be used in counter wrap around cases which will be described later.

"In some embodiments said trace control data comprises a trace start/stop value for said group, said trace start/stop value influencing whether or not trace enable is set or not, said trace start/stop value being set in response to detected predetermined behaviour of said at least one processor.

"Whether or not trace is enabled may be controlled by particular states of the processor. In some embodiments whether or not these states control the trace enable can be turned on or off with a start/stop value. Conventional processors have used this control value. However, where this is the case embodiments of the current invention store the value for a group, so that if that group is later cancelled the value can be restored to its correct value.

"In some embodiments, said trace control data comprises a trace multiple value, said value being set indicating that said group comprises two trace-active instructions generating trace elements, said value not being set indicating that said group comprises one or zero trace-active instructions.

"It may be that groups of instructions are limited to two or fewer trace-active instructions. In such a case, trace control data can include a trace multiple value that indicates whether or not a group has two trace-active instructions. In such a way, trace of a group can be performed using fewer values as becomes clear later.

"In other embodiments said trace multiple value comprises a value indicating a number of trace-active instructions in said group.

"In other embodiments the trace multiple value may be several bits and may indicate the number of trace-active instructions that are present in a group. In this way a two bit value can indicate whether there are 1, 2, 3 or 4 trace active instructions in a group which is more efficient than storing two trace keys (indicating the first and last values) would be.

"In some embodiments said trace unit is configured to generate an index value and to store said index value associated with each of said groups of instructions, said index value being updated for every trace element generated.

"One way of keeping track of the trace elements generated is to provide an index value which can be associated with each group of instructions and is updated for every trace element generated. Indexing in this way provides information that is easy to compress and can be understood by the diagnostic apparatus analysing the trace data.

"In some embodiments, said trace unit comprises a counter for generating said index value, said trace circuitry storing in said data store for each group of instructions at least one of a first counter value indicative of said counter value at a start of execution of said group and a last counter value indicative of said counter value at an end of execution of said group.

"The index value can index the trace information in a number of ways, but in some embodiments it comprises a counter. A counter is simple a way to provide an indexing function and furthermore, provides indexing that is easily compressible. It may be in some embodiments that both the first and last count values are stored for a group, while in others only one of them is stored. The value of the counter at the start of execution of the group and at the end of the execution of the group can be used when instructions are cancelled or committed to determine exactly which trace elements that have been output relate to cancelled and committed instructions. If only one of them is stored the trace elements that relate to cancelled and committed instructions can still be determined in cases where the number of trace-active instructions in a group is limited to two and where there is a multiple traced value stored for a group. In such a case the other of the first and last value can be deduced. An advantage of this is that the multiple traced value is a single bit, while a count value will be multiple bits.

"In some embodiments, said trace circuitry is configured on receipt of a cancelling indication from said data processing apparatus indicating that a selected group of instructions which has been speculatively executed has been cancelled to generate a cancelling item of trace indicative of said cancelled selected group of instructions and to include information regarding a difference between said current counter value and said counter value at a start of execution of said cancelled group in said cancelling item of trace.

"When a group of instructions are cancelled it is important that the diagnostic apparatus analysing the trace elements can deduce this, otherwise the diagnostic apparatus will not be able to analyse the executed stream correctly. When counter values have been used to index the trace elements, cancelling can be indicated to the diagnostic apparatus by simply providing a cancelling item of trace indicating how many of the trace elements that have been output in the stream are cancelled elements.

"In some embodiments, said trace circuitry is configured to determine said information regarding said difference in dependence upon said traced-interesting value.

"It may be that in some of the cancelled groups there were no traced instructions and the information output regarding the number of groups of instructions that are cancelled should not imply that a group that was cancelled that did not output a trace element. The traced interesting value is used to amend the output value so that this is not implied.

"In some embodiments, said trace unit is responsive to receipt of a committing indication from said data processing apparatus that a selected group of instructions which has been speculatively executed has been committed to generate a committing item of trace indicative of said selected group and to include information regarding a difference between said current counter value and said last counter value for said selected group.

"In a similar way to cancelling, the indexing of the groups of instructions can be used to indicate which instructions have been committed. When calculating what value to output to indicate which instructions are committed, the traced interesting value is also helpful so that where there are groups that have no instructions that have been traced the committing signal does not imply that some of the trace elements that are output belong to these groups.

"A second aspect of the present invention provides a data processing system comprising a data processing apparatus for executing a stream of instructions and a trace unit according to a first aspect of the present invention for monitoring said data processing apparatus.

"A third aspect of the present invention provides a method for generating items of trace data indicative of processing activities of at least one processor executing at least one stream of instructions, said at least one stream of instructions comprising a plurality of groups of instructions, said at least one processor executing at least some of said instructions speculatively, said method comprising the steps of monitoring a behaviour of said at least one processor using trace circuitry controlled by current trace control data; storing at least some of said trace control data associated with one of said groups of executed instructions; in response to detecting said at least one processor cancelling at least one group of said speculatively executed instructions, retrieving at least some of said trace control data stored in said data store for said group of instructions executed immediately before said cancelled speculatively executed instructions and controlling said trace circuitry with said retrieved trace control data.

"A fourth aspect of the present invention provides a trace means for generating items of trace data indicative of processing activities of at least one processor executing at least one stream of instructions, said at least one stream of instructions comprising a plurality of groups of instructions, said at least one processor executing at least some of said instructions speculatively, said trace means comprising: trace monitoring means for monitoring a behaviour of said at least one processor controlled by current trace control data; a data storage means for storing at least some of said trace control data associated with a corresponding one of said groups of executed instructions; said trace monitoring means being for storing said at least some of said trace control data in said data storage means in response to detection of execution of said group of instructions; said trace monitoring means being responsive to detecting said at least one processor cancelling at least one group of said speculatively executed instructions to retrieve at least some of said trace control data stored in said data storage means for said group of instructions executed before said cancelled speculatively executed instructions and to control said trace monitoring means with said retrieved trace control data.

"The above, and other objects, features and advantages of this invention will be apparent from the following detailed description of illustrate embodiments which is to be read in connection with the accompanying drawings."

For the URL and additional information on this patent, see: Gilkerson, Paul Anthony; Horley, John Michael. Tracing Speculatively Executed Instructions. U.S. Patent Number 8769344, filed June 13, 2011, and published online on July 1, 2014. Patent URL: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8769344.PN.&OS=PN/8769344RS=PN/8769344

Keywords for this news article include: ARM Limited, Information Technology, Information and Data Storage, Information and Data Processing.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Information Technology Newsweekly


Story Tools






HispanicBusiness.com Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters