1. A trace unit configured to generate items of trace data indicative of processing activities of a data processing apparatus, said trace unit comprising; prediction circuitry for predicting a response of said data processing circuitry at at least one given execution point to execution of a program instruction; tracing circuitry for tracing operation of at least a portion of said data processing apparatus and for determining whether a predicted response to said program instruction is correct and for outputting a prediction indicator indicating whether or not said predicted response is correct; a data store configured to store information relating to said predicted response of said data processing circuitry at said at least one given execution point for use by at least one of said prediction logic and said tracing circuitry at a later execution point; and a history buffer configured to store historical information with regard to one or more entries of said data store at a corresponding execution point prior to said at least one given execution point to enable restoration of said data store to a state corresponding to a previous execution point.