Abstract:
A device for generating an address branch trace for a microcontroller unit, a microprocessor or a data processing unit having a set of instructions including at least one predicated instruction and at least one instruction of the expanded type, said device including: means for receiving a first signal representative of an actually executed instruction; means for receiving a second signal representative of an expanded instruction; means for receiving a third signal representative of a discontinuity branch between a source address and a destination address of a program executed by said microcontroller, microprocessor or data processing unit; means for storing consecutive addresses pointed by a program counter; means for processing said first, second and third signals in order to determine a pair comprised of a source address and a destination address for an address branch, when appropriate; and means for storing said address pair.

Description:
TECHNICAL FIELD  
       [0001]     The present disclosure generally relates to the field of electronic systems having a microprocessor, and in particular but not exclusively to a branch trace device for a microprocessor.  
       BACKGROUND INFORMATION  
       [0002]     The use of microprocessors is spreading to all electronic systems. Aside from basic microcontrollers (such as 80C51 from Intel Corp.®), particularly sophisticated and powerful microprocessors can be found, and in particular digital signal processors (D.S.P.)  
         [0003]     The most advanced processing units are based on a set of complex instructions comprising in particular predicated instructions and expanded instructions.  
         [0004]     Thus, predicated instructions can be found in processors of the TIC62x DSP type by Texas Instrument®, in Itanium processors of Intel®, or in the StarCore SCx DSP family by Motorola etc. Instructions of the expanded type are found in processors such as Itanium from Intel®, ADSP Blackfin from Analog Devices® and in DSP kernels of the ST100 family from STMicroelectronics S.A®.  
         [0005]     The presence of predicated instructions (PREDICATED) or expanded instructions (EXPANDED) makes burn-in operation difficult and more generally impedes evaluation of the functionalities of a program written as an assembler. Indeed, on one hand, predicated instructions might not be executed, and on the other hand, instructions of the expanded type cause cascaded execution of sub-instructions that makes reading and interpretation of typical/standard branch trace files difficult.  
         [0006]     Generally, the typical branch tracing file generated during program flow does not allow computer programmers to easily follow program flow such as it is really executed, which does not really make programming error detection and correction easier.  
         [0007]     It is desired to have a simple and effective branch tracing mechanism that is perfectly adapted to the advanced instructions of the PREDICATED and EXPANDED types.  
       BRIEF SUMMARY OF THE INVENTION  
       [0008]     An embodiment of the present invention provides a new branch tracing mechanism adapted to use predicated or expanded instructions that can be found in last generation processors including sets of predicated and expanded instructions.  
         [0009]     One embodiment of the present invention provides an efficient branch tracing mechanism for realizing branch trace in microprocessors supporting predicated instructions and expanded instructions.  
         [0010]     An embodiment of this invention provides an effective programming error correction tool, adapted to the structure of sophisticated microprocessors integrating predicated instructions and expanded instructions.  
         [0011]     One embodiment of the invention provides a branch address tracing device that comprises:  
         [0012]     means for receiving a first signal (VALID) characteristic of an executed instruction;  
         [0013]     means for receiving a second signal (EXP) characteristic of an instruction of the expanded type;  
         [0014]     means for receiving a third signal (DISC) characteristic of a discontinuity branch between a source address and a destination address in a running program;  
         [0015]     means for storing consecutive addresses pointed by the program counter;  
         [0016]     means for processing signals VALID, EXP and DISC in order to determine a pair comprised of a source address and a destination address for an address branch, if necessary;  
         [0017]     FIFO-type means for storing the automatically generated address pair.  
         [0018]     In one embodiment, the device comprises:  
         [0019]     a first register receiving the current value of the program counter presented by said microcontroller, microprocessor or processing unit;  
         [0020]     a second register having an input and an output;  
         [0021]     a first multiplexer having an output, a first input connected to the output of said first register and a second input connected to its own output, and being controlled by said VALID signal in order to allow either storing of the contents of said first register, or recycling of the value previously stored in said second register.  
         [0022]     The device of an embodiment more particularly comprises:  
         [0023]     a third register having an input and an output;  
         [0024]     a second multiplexer having an output and a first input connected to the output of said second register and a second input connected to its own output, said second multiplexer being controlled by a first control signal (FSM 1 ) generated by a state machine.  
         [0025]     A third multiplexer comprises a first input connected to the output of the third register and a second input connected to the output of the second register, and an output connected to said storage means (FIFO). The third multiplexer is controlled by a second control signal (FSM 2 ) generated by said state machine.  
         [0026]     In an example embodiment, the state machine receiving the first, second and third signals (VALID, EXP, DISC) is a 3-state state machine, which allows generation of control signals (FSM 1 , FSM 2 ) for the second and third multiplexers, as well as generation of a write signal to FIFO memory. 
     
    
     BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS  
       [0027]     Other features of embodiments of the invention will appear when reading the following description and drawings, only given by way of nonrestrictive examples. In the accompanying drawings:  
         [0028]      FIG. 1  illustrates a first example of generation of a branch trace file for an assembler program.  
         [0029]      FIG. 2  illustrates a second example of generation of a branch trace file in the case of predicated instructions.  
         [0030]      FIG. 3  illustrates a mechanism of branch trace generation in accordance with one embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION  
       [0031]     Embodiments of branch tracing generator device for a microprocessor and microprocessor equipped with such a device are described herein. In the following description, numerous specific details are given to provide a thorough understanding of embodiments. One skilled in the relevant art will recognize, however, that the invention can be practiced without one or more of the specific details, or with other methods, components, materials, etc. In other instances, well-known structures, materials, or operations are not shown or described in detail to avoid obscuring aspects of the invention.  
         [0032]     Reference throughout this specification to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment. Thus, the appearances of the phrases “in one embodiment” or “in an embodiment” in various places throughout this specification are not necessarily all referring to the same embodiment. Furthermore, the particular features, structures, or characteristics may be combined in any suitable manner in one or more embodiments.  
         [0033]     For clarity&#39;s sake, it is pointed out that, generally, program execution tracing is carried out by generating a branch trace file that comprises tracing program counter branches when discontinuity of the program counter appears due to a branch instruction such as JUMP, CALL, GOTO etc.  
         [0034]     In practice, as can be seen in  FIG. 1 , each pair of the BRANCH TRACE file comprises a first address indicating the starting address (for example 0x80000410 in  FIG. 1 ), and the destination address (0x80000404) of the instruction branch.  
         [0035]     When the instruction to be executed is of predicated type, it is observed that the first executed instruction that follows a branch (resulting from JUMP, GOTO or CALL for example) is not always the instruction placed directly after the jump or branch. Indeed, since this instruction can be a predicated instruction, it might not be executed in certain cases and, consequently, it is necessary that the branch trace file clearly indicates which is the first instruction executed after a discontinuity.  FIG. 2  shows an example of an assembler program comprising an instruction GOTO causing branching to address 0x1c, at address 0x10. From destination address 0x1c, follows a sequence of four predicated instructions respectively associated to four guards G 0 , G 1 , G 2  and G 4 . If the contents of guards G 0 , G 1 , G 2 , G 4  are such that the first three instructions (corresponding to addresses 0x1c, 0x20 and 0x24) are not executed, it is then noted that the first instruction executed immediately after the address branch or jump is the instruction of address 0x28.  
         [0036]     To allow programmers to easily detect and correct programming errors, it is desirable that branch tracing shows actual program execution and clearly indicates program counter address branches, as shown in  FIG. 2  where the record of pair (0x10, 0x28) clearly shows a branch from 0x10 to 0x28. Thus, the programmer will be able to identify the first instruction executed after such branch, namely the instruction corresponding to address 0x28, without ambiguity.  
         [0037]     Regarding instructions of the EXPANDED type, it can be noted that they generate the execution of a sequence of sub-instructions. The typical case is instruction PUSHx (resp. POPx) that causes the execution of multiple sub-instructions of the LOAD type (resp. STORE). In such a situation to facilitate programmer corrections, it is also desirable that branch trace also takes into account the potential existence of expanded instructions (such as PUSH or POP for example), namely instructions the execution of which causes running of cascade sub-instructions (such as STORE or LOAD for example).  
         [0038]      FIG. 3  illustrates the schematic diagram of a mechanism in accordance with one embodiment of the present invention that makes it possible to advantageously generate an instruction branch trace file showing the actual execution of predicated instructions and expanded instructions.  
         [0039]     As can be seen on  FIG. 3 , the embodiment of the invention comprises a branch trace device  100  that is connected via an interface  90  to a processor of unspecified type, but integrating a set of predicated instructions and a set of expanded instructions, such as PUSH or POP. People qualified in the art will be able to readily adapt the teaching of the embodiment(s) of the invention to any particular processor, such as a microcontroller, a microprocessor, a digital signal processor (D.S.P.) etc.  
         [0040]     Interface  90  to the processor allows transfer of address  1  of the program counter that, as it is known, shows the current address of an executed instruction. Moreover, the interface comprises three control signals EXP, VALID and DISC, which are defined below:  
         [0041]     EXP (Expanded) is a signal that is in state 1 when the instruction corresponding to the current address is an expanded instruction.  
         [0042]     VALID (predicated) is a signal that is in state  1  when a predicated instruction is actually executed.  
         [0043]     DISC (Discontinuity) is a signal that switches to an active state whenever the processor detects an address branch or discontinuity in a program flow. More precisely, DISC goes to an active state when the destination PC of a discontinuity is present on input  1  (cf.  FIG. 3 ).  
         [0044]     The three control signals EXP, VALID and DISC are respectively stored in registers  5 ,  6  and  7  and are transmitted to a state machine  50 . For convenience purposes, hereinafter signals DISC, EXP and VALID are considered as being signals output from registers  5 ,  6  and  7 , which (regarding clock cycles) shall not be mixed up with the input signals of such registers.  
         [0045]     The branch trace device then comprises three registers, respectively  10 ,  20  and  30  having an output  11 ,  21  and  31 , respectively.  
         [0046]     The device  100  also comprises a first multiplexer  60  having a first input connected to output  11  of register  10  and a second input connected to output  21  of register  20 . The multiplexer  60  has an output connected to the input of register  20  and is controlled by signal VALID, stored in register  6 . As a result, when signal VALID is equal to 1, the value stored in register  10  is then transmitted to the output of multiplexer  60 , on the following cycle. On the other hand, when VALID is equal to 0, then, on the following cycle, the output of the register  20  is then recycled and fed back to the input of register  20  via multiplexer  60 .  
         [0047]     The device  100  also comprises a second multiplexer  70  having a first input connected to output  21  of register  20  and a second input connected to output  31  of register  30 . The multiplexer  70  has an output connected to the input of register  30  and is controlled by a signal FSM 1  generated by state machine  50 . When FSM 1  is equal to 1, then the output of register  20  is directly transmitted to the input of register  30  and, conversely, when FSM 1  is equal to 0, then the output of register  30  is recycled to the input and, consequently, the contents of register  30  are then recycled via multiplexer  70 .  
         [0048]     The device  100  finally comprises a third multiplexer  80  having a first input connected to output  21  of register  20  and a second input connected to output  31  of register  30 . Multiplexer  80  has an output  81  and is controlled by a control signal FSM 2  generated by state machine  50  so that when FSM 2 =1 then, output  31  of the register  30  is transmitted to output  81  of the multiplexer  80 . Conversely, when FSM 2 =0, the signal from output  21  is transmitted to output  81  of multiplexer  80 .  
         [0049]     Output  81  of multiplexer  80  is connected to input @SRC (address) of a FIFO memory  40 , which has an input @DEST (destination address) that is connected to output  11  of register  10 . The FIFO memory  40  is any kind of memory operating according to a “first-in, first-out” principle and such memory has a WRITE control that is also generated by state machine  50 .  
         [0050]     State machine  50  receives the three input signals EXP, VALID and DISC stored in registers  5 ,  6  and  7  respectively and comprises three distinct states making it possible to generate signals FSM 1 , FSM 2  and WRITE signal to FIFO memory.  
         [0051]     The operation of the device  100  according to embodiment(s) of the invention will now be more particularly described now.  
         [0052]     Generally, registers are controlled by a clock signal that is the clock signal of the microprocessor. With each clock cycle, the microcontroller or microprocessor sends the current address of the program counter and an active DISC signal (=1) whenever the program flow encounters a discontinuity (e.g., a destination PC according to the previous discussion about signal DISC).  
         [0053]     State machine  50  goes from a state 0 to a state 1 when both conditions VALID=0 and DISC=1 are simultaneously present. The state machine  50  returns from state 1 to state 0 when signal VALID switches from state to state 1.  
         [0054]     In addition, state machine  50  goes from a state 0 to a state 2 when the following conditions are met: DISC=0 and EXP=1 and VALID=1. Return from state 2 to state 0 occurs when the following conditions are met: VALID=1, DISC=1 and EXP=1  
         [0055]     Finally, the state machine  50  generates signals FSM 1  and FSM 2  in accordance with the following formulas:  
         [0056]     FSM 1  is active when the following conditions are met: DISC=0, VALID=1, EXP=1  
         [0057]     FSM 2  is active when the following conditions are met: DISC=1, VALID=0, EXP=1 and the state machine is in state 2 (FSM=2).  
         [0058]     As for the write signal:  
         [0059]     WRITE is activated when one the following condition occurs: (FSM=0, VALID=1, DISCONT=1) OR (FSM=1, VALID=1) OR (FSM=2, DISC=1)  
         [0060]     As will be noted, the described device makes it possible to store couples (source address @SRC, destination address @DEST) for both predicated instructions and expanded instructions.  
         [0000]     A. Predicated Instructions  
         [0061]     Let us consider for example the program illustrated in  FIG. 2 , and in particular its program flow before branching of address 0x10. It is supposed that state machine  50  is in state 0.  
         [0062]     At the cycle before the branch, (cycle  1 ), bus  1  carries address 0x0c and a signal Valid=1 that is then loaded in register  10 ,  6 .  
         [0063]     At the time of the following cycle (cycle  2 ), value 0x10 is presented to the bus of program counter  1 . Control signal VALID being active (which corresponds to the assumption of an actually executed instruction), multiplexer  60  transmits the signal present on its first input (output signal  11 ) to the input of register  20 . The value previously stored in register  10 —namely 0x0c—then goes to register  20  while the current address value 0x10 is stored in register  10 .  
         [0064]     The following instruction 0x10 corresponding to a branch instruction, the signal of discontinuity DISC is then activated.  
         [0065]     At the following cycle (cycle  3 ), the program counter shows value 0x1c that is stored in register  10  while the previously stored value—namely 0x10—goes to register  20 .  
         [0066]     As the corresponding instruction is not executed (since, by assumption, it is considered that condition G 0  is in a low state) then signal VALID is in state 0, which will cause recycling of the contents of register  20 —namely 0x10—by multiplexer  60 , at the following cycle.  
         [0067]     The simultaneous presence of conditions VALID=0 and DISC=1 implies state machine  50  going from state 0 to state 1. The state machine  50  remains in state 0 as long as VALID stays to 0.  
         [0068]     So, none of the following addresses 0x20 (cycle  4 ) and 0x24 (cycle  5 ) allow a return to state 0 since, by assumption, guards G 1  and G 2  are equal to 0, causing signal VALID to stay at state 0. During these two cycles corresponding to two not executed addresses 0x20 and 0x24, it can be noted that register  20  keeps the initial stored value, namely 0x10, which is the value of the source address (@SRC) counter.  
         [0069]     The presentation of address 0x28 (cycle  6 ), corresponding to an actually executed instruction (since G 4  is by assumption equal to 1), will cause the return of condition VALID=1 and, consequently, the return to state 0 of the state machine  50 , thus causing a write command WRITE to FIFO memory.  
         [0070]     Signal FSM 2  being at 0, it is noted that a pair of two addresses is written to the FIFO: a first address that is the contents of register  20 , namely 0x10, which is the branch source address (@SRC), and a second address, namely address 0x28, which is the destination address (@DEST).  
         [0071]     This address pair (0x10, 0x28) indeed identifies an address branch from a source address to a destination address that corresponds to an actually executed address.  
         [0072]     We will now show that the device is quite as effective in the case of an expanded instruction.  
         [0000]     B. EXPANDED Instructions  
         [0073]     Let us now consider the case of a program including instructions of the expanded type, such as PUSHX or POPX. In such a context, it will now be assumed that signal VALID stays at 1.  
         [0074]     More particularly, let us consider the example of a branch instruction (CALL) at an address 0x10, calling an instruction PUSH present at an address 0x20. The assembler program could be as follows:  
                                                   0x10 Call Sub           ...           ...           0x20: Push           0x24: Add           0x28: Sub           ....           0x34 Return                      
 
         [0075]     Instruction PUSH causes flowing of a series of sub-instructions, which will all be assumed to be at the same address 0x28:  
                                                     STORE R0             STORE R1             STORE R2             ...           STORE R15                      
 
         [0076]     Operation flow will now be described.  
         [0077]     During a first cycle, the processor executes the instruction present at address 0x10 while this specific address is stored in register  10 . Instruction CALL sub is then decoded and branching to address 0x20 occurs.  
         [0078]     In a second cycle, address 0x20 is presented on bus  1  and is stored in register  10  while the address value previously stored in this register (namely 0x10) is stored in register  20  via multiplexer  60 . At the same time, the processor having detected the presence of an expanded instruction activates control signal EXP. But it should be noted that signal DISC stays in a low state until the last sub-instruction because, before that sub-instruction, the processor cannot confirm an expanded instruction.  
         [0079]     It is thus noted that, as soon as signal EXP goes to 1, the state machine  50  switches from state 0 to state 2, which activates control signal FSM 1 . Consequently, the value previously stored in register  20  (0x10) will then be stored in register  30 , at the next clock cycle, where it will be kept and recycled until state machine  50  goes back to state 0.  
         [0080]     Thus, it is possible to keep value 0x10 that is a potential source address, which can however only be confirmed with the last sub-instruction (STORE R 15 ) by means of the activation of signal DISC.  
         [0081]     Thus, successive running of each sub-instruction making up expanded instruction PUSH . . . is obtained. The address that is common to all these sub-instructions, namely 0x20, stays on bus  1  and consequently remains stored in register  10 , whereas register  30  keeps value 0x10 that was the source address of the address branch.  
         [0082]     When the last sub-instruction (STORE R 15 ) is processed, control signal DISC goes to state 1 under processor control. The simultaneous occurrence of states VALID=1, EXP=1 and DISC=1 then causes state machine  50  to switch back to state 0 and activates control signal FSM 2 , controlling multiplexer  80 .  
         [0083]     State machine  50  generates a WRITE signal, thus causing the storage of pair (0x10, 0x20) in FIFO memory  40 , which indeed corresponds to the source and destination addresses of the branch that is realized.  
         [0084]     Thus, with a mechanism that is as simple as effective, it is possible to trace an instruction of the expanded type while, at the same time the execution of this instruction will only be confirmed with the execution of the last sub-instruction making up the expanded instruction. Namely when, during execution of the last sub-instruction, signal DISC=1 is received. It is thus possible to effectively follow a realized address branch and to update an address branch trace file.  
         [0085]     As can be seen, the invention thus allows the realization of a new mechanism making it possible to generate a BRANCH TRACE file when the processor integrates high-level PREDICATED and EXPANDED instructions. Meticulous examination of the BRANCH TRACE file allows programmers to follow program flow and thus to detect and correct programming errors.  
         [0086]     All of the above U.S. patents, U.S. patent application publications, U.S. patent applications, foreign patents, foreign patent applications and non-patent publications referred to in this specification and/or listed in the Application Data Sheet, are incorporated herein by reference, in their entirety.  
         [0087]     The above description of illustrated embodiments, including what is described in the Abstract, is not intended to be exhaustive or to limit the invention to the precise forms disclosed. While specific embodiments and examples are described herein for illustrative purposes, various equivalent modifications are possible within the scope of the invention and can be made without deviating from the spirit and scope of the invention.  
         [0088]     These and other modifications can be made to the invention in light of the above detailed description. The terms used in the following claims should not be construed to limit the invention to the specific embodiments disclosed in the specification and the claims. Rather, the scope of the invention is to be determined entirely by the following claims, which are to be construed in accordance with established doctrines of claim interpretation.