First-in-first-out (FIFO) structures are recognized and verified in integrated circuit (IC) designs. The FIFO recognition is based on structural analysis of the design. Specifically, the structural analysis includes performing seed based recognition by identifying logic elements that indicate the existence of candidate FIFO circuitry and then exploring the candidate circuitry to completely verify the presence of a FIFO structure. Recognized FIFOs may be verified to ensure the proper generation of the full and empty flags.