Method for recognizing and verifying FIFO structures in integrated circuit designs

1. A method for recognizing first-in-first-out (FIFO) structures in integrated circuit (IC) designs, comprising:

identifying at least one seed in an IC design that indicates the existence of a FIFO structure; and

checking locally to the identified at least one seed the existence of the FIFO structure in the IC design;

wherein the seed is a logic element included in the FIFO structure;

wherein the seed comprises at least one of: a memory unit, a synchronizer, an equal operator, a less-than (LT) operator, a less-than-or-equal (LTE) operator, a greater-than (GT) operator, a greater-than-or-equal (GTE) operator, or incremental operators of read and write counters;

wherein the memory-seed based recognition comprises:

identifying all memory units in the IC design, and

for each identified memory unit,

traversing forward from the memory until encountering a read pointer;

traversing backward from the memory until encountering a write pointer; and

traversing from the read pointer and the write pointer until encountering increment operators; and

wherein the step of traversing forward further comprises:

searching for select signals of multiplexers (MUXes) in a read decoder connected to the memory unit; and

determining the select signal that is not an internal signal and having minimum distance from the memory unit to its MUX to be the read pointer; and /or wherein the step of traversing backward further comprises:

searching for select signals of MUXes in a write decoder connected to the memory unit; and

determining the select signal that is not an internal signal and having minimum distance from the memory unit to its MUX to be the write pointer.

2. The method of claim 1 , further comprising:

verifying the identified FIFO structure to ensure proper FIFO flag generation.

3. The method of claim 1 , wherein recognizing the entire FIFO structure comprises detecting at least a read pointer and a write pointer.

4. The method of claim 1 , wherein the FIFO structure Includes; a synchronous FIFO or an asynchronous FIFO.

5. The method of claim 1 , wherein the synchronizer-seed based recognition comprises:

identifying all synchronizer logic elements in the IC design, and

for each identified synchronizer logic element,

tracing forward from the synchronizer until encountering Gray decoder;

tracing forward from the Gray decoder until encountering a write counter;

tracing backward from the synchronizer until encountering Gray encoder; and

tracing backward from the Gray decoder until encountering a read counter.

6. The method of claim 5 , wherein identifying the synchronizer logic element comprises identifying an address bus synchronized using a standard multi flip-flop structure.

7. The method of claim 1 , wherein locally exploring the design is by using simulation.

8. The method of claim 1 , wherein the identified FIFO structure is verified by:

generating a monitor circuit that checks the functionality of the FIFO structure using read and write pointers;

inserting the monitor circuit to the design; and

generating an error report by the monitor circuit error if a read operation is requested on an empty FIFO or a write operation is requested into a full FIFO.

9. A computer storage device storing a computer program for execution by a computer processor for use by a computer to perform operations for verifying unstable clock-domain crossings in integrated circuit (IC) designs, comprising:

identifying at least one seed in an IC design that indicates the existence of a FIFO Structure; and

checking locally to the identified at least one seed the existence of the FIFO structure in the IC design,

wherein the seed comprises at least one of: a memory unit, a synchronizer, an equal operator, a less-than (LT) operator, a less-than-or-equal (LTE) operator, a greater-than (GT) operator, a greater-than-or-equal (GTE) operator, or incremental operators of read and write counters;

wherein the memory-seed based recognition comprises:

identifying all memory units in the IC design; and

for each identified memory unit;

traversing forward from the memory until encountering a read pointer;

traversing backward from the memory until encountering a write pointer, and

traversing from the read pointer and the write pointer until encountering incremental operators, and

wherein the step of traversing forward further comprises:

searching for select signals of multiplexers (MUXes) in a read decoder connected to the memory unit; and

determining the select signal that is not an internal signal and having minimum distance from the memory unit to its MUX to be the read pointer, and/or wherein the step of traversing backward further comprises:

searching for select signals of MUXes in a write decoder connected to the memory unit; and

determining the select signal that is not an internal signal and having minimum distance from the memory unit to its MUX to be the write pointer.

10. The computer storage device of claim 9 , wherein the operations further comprise:

verifying the identified FIFO structure to ensure that empty and full FIFO flags are properly generated.

11. The computer storage device of claim 10 , wherein the seed is a logic element included in a FIFO structure.

12. The computer storage device of claim 9 , wherein recognizing the entire FIFO structure comprises detecting a read pointer and a write pointer of the FIFO structure.

13. The computer storage device of claim 9 , wherein the FIFO structure is one of a synchronous FIFO and an asynchronous FIFO.

14. The computer storage device of claim 9 , wherein the synchronizer-seed based recognition comprises:

identifying all synchronizer logic elements in the IC design; and

for each identified synchronizer logic element:

tracing forward from the synchronizer until encountering Gray decoder;

tracing forward from the Gray decoder until encountering a write counter;

tracing backward from the synchronizer until encountering Gray encoder; and

tracing backward from the Gray decoder until encountering a read counter.

15. The computer storage device of claim 14 , wherein identifying the synchronizer logic element comprises identifying an address bus synchronized using a multi flip-flop structure.

16. The computer storage device of claim 9 , wherein locally exploring the design comprises simulation.

17. The computer storage device of claim 9 , wherein verifying the identified FIFO structure further comprises:

generating a monitor circuit that checks the functionality of the FIFO structure using read and write pointers;

inserting the monitor circuit to the design; and

generating an error report by the monitor circuit error if a read operation is requested on an empty FIFO or a write operation is requested into a full FIFO.