Formal equivalence checking between two models of a circuit design using checkpoints

1. A method for determining whether a high-level model (HLM) for a circuit design is equivalent to a register-transfer-level (RTL) model for the circuit design, the method comprising:

identifying a set of checkpoints, wherein each checkpoint is associated with:

a first component which specifies a first characteristic function using one or more states of a finite-state-machine (FSM) representation of the HLM;

a second component which specifies a second characteristic function using one or more states of an FSM representation of the RTL model; and

a third component which describes an invariant using a set of variables in the HLM and a set of registers in the RTL model;

generating a set of invariant proof problems, wherein each invariant proof problem corresponds to a transition between two checkpoints in the set of checkpoints; and

determining, using a computer, whether the HLM is equivalent to the RTL model by solving the set of invariant proof problems.

2. The method of claim 1 , wherein the first characteristic function is associated with a location in the HLM which is either before or after a program statement in the HLM.

3. The method of claim 1 , wherein the invariant specifies a relationship between a variable in the set of variables and a register in the set of registers at a given time-point.

4. The method of claim 1 , further comprising:

determining whether an abstract state transition graph (ASTG) for the HLM is equivalent to an ASTG for the RTL model; and

in response to determining that the ASTG for the HLM is not equivalent to the ASTG for the RTL, reporting that the equivalence between the HLM and the RTL model could not be determined.

5. The method of claim 4 , wherein determining whether the ASTG for the HLM is equivalent to the ASTG for the RTL model includes:

determining the ASTG for the HLM; and

for each transition in the ASTG for the HLM, determining whether the ASTG for the RTL has an equivalent transition.

6. The method of claim 5 , wherein determining the ASTG for the HLM includes:

performing a forward symbolic simulation from a first location in the HLM which is associated with a first checkpoint; and

in response to determining that the forward symbolic simulation reaches a second location in the HLM which is associated with a second checkpoint, creating a transition between the first checkpoint and the second checkpoint in the ASTG for the HLM, wherein if the first checkpoint is the same as the second checkpoint, the transition is a self loop.

7. The method of claim 5 , wherein determining whether the ASTG for the RTL has an equivalent transition includes:

identifying a start-checkpoint in the RTL model which corresponds to a start-checkpoint for a transition in the HLM;

performing a forward symbolic simulation from the start-checkpoint in the RTL model, wherein the forward symbolic simulation assumes any conditions associated with the transition to be true; and

determining whether the forward symbolic simulation reaches an end-checkpoint in the RTL model which corresponds to an end-checkpoint for the transition in the HLM.

8. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for determining whether a high-level model (HLM) for a circuit design is equivalent to a register-transfer-level (RTL) model for the circuit design, the method comprising:

identifying a set of checkpoints, wherein each checkpoint is associated with:

a first component which specifies a first characteristic function using one or more states of a finite-state-machine (FSM) representation of the HLM;

a second component which specifies a second characteristic function using one or more states of an FSM representation of the RTL model; and

a third component which describes an invariant using a set of variables in the HLM and a set of registers in the RTL model;

generating a set of invariant proof problems, wherein each invariant proof problem corresponds to a transition between two checkpoints in the set of checkpoints; and

determining whether the HLM is equivalent to the RTL model by solving the set of invariant proof problems.

9. The non-transitory computer-readable storage medium of claim 8 , wherein the first characteristic function is associated with a location in the HLM which is either before or after a program statement in the HLM.

10. The non-transitory computer-readable storage medium of claim 8 , wherein the invariant specifies a relationship between a variable in the set of variables and a register in the set of registers at a given time-point.

11. The non-transitory computer-readable storage medium of claim 8 , the method further comprising:

determining whether an abstract state transition graph (ASTG) for the HLM is equivalent to an ASTG for the RTL model; and

in response to determining that the ASTG for the HLM is not equivalent to the ASTG for the RTL, reporting that the equivalence between the HLM and the RTL model could not be determined.

12. The non-transitory computer-readable storage medium of claim 11 , wherein determining whether the ASTG for the HLM is equivalent to the ASTG for the RTL model includes:

determining the ASTG for the HLM; and

for each transition in the ASTG for the HLM, determining whether the ASTG for the RTL has an equivalent transition.

13. The non-transitory computer-readable storage medium of claim 12 , wherein determining the ASTG for the HLM includes:

performing a forward symbolic simulation from a first location in the HLM which is associated with a first checkpoint; and

in response to determining that the forward symbolic simulation reaches a second location in the HLM which is associated with a second checkpoint, creating a transition between the first checkpoint and the second checkpoint in the ASTG for the HLM, wherein if the first checkpoint is the same as the second checkpoint, the transition is a self loop.

14. The non-transitory computer-readable storage medium of claim 12 , wherein determining whether the ASTG for the RTL has an equivalent transition includes:

identifying a start-checkpoint in the RTL model which corresponds to a start-checkpoint for a transition in the HLM;

performing a forward symbolic simulation from the start-checkpoint in the RTL model, wherein the forward symbolic simulation assumes any conditions associated with the transition to be true; and

determining whether the forward symbolic simulation reaches an end-checkpoint in the RTL model which corresponds to an end-checkpoint for the transition in the HLM.

15. An apparatus for determining whether a high-level model (HLM) for a circuit design is equivalent to a register-transfer-level (RTL) model for the circuit design, the apparatus comprising:

an identifying mechanism configured to identify a set of checkpoints, wherein each checkpoint is associated with:

a first component which specifies a first characteristic function using one or more states of a finite-state-machine (FSM) representation of the HLM;

a second component which specifies a second characteristic function using one or more states of an FSM representation of the RTL model; and

a third component which describes an invariant using a set of variables in the HLM and a set of registers in the RTL model;

a generating mechanism configured to generate a set of invariant proof problems, wherein each invariant proof problem corresponds to a transition between two checkpoints in the set of checkpoints; and

a determining mechanism configured to determine whether the HLM is equivalent to the RTL model by solving the set of invariant proof problems.

16. The apparatus of claim 15 , wherein the first characteristic function is associated with a location in the HLM which is either before or after a program statement in the HLM.

17. The apparatus of claim 15 , wherein the invariant specifies a relationship between a variable in the set of variables and a register in the set of registers at a given time-point.

18. The apparatus of claim 15 , wherein generating the set of invariant proof problems comprises:

determining whether an abstract state transition graph (ASTG) for the HLM is equivalent to an ASTG for the RTL model; and

in response to determining that the ASTG for the HLM is not equivalent to the ASTG for the RTL, reporting that the equivalence between the HLM and the RTL model could not be determined.

19. The apparatus of claim 18 , wherein determining whether an ASTG for the HLM is equivalent to an ASTG for the RTL model comprises:

determining the ASTG for the HLM; and

for each transition in the ASTG for the HLM, determining whether the ASTG for the RTL has an equivalent transition.

20. The apparatus of claim 19 , wherein determining the ASTG for the HLM comprises:

performing a forward symbolic simulation from a first location in the HLM which is associated with a first checkpoint; and

in response to determining that the forward symbolic simulation reaches a second location in the HLM which is associated with a second checkpoint, creating a transition between the first checkpoint and the second checkpoint in the ASTG for the HLM, wherein if the first checkpoint is the same as the second checkpoint, the transition is a self loop.

21. The apparatus of claim 19 , wherein determining whether the ASTG for the RTL has an equivalent transition comprises:

identifying a start-checkpoint in the RTL model which corresponds to a start-checkpoint for a transition in the HLM;

performing a forward symbolic simulation from the start-checkpoint in the RTL model, wherein the forward symbolic simulation assumes any conditions associated with the transition to be true; and

determining whether the forward symbolic simulation reaches an end-checkpoint in the RTL model which corresponds to an end-checkpoint for the transition in the HLM.